Removing induced even cycles from a graph

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

• Amarja Kathapurkar
• Thursday 05 March 2020, 15:00-16:00
• Watson 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.

This talk is included in these lists:

• Combinatorics and Probability seminar
• School of Mathematics events
• Watson LTA

Note that ex-directory lists are not shown.