Let m(r, k) denote the minimum number of edges in an r-uniform hypergraph that is not k-colorable. We give a new lower bound on m(r, k) for fixed k and large r. Namely, we prove that if k ≥ 2 n, then m(r, k) ≥ ε(k)k r (r/ln r) n/(n+1).
ASJC Scopus subject areas
- Computer Graphics and Computer-Aided Design
- Applied Mathematics