Wednesday, August 06, 2008

Hereditary and semihereditary graph properties

先看看底下關於 semihereditary graph property 的定義:
Definition. A graph property P is semihereditary if there exists a hereditary graph property H such that the following hold:

Any graph satisfying P also satisfies H.
There is a function M: (0,1) -> N, such that any graph G of size at least M(ε), which is far from satisfying P, contains an induced subgraph that does not satisfy H.

一開始看起來還蠻令人眼花撩亂的。事實上,semihereditary graph properties 是由 hereditary graph properties 所造出來的。造法就是對每一個 hereditary graph property 所代表的圖形集合「拿掉」其中一部分的圖。所以這也讓形成的「新集合」可能不會 "closed under taking induced subgraphs"。此外,那些 「ε-far from P 卻不包含不滿足 H 的 induced subgraph 」的圖形數目是「有限」的 (考慮 size at most M(ε) 的 graphs)。而對照一個 hereditary graph property P',ε-far from P' 的 G 「一定」含有不滿足 P' 的 induced subgraph。

根據上面的定義,每個 hereditary graph property 必定是 semihereditary (因為可以把 H 換成 P 自己)。根據 Alon 與 Shapira 在 2005 的結果 (also SICOMP 2008),一個 graph property 為 semihereditary 若且唯若它有一個 oblivious one-sided error testing algorithm。裡面的 "oblivious" 是指 testing algorithm 不需要知道 input graph 的 size。

1 comment:

Joseph, Chuang-Chieh Lin said...

關於很多重要的分析和 Lemmas,都在 Alon 等人在 2000 年發表的 Efficient testing of large graphs 這一篇文章裡。如果想要對 Regularity 熟悉一點,或者想要看懂相關的 SIAM Journal papers 的話,可以在一篇文章裡挖寶。

感覺上,實力變強了再回頭來看這篇文章,又會有不同的感覺。說實話,要讀懂這篇文章,可得有一定的功力才行啊。 (煙~)