Regular behaviour of the maximal hypergraph chromatic number

Abstract

Let $m(n,r)$ denote the minimal number of edges in an $n$-uniform hypergraph which is not $r$-colorable. It is known that for a fixed $n$ one has \[ c_n r^n < m(n,r) < C_n r^n. \] We prove that for any fixed $n$ the sequence $a_r:=m(n,r)/r^n$ has a limit, which was conjectured by Alon. We also prove the list colorings analogue of this statement.

arXiv admin note: text overlap with arXiv:1905.02893

Cited by in corpus (1)

• On the Erd{\H o}s--Hajnal problem in the case of 3-graphs