University of Birmingham > Talks@bham > Combinatorics and Probability Seminar > Two problems in extremal graph theory

Two problems in extremal graph theory

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

  • UserTaisa Martins (University of Warwick)
  • ClockTuesday 28 November 2017, 15:00-16:00
  • HouseWatson LTA.

If you have a question about this talk, please contact Guillem Perarnau.

In this talk, we prove a conjecture of Gyori and Tuza which states that the edges of every n-vertex graph G can be decomposed into edges and triangles C_1, . . . , C_k such that |C_1| . . . |C_k| ≤ (1/2 + o(1))n2 and we generalize a result of Sudakov concerning the number of edges needed to be removed from a K_4-free graph to make it bipartite. We show that if H is 6-colourable, then any H-free n-vertex graph can be made bipartite by deleting at most 4n2/25 edges. Both results are obtained using the flag algebra method. During the talk, we introduce the method and show how it can be applied to obtain the two results.

Joint work with P. Hu, D. Kral, B. Lidicky, S. Norin, Y. Pehova and J. 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 talks.cam from the University of Cambridge.