Off-diagonal hypergraph Ramsey numbers

Abstract: The Ramsey number

r_{k} (s, n)

is the minimum

N

such that every red-blue coloring of the

k

-subsets of

1, l d o t s, N

contains a red set of size

s

or a blue set of size

n

, where a set is red (blue) if all of its

k

-subsets are red (blue). A

k

-uniform emph{tight path} of size

s

, denoted by

P_{s}

, is a set of

s

vertices

v_{1} < c d o t s < v_{s}

in

m a t h b b Z

, and all

s - k + 1

edges of the form

v_{j}, v_{j + 1}, l d o t s, v_{j + k - 1}

. Let

r_{k} (P_{s}, n)

be the minimum

N

such that every red-blue coloring of the

k

-subsets of

1, l d o t s, N

results in a red

P_{s}

or a blue set of size

n

. The problem of estimating both

r_{k} (s, n)

and

r_{k} (P_{s}, n)

for

k = 2

goes back to the seminal work of Erdos and Szekeres from 1935, while the case

k g e 3

was first investigated by Erdos and Rado in 1952. In this paper, we deduce a quantitative relationship between multicolor variants of

r_{k} (P_{s}, n)

and

r_{k} (n, n)

. This yields several consequences including the following: (1) We determine the correct tower growth rate for both

r_{k} (s, n)

and

r_{k} (P_{s}, n)

for

s g e k + 3

. The question of determining the tower growth rate of

r_{k} (s, n)

for all

s g e k + 1

was posed by Erdos and Hajnal in 1972. (2) We show that determining the tower growth rate of

r_{k} (P_{k + 1}, n)

is equivalent to determining the tower growth rate of

r_{k} (n, n)

, which is a notorious conjecture of Erdos, Hajnal and Rado from 1965 that remains open. Some related off-diagonal hypergraph Ramsey problems are also explored.

Recommendations

Cites work

Cited in

(19)

This page was built for publication: Off-diagonal hypergraph Ramsey numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2396897)