# Theorems about piercing numbers

I'm searching for results relating to piercing numbers. One example of what I'm looking for is this theorem: any VC Class which is k-consistent has a bounded piercing number.

However, searching Google/arxiv only gives me the above theorem and a bunch of papers about convex sets. What are some other results/papers related to piercing numbers? Ideally, they should be combinatorial in nature as opposed to geometric.

Background: I'm asking this because I'm currently doing research on the possible connection between VC Classes and compression schemes.

-
Btw, I currently have to leave for a few hours, so don't worry if your answer isn't immediately accepted - I'll accept/vote up answers when I get back. –  Lopsy Jan 24 '12 at 7:33
What is k-consistent? There is a theorem of and Haussler-Welzl that $\tau\le O(VC(dim) \tau^* \log\tau^*)$, see eg. Matousek's book on Discrete Geometry, 10.2.7. –  domotorp Jan 24 '12 at 7:58
@Lopsy: You might try to sharpen your question... –  Joseph O'Rourke Jan 24 '12 at 12:34

## 2 Answers

One of the most general results is that of Alon and Kalai in their 1995 paper "Bounded the piercing number," solving the 1957 "$(p,q)$ problem" of Hadwiger and Debrunner. The show that, if there is a family of sets $\cal F$ (condition on these sets later) so that any $p$ of them contain a subset of $q$ with a non-empty intersection, $p \ge q$, then there is a set of at most $c$ points that intersects each member of $\cal F$, i.e., $c$ points pierce $\cal F$. The condition on $\cal F$ is that each member is the union of at most $k$ compact, convex sets in $\mathbb{R}^d$. Of course $c$ depends on all the parameters $\lbrace p, q, k, d \rbrace$, but the important point is that $c$ is finite. This is a geometric result, rather than a purely combinatorial one, but it is very broad. Discrete and Computational Geometry, Vol. 13, No. 1, 245-236, 1995.

You might also look at "the Colorful Caratheodory Theorem," described, e.g., at Gil Kalai's blog.

-

The result you are looking for is proved in Matousek's paper "bounded VC-dimension implies a fractional Helly theorem". It is theorem 4 there.

Matousek explains how to adapt Alon and Kleitman's proof of the $(p,q)$-theorem mentioned in Joseph's answer from families of convex sets to families of finite VC-dimension.

-
Here are two links to Matoušek's paper: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.6099 , dl.acm.org/citation.cfm?id=1005789 . –  Joseph O'Rourke Jan 24 '12 at 16:27