On-line size Ramsey number for monotone k-uniform ordered paths with uniform looseness

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 (R) over tilde (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 (R) over tilde (t)(P-r((k))). Letting m = r - k + 1 (the number of edges in P-r((k))), we prove m(t-1)/(3 root t) <= (R) over tilde (t) (P-r((2))) <= tm(t+1). For general k, a trivial upper bound is (R-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/(k lg R) <= (R) over tilde (t) (P-r((k))) <= R(lg R)(2+ epsilon), where epsilon is a positive constant and tm is sufficiently large in terms of epsilon(-1). Our upper bounds improve prior results when t grows faster than m/logm. We also generalize our results to l-loose monotone paths, where each successive edge begins l vertices after the previous edge. (C) 2020 Elsevier Ltd. All rights reserved.

Automated summary

An ordered hypergraph is a hypergraph with a specified linear ordering of vertices, and the appearance of G in H must respect the specified order. In online Ramsey theory, Builder presents edges for Painter to immediately color, aiming to force a monochromatic copy of G using t colors. Our bounds on (R) over tilde (t)(P-r((k))) improve prior results for t growing faster than m/logm.