Author
Hancock, R
Staden, K
Treglown, A
Journal title
SIAM Journal on Discrete Mathematics
Last updated
2022-01-31T14:28:29.87+00:00
Abstract
Many important problems in combinatorics and other related areas can be
phrased in the language of independent sets in hypergraphs. Recently Balogh,
Morris and Samotij, and independently Saxton and Thomason developed very
general container theorems for independent sets in hypergraphs; both of which
have seen numerous applications to a wide range of problems. In this paper we
use the container method to give relatively short and elementary proofs of a
number of results concerning Ramsey (and Tur\'an) properties of (hyper)graphs
and the integers. In particular:
(i) We generalise the random Ramsey theorem of R\"odl and Ruci\'nski by
providing a resilience analogue. Our result unifies and generalises several
fundamental results in the area including the random version of Tur\'an's
theorem due to Conlon and Gowers and Schacht.
(ii) The above result also resolves a general subcase of the asymmetric
random Ramsey conjecture of Kohayakawa and Kreuter.
(iii) All of the above results in fact hold for uniform hypergraphs.
(iv) For a (hyper)graph $H$, we determine, up to an error term in the
exponent, the number of $n$-vertex (hyper)graphs $G$ that have the Ramsey
property with respect to $H$ (that is, whenever $G$ is $r$-coloured, there is a
monochromatic copy of $H$ in $G$).
(v) We strengthen the random Rado theorem of Friedgut, R\"odl and Schacht by
proving a resilience version of the result.
(vi) For partition regular matrices $A$ we determine, up to an error term in
the exponent, the number of subsets of $\{1,\dots,n\}$ for which there exists
an $r$-colouring which contains no monochromatic solutions to $Ax=0$.
Along the way a number of open problems are posed.
Symplectic ID
820647
Download URL
http://arxiv.org/abs/1701.04754v4
Publication type
Journal Article
Publication date
15 January 2019
Please contact us with feedback and comments about this page. Created on 06 Sep 2018 - 17:30.