MATH Seminar

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.

See All Seminars