Caltech Home > PMA Home > Calendar > Combinatorics Seminar
open search form
Wednesday, October 23, 2024
3:00 PM - 4:00 PM
Linde Hall 255

Combinatorics Seminar

Ordered Ramsey numbers of powers of paths
Oliver Janzer, Trinity College, University of Cambridge,

Given two vertex-ordered graphs $G$ and $H$, the ordered Ramsey number $R_<(G,H)$ is the smallest $N$ such that whenever the edges of a vertex-ordered complete graph $K_N$ are red/blue-coloured, then there is a red (ordered) copy of $G$ or a blue (ordered) copy of $H$. Let $P_n^t$ denote the $t$-th power of a monotone path on $n$ vertices. The ordered Ramsey numbers of powers of paths have been extensively studied. We prove that there exists an absolute constant $C$ such that $R_<(K_s,P_n^t)\leq R(K_s,K_t)^{C} \cdot n$ holds for all $s,t,n$, which is tight up to the value of $C$. As a corollary, we obtain that there is an absolute constant $C$ such that $R_<(K_n,P_n^t)\leq n^{Ct}$. These results resolve a problem and a conjecture of Gishboliner, Jin and Sudakov. Furthermore, we show that $R_<(P_n^t,P_n^t)\leq n^{4+o(1)}$ for any fixed $t$. This answers questions of Balko, Cibulka, Král and Kyncl, and of Gishboliner, Jin and Sudakov.
Joint work with Antonio Girao and Barnabas Janzer.

For more information, please contact Math Department by phone at 626-395-4335 or by email at [email protected].