The geometry and combinatorics of discrete line segment hypergraphs

Abstract An r -segment hypergraph H is a hypergraph whose edges consist of r  consecutive integer points on line segments in R 2 . In this paper, we bound the chromatic number χ ( H ) and covering number τ ( H ) of hypergraphs in this family, uncovering several interesting geometric properties in the process. We conjecture that for r ≥ 3 , the covering number τ ( H ) is at most ( r − 1 ) ν ( H ) , where ν ( H ) denotes the matching number of H . We prove our conjecture in the case where ν ( H ) = 1 , and provide improved (in fact, optimal) bounds on τ ( H ) for r ≤ 5 . We also provide sharp bounds on the chromatic number χ ( H ) in terms of r , and use them to prove two fractional versions of our conjecture.