Combinatorics and Discrete Probability Seminar
Dhruv Mubayi
UIC
New results on the Erdos Rogers function
Abstract: Given integers 1 < s < t, what is the maximum size of a
K_s-free subgraph that every n vertex K_t-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 (which corresponds to the
case s=2). We prove almost optimal results in the case t=s+1 using
recent constructions in Ramsey theory. We also consider the problem where
we replace K_s and K_t by arbitrary graphs H and G and discover several
interesting new phenomena. This is joint work with Jacques Verstraete.
Monday September 16, 2024 at 3:00 PM in 1227 SEO