3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Lopsy
    Jan 24, 2012 at 7:33
  • $\begingroup$ 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. $\endgroup$
    – domotorp
    Jan 24, 2012 at 7:58
  • $\begingroup$ @Lopsy: You might try to sharpen your question... $\endgroup$ Jan 24, 2012 at 12:34

2 Answers 2

5
$\begingroup$

One of the most general results is that of Alon and Kalai in their 1995 paper "Bounding 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. 3–4, 245–256, 1995.

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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