On the chromatic number of a random hypergraph
classification
💻 cs.DM
math.CO
keywords
randomchromatichypergraphinfinitynumbertendsuniformachlioptas
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.