SYMMETRIC AND ASYMMETRIC RAMSEY PROPERTIES IN RANDOM HYPERGRAPHS
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...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Cambridge University Press
2017-01-01
|
| Series: | Forum of Mathematics, Sigma |
| Subjects: | |
| Online Access: | https://www.cambridge.org/core/product/identifier/S2050509417000226/type/journal_article |
| Summary: | 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. |
|---|---|
| ISSN: | 2050-5094 |