On the structural growth of bipartite Ramsey numbers

密集二部圖的 Ramsey 增長速率由密度指數 (q-1)/(p-2) 精確決定；邊數 q ≥ 2p-2 是「尺寸線性」行為崩潰的確切門檻。天津師範大學孟驥這篇論文，首次將二部 Ramsey 數的漸近行為與禁用子圖的結構密度直接掛鉤，並對偶圈給出精確上界 br(C_{2t}, G) ≤ m/2 + 29t√m/2，填補了這個領域五十年來的認知空白。

二部 Ramsey 理論的五十年增長懸案

Ramsey 理論的核心問題是「不可避免的結構」：對足夠大的圖做任意邊染色，特定的單色子圖必然出現。二部 Ramsey 數 br(G₁, G₂) 是最小的 N，使得完全二部圖 K_{N,N}（兩邊各 N 個頂點）的任意紅藍染色，必然包含紅色的 G₁ 或藍色的 G₂；q 色版本則要求每種顏色各自出現對應的單色子圖。

這個問題的系統研究始於五十年前：1974 年 Faudree 與 Schelp、以及 Gyárfás 與 Lehel 各自獨立確定了路徑 br(P_n, P_n) 的精確值；1975 年 Beineke 與 Schwenk 開始研究 br(K_{s,s}, K_{s,s})。目前最佳的界：下界 br(K_{s,s}, K_{s,s}) = Ω((√2)^s)，上界 br(K_{s,s}, K_{s,s}) ≤ O(2^{s+1})——兩個指數的底數之間有近兩倍的差距。儘管特定圖的精確值已有部分結果，「br(G₁, G₂) 的一般漸近行為如何由 G₁、G₂ 的結構參數決定」這個核心問題仍幾乎無解，本文直接在這個空白上發力。

Theorem 1：q 色 Ramsey 的概率構造下界

第一個主要結果給出 br(K_{s,t}; q)——q 種顏色下、K_{s,t} 為禁用子圖的 Ramsey 數——的顯式下界。核心工具是把 Nikiforov 和 Sawin 對普通多色 Ramsey 數的概率方法移植到二部圖設定。定義 w_{s,t} 為：在不含 K_{s,t} 的二部圖中，隨機選取 s+t 個頂點（s 個在一邊、t 個在另一邊）恰好形成獨立集的下確界概率。

論文先用隨機二部圖（頂點數 R ≈ 2^{st/(s+t)}，獨立邊概率 p = 1/2）構造一個 K_{s,t}-free 的小圖，Markov 不等式確認以超過 1/2 的概率圖中無 K_{s,t}；再做「吹脹（blow-up）」操作讓頂點數趨無窮，估計出 w_{s,t} 的上界。最後通過 q-2 個隨機映射對 K_{N,N} 染色——前 q-2 種顏色按映射邊分配，剩余邊隨機分給最後兩色——聯合界計算給出：

br(K_{s,t}; q) > 2^{(q-2)/(s+t)·[st − (st)²/(s+t)² − log(s^s·t^t)] + st/(s+t)}

指數中的 st − (st)²/(s+t)² 項由獨立集密度的優化推導而來，log(s^s·t^t) = s·log s + t·log t 來自 Stirling 估計對階乘的處理。

Theorem 2 與推論：增長速率的密度門檻

論文最核心的結果：設 G 是有 p 個頂點、q 條邊的固定二部圖，則存在常數 C，對所有足夠大的 n：

br(G, K_{n,n}) > C · (n/log n)^{(q-1)/(p-2)}

指數 (q-1)/(p-2) 是圖 G 的密度型參數，量化了禁用圖的邊數相對於頂點數的比值，直接決定 Ramsey 數的增長速率。證明工具是非對稱 Lovász 局部引理（asymmetric Local Lemma）：把 K_{N,N} 的邊以概率 r = c₁N^{-s}（s = (p-2)/(q-1)）染成紅色，對每個 p 頂點子集定義「紅色子圖含 G」的壞事件，對每個 2n 頂點子集定義「藍色子圖含 K_{n,n}」的壞事件，局部引理確認兩類事件可以同時避開，從而建立 br(G, K_{n,n}) > N 的下界。

由此立刻推出 Corollary 1：若 G 滿足 p(G) ≥ 3 且 q(G) ≥ 2p(G) − 2，則 G 不是二部 Ramsey 尺寸線性的。「尺寸線性」指存在常數 C 使 br(H, G) ≤ C·m 對所有 m 邊圖 G 成立，是最溫和的增長行為。Erdős 等人的經典結果已給出：邊數 q ≤ p+1 的連通圖一定是尺寸線性的；本文新建立的邊界顯示，一旦 q ≥ 2p−2，尺寸線性必然失敗。中間範圍 p+2 ≤ q ≤ 2p−3 仍是完全開放的問題——這個「密度門檻」的精確位置尚未確定。

Theorem 3-4：偶圈的 Zarankiewicz 上界

論文後半部轉向上界，結合 Zarankiewicz 函數——K_{r,r} 中不含 K_{s,s} 子圖的最大邊數——和雙重計數論證。核心引理來自 Naor 與 Verstraëte：K_{r,r} 中不含 C_{2t} 的子圖邊數 ≤ (2t−3)(r^{1+1/t}+2r)。

Theorem 3 的論證：若 K_{r,r} 的 (k+1) 色染色中前 k 色無 C_{2t}、第 k+1 色無 K_{n,n}，則兩部分邊數之和 ≥ r²。設 r = cn²/log²n，代入兩個 Zarankiewicz 估計後右邊嚴格小於 r²，得出矛盾，從而證明：br_k(C_{2t}; K_{n,n}) ≤ c_{t,k}·n²/log²n。

在此基礎上，Theorem 4 給出精確的線性上界：對任意 t ≥ 2、任意 m 邊且無孤立頂點的連通二部圖 G，br(C_{2t}, G) ≤ m/2 + 29t·√m/2。證明採用貪心嵌入策略：先刪去「紅度」≥ 7t√m 的頂點，再逐一把 G 的頂點嵌入剩餘圖的藍色子圖；若某步嵌入失敗，分 r ≤ m/2 和 m/2 < r ≤ m 兩個子情形，分別從鄰居集大小 |W'| 的上下界導出矛盾，確認嵌入必然成功。主項 m/2 是線性的，修正項 29t·√m/2 僅為 O(√m)——偶圈的 Ramsey 數幾乎是「尺寸線性」的。

密度指數 (q-1)/(p-2) 精確決定二部 Ramsey 增長率；q ≥ 2p−2 是尺寸線性的硬性上限，偶圈的 Ramsey 數接近線性，修正項僅 O(√m)。