Monochromatic loose paths in multicolored $k$-uniform cliques

Publication date: 13 January 2020

Abstract: For integers

k g e 2

and

e l l g e 0

, a

k

-uniform hypergraph is called a loose path of length

e l l

, and denoted by

P_{e} l l^{(k)}

, if it consists of

e l l

edges

e_{1}, d o t s, e_{e} l l

such that

| e_{i} c a p e_{j} | = 1

if

| i - j | = 1

and

e_{i} c a p e_{j} = e m p t y s e t

if

| i - j | g e 2

. In other words, each pair of consecutive edges intersects on a single vertex, while all other pairs are disjoint. Let

R (P_{e} l l^{(k)}; r)

be the minimum integer

n

such that every

r

-edge-coloring of the complete

k

-uniform hypergraph

K_{n}^{(k)}

yields a monochromatic copy of

P_{e} l l^{(k)}

. In this paper we are mostly interested in constructive upper bounds on

R (P_{e} l l^{(k)}; r)

, meaning that on the cost of possibly enlarging the order of the complete hypergraph, we would like to efficiently find a monochromatic copy of

P_{e} l l^{(k)}

in every coloring. In particular, we show that there is a constant

c > 0

such that for all

k g e 2

,

e l l g e 3

,

2 l e r l e k - 1

, and

n g e k (e l l + 1) r (1 + l n (r))

, there is an algorithm such that for every

r

-edge-coloring of the edges of

K_{n}^{(k)}

, it finds a monochromatic copy of

P_{e} l l^{(k)}

in time at most

c n^{k}

. We also prove a non-constructive upper bound

R (P_{e} l l^{(k)}; r) l e (k - 1) e l l r

.