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).
|Original language||English (US)|
|Number of pages||10|
|Journal||Random Structures and Algorithms|
|State||Published - Jan 2004|
ASJC Scopus subject areas
- Computer Graphics and Computer-Aided Design
- Applied Mathematics