A combinatorial dichotomy

I have just read about the following very nice dichotomy: suppose we have an infinite set X, and a collection of subsets C in X; suppose further we look at all subsets F of X of finite size n, and at the subsets of F which can be defined by intersection of F with an element of C. How rich can this collection of subsets of F be, as F varies over all subsets of fixed (but growing) size?

For example, X could be the real line, and C the collection of half-lines ]-∞,a]. Then if we enumerate the finite subset F in increasing order

x_1\lt x_2 \lt \ldots \lt x_n

the subsets we obtain by intersecting with C are rather special: apart from the emptyset, we have only the n subsets of elements in increasing order up to some a:

x_1\lt x_2 \lt \ldots \lt x_r \le a

with r≤n. In particular, there are only n+1 subsets of F which can be obtained in this manner, much less than the 2n subsets of F.

As a second example, if C is the collection of all open subsets of the real line, we can clearly obtain all subsets of F as intersection of an element of C and F.

The dichotomy in question is that, in fact, those two examples are typical in the following sense: either one can, for all n, find an n element set F and recover all its subsets as intersection with C (as in the second example); or for any n and any F in X of size n, the number of subsets obtained from F by intersecting with C is bounded by a polynomial function of n. So it is not possible to have intermediate behavior (subexponential growth which is not polynomial), and this is certainly surprising at first (at least for me).

This very nice fact is due to Vapnik-Chernovenkis and Shelah, independently (published in 1969 and 1971, respectively). What is quite remarkable is that the first authors were interested in basic probability theory (they found conditions for the “empirical” probability of an event in the standard Bernoulli model to converge uniformly to the mathematical probability over a collection of events, generalizing the weak law of large numbers), while Shelah was dealing with model-theoretic properties of various first-order theories (in particular, stability).

In fact, these references are given by L. van den Dries (Notes to Chapter 5 of “Tame topology and O-minimal structures”, which is where I’ve read about this, and which is available in the Google preview), but whereas it’s easy to find the result in the paper of Vapnik-Chernovenkis, I would be hard put to give a precise location in Shelah’s paper where he actually states this dichotomy! This is a striking illustratation both of the unity and divergence of mathematics…

The proof of the dichotomy, as one can maybe expect (given the information that it is true), is clever but fairly simple, and gives rather more precise information than what I stated. Let’s say that C is a rich uncle of a finite set F if any subset of F is the intersection of F with a subset in C. We must show that either C is a rich uncle for at least one finite subset of every order, or else C only represents relatively few subsets of any finite subset.

First, a lemma states that:

Given a finite set of size n and a collection D of subsets of F, which contains (strictly) more subsets than there are subsets of F of size up to (but strictly less than) some d, one can always find in F a subset E of size d such that D is a rich uncle of E.

Note that this is best possible, because if we take D to be those substes F of size up to (and excluding) d, it certainly can not be a rich uncle of a set of size d.

If we grant this lemma, the proof of the dichotomy proceeds as follows: assume we are not in the first case, so for some d, C is a rich uncle for no subset of order d. Let n>d be given (to get polynomial behavior, we can restrict to this case), and let F be a subset of order n. The lemma (applied with D the intersections of C with F), and the definition of d, imply by contraposition that the number of subsets of F which are obtained by intersection from C is less than the number of subsets of a set of order n which are of order d at most. But this is a polynomial function of n, of degre d.

As for the lemma, I leave the proof as an exercise (see page 80 in the book of van den Dries, which is also in the preview), with a hint: proceed by induction on n. (One is tempted, in view of the statement, to use the pigeon-hole principle to say that D must contain one subset at least of order d, but the proof by induction doesn’t use that).

Now I am going to try and think if I can find some other application of this fact…

Published by

Kowalski

I am a professor of mathematics at ETH Zürich since 2008.

2 thoughts on “A combinatorial dichotomy”

Comments are closed.