Sidorenko 猜想是极值组合学（extremal combinatorics）领域的一个重要问题，其解决方案仍然难以解决。它对多部分超图（hypergraphs）的直接推广并不完全正确，但对某些图族（families of graphs）来说却成立。这些图族有什么特点？这项工作旨在研究 Sidorenko 型不等式的超图扩展，旨在阐明这一问题及其相关问题。
论文题目：Hypergraph Homomorphism Inequalities
作者：Cynthia Stoner
类型：2024年博士论文
学校：Stanford University（美国斯坦福大学）
下载链接：
链接: https://pan.baidu.com/s/1Pm5prJwW9rCAP3uSicrr1Q?pwd=svfw
硕博论文汇总：
链接: https://pan.baidu.com/s/1Gv3R58pgUfHPu4PYFhCSJw?pwd=svp5
给定一个图 G，在另一个图 H 中可以找到多少个副本？这个基本的组合问题涵盖了图论中许多有趣且深入研究的问题。了解图中局部结构的存在和相对普遍性对于图论的外部应用也很重要，例如社交媒体或交通网络的分析[17]。
一种极端的可能性是 H 不包含 G 的副本。这种情况与 ex (n, G) 的研究有关，ex (n, G) 被定义为一个 n 个顶点上的简单图中不包含 G 副本的最大边数。当 G 为完全图时，可以通过 Tur´an 定理 [10] 精确地知道这一点，并且对于非二分图 G，可以通过 Erd˝os-Stone 定理 [5] 渐近地理解这一点。在 Ramsey 理论的广泛领域中，也研究了该问题的多种变体。
本研究的重点将放在相反的环境中，即 H 包含 G 的许多副本。在这种情况下，讨论 G 在 H 中的密度是合理的。为此，我们首先通过引入图同态的概念来使事情精确化。
定义 1.0.1. 图 G 和图 H 之间的图同态是一个映射 ϕ : V (G) →V (H)，使得对于每个 (u, v) ∈ E (G)，(ϕ (u) , ϕ (v)) 是 H 中的一条边。此类同态的数量用 hom (G, H) 表示。
换句话说，图同态是图之间的顶点映射，将边发送到边。请注意，这种同态计数的具体实例可以对应于组合图属性。例如，考虑 H 是两顶点图的情况，其顶点之间有一条边，其中一个顶点上有环。在这种情况下，hom (G, H) = i (G)，即 G 的独立集数。这是因为当 H 中非环顶点的原像是 G 中的独立集时，映射 ϕ : V (G) → V (H) 将是有效的同态。
现在，G 在 H 中的密度定义为均匀随机选择的映射 ϕ : V (G) → V (H) 为同态的概率。
定义 1.0.2. G 在 H 中的图密度由下式给出
通过图极限理论，涉及这些离散概念的陈述可以在分析环境中转化为等效的连续陈述 [9]。实现这一目标的机制就是图元。
定义 1.0.3. 图子是对称的可测函数 W : [0, 1]2 → [0, 1]。图 G 在 W 中的密度由下式给出
如果我们将 W 视为与图 H 的邻接矩阵相对应的块图元，则该密度与 t (G, H) 一致。更通用的框架自然会处理边和顶点加权图的情况。通过图元，与图密度有关的陈述可以转化为与单位正方形上的对称函数有关的解析不等式。Sidorenko 猜想就是这样一个解析不等式。在 [20] 中，Sidorenko 提出了以下与图密度有关的猜想：
猜想 1.0.4 (Sidorenko)。对于所有二分图 G 和图元 W ，以下不等式成立。
当 W 是常数图元时，等式成立，这对应于当 n → ∞ 时，伪随机图 G (n, ρ) 的图极限（其中 ρ 固定）。在离散设置中，Sidorenko 猜想认为，对于任何固定的二分图 G 和 H 的边密度 ρ，当 H 是较大的伪随机图 G (n, ρ) 时，H 中 G 的密度最小。
最近，这种二维情况取得了很大进展，尽管它仍未得到解决（例如，参见 [19]、[12]、[16]）。这些论文使用各种分析和组合技术来证明各种二分图类的猜想。
在提出猜想的论文中，Sidorenko 指出，将这个猜想自然扩展到 k-partite、k-uniform 超图通常不成立。也就是说，以下成立。
命题 1.0.5 (Sidorenko). 对于每个 k ≥ 3，存在一个 k-分体、k-均匀超图 G 和超图子 W，且下列命题成立。
在这里，超图子是图子到 k 维的自然扩展；我们将在第 4 节中进一步讨论这些。这引出了一个自然的问题：对于哪些 k-partite、k-uniform 超图，猜想 1.0.4 的自然超图扩展成立？通过研究相关的图和超图同态不等式，我们旨在开发一些可能阐明猜想的两个变体的技术。
在第二部分中，我们提出了 Kahn 不等式 [11] 的广义版本以及来自 [18] 的相关下界不等式。我们证明了关于超图度和相关度量的各种分析结果，并利用这些结果证明这些广义不等式对某些类的超图成立。
接下来，我们研究支配密度指数。它首次出现在 [13] 中，定义为图 G、H 的最小常数 c，使得对于每个图 W，t (G, W) ≥ t (H, W)c。这一广泛的概括包括 Sidorenko 猜想、路径上的 Erd˝os-Simonovits 定理以及与图同态密度相关的各种其他陈述。我们介绍了一些用于估计密度支配指数的通用工具，并将以前的结果扩展到新的图体系。
在最后一节中，我们研究了超图的 Sidorenko 猜想的边缘局部化版本。此彩虹变体将目标的边密度（edge density ）替换为对应于有界最小子图密度（subgraph density）的分析条件。我们证明这个更强的陈述恰好适用于超森林（hyperforests ）。
