Graph Theory Seminar: Hamilton cycles in sparse graphs: between randomness and symmetry.

Abstract: When does a graph G contain a Hamilton cycle? This is one of the central questions of graph theory, which is one of Karp´s original  21 NP-complete problems. In this talk, I’ll revise conditions on sparse graphs that ensure the existence of a Hamilton cycle. In particular, optimal pseudorandom conditions forcing not only Hamiltonicity, but also resilience and (approximate) Hamilton decompositions, and how symmetry also plays a role in the Hamiltonicity problem, as in the Lovász conjecture from 1969.

Speaker: Matías Pavez Signé (Universidad de Chile/CMM)