A Model-Theoretic Helly's Theorem - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T22:45:10Z http://mathoverflow.net/feeds/question/80177 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/80177/a-model-theoretic-hellys-theorem A Model-Theoretic Helly's Theorem Richard Rast 2011-11-06T00:30:11Z 2011-11-27T19:23:38Z <p>There is a combinatorial question posed to me (or rather, posed near me) by my adviser. I am having quite a lot of difficulty proving it. It goes:</p> <blockquote> <p>For any NIP theory $T$ (complete with infinite models as usual) and any partitioned formula $\phi(x; y)$, there are natural numbers $k$ and $N$ such that for any finite sets $A$ and $B$, if $A$ is $k$-consistent in $B$, then there is a $B_0\subset B$ with $|B_0|=N$ and so that for any $a\in A$, there is $b\in B_0$ such that $\phi(a;b)$ holds.</p> </blockquote> <p>Here, by $k$-consistent, we mean for any $a_1, \ldots, a_n\in A$ there is $b\in B$ such that $\bigwedge_{i=1}^n \phi(a_i,b)$ holds. Also, while it isn't stated, we can take $A$ and $B$ to be sets of tuples; I don't think this affects much of anything.</p> <p>This is used in a proof that NIP theories have UDTFS, in an unpublished paper by Pierre Simon and Artem Chernikov. They claim this lemma has been proved "in the literature;" neither I nor my adviser has been able to verify this, except for a very long-winded probabilistic argument which feels non-illustrative.</p> <p>So, what I'm hoping for is either a reference to where it has been proved (or even discussed), some direction on the literature hunt, or just an explanation of why it may or may not be true (or a counterexample, if it is false). Just anything, really.</p> <p>Note: this fails immediately in the unstable NIP case (take $A=B$ to be an $\omega$-sequence, ordered by $\phi$, so the sets $\phi(a_i,B)$ are strictly decreasing, infinite, with empty intersection).</p> http://mathoverflow.net/questions/80177/a-model-theoretic-hellys-theorem/81845#81845 Answer by Hunter Johnson for A Model-Theoretic Helly's Theorem Hunter Johnson 2011-11-25T03:56:53Z 2011-11-25T16:43:08Z <p>I believe this can be translated into a question about fractional Helly number, which is answered in a paper of Matousek. </p> <p>The citation is: Bounded VC-Dimension Implies a Fractional Helly Theorem, Discrete &amp; Computational Geometry, Volume 31, Number 2. </p> <p>A pdf can be found by googling "the (p,k) property, VC dimension"</p> <p>For a set $X$, any $\mathcal{F} \subseteq \mathcal{P}(X)$ is a <em>set system</em> on $X$.</p> <p>Theorem 4 of the paper states:</p> <blockquote> <p>Let $\mathcal{F}$ be a set system with $\pi_{\mathcal{F}}^*(m) = o(m^k)$ for some integer $k$, and let $p \geq k$. Then there is a constant $N$ such that the following holds for every finite $\mathcal{G} \subseteq \mathcal{F}$: If $\mathcal{G}$ has the $(p,k)$ property then $\tau(\mathcal{G}) \leq N$</p> </blockquote> <p>The terminology in the theorem can be found online, but I will list some definitions here.</p> <p>The symbol $\pi_{\mathcal{F}}^*(m)$ refers to the dual-shatter function of $\mathcal{F}$. </p> <p>A sufficient condition for the assumption $\pi_{\mathcal{F}}^*(m) = o(m^k)$ is simply that the independence dimension of $\mathcal{F}$ is at most $k-1$. If you are unfamiliar with the dual-shatter function, more can be found in this paper: <a href="http://arxiv.org/abs/1109.5438" rel="nofollow">http://arxiv.org/abs/1109.5438</a>.</p> <p>We say that $\mathcal{F}$ has the $(p,k)$-<em>property</em> if among any $p$ elements of $\mathcal{F}$, some $k$ have non-empty intersection. </p> <p>The <em>transversal number</em> of $\mathcal{F}$, denoted $\tau(\mathcal{F})$, is the least integer $N$ such that there is a subset $X_0 \subseteq X$ with $|X_0|=N$, and $F \cap X_0 \neq \emptyset$ for every $F \in \mathcal{F}$.</p> <p>I will try to translate your question as follows. We make the assumption that there is some theory $T$ and monster $M \models T$ with respect to which formulas are evaluated.</p> <p>Let $\varphi(x,y)$ be the given formula. As you remark, if $x$ and $y$ are tuples, rather than arity 1, it makes no difference. For sets $A$ and $B$, let $S_\phi(B)^A$ denote the set family</p> <p>$$\lbrace \varphi(a;B): a \in A \rbrace$$</p> <p>Take $\mathcal{F} = S_\phi(M)^M$. Since $T$ is NIP (note we need only $\varphi$ NIP), $\mathcal{F}$ has finite independence dimension, say $d$. </p> <p>The $k$ that suffices for your claim is $d+1$. The $N$ that suffices is given by applying Theorem 4 with $p=k=d+1$.</p> <p>I will argue for the correctness of this statement. If finite sets $A$ and $B$ are given, your hypothesis allows us to assume that $\mathcal{G} = S_\varphi(B)^A$ has the $(k,k)$ property. </p> <p>I now need to make an assumption which I cannot really justify, which is that although $\mathcal{G} \subseteq \mathcal{F}\vert_B$ rather than $\mathcal{G} \subseteq \mathcal{F}$, this makes no difference.</p> <p>Given this assumption, Theorem 4 now gives a $B_0 \subseteq B$ of cardinality $N$ which pierces $\mathcal{G}$. Translating this back to model theory, it is easy to see that $B_0$ is the set sought after.</p> http://mathoverflow.net/questions/80177/a-model-theoretic-hellys-theorem/81941#81941 Answer by Pierre Simon for A Model-Theoretic Helly's Theorem Pierre Simon 2011-11-26T09:03:39Z 2011-11-26T09:03:39Z <p>First, let me point out that the proof of udtfs is joint work with Artem Chernikov.</p> <p>Hunter Johnson's answer is correct. The reference is Matousek's paper. I don't know of any proof not using probabilty theory. I tried a little bit to look for a model theoretic proof, but did not find any.</p> <p>However, Matousek's $(p,k)$-theorem gives us more than we need, and the proof can be made much shorter as:</p> <ul> <li><p>we are only interested in the case $p=k$ of the $(p,k)$-theorem,</p></li> <li><p>we do not need an optimal value of $k$.</p></li> </ul> <p>I will sketch the argument:</p> <p>Let $\phi(x,y)$, $A$ and $B$ as in your question.</p> <p>Pick any $\epsilon>0$.</p> <p>Use the VC-theorem to get $N$ such that for any probability measure on $A$, there is an $\epsilon$-net of size $N$ (namely, a subset $A_0$ of size $N$ such that for any $b$ the measure of $\phi(A,b)$ is within $\epsilon$ of $\frac {|\phi(A_0,b)|}{N}$.)</p> <p>Assume that $A$ is $N$-consistent in $B$ (using your terminolgy). It follows that for any probability measure on $A$, there is $b$ such that $\phi(A,b)$ has measure at least $1-\epsilon$.</p> <p>Next, apply Farkas' lemma exactly as in the paper by Alon and Kleitman to which Matousek refers (there are some unnecessary intermediate steps there). You obtain a measure on $B$ such that every subset $\phi(a,B)$ has large measure. Then apply the VC-theorem again to extract an $\epsilon$-net $B_0 \subseteq B$ of bounded size (for some, possibly smaller $\epsilon$). Then every $\phi(a,B)$ intersects $B_0$, so we have what we want.</p> <p>Compared with Matousek's proof, we can avoid the fractional Helly property and Lemma 2.2 in Alon and Kleitman.</p>