On the chromatic number of a random hypergraph

DOI10.1016/J.JCTB.2015.01.002zbMATH Open1315.05051arXiv1208.0812OpenAlexW2088764637WikidataQ56323772 ScholiaQ56323772MaRDI QIDQ2347844FDOQ2347844

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)

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.

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

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

zbMATH Keywords

chromatic numbercolouringhypergraphuniform hypergraphrandom hypergraph

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The first cycles in an evolving graph
• Title not available (Why is that?)
• Upper-bounding the \(k\)-colorability threshold by counting covers
• On the number of perfect matchings in random lifts
• Title not available (Why is that?)
• Constrained Critical Points
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Title not available (Why is that?)
• The condensation transition in random hypergraph 2-coloring
• Sharp thresholds for constraint satisfaction problems and homomorphisms
• Two‐coloring random hypergraphs

Cited In (44)

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

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)