Nová verze webových stránek Ústavu informatiky AV ČR v.v.i. je přístupná zde ...
Datum Název
25.9.17 10:00Maryam Sharifzadeh (Warwick University): Proof of Komlós's conjecture on Hamiltonian subsets
Popis: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.
www:http://uivty.cs.cas.cz/ExtrA/seminar.html
Nová verze webových stránek Ústavu informatiky AV ČR v.v.i. je přístupná zde ...