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

## Removing induced even cycles from a graphAdd 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:Note that ex-directory lists are not shown. |
## Other listsEPS - College Research and KT Support Activities Optimisation and Numerical Analysis Seminars PIPS - Postgraduate Informal Physics Seminars## Other talksCounting cycles in planar graphs TBA TBA Waveform modelling and the importance of multipole asymmetry in Gravitational Wave astronomy TBA Quantum Sensing in Space |