稠密圖的 graphon 極限（the graphon limit of dense graphs）

graphon 是稠密圖序列的極限物件——即邊數為 n^2 階、邊密度遠離 0 的圖。Benjamini-Schramm 收斂是稀疏圖的正確概念（局部視角），而 graphon 是稠密圖的正確概念（整體視角），捕捉每一對頂點「區域」之間邊的極限密度。它回答的問題是：在什麼意義下，越來越大的稠密圖序列會收斂，而極限是什麼？

graphon 是一個對稱可測函數 W，由 [0,1] x [0,1] 映到 [0,1]；把 [0,1] 想成頂點的連續體，W(x,y) 是型別 x 與 y 之間有邊的機率（或密度）。每張有限圖 G 本身就是一個 graphon W_G（由其鄰接矩陣給出的格上 0/1 階梯函數），而 Lovasz 與 Szegedy 的理論說：稠密圖序列 G_n 收斂當且僅當對每個固定小圖 F，同態密度 t(F, G_n)（把 F 的頂點均勻隨機映入 G_n 而保邊的機率）收斂。此「左收斂」等價於切距離（cut metric）下的收斂，那是一個量度所有頂點子集對之間邊密度最大差異的距離——而 graphon 空間模去保測重標號後，在切距離下緊（Lovasz-Szegedy 緊性定理，用 Szemeredi 正則化引理證明）。序列的極限是一個 graphon W，反之從 graphon 抽樣（在 [0,1] 中放 n 個隨機點 x_1, ..., x_n，以機率 W(x_i, x_j) 獨立地連 i 與 j）生成一個 W-隨機圖，其極限為 W。厄多斯-雷尼 G(n,p) 是恆等於常數 p 之常數 graphon 的 W-隨機圖；隨機區塊模型是階梯函數 graphon 的 W-隨機圖。

graphon 之所以重要，是因為它把關於大型稠密圖的極值與統計問題，化為函數空間上的分析：子圖密度成為對 W 的積分，極限理論解釋並統一了正則化引理、擬隨機性與性質檢測，而 graphon 是估計單一大型網路結構的自然無母數模型（網路直方圖、隨機區塊模型擬合）。誠實的提醒至關重要。其一，graphon 只描述稠密圖：稀疏圖（o(n^2) 條邊）的同態密度全趨於 0，故其 graphon 極限是零 graphon，丟掉全部資訊——稀疏圖需要 Benjamini-Schramm 或稀疏圖極限的另一套理論（L^p graphon、graphing）。其二，graphon 只在 [0,1] 的保測變換（重標號連續體頂點）下唯一，故「那個」極限其實是個等價類。其三，切距離下的收斂是整體、密度層級的概念；它對牽涉 o(n^2) 條邊的特徵不敏感，故兩張有相同 graphon 的稠密圖在一切「低階」之處仍可能不同。