Monday, July 07, 2008

Density of a regular pair is the average density of sub-pairs

一些關於 regular pairs 的性質。
給定一個圖 G,令 A, BG 中兩個互斥的頂點集。假設



分別為 AB 的 partitions。在此先考慮一個特殊的情況:



所以很容易地,我們可以得到

.................... (*)






亦即 (A,B) 的 density 等於 A, B 所有 subgraphs 形成的 "sub"-density 之平均值。更進一步地來說,可以考慮底下的定理 (即 Fact 1.2 in Komlós and Simonovits 在 1996 年的 survey):

Theorem: Given a bipartite graph with classes A and B, then for all integers k < |A| and l < |B|, we have



這一樣也是整體 density 等於所有同等大小 subsets 的 density 平均值。以上這些東西,paper 有時會出現。在這邊給個 remark 也好。

No comments: