《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] 為穩定性結果提供了一個統一框架。他們的方法不僅為許多現有的穩定性定理提供了簡化的證明，而且還給出了這些結果的強化版本。
在本文中，我們專注于關于?2-范數定義的Turán問題變體的Andrásfai–Erd?s–Sós型定理。給定一個r-圖H和一個頂點v ∈ V(H)，v的關聯圖定義為 LH(v) ? {e ∈ (V(H) choose r-1) : {v} ∪ e ∈ H}。v在H中的度定義為 dH(v) ? |LH(v)|，即H中包含v的邊的數量。我們將H的最小度和最大度分別記為 δ(H) 和 Δ(H)。對于一個(r-1)-元集 T ∈ (V(H) choose r-1)，T在H中的鄰域定義為 NH(T) ? {v ∈ V(H) : T ∪ {v} ∈ H}，T在H中的余度（codegree）定義為 dH(T) ? |NH(T)|，即H中包含T的邊的數量。上下文清楚時，我們省略下標H。
對于每個實數 p ≥ 1，一個r-圖H的?p-范數定義為 ‖H‖p? ΣT∈(V(H) choose r-1)dHp(T)，其中 dHp(T) 表示 (dH(T))p。一個圖族F的?p-范數Turán數定義為 ex?p(n, F) ? max { ‖H‖p: H 是一個n個頂點上的F-free r-圖 }。F的?p-范數Turán密度定義為 π?p(F) ? limn→∞ex?p(n, F) / ( (n choose r-1) * (n - r + 1)p)。這個極限的存在性已在[3, 命題1.8]和[5, 命題2.2]中確立。
擴展度的定義，一個頂點v ∈ V(H)的?p-范數度，記為 dp, H(v)，定義為 dp, 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(K43) = 1/3 和 π?2(K53) = 5/8。最近，研究人員已經確定了幾個經典超圖的?2-范數Turán密度和精確的?2-范數Turán數，包括Fano平面[9]和長度為5減一條邊的3-一致緊圈[4]。超圖的?p-范數Turán問題在其他近期工作中也得到了進一步發展，例如[5], [6], [7]。
在本文中，我們專注于一個稱為F3,3的3-圖。令F3,3為在6個頂點上、邊集為 {123, 145, 146, 156, 245, 246, 256, 345, 346, 356} 的3-圖。如果一個3-圖H存在一個劃分 V(H) = V1∪ V2使得H的每條邊都與V1和V2相交，則稱H是二部圖。令Bn表示在n個頂點上的平衡完全二部3-圖。一個直接的計算表明 |Bn| = (1/8 + on(1)) n3, ‖Bn‖2= (5/16 + on(1)) n4, 以及 δ?2(Bn) = (5/4 + on(1)) n3。
觀察到每個二部3-圖都是F3,3-free的。Keevash和Mubayi [12]，以及獨立地Goldwasser和Hansen [8] 證明了對于所有 n ≥ 6，ex(n, F3,3) = |Bn|，此外，Bn是唯一的極值構造。Balogh、Clemen和Lidicky [3] 證明了 π?2(F3,3) = 5/8，并且對于所有充分大的n，有 ex?2(n, F3,3) = ‖Bn‖2，而且Bn也是?2-范數下的唯一極值構造。
在本文中，我們通過建立F3,3在?2-范數下的Andrásfai–Erd?s–Sós型穩定性定理，強化了Balogh、Clemen和Lidicky的結果如下。
定理 1.2
存在常數 ξ > 0 和 N0使得以下結論對所有 n ≥ N0成立。如果 H 是一個在 n 個頂點上的 F3,3-free 3-圖，且其最小 ?2-范數度 δ?2(H) ≥ (5/4 - ξ) n3，那么 H 是二部圖。
備注 (Remarks)
使用如[3, 定理1.7]證明中那樣的標準頂點移除論證（移除具有最小?2-范數度的頂點），定理1.2意味著對于所有充分大的n，ex?2(n, F3,3) 的極值構造是二部圖。因此，可以直截了當地確定 ex?2(n, F3,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-度，記為 dQ, H(v)，定義為 dQ, H(v) ? N(Q, H) - N(Q, H - v)，即H中包含v的Q的拷貝數量。
定理 1.2 的證明 (Proof of Theorem 1.2)
在本節中，令 B 表示所有二部3-圖的族。容易看出 B 是遺傳的。根據定理2.3，F3,3關于 B 是?2-邊穩定的。因此，根據定理2.2，只需證明 F3,3關于 B 是?2-頂點可擴展的。
定理 3.1
3-圖 F3,3關于 B 是 ?2-頂點可擴展的。
定理 3.1 的證明 (Proof of Theorem 3.1)
令 ξ > 0 足夠小，N0足夠大，且 n ≥ N0為整數。令 H 為一個在 n + 1 個頂點上的 F3,3-free 3-圖，且滿足 δ?2(H) ≥ (2π?2(F3,3) - ξ) n3= (5/4 - ξ) n3。假設...
