The ACO Seminar (2024–2025)

What is the maximum size of a triangle-free subgraph that every n vertex K_4-free graph is guaranteed to contain? This problem was posed by Hajnal, Erdos and Rogers in the 1960s as a way to generalize classical graph Ramsey numbers. We prove almost optimal results using recent constructions in Ramsey theory. We also consider the problem where we replace triangle and K_4 by arbitrary graphs H and G and discover several interesting new phenomena. This is joint work with Jacques Verstraete.