Combinatorics Seminar
Date/Day: 7th August, Wednesday.
Venue/Time: Ramanujan Hall, 11:30 am
Speaker: Dhruv Mubayi, University of Illinois at Chicago
Title: 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.