MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 5 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer
Here are two links to Matoušek's paper: , . – Joseph O'Rourke Jan 24 '12 at 16:27

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.