pith. sign in

arxiv: 1208.0812 · v4 · pith:CSQGMNPFnew · submitted 2012-08-03 · 💻 cs.DM · math.CO

On the chromatic number of a random hypergraph

classification 💻 cs.DM math.CO
keywords randomchromatichypergraphinfinitynumbertendsuniformachlioptas
0
0 comments X
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.