Regularity lemmas for clustering graphs

Regularity lemmas for clustering graphs

-
Fan Chung, University of California, San Diego
Fine Hall 224

A fundamental tool in graph theory is Szemeredi's regularity lemma which asserts that any dense graph can be partitioned into finitely many parts so that almost all edges are contained in the union of bipartite subgraphs between pairs of the parts and these bipartite subgraphs are random-like under the notion of epsilon-regularity. Here, we consider a variation of the regularity lemma for graphs with a nontrivial clustering coefficient. The clustering coefficient is the ratio of the number of triangles and the number of paths of length 2 in a graph. Note many real-world graphs have large clustering coefficients and such a clustering effect is one of the main characteristics of the so-called ``small world phenomenon''. In this talk, we give a regularity lemma for clustering graphs without any restriction on edge density. We also discuss several generalizations of the regularity lemma and mention some related problems.