Upcoming Seminars
| Title: Erdos-Rogers Functions |
|---|
| Seminar: Combinatorics |
| Speaker: Jacques Verstraete of University of California San Diego |
| Contact: Liana Yepremyan, liana.yepremyan@emory.edu |
| Date: 2024-04-26 at 4:00PM |
| Venue: MSC W201 |
| Download Flyer |
| Abstract: The Erdos-Rogers functions are generalizations of Ramsey numbers, introduced around fifty years ago. The general question given graphs $F$ and $H$ is to determine the maximum number of vertices $f(n,F,H)$ in an $F$-free induced subgraph of any $H$-free $n$-vertex graph. The case $F = K_2$ is equivalent to determining Ramsey numbers $r(H,t)$. The case $F$ and $H$ are cliques has received considerable attention. In this talk we give almost tight bounds, showing that for $s > 3$, $$ f(n,K_s,K_{s-1}) = \sqrt{n}(\log n)^{\Theta(1)} $$ where the exponent of the logarithm is between $1/2 - o(1)$ and $1 + o(1)$. We also give new bounds on Ramsey numbers $r(F,t)$. In part joint work with David Conlon, Sam Mattheus and Dhruv Mubayi. |