Printable PDF
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

****************************