# Maximising the number of induced cycles

Thursday, September 15, 2016 -

3:00pm to 4:30pm

How many holes can a graph on n vertices contain? How many induced cycles? For sufficiently large n, we determine the maximum number of induced cycles, the maximum number of holes, and the maximum number of even or odd induced cycles, and in each case characterize the graphs achieving this bound. This answers a question of Tuza, and a conjecture of Chvatal and Tuza from 1988. Joint work with Natasha Morrison.

Speaker:

Alex Scott

Oxford University

Event Location:

Fine Hall 224