Computer Science/Discrete Mathematics Seminar I

Paths and cycles in expanders

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.

Date & Time

February 10, 2020 | 11:00am – 12:00pm

Location

Simonyi Hall 101

Affiliation

Tel Aviv University