Coloring Uniform Hypergraphs with Few Colors

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Pages (from-to)1-10
Number of pages10
JournalRandom Structures and Algorithms
Issue number1
StatePublished - Jan 2004

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


Dive into the research topics of 'Coloring Uniform Hypergraphs with Few Colors'. Together they form a unique fingerprint.

Cite this