Bounds on piercing and line-piercing numbers in families of convex sets in the plane

DOI10.1016/J.DISC.2023.113787zbMATH Open1530.52003arXiv2303.16240OpenAlexW4388965295MaRDI QIDQ6136671FDOQ6136671

Authors: Shira Zerbib 

Publication date: 17 January 2024

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: A family of sets has the $(p,q)$ property if among any $p$ members of it some $q$ intersect. It is shown that if a finite family of compact convex sets in $R^2$ has the $(p+1,2)$ property then it is pierced by $lfloorfracp2floor+1$ lines. A colorful version of this result is proved as well. As a corollary, the following is proved: Let $F$ be a finite family of compact convex sets in the plane with no isolated sets, and let $F^{\prime }$ be the family of its pairwise intersections. If $F$ has the $(p+1,2)$ property and $F^{\prime }$ has the $(r+1,2)$ property, then $F$ is pierced by $(lfloorfracr2floo{r}^2+lfloorfracr2floor)p$ points when $rge2$, and by $p$ points otherwise. The proofs use the topological KKM theorem.

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

Recommendations

• Bounding the piercing number
• scientific article; zbMATH DE number 1406328
• Piercing convex sets
• Piercing numbers for balanced and unbalanced families
• Piercing families of convex sets in the plane that avoid a certain subfamily with lines

zbMATH Keywords

convex sets in the planepiercing numbers\((p, q)\) property\((p, 2)\) propertyline-piercing numbers

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10)

Cites Work

• Transversals of \(d\)-intervals
• Transversals of 2-intervals, a topological approach
• Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
• Title not available (Why is that?)
• Über eine Variante zum Hellyschen Satz
• Über eine kombinatorisch-geometrische Frage von Hadwiger und Debrunner
• Title not available (Why is that?)
• Equilibrium in a discrete exchange economy with money
• Piercing families of convex sets with the \(d\)-intersection property in \(\mathbb R^{d}\)
• A Gallai-type transversal problem in the plane
• Title not available (Why is that?)
• Bounding the piercing number
• On max-clique for intersection graphs of sets and the Hadwiger-Debrunner numbers
• A family of convex sets in the plane satisfying the (4, 3)-property can be pierced by nine points
• Piercing axis-parallel boxes
• Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
• Line Transversals in Families of Connected Sets in the Plane
• The \((2,2)\) and \((4,3)\) properties in families of Fat sets in the plane

Cited In (1)

• Piercing families of convex sets in the plane that avoid a certain subfamily with lines

This page was built for publication: Bounds on piercing and line-piercing numbers in families of convex sets in the plane

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