BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Combinatorics and Probability seminar
SUMMARY:Path and cycle decompositions of dense graphs - Be
rtille Granet (University of Birmingham)
DTSTART:20191017T130000Z
DTEND:20191017T140000Z
UID:TALK3902AT
URL:/talk/index/3902
DESCRIPTION:We make progress on three long standing conjecture
s from the 1960s about path and cycle decompositio
ns of graphs. Gallai conjectured that any connecte
d graph on n vertices can be decomposed into at mo
st ⌊n/2⌋ paths\, while a conjecture of Hajós state
s that any Eulerian graph on n vertices can be dec
omposed into at most ⌈(n-1)/2⌉ cycles. The Erdős-G
allai conjecture states that any graph on n vertic
es can be decomposed into O(n) cycles and edges.\n
\nWe show that if G is a sufficiently large graph
on n vertices with linear minimum degree\, then th
e following hold.\n(i) G can be decomposed into n/
2+o(n) paths.\n(ii) If G is Eulerian\, then it can
be decomposed into n/2+o(n) cycles.\n(iii) G can
be decomposed into 3n/2+o(n) cycles and edges.\nAl
l bounds in (i)-(iii) are asymptotically best poss
ible.\n\nThis is joint work with António Girão\, D
aniela Kühn\, and Deryk Osthus.
LOCATION:Watson LTB
CONTACT:Eoin Long
END:VEVENT
END:VCALENDAR