Cycles and Cliques Minors in Expanders

COMPUTER SCIENCE/DISCRETE MATH II
Topic:Cycles and Cliques Minors in Expanders
Speaker:Benny Sudakov
Affiliation:Princeton University
Date:Tuesday, December 12
Time/Room:10:30am - 12:30pm/S-101

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. Parts of this work are joint with J. Verstratete and with M. Krivelevich.