Graphs on Surfaces. II. Random graphs

本來沒有想繼續寫這個大家不是很感興趣的topic，不過過一陣要在兩個conference上再講這個問題，所以還是寫一寫。（另：有去SIAM DM開會的朋友到時候一塊吃飯。。）

之前的文章講了什麼是genus of a graph，並且提到了，確定一個特定graph的genus是非常困難的：主要工具是current graph，group theory，representation theory加上一些構造。到現在關於確定完全圖的genus的證明（Ringel-Youngs Theorem）還沒有簡單證明（原證明大概400頁）。注意genus of complete graph蘊含了Heawood conjecture。Yifan：在數學或是計算機科學中，有什麼優美的結論會有一些小的特例不滿足？

基本上確定任何的一類圖的genus的paper都可以發在top journal上。這裡我們考慮一個簡單的情形：Random Graph。Random graph的好處是，對於我們想要的情形，我們可以計算髮生的概率。然而對於一個給定的圖，只有發生和不發生兩種情形，所以比較困難。主要結論base on [arXiv:1712.09989]

Archdeacon and Grable在1995年猜想，random graph 是不是都存在一個minimum genus embedding是一個k邊形嵌入，其中k被 決定？random bipartite graph 是不是也有相似的結論？比如下圖就是一個局部的六邊形嵌入。

另外我們知道當p等於1時，對 的某些n，存在三角剖分曲面的嵌入。

我們證明了random bipartite graph情形下猜想成立。主要工具是hypergraph matching theory。

證明思路：其實思路很簡單。首先我們數一數random graph中大概會有多少個四邊形，這些四邊形大概是怎麼分布的。因為在嵌入中，每條邊被兩個面覆蓋，所以假如有一萬個四邊形，但是都集中在一兩個點上，肯定不行。對了，數學中「大概」的意思是依概率測度收斂。之後證明，因為圖中有很多很多四邊形，大概會分布的很均勻，於是我們就能找到一個四邊形的集合，每條邊被裡面的兩個四邊形覆蓋。

至於怎麼找到這個集合，我同事2014年寫過一篇paper，發在了adv. math.和STOC上。本質上就是hypergraph(3-complex)上的perfect matching。

找到這個集合之後，我們知道在一個embedding中，一個點周圍的面像一個「花」一樣把它包圍起來。因此如果我們找到的集合中，四邊形在點周圍形成了不止一個「花」，我們就得不到embedding。這也是為什麼相同的方法不能作用在一個給定的圖上，而只能用在random graph上。

不過既然是random graph，我們可以數出來花有多少，然後刪掉他們。這裡面思路上我用了兩個實分析常用的技巧，一個是用函數的supp的測度控制積分，還有一個是用一列子集來逼近全空間來把好的性質延拓到全空間上。因為如果不做任何處理，直接計算會發現裡面的「花」太多了，刪掉就不剩啥了。具體的細節比較technical，需要一系列lemma。

另外比較surprising的是，對於random bipartite graph，如果兩個點集中的一個是常數，那麼無論 是多少，graph都有一個四邊形剖分的嵌入，而不會因為 變小而變為六邊形，八邊形等等。

證明就說到這裡。關於這個問題還有一個小故事。其實整個問題是我在暑假的某一天中的某個小時想到的。那時我做一個另外的問題時需要用到random graph的genus，然而那時我不知道這個是open的，我以為早就是眾所周知的結果了並為自己不知道這個結論而羞愧。by common sense，很容易猜到random graph的minimum genus embedding對曲面有一個正則的剖分，畢竟random graph嘛，二項分布性質怎麼可能不好。因為這個是另一個問題里我證明思路的一步，我不想浪費時間查paper（因為我覺得我猜測的肯定對），但是又怕猜錯，後面的證明用這個結論就都錯了，浪費時間。於是我就在大腦中說服自己我的猜想肯定是對的，就有了整個證明的雛形。後來聽老闆說這個是open的就寫了下來。

其實原計劃是不在這個專欄里提自己的research，本來打算申一個新的專欄叫some boring combinatorial problems里提提自己的research，但是審批一直不通過。。

【待續】

推薦閱讀：