BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Combinatorics and Probability seminar
SUMMARY:Sharp bounds for decomposing graphs into edges and
triangles - Yanitsa Pehova (University of Warwick
)
DTSTART:20190328T130000Z
DTEND:20190328T140000Z
UID:TALK3602AT
URL:/talk/index/3602
DESCRIPTION:In a paper from 1966 Erdős\, Goodman and Pósa show
ed that for every graph G of order n there exists
a decomposition of the edges of G into at most n^2
^/4 complete graphs. In fact\, it is enough to con
sider only edges and triangles for this decomposit
ion. This is best possible\, as witnessed by the c
omplete balanced bipartite graph. It was later sho
wn by Győri and Kostochka\, by Chung\, and by Kahn
\, that if one seeks to minimise not the number\,
but the sum of the sizes of cliques in a decomposi
tion\, the corresponding minimum is n^2^/2. It was
conjectured by Győri and Tuza that edges and tria
ngles suffice here too\, up to a small constant. W
e prove this conjecture for large n\, and consider
extensions of this problem to other cost regimes.
This is joint work with (various subsets of) Adam
Blumenthal\, Dan Král'\, Taísa Martins\, Bernard
Lidický\, Florian Pfender\, Oleg Pikhurko and Jan
Volec.
LOCATION:Watson LTB
CONTACT:Richard Montgomery
END:VEVENT
END:VCALENDAR