go-v.orgdoi

The Maximum Piercing Number for some Classes of Convex Sets with the $(4,3)$-property

Jan Kynčl, Martin Tancer · The Electronic Journal of Combinatorics · 2008

  • DOI 10.37236/751
  • Publisher Electronic Journal of Combinatorics
  • Type article
  • Issued 2008

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2008

Abstract

A finite collection ${\cal C}$ of closed convex sets in ${\Bbb R}^d$ is said to have a $(p,q)$-property if among any $p$ members of ${\cal C}$ some $q$ have a non-empty intersection, and $|{\cal C}| \ge p$. A piercing number of ${\cal C}$ is defined as the minimal number $k$ such that there exists a $k$-element set which intersects every member of ${\cal C}$. We focus on the simplest non-trivial case in ${\Bbb R}^2$, i.e., $p=4$ and $q=3$. It is known that the maximum possible piercing number of a finite collection of closed convex sets in the plane with $(4,3)$-property is at least $3$ and at most $13$.

We consider the following three special types of collections of closed convex sets: segments in ${\Bbb R}^d$, unit discs in the plane and positively homothetic triangles in the plane, in each case only those satisfying $(4,3)$-property. We prove that the maximum possible piercing number is $2$ for the collections of segments and $3$ for the collections of the other two types.

Open the resolved locator · 10.37236/751

Metadata licence: OpenAlex metadata (CC0)