University of Birmingham > Talks@bham > Combinatorics and Probability seminar > Sharp bounds for decomposing graphs into edges and triangles

Sharp bounds for decomposing graphs into edges and triangles

Add to your list(s) Download to your calendar using vCal

  • UserYanitsa Pehova (University of Warwick)
  • ClockThursday 28 March 2019, 13:00-14:00
  • HouseWatson LTB.

If you have a question about this talk, please contact Richard Montgomery.

In a paper from 1966 Erdős, Goodman and Pósa showed that for every graph G of order n there exists a decomposition of the edges of G into at most n2/4 complete graphs. In fact, it is enough to consider only edges and triangles for this decomposition. This is best possible, as witnessed by the complete balanced bipartite graph. It was later shown 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 decomposition, the corresponding minimum is n2/2. It was conjectured by Győri and Tuza that edges and triangles suffice here too, up to a small constant. We 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.

This talk is part of the Combinatorics and Probability seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on from the University of Cambridge.