On the Ramsey classes of random hypergraphs

Abstract

Let $r,s,t\ge 2$ be integers. For $r$-graphs $G$ and $F_1,\dots ,F_s$, we write $G\to (F_1,\dots ,F_s)$ if every $s$-edge-coloring of $G$ yields a monochromatic copy of $F_i$ in the $i$-th color for some $1\le i\le s$. Let $\mathcal{R}(F_1,\dots ,F_s)$ denote the family of all $r$-graphs $G$ with $G\to (F_1,\dots ,F_s)$. When $F_1=\cdots =F_s=F$, we write $\mathcal{R}(F;s)=\mathcal{R}(F_1,\dots ,F_s)$. In this paper, we investigate when $\mathcal{R}(H;s)\subseteq \mathcal{R}(Q_1,\dots ,Q_t)$ holds, where $H=H^{(r)}(n,p)$ is a random $r$-graph and $Q_1,\dots ,Q_t$ are fixed $r$-graphs. Our main result determines the threshold for a large class of such $Q_1,\dots ,Q_t$, including complete $r$-graphs. The key ingredient in our proof is a generalization of a result of Graham, Łuczak, Rödl, and Ruciński, which provides a necessary and sufficient condition for $\mathcal{R}(F_1,\dots ,F_s)\subseteq \mathcal{R}(Q_1,\dots ,Q_t)$, where $Q_1,\dots ,Q_t$ are highly connected. As a byproduct, we characterize when two tuples of highly connected $r$-graphs are Ramsey equivalent.

13 pages