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, Tome 15 (2008)

Résumé

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.

Détail

DOI : 10.37236/751

Classification : 52A35