SYMMETRIC AND ASYMMETRIC RAMSEY PROPERTIES IN RANDOM HYPERGRAPHS

Abstract

A celebrated result of Rödl and Ruciński states that for every graph $F$ , which is not a forest of stars and paths of length 3, and fixed number of colours $r\geqslant 2$ there exist positive constants $c,C$ such that for $p\leqslant cn^{-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\geqslant Cn^{-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ödl 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 threshold exists if $k\geqslant 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öhel who showed a similar result in the graph case. We prove the corresponding 0-statement for hypergraphs satisfying certain balancedness conditions.

Keywords

• 05C80
• 05D10
• 05C65