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

m a t h b b R^{2}

. In this paper, we bound the chromatic number

c h i (H)

and covering number

a u (H)

of hypergraphs in this family, uncovering several interesting geometric properties in the process. We conjecture that for

r g e 3

, the covering number

a u (H)

is at most

(r - 1) u (H)

, where

u (H)

denotes the matching number of

H

. We prove our conjecture in the case where

u (H) = 1

, and provide improved (in fact, optimal) bounds on

a u (H)

for

r l e 5

. We also provide sharp bounds on the chromatic number

c h i (H)

in terms of

r

, and use them to prove two fractional versions of our conjecture.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: The geometry and combinatorics of discrete line segment hypergraphs