Computer Science/Discrete Mathematics Seminar II

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.