Journal
EUROPEAN JOURNAL OF COMBINATORICS
Volume 92, Issue -, Pages -Publisher
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
DOI: 10.1016/j.ejc.2020.103242
Keywords
-
Categories
Funding
- NSERC
- Ryerson University
- National Natural Science Foundation of China [NSFC 11871439, 11971439]
Ask authors/readers for more resources
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.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available