Even-degenerate random graph–魔貨物車輛，一次載2k隻走

先來講講這篇paper的motivation(X)先來講講副標題到底是三小(O)

遙想當年歐拉為了研究七橋問題，漸漸地發展出了圖論。隨著人類來到了工業時代(?)，而圖論也與關係到了城鎮之間的連接(?)。想像一下你有 $n$ 個城市，兩兩之間有一條道路，但這些道路上有可能出現怪獸，於是城市市長們聚在一起想要解決這個問題。每個市長都有一些車輛可以把這些怪物載走，但由於魔貨物車輛的特殊效果(請見影片1:23開始)

魔貨物車輛一次要載走兩隻怪獸，所以一個城市可以發出 $k$ 量的話一次載 $2k$ 隻走。而且這些城市的車長約好要下班一起去喝酒，所以他們只肯同時發車，也就是說，作為市長聯盟主席的你，每次得選一個城市，使得他連出去的道路上有偶數隻怪獸，然後讓這座城市發車清除這些怪獸。然而，我們都知道這樣做奇偶性不會變，所以你的目標是消滅到剩下一隻怪獸，然後與牠肉搏。

當然，有可能不幸的怪獸出現的道路讓你無法完成這項任務，例如一開始每座城市都看到了奇數隻怪物，那你就無法處理(注意：你如果此時出現與其中一隻怪物肉搏，那所有怪物會一擁而上圍毆你)。但就像奇異博士看了14,000,605種可能，你只需要在大部分的時間線上達成任務即可。更精確來說，每條道路上怪物出現的機率是 $p$ 且出現是獨立事件，其中 $p\in (0,1)$ 是個常數，你需要高機率(若 $n$ 趨近無限，則機率趨近於 $1$ )達成這件事即可。

胡扯完motivation了，先來講講研究故事，嚴謹的數學statement跟證明idea放在後面說。基本上這問題是某天Dingding跟Zixuan在看別人關於這個問題的證明，其中他們證了 $p=1/2$ 的case，然後我就湊過去問說她們在看啥，然後我們就開始想general $p$ 的case。一段時間之後，我們有了個看起來很不錯的algorithm可以拔掉constant fraction個點。但with hindsight這只能得到機率至少是某個很小的常數，為了解決這個問題，我們試著把這個algorithm用不只一次，然後只要其中一次成功就行了。但問題來了，因為每次algorithm會揭露出圖的一些資訊，所以用太多次會很難分析。於是我們接下來幾個月就在"如何分析→會分析了→寫下來發現是一坨屎山→發現一個嚴重的問題→知道怎麼修了→寫下來發現是另一坨屎山→努力把證明寫好"中度過。

不得不說，這次寫作學到了random graph好難寫OAO。把話講清楚比想像中還累，而且每一步都在condition on不同的資訊，要認真弄清楚好麻煩，但至少我可能或許比較會random graph的寫作了嗎XD。或是說我學會了條列式狂魔(?)的enumerate大法(?)加上怎麼manage每天都能見到的合作者(?)

Fun Fact:

(1) 終於跟Noga(的學生)^i, $i=1,2,3,4$ 合作過了， $i<0$ 不可能， $i=0$ 有點難， $i\geq 5$ 不存在。

(2) 合作者華人:非華人來到了驚人的14:2

(3) 目前已跟兩個xzx合作

(4) 就算用嚴格的標準來數我圖論的paper數量，它也超過了我polynomial method paper數量了OAO，我什麼時候可以回去做我的主線QQ

那，以下進入數學部分。先上paper連結：https://arxiv.org/abs/2506.01021

正如前面所說，我們有興趣的是even-degenerate這個性質。一般來說， $k$ -degenerate意思是你可以每次從圖裡拔掉一個度數至多是 $k$ 的點，直到拔完。所以even-degenerate的定義不難猜出來會是如下：

定義：一張 $n$ 個點的圖 $G=(V,E)$ 是even-degenerate的若我們可以排序 $V=\{v_1,\dots,v_n\}$ 使得對於所有 $i=1,\dots,n-2$ ， $v_i$ 與 $v_{i+1},\dots,v_n$ 之間有偶數條邊。

