?2-范数下F3,3的Andrásfai–Erd?s–Sós型稳定性定理

《Discrete Mathematics》：An Andrásfai–Erd?s–Sós type theorem for F 3,3 in the ? 2-norm

本文为组合数学中极值图论领域的最新进展。文章针对一种特定的三元超图F3,3，在?2-范数（?2-norm）的框架下，建立了一个类似于Andrásfai–Erd?s–Sós定理的稳定性结果。研究证明，对于充分大的顶点数n，任何最小?2-范数度（?2-norm degree）不低于(5/4 - ξ)n3的F3,3-free三元超图必然是二部图（bipartite）。这一结论强化了Balogh, Clemen和Lidicky之前关于?2-范数Turán数（?p-norm Turán number）的工作，为该领域的Turán问题（Turán problems）与稳定性理论（stability theory）提供了新的工具和视角。

　　

高亮 (Highlights)

对于一个整数r ≥ 2，一个r-一致超图（或简称为r-图）H是一个集合V的r-元素子集的集合。我们将超图H等同于其边集，因此|H|表示H中的边数。给定一个r-图族F，如果H不包含F中的任何成员作为子图，则称H是F-free的。Turán数ex(n, F)是n个顶点上F-free的r-图所能拥有的最大边数。

对图族F的ex(n, F)研究或许是极值组合学的中心主题，并且已知在r ≥ 3时通常非常困难。有关2011年之前已知结果的全面概述，我们请读者参阅Keevash的综述[11]。

引言 (Introduction)

研究Turán问题的一个有力工具是稳定性理论，它在极值组合学的许多基本结果中起着关键作用。非正式地说，它指出对于一个被禁止的r-图族F，任何大小接近ex(n, F)的F-free r-图都可以通过删除和添加极少量的边，转化为其极值构造。第一个稳定性定理，即对于所有整数? ≥ 2，完全图K_?+1是稳定的，由Erd?s和Simonovits独立证明[14]。另一个关于带有最小度限制的K_?的基本结果是Andrásfai–Erd?s–Sós定理[1]。

定理 1.1 Andrásfai–Erd?s–Sós [1]

对于? ≥ 2，每个n个顶点上、最小度大于 (3? - 4)/(3? - 1) * n 的 K_?+1-free 图是 ?-部图。

最近，Liu, Mubayi 和 Reiher [13] 为稳定性结果提供了一个统一框架。他们的方法不仅为许多现有的稳定性定理提供了简化的证明，而且还给出了这些结果的强化版本。

在本文中，我们专注于关于?₂-范数定义的Turán问题变体的Andrásfai–Erd?s–Sós型定理。给定一个r-图H和一个顶点v ∈ V(H)，v的关联图定义为 L_H(v) ? {e ∈ (V(H) choose r-1) : {v} ∪ e ∈ H}。v在H中的度定义为 d_H(v) ? |L_H(v)|，即H中包含v的边的数量。我们将H的最小度和最大度分别记为 δ(H) 和 Δ(H)。对于一个(r-1)-元集 T ∈ (V(H) choose r-1)，T在H中的邻域定义为 N_H(T) ? {v ∈ V(H) : T ∪ {v} ∈ H}，T在H中的余度（codegree）定义为 d_H(T) ? |N_H(T)|，即H中包含T的边的数量。上下文清楚时，我们省略下标H。

对于每个实数 p ≥ 1，一个r-图H的?_p-范数定义为 ‖H‖_p? Σ_{T∈(V(H) choose r-1)}d_H^p(T)，其中 d_H^p(T) 表示 (d_H(T))^p。一个图族F的?_p-范数Turán数定义为 ex_?p(n, F) ? max { ‖H‖_p: H 是一个n个顶点上的F-free r-图 }。F的?_p-范数Turán密度定义为 π_?p(F) ? lim_n→∞ex_?p(n, F) / ( (n choose r-1) * (n - r + 1)^p)。这个极限的存在性已在[3, 命题1.8]和[5, 命题2.2]中确立。

扩展度的定义，一个顶点v ∈ V(H)的?_p-范数度，记为 d_{p, H}(v)，定义为 d_{p, H}(v) ? ‖H‖_p- ‖H - v‖_p，其中 H - v 表示通过移除顶点v以及所有包含v的边得到的r-图。我们将H的最小?_p-范数度记为 δ_?p(H)。

