Independent sets in hypergraphs and Ramsey properties of graphs and the integers

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 [J. Amer. Math. Soc., 28 (2015), pp. 669--709], and independently Saxton and Thomason [Invent. Math., 201 (2015), pp. 925--992], 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án) properties of (hyper)graphs and the integers. In particular we do the following: (a) We generalize the random Ramsey theorem of Rödl and Ruciński [Combinatorics, Paul Erdös Is Eighty, Vol. 1, Bolyai Soc. Math. Stud., János Bolyai Mathematical Society, Budapest, 1993, pp. 317--346; Random Structures Algorithms, 5 (1994), pp. 253--270; J. Amer. Math. Soc., 8 (1995), pp. 917--942] by providing a resilience analogue. Our result unifies and generalizes several fundamental results in the area including the random version of Turán's theorem due to Conlon and Gowers [Ann. of Math., 184 (2016), pp. 367--454] and Schacht [Ann. of Math., 184 (2016), pp. 331--363]. (b) The above result also resolves a general subcase of the asymmetric random Ramsey conjecture of Kohayakawa and Kreuter [Random Structures Algorithms, 11 (1997), pp. 245--276]. (c) All of the above results in fact hold for uniform hypergraphs. (d) 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$-colored, there is a monochromatic copy of $H$ in $G$). (e) We strengthen the random Rado theorem of Friedgut, Rödl, and Schacht [Random Structures Algorithms, 37 (2010), pp. 407--436] by proving a resilience version of the result. (f) 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$-coloring which contains no monochromatic solutions to $Ax=0$. Along the way a number of open problems are posed.


Read More: https://epubs.siam.org/doi/abs/10.1137/18M119642X?af=R