A Sharp Ramsey Theorem for Ordered Hypergraph Matchings

Abstract

We prove essentially sharp bounds for Ramsey numbers of ordered hypergraph matchings, inroduced recently by Dudek, Grytczuk, and Ruciński. Namely, for any $r\ge 2$ and $n\ge 2$, we show that any collection $\mathcal{H}$ of $n$ pairwise disjoint subsets in $\mathbb{Z}$ of size $r$ contains a subcollection of size $\lfloor n^{1/(2^r-1)}/2\rfloor$ in which every pair of sets are in the same relative position with respect to the linear ordering on $\mathbb{Z}$. This improves previous bounds of Dudek-Grytczuk-Ruciński and of Anastos-Jin-Kwan-Sudakov and is sharp up to a factor of $2$. For large $r$, we even obtain such a subcollection of size $\lfloor (1-o(1))\cdot n^{1/(2^r-1)}\rfloor$, which is asymptotically tight (here, the $o(1)$-term tends to zero as $r\to \infty$, regardless of the value of $n$). Furthermore, we prove a multiparameter extension of this result where one wants to find a clique of prescribed size $m_P$ for each relative position pattern $P$. Our bound is sharp for all choices of parameters $m_P$, up to a constant factor depending on $r$ only. This answers questions of Anastos-Jin-Kwan-Sudakov and of Dudek-Grytczuk-Ruciński.

Journal version accepted to Advances in Combinatorics