printable pdf
比利时vs摩洛哥足彩 ,
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

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