An ordered hypergraph is a hypergraph $H$ with a specified linear ordering of the vertices, and the appearance of an ordered hypergraph $G$ in $H$ must respect the specified order on $V(G)$. In on-line Ramsey theory, Builder iteratively presents edges that Painter must immediately color. The $t$-color on-line size Ramsey number $tilde R_t (G)$ of an ordered hypergraph $G$ is the minimum number of edges Builder needs to play (on a large ordered set of vertices) to force Painter using $t$ colors to produce a monochromatic copy of $G$. The monotone tight path $P_r^{(k)}$ is the ordered hypergraph with $r$ vertices whose edges are all sets of $k$ consecutive vertices. We obtain good bounds on $tilde R_t (P_r^{(k)})$. Letting $m=r-k+1$ (the number of edges in $P_r^{(k)}$), we prove $m^{t-1}/(3sqrt t)letilde R_t (P_r^{(2)})le tm^{t+1}$. For general $k$, a trivial upper bound is ${R choose k}$, where $R$ is the least number of vertices in a $k$-uniform (ordered) hypergraph whose $t$-colorings all contain $P_r^{(k)}$ (and is a tower of height $k-2$). We prove $R/(klg R)letilde R_t(P_r^{(k)})le R(lg R)^{2+epsilon}$, where $epsilon$ is any positive constant and $t(m-1)$ is sufficiently large. Our upper bounds improve prior results when $t$ grows faster than $m/log m$. We also generalize our results to $ell$-loose monotone paths, where each successive edge begins $ell$ vertices after the previous edge.
Download