***********************************
* Princeton Discrete Math Seminar *
***********************************
Speaker: Fan Chung, University of California, San Diego
Thursday 3rd October, 3:00 in Fine Hall 224.
Title: Regularity lemmas for clustering graphs
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.
----------------------------------
Next week: Andrey Kupavskii
Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)