Department of Mathematics,
University of California San Diego
****************************
Math 269 - Combinatorics
Mikhail Lavrov
University of Illinois at Urbana-Champaign
Ordered size Ramsey number of paths
Abstract:
The Erd\H{o}s--Szekeres theorem can be interpreted as saying that in any red-blue edge-coloring of an ordered complete graph on $rs+1$ vertices, there is a red ordered path of length $r$ or a blue ordered path of length $s$. We consider the size Ramsey version of this problem and show that $\tilde{r}(P_r, P_s)$, the least number of edges in an ordered graph with this Ramsey property, satisfies \[ \frac18 r^2 s \le \tilde{r}(P_r, P_s) \le C r^2 s (\log s)^3 \] for any $2 \le r \le s$, where $C>0$ is a constant. This is joint work with J\'ozsef Balogh, Felix Clemen, and Emily Heath.
Host: Jacques Verstraete
November 26, 2019
1:00 PM
AP&M 7321
****************************