Multipass greedy coloring of simple uniform hypergraphs

الأصل · EN

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)=Ω(4ⁿ/²(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 Ω(rⁿ /(n)). By trimming arguments it implies that every such graph has Ω((rⁿ /(n))ᵇ⁺¹/ᵇ) edges. For any fixed r ≥ 2 our techniques yield also a lower bound Ω(rⁿ/(n)) for van der Waerden numbers W(n,r).