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

Say a collection of sets $\mathcal{F}$ satisfies the (p,q) property if whenever $\mathcal{G}\subseteq\mathcal{F}$ with $|\mathcal{G}|\geq p$, there is a $\mathcal{H}\subseteq\mathcal{G}$ with $|\mathcal{H}|\geq q$ and $\bigcap\mathcal{H}\neq\emptyset$. A (p,q) theorem for some class of sets $\mathcal{C}$ gives a bound $T_{p,q}$ so that whenever $\mathcal{F}\subseteq\mathcal{C}$ has the (p,q) property, there is a set $S$ such that $|S|\leq T_{p,q}$ and whenever $F\in\mathcal{F}$, $F\cap S\neq\emptyset$.

The main classes I know of for which a (p,q) theorem has been proven are the convex sets in $\mathbb{R}^d$ and the sets of bounded VC dimension. But both of these are Glivenko-Cantelli classes, which means that if we select a sufficiently large finite set $S$ at random then, with probability $1$, every set in the class intersects with $S$ with fraction close to its measure. In particular, by choosing $S$ large enough, this means every set in the class of measure $\geq\epsilon$ contains a fraction of $S$ of size, say $(\epsilon/2)|S|$. (Technically $S$ is a multiset, but when the base set is large enough, this doesn't make a difference.)

Unless I'm misunderstanding something, the conclusion of Glivenko-Cantelli is much stronger than the conclusion of the (p,q) theorem: the claim holds for almost every choice of $S$, for all large sets in the class simultaneously, and each set has "large" intersection with $S$ instead of just one point. Also, Glivenko-Cantelli-type theorems seem to be easier to prove.

The only catch is that Glivenko-Cantelli only covers the large sets in the class, while the (p,q) theorem covers every single set in the class satisfying the (p,q) property.

This brings me to the problem: the main example of a collection $\mathcal{F}$ with the (p,q) property seems to be a collection of sets with measure $\geq\epsilon$ for some fixed $\epsilon$. In other words, exactly the collections already covered by Glivenko-Cantelli.

My question is, roughly, what more the (p,q) theorem does for us. Am I missing something about the statements, so that the (p,q) theorem provides more? Or are there interesting collections with the (p,q) property which aren't already covered by being a Glivenko-Cantelli class?

share|cite|improve this question
up vote 1 down vote accepted

I think the (p,q) theorem is completely different from Glivenko-Cantelli. Why do you say that the convex sets form a GL class? Consider the following family in R: Intervals containing 0 or 1. This is a (3,2) family but it is not GL, as it contains the {0} point. (Of course if you change the measure and concentrate it on {0,1}, then this does become a GL class, which is not surprising knowing the proof of the (p,q) theorem.)

share|cite|improve this answer
Whether or not the convex sets form a GC class depends on the measure (I was basing the statement on "Glivenko-Cantelli Theorems for Classes of Convex Sets", which shows that they are for various measures). I guess one way to apply the (p,q) theorem would be to choose a measure for which the convex sets fail to satisfy Glivenko-Cantelli, and use that measure to construct a (p,q) family, but if that's the only way to generate (p,q) families, it doesn't address the VC dimension case, since VC sets will satisfy Glivenko-Cantelli for any measure. – Henry Towsner Jun 19 '12 at 21:53

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.