Comming seminars

  • Maryam Sharifzadeh (Warwick University): Proof of Komlós's conjecture on Hamiltonian subsets

    25.9.2017 10:00 @ Applied Mathematical Logic

    Komlós conjectured in 1981 that among all graphs with minimum degree at least d, the complete graph K_{d+1} minimises the number of Hamiltonian subsets, where a subset of vertices is Hamiltonian if it contains a spanning cycle. We prove this conjecture when d is sufficiently large. In fact we prove a stronger result: for large d, any graph G with average degree at least d contains almost twice as many Hamiltonian subsets as K_{d+1}, unless G is isomorphic to K_{d+1} or a certain other graph which we specify. This is joint work with Jaehoon Kim, Hong Liu and Katherine Staden.