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

Abstract: 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

i l d e 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

i l d e R_{t} (P_{r}^{(k)})

. Letting

m = r - k + 1

(the number of edges in

P_{r}^{(k)}

), we prove

m^{t - 1} / (3 s q r t t) l e i l d e R_{t} (P_{r}^{(2)}) l e t m^{t + 1}

. For general

k

, a trivial upper bound is

R c h o o s e 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 l g R) l e i l d e R_{t} (P_{r}^{(k)}) l e R (l g R)^{2 + e p s i l o n}

, where

e p s i l o n

is any positive constant and

t (m - 1)

is sufficiently large. Our upper bounds improve prior results when

t

grows faster than

m / l o g m

. We also generalize our results to

e l l

-loose monotone paths, where each successive edge begins

e l l

vertices after the previous edge.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: On-line size Ramsey number for monotone \(k\)-uniform ordered paths with uniform looseness