On the chromatic number of a random hypergraph

DOI10.1016/J.JCTB.2015.01.002MaRDI QIDQ2347844zbMATH OpenOpenAlexWikidataFDO

Authors Catherine Greenhill, Martin Dyer, Alan Frieze

Publication date 10 June 2015

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numbercolouringhypergraphrandom hypergraphuniform hypergraph

Mathematics Subject Classification ID

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

Abstract: We consider the problem of $k$-colouring a random $r$-uniform hypergraph with $n$ vertices and $cn$ edges, where $k$, $r$, $c$ remain constant as $n$ tends to infinity. Achlioptas and Naor showed that the chromatic number of a random graph in this setting, the case $r=2$, must have one of two easily computable values as $n$ tends to infinity. We give a complete generalisation of this result to random uniform hypergraphs.

Recommendations

• On the chromatic index of random uniform hypergraphs
• On the chromatic numbers of random hypergraphs
• Estimating the r-colorability threshold for a random hypergraph
• Two‐coloring random hypergraphs
• scientific article; zbMATH DE number 1380583

Cites work

• Constrained Critical Points
• scientific article; zbMATH DE number 193053 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1380583 (Why is no real title available?)
• scientific article; zbMATH DE number 1380613 (Why is no real title available?)
• scientific article; zbMATH DE number 3256625 (Why is no real title available?)
• On the number of perfect matchings in random lifts
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Sharp thresholds for constraint satisfaction problems and homomorphisms
• The condensation transition in random hypergraph 2-coloring
• The first cycles in an evolving graph
• Two‐coloring random hypergraphs
• Upper-bounding the k-colorability threshold by counting covers

Cited in

(49)

• Chromatic number of random Kneser hypergraphs
• Panchromatic 3-coloring of a random hypergraph
• Charting the replica symmetric phase
• Chromatic capacities of graphs and hypergraphs
• Choosability in random hypergraphs
• Panchromatic colorings of random hypergraphs
• The satisfiability threshold for random linear equations
• New lower bound for the minimal number of edges of simple uniform hypergraph without the property \(B_k\)
• Model-based clustering for random hypergraphs
• On the strong chromatic number of random hypergraphs
• Estimating the r-colorability threshold for a random hypergraph
• On the strong chromatic number of a random 3-uniform hypergraph
• Isomorphism for random \(k\)-uniform hypergraphs
• On the chromatic numbers of random hypergraphs
• Equitable colorings of hypergraphs with few edges
• On the weak chromatic number of random hypergraphs
• Randomly coloring simple hypergraphs with fewer colors
• Waiter-client and client-waiter colourability and \(k\)-SAT games
• On the number of solutions in random hypergraph 2-colouring
• On the concentration of the chromatic number of a random hypergraph
• Panchromatic 3-colorings of random hypergraphs
• On the \(s\)-colorful number of a random hypergraph
• Estimating the strong r-colorability threshold in random hypergraphs
• On the chromatic number of set systems
• A randomized version of Ramsey's theorem
• An asymptotic upper bound for the chromatic index of random hypergraphs
• Ramsey Properties of Random k-Partite, k-Uniform Hypergraphs
• How many random edges make a dense hypergraph non-2-colorable?
• On the 2-colorability of random hypergraphs
• Two‐coloring random hypergraphs
• Phase transitions in the \(q\)-coloring of random hypergraphs
• scientific article; zbMATH DE number 1380583 (Why is no real title available?)
• scientific article; zbMATH DE number 878895 (Why is no real title available?)
• Randomized algorithms for colourings of hypergraphs
• On the Choice Number of Random Hypergraphs
• The replica symmetric phase of random constraint satisfaction problems
• On two limit values of the chromatic number of a random hypergraph
• Hypergraph coloring up to condensation
• Rigid colorings of hypergraphs and contiguity
• On the chromatic index of random uniform hypergraphs
• On panchromatic colourings of a random hypergraph
• Necessary spectral conditions for coloring hypergraphs
• The two possible values of the chromatic number of a random graph
• On the concentration of values of j-chromatic numbers of random hypergraphs
• Bounds on threshold probabilities for coloring properties of random hypergraphs
• On r-chromatic hypergraphs
• Random Kneser graphs and hypergraphs
• Upper bounds on the 2-colorability threshold of random d-regular k-uniform hypergraphs for k 3
• On the Potts antiferromagnet on random graphs

This page was built for publication: On the chromatic number of a random hypergraph

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