The geometry and combinatorics of discrete line segment hypergraphs

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 chi(H) and covering number tau (H) of hypergraphs in this family, uncovering several interesting geometric properties in the process. We conjecture that for r >= 3, the covering number tau (H) is at most (r - 1)nu(H), where nu(H) denotes the matching number of H. We prove our conjecture in the case where nu(H) = 1, and provide improved (in fact, optimal) bounds on t (H) for r <= 5. We also provide sharp bounds on the chromatic number chi(H) in terms of r, and use them to prove two fractional versions of our conjecture. (C) 2020 Elsevier B.V. All rights reserved.