2018/07/13 by Xavier Pérez‐Giménez, Perez-Gimenez, Xavier, Paweł Prałat +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1807.05038
openalex publication_date 2018/07/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An ordered hypergraph is a hypergraph H with a specified linear ordering of\nthe vertices, and the appearance of an ordered hypergraph G in H must\nrespect the specified order on V(G). In on-line Ramsey theory, Builder\niteratively presents edges that Painter must immediately color. The t-color\non-line size Ramsey number Rt (G) of an ordered hypergraph G is the\nminimum number of edges Builder needs to play (on a large ordered set of\nvertices) to force Painter using t colors to produce a monochromatic copy of\nG. The monotone tight path Pr(k) is the ordered hypergraph with r\nvertices whose edges are all sets of k consecutive vertices.\n We obtain good bounds on Rt (Pr(k)). Letting m=r-k+1 (the\nnumber of edges in Pr(k)), we prove mt-1/(3\√ t)\≤ Rt\n(Pr(2))\≤ tmt+1. For general k, a trivial upper bound is R choose\nk, where R is the least number of vertices in a k-uniform (ordered)\nhypergraph whose t-colorings all contain Pr(k) (and is a tower of\nheight k-2). We prove R/(k lg R)\≤ Rt(Pr(k))\≤ R( lg\nR)2+\ε, where \ε is any positive constant and t(m-1) is\nsufficiently large. Our upper bounds improve prior results when t grows\nfaster than m/\log m. We also generalize our results to \ℓ-loose monotone\npaths, where each successive edge begins \ℓ vertices after the previous\nedge.\n