Thursday, June 07, 2007

Study schedule about graph property testing

我想我得列出一個 schedule 來研讀 "我所需要的" property testing papers。

  • Three theorems regarding testing graph properties [Goldreich and Trevisan; RSA 2003]
  • Testing graph properties closed under induced subgraphs
    • 詳見 [GT03], [Alon and Shapira; STOC'05] and [Alon and Shapira; FOCS'05]
  • Understanding Szemerédi's regularity lemma and Szemerédi's theorem
    • Szemerédi's regularity lemma 用在 testing in dense graphs
  • Testing k-colorability [Alon, Krivelevich; SIDA 2002]
  • Testing graphs for colorability properties [Fischer; RSA 2005]
  • Testing bipartiteness [Ron; lecture note]
要先找的 papers:
  • A combinatorial characterization of the testable graph properties: it's all about regularity. A. Shapira, STOC'06, pp. 251-260.
  • A characterization of the (natural) graph properties testable with one-sided error. N. Alon and A. Shapira, FOCS'05, pp. 429-438.

如果說 "Monotone graph properties are the properties closed under removal of edges or vertices",而 "Hereditary graph properties are the ones closed under removal of vertices"。若一個 graph G in H,則 G 不一定 in M。反過來說,若 G is in M,則 G 必 in H. 所以


Joseph, Chuang-Chieh Lin said...

A graph property P is monotone if it is closed under removal of vertices and edges. Equivalently, P is closed under taking subgraphs.

A graph property P is hereditary if it is closed under removal of vertices. Equivalently, P is closed under taking subgraphs.

So clearly, any monotone graph property is also hereditary.

Joseph, Chuang-Chieh Lin said...


A graph property P is closed under removal of edges.

A graph property P' is closed under adding an edge between any two vertices of the graph.

The definitions of P and P' are not equivalent since connectivity is P'-type but not P-type.