The independent neighborhoods process

2014/07/27 by Tom Bohman, Bohman, Tom, Dhruv Mubayi +3
Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods

paper · pdf · doi:10.48550/arxiv.1407.7192

openalex publication_date 2014/07/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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_s^(r)) has order of magnitude s^r/log s. This answers questions posed in~\citeBFM, KMV and generalizes the celebrated results of Ajtai-Komlós-Szemerédi~\citeAKS and Kim~\citeK to hypergraphs.

Related

• A note on the random greedy independent set algorithm
• On independent sets in hypergraphs
• On the random greedy F-free hypergraph process
• Independent sets in hypergraphs omitting an intersection
• Dynamic concentration of the triangle-free process