Abstract
A triangle T (r) in an r-uniform hypergraph is a set of r+1 edges such that r of them share a common (r-1)-set of vertices and the last edge contains the remaining vertex from each of the first r edges. Our main result is that the random greedy triangle-free process on n points terminates in an r-uniform hypergraph with independence number O((n log n)1/r). As a consequence, using recent results on independent sets in hypergraphs, the Ramsey number r(T (r),K (r) s ) has order of magnitude s r/ log s. This answers questions posed in [4, 10] and generalizes the celebrated results of Ajtai–Komlós–Szemerédi [1] and Kim [9] to hypergraphs.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Ajtai, J. Komlós and E. Szemerédi, A note on Ramsey numbers, Journal of Combinatorial Theory. Series A 29 (1980), 354–360.
P.Bennett and T.Bohman, A note on the random greedy independent set algorithm, submitted, http://arxiv.org/abs/1308.3732.
T. Bohman, The triangle-free process, Advances in Mathematics 221 (2009), 1653–1677.
T. Bohman, A. Frieze and D. Mubayi, Coloring H-free hypergraphs, Random Structures & Algorithms 36 (2010), 11–25.
T. Bohman and P. Keevash, The early evolution of the H-free process, Inventiones Mathematicae 181 (2010), 291–336.
T.Bohman and P.Keevash, Dynamic concentration of the triangle-free process, submitted, http://arxiv.org/abs/1302.5963.
J.Cooper and D.Mubayi, Coloring sparse hypergraphs, SIAM Journal on Discrete Mathematics, accepted, http://arxiv.org/abs/1404.2895.
G.Fiz Pontiveros, S.Griffiths and R.Morris, The triangle-free process and R(3, k), submitted, http://arxiv.org/abs/1302.6279.
J. H. Kim, The Ramsey number R(3, t) has order of magnitude t2/log t, Random Structures & Algorithms 7 (1995), 173–207.
A. Kostochka, D. Mubayi and J. Versträete, On independent sets in hypergraphs, Random Structures & Algorithms 44 (2014), 224–239.
K. T. Phelps and V. Rödl, Steiner triple systems with minimum independence number, Ars Combinatoria 21 (1986), 167–172
J. B. Shearer, A note on the independence number of triangle-free graphs, Discrete Mathematics 46 (1983), 83–87.
J. B. Shearer, A note on the independence number of triangle-free graphs II, Journal of Combinatorial Theory. Series B 2 (1991), 300–307.
N. Wormald, The differential equation method for random graph processes and greedy algorithms, in Lectures on Approximation and Randomized Algorithms, Proceedings of the Berlin–Poznán Summer School, Polish Scientific Publishers PWN, Warsaw, 1999, pp. 73–155.
Author information
Authors and Affiliations
Corresponding author
Additional information
Research supported by NSF grant DMS-1100215.
Research supported by NSF grant DMS-1300138.
Rights and permissions
About this article
Cite this article
Bohman, T., Mubayi, D. & Picollelli, M. The independent neighborhoods process. Isr. J. Math. 214, 333–357 (2016). https://doi.org/10.1007/s11856-016-1331-8
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11856-016-1331-8