Cycles and cliques minors in expanders

Benjamin Sudakov
University of California, Los Angeles (UCLA)

Let G be a graph which contains no subgraphs isomorphic to fixed bipartite graph H. Using well known results from Extremal Graph theory, one can show that such G has certain expansion properties, i.e., all small subsets of G have large boundary. This simple observation appears to be a powerful tool in attacking several extremal problems. In this talk we survey some known and very recent results which imply that expanders contain long cycles and large cliques minors. We also show how these results together with above observation can be used used to resolve several conjectures about cycle lengths and clique-minors in H-free graphs.

Presentation (PDF File)

Back to Expanders in Pure and Applied Mathematics