The geometry and combinatorics of discrete line segment hypergraphs
Por:
Oliveros, Deborah, O'Neill, Christopher, Zerbib, Shira
Publicada:
1 ene 2020
Resumen:
An r-segment hypergraph H is a hypergraph whose edges consist of r consecutive integer points on line segments in R2. In this paper, we bound the chromatic number ?(H) and covering number t(H) of hypergraphs in this family, uncovering several interesting geometric properties in the process. We conjecture that for r=3, the covering number t(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 t(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. © 2020 Elsevier B.V.
Filiaciones:
Oliveros, Deborah:
Instituto de Matemáticas, Universidad Nacional Autónoma de México, Mexico
Univ Nacl Autonoma Mexico, Inst Matemat, Mexico City, DF, Mexico
O'Neill, Christopher:
Mathematics Department, San Diego State University, San Diego, CA 92182, United States
San Diego State Univ, Math Dept, San Diego, CA 92182 USA
Zerbib, Shira:
Department of Mathematics, Iowa State University, Ames, Iowa 50011, United States
Iowa State Univ, Dept Math, Ames, IA 50011 USA
|