On the 2-colorability of random hypergraphs

MaRDI QIDQ4440429zbMATH OpenFDO

Authors Cristopher Moore, D. Achlioptas

Publication date 17 December 2003

Full work available at URL https://arxiv.org/abs/2011.04809, http://link.springer.de/link/service/series/0558/bibs/2483/24830078.htm

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)

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.

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

Cited in

(24)

• A note on two-colorability of nonuniform hypergraphs
• Upper-bounding the k-colorability threshold by counting covers
• How many random edges make a dense hypergraph non-2-colorable?
• A sharp threshold for a random constraint satisfaction problem
• Random hypergraphs and property B
• Bounds on threshold probabilities for coloring properties of random hypergraphs
• 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
• On 2-coloring certain k-uniform hypergraphs
• Charting the replica symmetric phase
• Hunting for sharp thresholds
• 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

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)