Discrete Helly-type theorems for pseudohalfplanes

DOI10.1016/J.EJC.2021.103469MaRDI QIDQ2066005zbMATH OpenOpenAlexWikidataFDO

Authors Balázs Keszegh

Publication date 13 January 2022

Published in European Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2103.11142

zbMATH Keywords

geometric hypergraphspseudohalfplane hypergraphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Hypergraphs (05C65) Helly-type theorems and geometric transversal theory (52A35)

Abstract: We prove discrete Helly-type theorems for pseudohalfplanes, which extend recent results of Jensen, Joshi and Ray about halfplanes. Among others we show that given a family of pseudohalfplanes $calH$ and a set of points $P$, if every triple of pseudohalfplanes has a common point in $P$ then there exists a set of at most two points that hits every pseudohalfplane of $calH$. We also prove that if every triple of points of $P$ is contained in a pseudohalfplane of $calH$ then there are two pseudohalfplanes of $calH$ that cover all points of $P$. To prove our results we regard pseudohalfplane hypergraphs, define their extremal vertices and show that these behave in many ways as points on the boundary of the convex hull of a set of points. Our methods are purely combinatorial. In addition we determine the maximal possible chromatic number of the regarded hypergraph families.

Recommendations

• Discrete and lexicographic Helly-type theorems
• Transversal numbers for hypergraphs arising in geometry
• scientific article; zbMATH DE number 4096266
• Bounding the piercing number
• Polychromatic coloring for half-planes

Cites work

• scientific article; zbMATH DE number 6776481 (Why is no real title available?)
• scientific article; zbMATH DE number 2209723 (Why is no real title available?)
• An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes
• Coloring half-planes and bottomless rectangles
• Coloring hypergraphs defined by stabbed pseudo-disks and ABAB-free hypergraphs
• Coloring intersection hypergraphs of pseudo-disks
• Convexity in cristallographical lattices
• Discrete and lexicographic Helly-type theorems
• Polychromatic coloring for half-planes

Cited in

(2)

• Helly-type results on support lines for disjoint families of unit disks
• A new discrete theory of pseudoconvexity

This page was built for publication: Discrete Helly-type theorems for pseudohalfplanes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2066005)