Multipass greedy coloring of simple uniform hypergraphs

2013/10/22 by Kozik, Jakub
#05C15 #05C65 #05D40 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #G.2.2 #G.3

paper · doi:10.48550/arxiv.1310.5984

Abstract

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

Related

• Improved algorithms for colorings of simple hypergraphs and applications
• A note on random greedy coloring of uniform hypergraphs
• Coloring Simple Hypergraphs
• On some generalizations of the property B-problem of an n-uniform hypergraph
• Improved Lower Bounds for Property B