Projects per year
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 [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
Read More: https://epubs.siam.org/doi/abs/10.1137/18M119642X?af=R
Original language | English |
---|---|
Pages (from-to) | 153-188 |
Number of pages | 36 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 33 |
Issue number | 1 |
DOIs | |
Publication status | Published - 15 Jan 2019 |
Keywords
- Container method
- Ramsey theory
- Random graphs
- Random sets of integers
ASJC Scopus subject areas
- General Mathematics
Fingerprint
Dive into the research topics of 'Independent sets in hypergraphs and Ramsey properties of graphs and the integers'. Together they form a unique fingerprint.Projects
- 1 Finished
-
EPSRC Fellowship: Dr Andrew Treglown - Independence in groups, graphs and the integers
Treglown, A. (Principal Investigator)
Engineering & Physical Science Research Council
1/06/15 → 31/05/18
Project: Research Councils