• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Working paper

Regular behaviour of the maximal hypergraph chromatic number

Cherkashin D., Petrov F.
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.