## Thursday, June 07, 2007

### Study schedule about graph property testing

• 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]

• 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.
Remark:

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...

Note:

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.