On the 2-colorability of random hypergraphs

zbMATH Open1030.05084arXiv2011.04809MaRDI QIDQ4440429FDOQ4440429

Authors: Cristopher Moore, D. Achlioptas 

Publication date: 17 December 2003

Abstract: A 2-coloring of a hypergraph is a mapping from its vertices to a set of two colors such that no edge is monochromatic. Let $H_k(n,m)$ be a random $k$-uniform hypergraph on $n$ vertices formed by picking $m$ edges uniformly, independently and with replacement. It is easy to show that if $rgeq{r}_c=2^{k-1}ln2-(ln2)/2$, then with high probability $H_k(n,m=rn)$ is not 2-colorable. We complement this observation by proving that if $rleq{r}_c-1$ then with high probability $H_k(n,m=rn)$ is 2-colorable.

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

Recommendations

• Two‐coloring random hypergraphs
• On the chromatic number of a random hypergraph
• Two-colorings of a random hypergraph
• Random hypergraphs and property B
• Estimating the \(r\)-colorability threshold for a random hypergraph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Cited In (24)

• How many random edges make a dense hypergraph non-2-colorable?
• Upper-bounding the \(k\)-colorability threshold by counting covers
• A sharp threshold for a random constraint satisfaction problem
• Bounds on threshold probabilities for coloring properties of random hypergraphs
• Random hypergraphs and property B
• On 2-colorings of hypergraphs
• An average study of hypergraphs and their minimal transversals
• Phase transitions in discrete structures
• Estimating the \(r\)-colorability threshold for a random hypergraph
• Hunting for sharp thresholds
• On 2-coloring certain \(k\)-uniform hypergraphs
• Charting the replica symmetric phase
• Two‐coloring random hypergraphs
• A positive temperature phase transition in random hypergraph 2-coloring
• Colorings of partial Steiner systems and their applications
• On the number of solutions in random hypergraph 2-colouring
• Waiter-client and client-waiter colourability and \(k\)-SAT games
• On the \(s\)-colorful number of a random hypergraph
• 随机图的$f$-染色的分类 II
• Searching for (sharp) thresholds in random structures: where are we now?
• Two-colorings of a random hypergraph
• Deciding hypergraph 2-colourability by H-resolution
• Bicolouring random hypergraphs
• A note on two-colorability of nonuniform hypergraphs

This page was built for publication: On the 2-colorability of random hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4440429)