Computer Science/Discrete Mathematics Seminar I

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.