  Let $m^*(n)$ be the minimum number of edges in an $n$-uniform simple
hypergraph that is not two colorable. We prove that
$m^*(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 \geq 2$ our
techniques yield also a lower bound $\Omega(r^n/\ln(n))$ for van der Waerden
numbers $W(n,r)$.
