Hamilton Cycles in Expanding and Highly Connected Graphs

COMPUTER SCIENCE/DISCRETE MATH I
Topic:	Hamilton Cycles in Expanding and Highly Connected Graphs
Speaker:	Michael Krivelevich
Affiliation:	Tel Aviv University
Date:	Monday, February 27
Time/Room:	11:15am - 12:15pm/S-101

---

A Hamilton cycle in a graph G is a cycle passing through all vertices of G. Hamiltonicity is one of the most central and appealing notions in Graph Theory, with a variety of known conditions and approaches to show the existence of a Hamilton cycle.

In a recent joint work with Dan Hefetz (Tel Aviv) and Tibor Szabo (ETH) we managed to derive the following sufficient condition for Hamiltonicity:

Let G=(V,E) be a graph on n vertices, and let d=d(n) be a parameter. Suppose that:

[Expansion] Every set S of vertices of cardinality |S|< cn\log(d)/(d\log(n)) has at least d|S| outside neighbors;

[High connectivity] G has an edge between every pair of disjoint vertex subsets A,B of cardinalities |A|,|B|>cn\log(d)/\log(n).

Then G is Hamiltonian, for large enough n. [In fact, the actual statement is stronger by some logarithmic factors, that are omitted here for the sake of readability.]

In this talk I will discuss the above theorem, the circumstances under which it can be applied, and its consequences. I will also compare it with previously known Hamiltonicity criteria and will indicate some ideas of its proof.