How many random edges make a dense hypergraph non-2-colorable?

DOI10.1002/rsa.25155zbMath1149.05038arXiv0707.0315OpenAlexW2950781851MaRDI QIDQ3503605

Jan Vondrák, Benjamin Sudakov

Publication date: 5 June 2008

Published in: Random Structures and Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0707.0315

zbMATH Keywords

random hypergraphssmoothed analysis2-colorability

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15)

Related Items (5)

Large Rainbow Cliques in Randomly Perturbed Dense Graphs ⋮ Smoothed Analysis on Connected Graphs ⋮ Small rainbow cliques in randomly perturbed dense graphs ⋮ The Effect of Adding Randomly Weighted Edges ⋮ Monochromatic Schur Triples in Randomly Perturbed Dense Sets of Integers

Cites Work

• Smoothed analysis of algorithms

This page was built for publication: How many random edges make a dense hypergraph non-2-colorable?