Discrete Helly-type theorems for pseudohalfplanes

DOI10.1016/J.EJC.2021.103469zbMATH Open1480.05101arXiv2103.11142OpenAlexW4206085184WikidataQ113875495 ScholiaQ113875495MaRDI QIDQ2066005FDOQ2066005

Authors: Balázs Keszegh 

Publication date: 13 January 2022

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Convexity in cristallographical lattices
• Title not available (Why is that?)
• Polychromatic coloring for half-planes
• Coloring half-planes and bottomless rectangles
• Discrete and lexicographic Helly-type theorems
• Coloring intersection hypergraphs of pseudo-disks
• An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes
• Coloring hypergraphs defined by stabbed pseudo-disks and ABAB-free hypergraphs

Cited In (1)

• Helly-type results on support lines for disjoint families of unit disks

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)