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

Simple item page
dc.creatorSudakov, Benny
dc.creatorVondrak, Jan
dc.date2007-07-02
dc.date.accessioned2026-07-07T08:13:42Z
dc.date.available2026-07-07T08:13:42Z
dc.descriptionWe study a model of random uniform hypergraphs, where a random instance is obtained by adding random edges to a large hypergraph of a given density. We obtain a tight bound on the number of random edges required to ensure non-2-colorability. We prove that for any k-uniform hypergraph with Omega(n^{k-epsilon}) edges, adding omega(n^{k epsilon/2}) random edges makes the hypergraph almost surely non-2-colorable. This is essentially tight, since there is a 2-colorable hypergraph with Omega(n^{k-ε}) edges which almost surely remains 2-colorable even after adding o(n^{k ε/ 2}) random edges.
dc.identifierhttps://arxiv.org/abs/0707.0315
dc.identifierhttp://arxiv.org/abs/0707.0315
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/132863
dc.subjectCombinatorics
dc.subject05D40
dc.titleHow many random edges make a dense hypergraph non-2-colorable?
dc.typetext

Files

Collections

arXiv