注意到，如果一開始邊數是奇數，則我們允許留下一條邊。而如前面所說，我們關心的是以下問題：

問題：對於一個Erdős–Rényi隨機圖 $G=G(n,p)$ ，其中 $p\in (0,1)$ 是個常數，我們是否有 $\mathbb{P}(G\text{ is not even-degenerate})=o(1)$ ？

對於這個問題，Janzer跟Yip證明了當 $p=1/2$ 的時候是對的，而且機率是 $e^{-\Theta(n)}$ 。其中他們用到了以下的重要性值：

性質：假設condition on $G(n,1/2)$ 中的所有點出度的奇偶性並移除一個出度為偶數的點，則剩下的 $n-1$ 個點之間的圖會是 $G(n-1,1/2)$ 。

這性質有興趣的讀者可以自己證證看，或是等等會提到一個更簡單的性質會imply這件事。然而，這在 $p\neq 1/2$ 的時候就是錯的了，原因是假設 $p=0.01$ ，你如果知道 $u$ 跟 $v$ 的出度的話，移除 $u$ 你會有 $0.99$ 的機率 $v$ 的出度奇偶性不變，所以我們需要更有創意(?)

在此之前，先讓小弟我formally state一下我們的定理。

定理：給定 $p\in (0,1),\alpha\in (0,1/2)$ ，我們有 $\mathbb{P}(G\text{ is not even-degenerate})=e^{-\Omega(n^{1/2-\alpha})}$

好啊，在講我們要怎麼選點來拔之前，我們先講一些簡單的性質。

性質1：假設有 $\eta$ 個機率為 $p$ 的硬幣，則他們有奇數/偶數個正面的機率都在 $1/2\pm e^{-\Theta(\eta)}$ 以內。

這性質可以從二項式定理推出來，留給讀者做練習。這性質教會我們，你一開始問其中一個點的奇偶性會非常接近一半一半。

性質2：你有一個機率任意的硬幣，跟一個公平的硬幣。則他們兩個一起出現奇數/偶數個正面的機率還是一半一半。

加上性質1，這性質告訴我們，只要你一個點連出去的邊中剩下足多還是隨機的，你問他奇偶性的時候都是接近一半一半。

性質3：你有一個機率任意的硬幣，跟一個公平的硬幣。Condition on兩個人總共有偶數個正面，第一個硬幣的機率分布跟沒condition一樣。

這性質告訴我們，你告訴我一個點出度是偶數可以想像成我把這個點連出去的一些邊放在一旁，說這些邊會fix這個奇偶性，然後就不用這些邊了。

當然，我們實際上需要的是以上性質的近似版本，也就是說公平的硬幣要換成接近公平的硬幣，且我們也需要更複雜的設定下的這些敘述。以下是其中一個我們用到的引理。

引理：假設 $A,B$ 各有 $\eta$ 個不同的點，其中他們之間的連邊是 $p$ -random的，也就是說任何一組 $a\in A,b\in B$ 之間有獨立的機率 $p$ 連一條邊。則 $(\deg(a),\deg(b))_{a\in A,b\in B}$ 的奇偶性非常接近和是偶數的均勻隨機。這裡非常接近的意思是出現某組特定總和是偶數的奇偶性的機率跟均勻隨機的ratio介在 $(1-e^{-\Theta(\eta)})$ 跟 $(1-e^{-\Theta(\eta)})^{-1}$ 之間。

簡單講一下這個證明要用到的idea。首先，如果只有一邊的奇偶性，那根據前面的性質1就有了。所以我們可以想成condition on $A$ 裡的所有奇偶性，要證明 $B$ 裡的分布是均勻的。把 $B$ 裡的點排成一列 $b_1,\dots,b_{\eta}$ ，如果 $b_i,b_{i+1}$ 到某個點 $a$ 之間一個有連一個沒連，那把邊交換過來只會改變 $b_i,b_{i+1}$ 的奇偶性，不會改變其他人的奇偶性跟這張圖出現的機率，所以condition on總是找的到兩條邊可以交換的話，每個總和是偶數的奇偶性機率應該要是均勻的。然後只要兩個人鄰居這個set不完全一樣就能交換，而這件事發生的機率是exponentially small的，所以在省略了很多繁瑣的細節後，這引理就得證了。