注意到当 p = 1 时，?_p-范数Turán问题简化为经典的Turán问题。受此启发，Balogh、Clemen和Lidicky [2], [3] 最近开创了对超图族的?_p-范数Turán密度π_?p(F)的系统性研究。他们的工作包括几个显著的结果，包括使用旗代数计算得到的 π_?2(K₄³) = 1/3 和 π_?2(K₅³) = 5/8。最近，研究人员已经确定了几个经典超图的?₂-范数Turán密度和精确的?₂-范数Turán数，包括Fano平面[9]和长度为5减一条边的3-一致紧圈[4]。超图的?_p-范数Turán问题在其他近期工作中也得到了进一步发展，例如[5], [6], [7]。

在本文中，我们专注于一个称为F_3,3的3-图。令F_3,3为在6个顶点上、边集为 {123, 145, 146, 156, 245, 246, 256, 345, 346, 356} 的3-图。如果一个3-图H存在一个划分 V(H) = V₁∪ V₂使得H的每条边都与V₁和V₂相交，则称H是二部图。令B_n表示在n个顶点上的平衡完全二部3-图。一个直接的计算表明 |B_n| = (1/8 + o_n(1)) n³, ‖B_n‖₂= (5/16 + o_n(1)) n⁴, 以及 δ_?2(B_n) = (5/4 + o_n(1)) n³。

观察到每个二部3-图都是F_3,3-free的。Keevash和Mubayi [12]，以及独立地Goldwasser和Hansen [8] 证明了对于所有 n ≥ 6，ex(n, F_3,3) = |B_n|，此外，B_n是唯一的极值构造。Balogh、Clemen和Lidicky [3] 证明了 π_?2(F_3,3) = 5/8，并且对于所有充分大的n，有 ex_?2(n, F_3,3) = ‖B_n‖₂，而且B_n也是?₂-范数下的唯一极值构造。

在本文中，我们通过建立F_3,3在?₂-范数下的Andrásfai–Erd?s–Sós型稳定性定理，强化了Balogh、Clemen和Lidicky的结果如下。

定理 1.2

存在常数 ξ > 0 和 N₀使得以下结论对所有 n ≥ N₀成立。如果 H 是一个在 n 个顶点上的 F_3,3-free 3-图，且其最小 ?₂-范数度 δ_?2(H) ≥ (5/4 - ξ) n³，那么 H 是二部图。

备注 (Remarks)

使用如[3, 定理1.7]证明中那样的标准顶点移除论证（移除具有最小?₂-范数度的顶点），定理1.2意味着对于所有充分大的n，ex_?2(n, F_3,3) 的极值构造是二部图。因此，可以直截了当地确定 ex_?2(n, F_3,3) 的精确值。这也为[3, 定理1.7和6.3]提供了一个替代证明。

在下一节中，我们将介绍一些定义和预备结果。定理1.2的证明在第3节中给出。

第二部分概览 (Section snippets)

预备知识 (Preliminaries)

给定一个r-图H和一个顶点集 S ? V(H)，令 H[S] 表示H在S上的诱导子图，令 H - S 表示H在 V(H) \ S 上的诱导子图。给定一个图G和两个不相交的集合 S, T ? V(G)，令 G[S, T] 表示G在S和T之间的诱导二部子图。给定两个r-图 Q 和 H，令 N(Q, H) 表示H中Q的拷贝数量。对于一个顶点 v ∈ V(H)，v在H中的Q-度，记为 d_{Q, H}(v)，定义为 d_{Q, H}(v) ? N(Q, H) - N(Q, H - v)，即H中包含v的Q的拷贝数量。

定理 1.2 的证明 (Proof of Theorem 1.2)

在本节中，令 B 表示所有二部3-图的族。容易看出 B 是遗传的。根据定理2.3，F_3,3关于 B 是?₂-边稳定的。因此，根据定理2.2，只需证明 F_3,3关于 B 是?₂-顶点可扩展的。

定理 3.1

3-图 F_3,3关于 B 是 ?₂-顶点可扩展的。

定理 3.1 的证明 (Proof of Theorem 3.1)

令 ξ > 0 足够小，N₀足够大，且 n ≥ N₀为整数。令 H 为一个在 n + 1 个顶点上的 F_3,3-free 3-图，且满足 δ_?2(H) ≥ (2π_?2(F_3,3) - ξ) n³= (5/4 - ξ) n³。假设...