Multipass greedy coloring of simple uniform hypergraphs

Abstract

Let $m^{\ast }(n)$ be the minimum number of edges in an $n$-uniform simple hypergraph that is not two colorable. We prove that $m^{\ast }(n)=\Omega (4^n/{\ln }^2(n))$. Our result generalizes to $r$-coloring of $b$-simple uniform hypergraphs. For fixed $r$ and $b$ we prove that a maximum vertex degree in $b$-simple $n$-uniform hypergraph that is not $r$-colorable must be $\Omega (r^n/\ln (n))$. By trimming arguments it implies that every such graph has $\Omega ((r^n/\ln (n){)}^{b+1/b})$ edges. For any fixed $r\ge 2$ our techniques yield also a lower bound $\Omega (r^n/\ln (n))$ for van der Waerden numbers $W(n,r)$.