University of Birmingham > Talks@bham > Combinatorics and Probability seminar > Removing induced even cycles from a graph

Removing induced even cycles from a graph

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

  • UserAmarja Kathapurkar
  • ClockThursday 05 March 2020, 15:00-16:00
  • HouseWatson LTA.

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

What is the minimum proportion of edges which must be added to or removed from a graph of density p to eliminate all induced cycles of length h? The maximum of this quantity over all graphs of density p is measured by the edit distance function, ed_{Forb(C_h)}(p). Edit distances provide a natural metric between graphs and hereditary properties.

Martin and Peck determined ed_{Forb(C_h)}(p) for all p for odd cycles, and for p\geq 1/\lceil h/3 \rceil for even cycles. We improve on this result for even cycles by determining the function for all p \geq p_0, where p_0 \leq c/h^2, for some constant c. We also prove an analogous result for powers of cycles which holds for every p in [0,1], thus improving on a result of Berikkyzy, Martin, and Peck.

This is joint work with Richard Mycroft.

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.