那接下來說說怎麼證明我們的定理的。以下會省略一些technical details，所以充滿了各種white lie。首先我們先把點分成兩部分各 $n/2$ 個點，分別稱為 $U,W$ 。我們把 $U$ 排好一個順序 $u_1,\dots,u_{n/2}$ ，把 $W$ 切成 $s$ 份一樣大的 $W_1,\dots,W_s$ ，其中 $s$ 大概是 $n^{1/2}$ 。我們的目標如下：

假設 $\mathfrak{p},\mathfrak{q}$ 是兩個指標，分別指著 $U,W$ 裡拔掉了幾個點。考慮總共有 $n/2$ 輪， $\mathfrak{p}=1,\dots,n/2$ 。依序考慮 $u_{\mathfrak{p}}$ ，如果 $u_{\mathfrak{p}}$ 在當前的圖裡出度是偶數的，我們就把他拔了， $\mathfrak{p}++$ ，然後進下一輪。如果是奇數，我們在 $W_{\mathfrak{q}}$ (其中下標總是mod $s$ )中找一個點 $w$ 使得

(1) $u_{\mathfrak{p}}w$ 之間有邊

(2) $w$ 的出度是偶數

則我們可以先拔 $w$ 再拔 $u_{\mathfrak{p}}$ ， $\mathfrak{p}++,\mathfrak{q}++$ ，然後進下一輪。

那我們簡單說服一下自己為什麼這個高機率能拔完 $U$ 裡的點，且 $W$ 裡剩下大概 $n/4$ 個點。首先， $u_{\mathfrak{p}}$ 問到的奇偶性應該要接近一半一半，因為在此之前你基本上沒問過任何關於這個點的資訊。然後假設你問到了 $u_{\mathfrak{p}}$ 出度是奇數，那根據Chernoff bound，他在 $W_{\mathfrak{q}}$ 中高機率會有constant fraction有連邊，這是因為你可以先拋開一部分的邊作為古希臘掌管它奇偶性的神，剩下的可以想成 $p$ -random。我們同時詢問 $W_{\mathfrak{q}}$ 裡每個點的奇偶性，我們可以想成每個都接近公平的硬幣(等等會解釋為什麼)，所以再次根據Chernoff bound，高機率跟 $u_{\mathfrak{p}}$ 有連邊的那些人中，會有至少一個出度是偶數。所以這輪有高機率成功，根據union bound，每一輪都成功也是高機率的。而由於 $u_{\mathfrak{p}}$ 出度的奇偶性都是接近一半一半，所以再次根據Chernoff bound高機率有一半左右的次數是偶數，所以 $W$ 裡應該用了 $|U|/2=n/4$ 個點左右。

好，那剩下一個問題，為什麼 $W_{\mathfrak{q}}$ 裡每個點的奇偶性，我們可以想成每個都接近公平的硬幣呢？注意到對於某個 $w\in W_{\mathfrak{q}}$ ，它可能在前面的輪次就被問過奇偶性了(因為 $W_{\mathfrak{q}}$ 下標是mod $s$ 的)。但注意到， $w$ 距離上次被問，我們已經拔掉了 $s$ 個點，他上次被問的時候，我們詢問了 $w$ 到那時候的圖中所有點的有奇數還是偶數條邊，而這次被問，我們詢問了到當前的圖的。所以兩次之間的差是 $w$ 到過程中被拔掉的點的奇偶性。注意到我們沒有單獨用到這些資訊，所以它基本上會給你足夠的randomness讓這個奇偶性接近一半一半，所以兩次 $w$ 被詢問之間是沒什麼關聯的。也就是說，可以想成我們拔掉了 $s$ 個 $W$ 裡的點後， $W_{\mathfrak{q}}$ 的奇偶性被重置了。

那我們來簡單想一下這個拔法會給我們什麼。首先，我們會有剩下的圖接近一個 $G(n/4,p)$ (not quite true but let’s assume this for now)。假設 $G(n,p)$ 失敗的機率是 $f(n)$ ，則上面的操作大概告訴我們 $f(n)\leq f(n/4)+o(1)$ ，因為你上面失敗的機率是 $o(1)$ ，成功的話剩下 $n/4$ 個點失敗機率是 $f(n/4)$ 。但這樣就會發現，你遞迴下去頂多證明 $f(n)$ 小於某個常數，跟他趨近零還有一段距離。

