Symmetric and asymmetric Ramsey properties in random hypergraphs

Abstract: A celebrated result of R"odl and Ruci'nski states that for every graph

F

, which is not a forest of stars and paths of length

3

, and fixed number of colours

r g e 2

there exist positive constants

c, C

such that for

p l e q c n^{- 1 / m_{2} (F)}

the probability that every colouring of the edges of the random graph

G (n, p)

contains a monochromatic copy of

F

is

o (1)

(the "0-statement"), while for

p g e q C n^{- 1 / m_{2} (F)}

it is

1 - o (1)

(the "1-statement"). Here

m_{2} (F)

denotes the

2

-density of

F

. On the other hand, the case where

F

is a forest of stars has a coarse threshold which is determined by the appearance of a certain small subgraph in

G (n, p)

. Recently, the natural extension of the 1-statement of this theorem to

k

-uniform hypergraphs was proved by Conlon and Gowers and, independently, by Friedgut, R"odl and Schacht. In particular, they showed an upper bound of order

n^{- 1 / m_{k} (F)}

for the

1

-statement, where

m_{k} (F)

denotes the

k

-density of

F

. Similarly as in the graph case, it is known that the threshold for star-like hypergraphs is given by the appearance of small subgraphs. In this paper we show that another type of thresholds exists if

k g e 4 :

there are

k

-uniform hypergraphs for which the threshold is determined by the asymmetric Ramsey problem in which a different hypergraph has to be avoided in each colour-class. Along the way we obtain a general bound on the

1

-statement for asymmetric Ramsey properties in random hypergraphs. This extends the work of Kohayakawa and Kreuter, and of Kohayakawa, Schacht and Sp"ohel who showed a similar result in the graph case. We prove the corresponding 0-statement for hypergraphs satisfying certain balancedness conditions.

Recommendations

Cites work

Cited in

(19)

This page was built for publication: Symmetric and asymmetric Ramsey properties in random hypergraphs

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