##### Department of Mathematics,

University of California San Diego

****************************

### Math 295 - Mathematics Colloquium

## Fan Chung

#### UCSD

## Regularity lemmas for clustering graphs

##### Abstract:

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$-regular. \medskip 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 triangles and the number of paths of length $2$ in a graph. Note many real-world graphs have large clustering coefficients and such clustering effect is one of the main characteristics of the so-called ``small world phenomenon''. \medskip 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.

### March 14, 2019

### 4:00 PM

### AP&M 6402

****************************