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 Turan) properties of (hyper) graphs and the integers. In particular we do the following: (a) We generalize the random Ramsey theorem of Rodl and Rucinski [Combinatorics, Paul ErdH os Is Eighty, Vol. 1, Bolyai Soc. Math. Stud., Janos 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 Turan'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, Rodl, 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,..., 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.