Theorems about piercing numbers - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T12:20:43Z http://mathoverflow.net/feeds/question/86513 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/86513/theorems-about-piercing-numbers Theorems about piercing numbers Lopsy 2012-01-24T07:30:01Z 2012-01-24T16:03:33Z <p>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.</p> <p>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.</p> <p>Background: I'm asking this because I'm currently doing research on the possible connection between VC Classes and compression schemes.</p> http://mathoverflow.net/questions/86513/theorems-about-piercing-numbers/86525#86525 Answer by Joseph O'Rourke for Theorems about piercing numbers Joseph O'Rourke 2012-01-24T11:52:11Z 2012-01-24T13:16:26Z <p>One of the most general results is that of Alon and Kalai in their 1995 paper "<em>Bounded the piercing number</em>," solving the 1957 "$(p,q)$ problem" of Hadwiger and Debrunner. The show that, <em>if</em> 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$, <em>then</em> 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. <a href="http://www.springerlink.com/content/a31460001208k7j3/" rel="nofollow"><em>Discrete and Computational Geometry</em>, Vol. 13, No. 1, 245-236, 1995</a>.</p> <p>You might also look at "the Colorful Caratheodory Theorem," described, e.g., at <a href="http://gilkalai.wordpress.com/2009/03/15/colorful-caratheodory-revisited/" rel="nofollow">Gil Kalai's blog</a>.</p> http://mathoverflow.net/questions/86513/theorems-about-piercing-numbers/86541#86541 Answer by Pierre Simon for Theorems about piercing numbers Pierre Simon 2012-01-24T16:03:33Z 2012-01-24T16:03:33Z <p>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.</p> <p>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.</p>