那怎麼辦呢？我們可以考慮把上面的拔法用兩次。我們把點集合 $V$ 切成兩部分一樣大的 $B,C$ ，一次做 $U=B,W=C$ ，一次做 $U=C,W=B$ 。這樣兩次分別都會高機率成功，假設第一次剩下 $V_C\subseteq C$ ，第二次剩下 $V_B\subseteq B$ ，分別有大概 $n/4$ 個點。重點是，這兩坨因為不相交，所以假設兩次都成功的話， $G[V_B],G[V_C]$ 應該(?!?)是獨立的兩個 $G(n/4,p)$ ，於是會有 $1-f(n)\geq (1-o(1))(1-f(n/4)^2)$ 。這是因為你有 $(1-o(1))$ 機率成功兩次都成功，然後如果 $G[V_B],G[V_C]$ 其中一個even-degenerate就win了，所以有 $(1-f(n/4)^2)$ 的機率可以拔完。

好，那，上面那個應該後面的(?!?)是怎麼回事呢？答案就是，他是錯的，因為兩邊其實是共用一些資訊的，而且在拔的過程中會有一些資訊留下來。分別有三種資訊，給讀者們五分鐘猜一下XD

(防雷)

(五分鐘過後)

首先，最好猜的應該是

(1) $G[V_B],G[V_C]$ 中總邊數的奇偶性要是一樣的。

再來，從我們移除的過程中，我們知道 $B$ 在作為 $W$ 的時候，實際上是用過 $w\in W_{\mathfrak{q}}$ 的奇偶性的。如果 $\mathfrak{q}$ 非常接近結束的那幾輪的話，那他的奇偶性還來不及被重置，所以有一小部分人 $w$ 使得 $w$ 到所有剩下的人的出度奇偶性是知道的。這給了我們

(2) 某個不大的 $A_B\subseteq V_B$ 使得 $w\in A_B$ 到 $V_B$ 的奇偶性是知道的。 $C$ 的部分類似。

然後第三個其實比較像是為了technical reason，雖然上面說過 $B$ 在作為 $U$ 的時候，問的奇偶性被另一邊掌管，但實際上 $U,W$ 兩部分之間的邊用的情況在兩輪之間有點混亂，所以有可能有某些 $U$ 內的資訊被留下來，尤其是 $U$ 裡最後幾個人，他們restricted to $U$ 的出度奇偶性會相當bias且很有可能告訴你他們之間有沒有連邊。那乾脆一開始就告訴你，所以我們把這些點加進 $A_B$ 裡，然後直接大放送告訴你 $A_B$ 裡面長怎樣

(3) $G[A_B]$ 裡的所有邊。

根據上面的motivation，我們可以定義一個partially revealed graph $G=(V,E)$ with $A\subseteq V$ revealed 是一張告訴了你

(1) $G$ 的總邊數

(2) $\deg_G(a)$ 的奇偶性 for all $a\in A$

(3) $G[A]$

的 $G(n,p)$ 。假設 $f(n)$ 是 $n$ 個點的partially revealed graph不是even-degenerate的最大的機率(among 所有可能的reveal資訊)，則我們真的會有形如 $1-f(n)\geq (1-o(1))(1-f(n/4)^2)$ 的遞迴。解遞迴就留給讀者自行思考。

But！人生就是這個but(?)我們其實從頭到尾都沒否定 $f(n)=1$ holds for all $n$ large enough。你仔細盯著遞迴就會發現這也是一組解，怎麼辦。於是我們有了構造題：給定你partially revealed graph的revealed的資訊，請找一張圖滿足這些資訊且他是even-degenerate的。有了這個構造之後，我們就可以說 $f(n)$ 總是小於 $1$ 了。

趙庭偉的blog

Even-degenerate random graph–魔貨物車輛，一次載2k隻走

發表留言取消回覆

Even-degenerate random graph–魔貨物車輛，一次載2k隻走

分享此文：

發表留言 取消回覆

發表留言取消回覆