Computer Science/Discrete Mathematics Seminar I

Expanders have grown to be one of the most central and studied notions in modern graph theory. It is thus only natural to research extremal properties of expanding graphs. In this talk we will adapt the following (rather relaxed) definition of expanders. For a constant alpha>0, a graph G on n vertices is called an alpha-expander if the external neighborhood of every vertex subset U of size |U|<=n/2 in G has size at least alpha*|U|. We will discuss long paths, cycles, and cycle lengths in alpha-expanders. The talk is mostly based on a joint work with Limor Friedman.