Selected topics in combinatorics revolving around Vapnik-Chervonenkis dimension

Spring 2023

Lecturer: Szymon Toruńczyk

What is this lecture about? A big portion of the lectures will be concerned with the Vapnik-Chervonenkis dimension. This fundamental notion has numerous applications in computational learning theory, combinatorics, logic, computational geometry, and theoretical computer science. We will develop the foundations of the theory and study its applications.

Outline

1. Set systems, Vapnik-Chervonenkis dimension, Sauer-Shelah-Perles lemma
2. Vapnik-Chervonenkis theorem, fundamental theorem of PAC learning, ε-nets
3. Helly-type properties, (p,q)-theorem
4. Sample compression schemes
5. Haussler's packing theorem
6. Zarankiewicz's problem, Kovari-Sos-Turan theorem, incidence geometry, Szemerédi-Trotter theorem, Kovari-Sos-Turan for bounded VC-dimension
7. Matchings with low crossing number
8. Geometric range searching
9. Szemeredi regularity
10. Regularity theorem for graphs of bounded VC-dimension
11. Regularity theorem for stable graphs
12. Permutation classes.

Literature

• Lectures in Discrete Geometry, Jiri Matousek
• Geometric Discrepancy, Jiri Matousek
• Topics in Combinatorics, lecture notes, Artem Chernikov,
• Geometric set systems, Jiri Matousek
• Geometric range searching, Jiri Matousek
• Understanding Machine Learning: From Theory to Algorithms, Shai Shalev-Shwartz and Shai Ben-David

Additional sources

• Proofs from the Book
• Combinatorial Geometry, Janos Pach, Pankaj Agarwal,
• Lecture notes on Extremal graph theory, David Conlon,
• Computational Learning Theory, James Worrell,
• Traces of finite sets: Extremal problems and geometric applications, Furedi, Pach.
• Turan-type theorems: The history of degenerate (bipartite) extremal graph problems Zoltan Furedi and Miklos Simonovits,

Specific topics

• min-max theorem, Farkas lemma, finite-dimensional Hahn-Banach: Matousek, Lectures on Discrete Geometry; also post by Terence Tao.

• Szemeredi-Trotter: Matousek, Lectures on Discrete Geometry, Chap. 4.3; using cutting and Kovari-Sos-Turan: Chap. 4.5.

• Cutting Lemma: Matousek, Lectures on Discrete Geometry, Chap. 4.6 (weaker version), 4.7 (stronger version)

VC-dimension

Set systems

Definition: A set system consists of a domain $X$ (a set) and a family $\cal F\subseteq P(X)$ of subsets of $X$. For $Y\subset X$, write ${\cal F}\cap Y$ for the set system with domain $Y$ and family $\{F\cap Y: F\in\cal F\}$.

Remark A set system is the same as a hypergraph.

Examples:

• open intervals: domain $\mathbb R$, family $\{(a,b):a,b\in\mathbb R, a<b\}$
• rectangles: domain $\mathbb R^2$, family $\{(a,b)\times (c,d):a,b,c,d\in\mathbb R, a<b,c<d\}$
• discs: domain $\mathbb R^2$ family $\{D_r(p): p\in \mathbb R^2, r>0\}$
• convex sets in $\mathbb R^2$
• higher-dimensional analogues in $\mathbb R^d$,
• neighborhoods in graphs

Usually $X=\bigcup\cal F$, then we just mention $\cal F$.

• Concepts in machine learning. Goal: given a labelled sample, find a reasonable hypothesis (concept). A labelled sample is the same as a set $Y$ and a set $F\cap Y$, for some concept $F\in\cal F$. The goal is to "guess" the concept $F$, or something close to $F$.

• In the area of geometric range searching, we fix a set system of geometric shapes in $\mathbb R^d$, like the ones in the examples above. The sets in $\cal F$ are called ranges. Given a finite set $X\subset \mathbb R^d$, the task is to compute a data structure that allows to quickly answer queries of the form: for a given range $F\in\cal F$, what is $\#(F\cap X)$?

VC-dimension and shatter function

The goal is to define a measure of complexity of a set system. Machine learning intuition: understand which concept classes are learnable. When does Ockham's razor work well?

Definition (VC-dimension) [Vapnik, Chervonenkis, 71] Let $\cal F$ be a set system with domain $X$. A set $Y\subseteq X$ is shattered by $\cal F$ if ${\cal F}\cap Y=2^Y$. The VC-dimension of $\cal F$ is the maximum size $d$ of a set $Y\subseteq X$ shattered by $\cal F$, or $\infty$ if arbitrarily large sets are shattered.

Definition (Shatter function). Let $\cal F$ be a set system on $X$. Let

Examples

• half-spaces in $\mathbb R^d$ have VC-dim at most $d+1$ (see exercises)
• revisit examples above.

Observation If $\cal F$ has infinite VC-dimension then $\pi_{\cal F}(m)=2^m$ for all $m$.

Definition (Dual set system). Let $\cal F$ be a set system with domain $X$. The dual system $\cal F^*$ is the system with domain $\cal F$ and family $\{x^*:x\in X\}$, where $x^*=\{F\in\cal F: x\in F\}\subset\cal F$.

Another view on set systems: bipartite graphs $(L,R,E)$, $E\subseteq L\times R$. (Multiplicities are ignored). Dual: $(R,L,E^{-1})$. In particular, $(\cal F^*)^*\cong\cal F$, up to removing twins (elements in the domain that belong to exactly the same sets).

$\pi_{\cal F^*}$ is denoted $\pi^*_{\cal}$, and is called the dual shatter function of $\cal F$. $VC(\cal F^*)$ is denoted $VC^*(\cal F)$, and is called the dual VC-dimension of $\cal F$.

$VC(\cal F^*)$ is the maximal number of sets in $\cal F$ such that every cell in the Venn diagram is occupied by some element of the domain. $\pi^*_{\cal F}(m)$ is the maximal number of occupied cells in the Venn diagram of ${\le}m$ sets from $\cal F$.

Example If $\cal F$ is the family of half-planes in $\mathbb R^2$, then $\pi^*_{\cal F}(m)$ is the maximal number of regions into which $m$ half-planes can partition the plane. For example, $\pi^*_{\cal F}(2)=4$ and $\pi^*_{\cal F}(3)=7$.

Exercise Prove that $\pi^*_{\cal F}(m)={m+1\choose 2}+1$.

Exercise If $VC(\cal F)\le d$ then $VC^*(\cal F)< 2^{d+1}$.

In all examples, we have either a polynomial, or an exponential shatter function – nothing in between.

Sauer-Shelah-Perles Lemma. [Sauer (72), Shelah and Perles (72), Vapnik-Chervonenkis (71)] Let $\cal F$ be a set system on $n$ elements of VC-dimension at most $d$. Then

Note. This bound is tight. Consider the set system $\cal F$ of all $\le d$-element subsets of an infinite set $X$. Clearly $\pi_{\cal F}(m)=\Phi_d(m)$. So the bound is tight.

Proof. Proof by "shifting", due to Alon (83) and Frankl (83): see Chernikov's notes. Inductive proof: see Geometric Discrepancy by Matousek, Lemma 5.9.

Exercise For every element $v$ in the domain, define a (partial) matching $M_v^{\cal F}$ on $\cal F$, by

Set systems in logical structures

Let $M$ be a logical structure and $\phi(\bar x;\bar y)$ be a formula. For a tuple $\bar b\in M^{\bar y}$ denote

Consider the set system $\cal F_\phi$ with domain $M^{\bar x}$ and sets $\phi(M;\bar b)$, for $\bar b\in M^{\bar y}$.

Examples

• $(\mathbb R,+,\cdot,\le,0,1)$, formula

Then $\cal F_\phi$ is the set system of closed intervals on $\mathbb R$.

• $(\mathbb R,+,\cdot,\le,0,1)$, formula

Then $\cal F_\phi$ is the set system of discs in $\mathbb R^2$.

• $(\mathbb R,+,\cdot,\le,0,1)$

$\cal F_\phi$ is the set of rectangles in $\mathbb R^2$.

• A graph $G=(V,E)$ is seen as a logical structure with a binary relation $E$, denoting adjacency.

A first-order formula is a formula using $\exists, \forall, \lor,\land,\neg$, where the quantifiers range over elements of the domain.

Example $\phi(x,y)\equiv \exists z.y=x+z^2$ is equivalent in $(\mathbb R,+,\cdot,\le,0,1)$ to $x\le y$. So $\le$ is definable in $(\mathbb R,+,\cdot)$. The relation $y=e^x$ is not definable in $(\mathbb R,+,\cdot)$.

Example The formula $\delta_1(x,y)\equiv (x=y) \lor E(x,y)$ expresses that $dist(x,y)\le 1$, and the formula $\delta_2(x,y)\equiv x=y \lor E(x,y)\lor \exists z. E(x,z)\land E(z,y)$ expresses that $dist(x,y)\le 2$, and similarly we can define $\delta_r(x,y)$ expressing $dist(x,y)\le r$, for any fixed number $r$. There is no first-order formula that expresses the property `$x$ and $y$ are at a finite distance' in all graphs. This can be expressed by a formula of monadic second-order logic (MSO).

Theorem (Shelah, 71) Let $M$ be a logical structure. The following conditions are equivalent:

• every first-order formula $\phi(\bar x;\bar y)$ has bounded VC-dimension in $M$,
• every first-order formula $\phi(x;\bar y)$ has bounded VC-dimension in $M$ (here $x$ is a singleton).

If the above conditions hold, then $M$ is called NIP.

Example $(\mathbb R,+,\cdot,\le)$ is NIP. We use the result of Tarski:

Theorem (Tarski, 40) The structure $(\mathbb R,+,\cdot,\le,0,1)$ has quantifier elimination: every first-order formula $\phi(x_1,\ldots,x_k)$ is equivalent to a formula without quantifiers.

Such formulas are just boolean combinations of sets of the form:

or

where $p(x_1,\ldots,x_k)$ is a polynomial with integer coefficients, such as $x_1^2+x_2^2\le 5$.

Corollary (Tarski, 30) For every first-order formula $\phi(x;y_1,\ldots,y_k)$ and parameters $b_1,\ldots,b_k\in\mathbb R$, the set $\phi(\mathbb R;b_1,\ldots,b_k)\in\mathbb R$ is a union of at most $k_\phi$ intervals, where $k_\phi$ depends only on $\phi$ (and not on $b_1,\ldots,b_k$).

Proof. We may assume that $\phi$ is a boolean combination of $\ell$ sets as above. Let $d$ be the maximum degree of the polynomials. Each polynomial of degree $d$ with one free variable defines a set that is a union of at most $d$ intervals. A boolean combination of $k$ such sets is a union of at most $k:=\ell d$ intervals.

Corollary The structure $(\mathbb R,\cdot,+,\le,0,1)$ is NIP.

Proof. The family of all sets that are unions of $k$ intervals cannot shatter a set of $2k+1$ points. The conclusion follows from the result of Shelah.

Definition A structure $M$ with a total order $<$ and other relations/functions is o-minimal if for every first-order formula $\phi(x;y_1,\ldots,y_k)$ and parameters $b_1,\ldots,b_k$, the set $\phi(M;b_1,\ldots,b_k)$ is a union of finitely many intervals.

It is known that this implies that then it is a union of at most $n_\phi$ intervals, for some $n_\phi$ that depends only on $\phi$.

Corollary Every o-minimal structure is NIP.

Examples of o-minimal structures

• $(\mathbb R,+,\cdot,\le,0,1)$
• $(\mathbb R,+,\cdot,\le,e^x, 0,1)$ (Wilkie's theorem)

Other examples of NIP structures

• abelian groups
• Presburger arithmetic $(\mathbb Z,+,<)$.

Classes of structures

Let $\cal C$ be a class of logical structures. For example, the class of all planar graphs. A formula $\phi(\bar x;\bar y)$ defines a set system ${\cal F}^M_{\phi}$ in each structure $M\in\cal C$. We say that $\phi$ has VC-dimension ${\le}d$ in $\cal C$ if each of the set systems ${\cal F}^M_\phi$ has VC-dimension at most ${\le}d$. The shatter function $\pi_{\phi,\cal F}(m)$ is defined as the maximum of $\pi_{{\cal F}^M_\phi}$, over all $M\in\cal C$. A class $\cal C$ is NIP if every formula $\phi(\bar x;\bar y)$ has bounded VC-dimension on $\cal C$.

Example Let $\cal C$ a class of graphs and $\phi(x,y)\equiv E(x,y)$. Then $\pi_{E,\cal C}(m)$ is the following quantity: the maximum, over all planar graphs $G$ and sets $A\subseteq V(G)$ with $|A|\le m$, of the number of distinct vertices $v\in V(G)$ with different neighborhoods in $A$. If $\cal C$ is the class of bipartite graphs, then $\pi_{E,\cal C}(m)=2^m$. If $\cal C$ is the class of planar graphs, then $\pi_{E,\cal C}(m)=O(m)$.

Fact The class $\cal C$ of planar graphs is NIP. [Podewski, Ziegler, 1978] Moreover, for every fixed first-order formula $\phi(x;y)$, we have $\pi_{\phi,\cal C}(m)=O(m)$

This holds more generally for all classes $\cal C$ with bounded expansion [Pilipczuk, Siebertz, Toruńczyk, 2018] and for classes of bounded twin-width [Przybyszewski, 2022]. Classes with bounded expansion include classes of bounded tree-width, classes of graphs that can be embedded in a fixed surface, classes of graphs with bounded maximum degree, and classes that exclude a fixed minor.

They are contained in nowhere dense classes. $\pi_{\phi,\cal C}(m)=O(m^{1+\varepsilon})$ holds for every nowhere dense class $\cal C$ and fixed $\varepsilon>0$ [PST, 2018].

VC-density

Definition (VC-density). The VC-density of a set system $\cal F$ is the infimum of all $r\in\mathbb R$ such that $\pi_{\cal F}(m)=O(m^r)$. Similarly, we define the VC-density of a formula $\phi(\bar x;\bar y)$ in a class $\cal C$ of structures.

Example Every formula $\phi(\bar x;y)$ (with $y$ singleton) has VC-density $1$ on the class of planar graphs, and more generally, on all nowhere dense classes.

Theorem (Assouad, 1983) The VC-density of any set system $\cal F$ is either $0$, or a real number ${\ge }1$. For every real $\alpha\ge 1$ there is a set system $\cal F$ with VC-density $\alpha$.

We will construct a family with VC-density $3/2$. See Chernikov's notes, Example 2.7. For this we use the following.

Theorem (Kovari, Sos, Turan, 1954) Every $K_{2,2}$-free bipartite graph with $n+n$ vertices has $O(n^{3/2})$ edges.

Example Fix a prime number $p$. For every power $q$ of $p$ there is a field $\mathbb F_q$ with $q$ elements. Consider the set system $\cal F_q$ where:

• the domain consists of points in $\mathbb F_q^2$ and lines in $\mathbb F_q^2$ (solutions of equations $y=ax+b$).
• the family consists of two-element sets $\{p,\ell\}$ where $\ell$ is a line and $p$ is a point in $\ell$.

1. $\pi_{\cal F_q}(m)=O(m^{3/2})$. Pick an $m$-element subset $A$. The restriction $\cal F_q\cap A$ consists of:

• the empty set (1 element),
• singletons ($m$ elements),
• and of pairs $\{p,\ell\}$ such that $p,\ell\in A$ and $p\in \ell$.

The number of pairs is the number of edges in the bipartite graph $G_A$ whose parts are the points $p\in A$, and the lines $\ell \in A$, and edges denote incidence. The graph $G_A$ is $K_{2,2}$-free, so it has at most $O(m^{3/2})$ edges. Altogether, $|{\cal F}_q\cap A|\le 1+m+O(m^{3/2})=O(m^{3/2})$.

On the other hand, $|{\cal F}_q|\ge q^3$ and there are at most $2q^2$ points and lines. Therefore, $|{\cal F}_q|\ge \Omega(|points|+|lines|)^{3/2}$.

VC-theorem and PAC learning

Let $D$ be a fixed domain. For a multiset $S\subset D$ and a set $F\subset D$, write $Av_S(F)$ to denote the average number of points in $S$ that belong to $D$,

Definition ($\varepsilon$-approximation). Fix a probability measure $\mu$ on $D$. A multiset $S$ is an $\varepsilon$-approximation for $\mu$ on a (measurable) set $F\subset D$ if

A multiset $S$ is an $\varepsilon$-approximation for $\mu$ on a set family $\cal F$ with domain $F$, if $S$ is an $\varepsilon$-approximation for $\mu$ on $F$, for each $F\in\cal F$.

Recall the weak law of large numbers:

Theorem (Weak law of large numbers) Fix a probability measure $\mu$ on a domain $D$ and a measurable set $F\subset D$. For every $\varepsilon>0$ and number $n$, a randomly and independently selected sequence $S$ of $n$-elements of $D$ is an $\varepsilon$-approximation for $\mu$ on $F$ with probability at least $1-\frac 1 {4n\varepsilon^2}$.

The VC-theorem is a uniform version, for an entire family $\cal F$ of small VC-dimension. We assume here that the domain is finite. This assumption can be removed at the cost of some additional assumptions.

Theorem (VC-theorem) Fix a probability measure $\mathbb P$ on a finite domain $D$ and a family $\cal F$ of subsets of $D$. For every $\varepsilon>0$ and number $n$, a randomly and independently selected sequence of $n$-elements of $D$ is an $\varepsilon$-approximation for $\mathbb P$ on $\cal F$ with probability at least

For the proof, see e.g. Chernikov's lecture notes.

Corollary For every fixed $d\in\N$ and $\varepsilon>0$ there is a number $N(d,\varepsilon)$ such that if $\cal F$ has VC-dimension $d$ and $\mathbb P$ is a probability distribution on $D$, then there exists an $\varepsilon$-approximation for $\mathbb P$ on $\cal F$ of size at most $N(d,\varepsilon)$. Moreover, we can take

Proof of Corollary. By Sauer-Shelah-Perles we have that $\pi_{\cal F}(n)\le O(n^d)$. The key point is that in the value in the VC-theorem,

converges rapidly to $0$ as $n\rightarrow\infty$. In particular, we can find $N(d,\varepsilon)$ large enough so that this number is smaller than any fixed constant $c>0$. A more careful analysis shows that $O(\frac{d}{\varepsilon^2}\log \left(\frac d\varepsilon\right))$ suffices. See Chernikov's lecture notes. $\square$

Let $\mu$ be a probability distribution on (a $\sigma$-algebra on) $D$ and let $\cal F$ be a system of (measurable) subsets of $D$.

For $\varepsilon>0$, a set $S\subset D$ is called a $\varepsilon$-net for $\mu$ on $\cal F$, if every set $F\in\cal F$ with $\mu(F)\ge \varepsilon$ has a nonempty intersection with $S$.

Lemma Every $\varepsilon$-approximation is an $\varepsilon$-net. Proof. For every $F\in \cal F$, if $S$ has an empty intersection with $F$ then $Av_F(S)=0$. If $S$ is an $\varepsilon$-approximation, this implies that $\mu(F)\le \varepsilon$. $\square$

Corollary For every fixed $d\in\N$ and $\varepsilon>0$ there is a number $N(d,\varepsilon)$ such that if $\cal F$ has VC-dimension $d$ and $\mathbb P$ is a probability distribution on $D$, then there exists an $\varepsilon$-net for $\mathbb P$ on $\cal F$ of size at most $N(d,\varepsilon)$. In fact, a random (with probability $\mathbb P$) sample of $N(d,\varepsilon)$ elements of $D$ is an $\varepsilon$-net, with probability at least $1-\varepsilon$. Moreover, we can take

In fact, for $\varepsilon$-nets (as opposed to $\varepsilon$-approximations) one can improve the bound above and get

Although we will use this bound in the sequel, the improvement over the previous bound will not be relevant to us.

PAC learning

A concept is a function $f: D\to[0,1]$. A concept class is a family of concepts on $D$.

We restrict to $\{0,1\}$-valued functions (aka sets), which can be seen as a classification problem. So now concept classes are just set families.

A labeled sample is a multiset $S\subset D$ with a partition $S=S_+\cup S_-$. Denote by $S_N(D)$ the set of all labeled samples of size $N$. A learning map is a function $f$ that maps every $N$-sample $S\in S_N(D)$ to a generalization $f(S)\subset D$. Ideally, $f(S)$ should be consistent with $S$, that is, $S_+=S\cap f(S)$ and $S_-=S\setminus f(S)$, but this does not need to happen (it is even desirable to allow errors in the labelling of $S$).

Intuition See the papaya intuition from Understanding Machine Learning.

Overfitting We pick $f(S)$ to be $S_+$. To avoid this, we restrict to some family $\cal F$ of concepts that we are willing to consider, and require that the range of $f$ should be contained in $\cal F$.

Empirical Risk Minimization is the learning approach that we pick $f(S)$ to be any concept $C\in\cal F$ that minimizes the number of errors on the training set. That is, the number of points in $S$ such that belong to $S_+\triangle C$ is the smallest possible. Here $\cal F$ is a predefined set family (representing our knowledge of the world).

PAC learnability

Say that $\cal F$ is PAC-learnable if for every $\varepsilon,\delta>0$ there exists $N=N(\varepsilon,\delta)$ and a learning map $f:S_N(D)\to 2^D$ such that for every concept $C\in \cal F$ and probability distribution $\mu$ on $D$, if we select $N$ elements of $D$ independently with distribution $\mu$ each and label it with respect to $C$, obtaining a labeled sample $S=S_+\uplus S_-$, then we will have that $\mu(f(S)\triangle C)\le \varepsilon$ with probability at least $1-\delta$.

If moreover $f$ always returns concepts in $\cal F$, then we say that $\cal F$ is properly PAC learnable. We say that $\cal F$ is consistently PAC learnable if every function $f:S_N(D)\to \cal F$ such that $f(S)\in \cal F$ is any concept that agrees with $S$, works.

Theorem (Fundamental theorem of PAC learning). Let $\cal F$ be a concept class. The following conditions are equivalent:

• $\cal F$ is PAC learnable,
• $VC(\cal F)$ is finite.

Remark There are some untold hidden assumptions in this statement. Either we should assume some measurability conditions, similar to the ones in the VC theorem for infinite domains, or we should assume that the domain is finite. Then the equivalence of the two implications in the theorem should be read as follows. Bottom-up implication: the sample complexity $N(\varepsilon,\delta)$ can be bounded in terms of $\varepsilon,\delta$ and on the VC-dimension of the family $\cal F$. Top-down implication: the VC-dimension of $\cal F$ can be bounded in terms of the function $N(\cdot,\cdot)$. More precisely, we can bound it in terms of $N(\frac 1 3,\frac 1 3)$.

Proof For the bottom-up implication, we may assume for simplicity (by taking the min) that $\delta=\varepsilon$. Let $N=N(d,\varepsilon)$ be the number obtained from the $\varepsilon$-net Corollary.

The learning map $f:S_N(D)\to \cal F$ be defined so that $f(S_+,S_-)$ is any concept in $C\in\cal F$ that contains $S_+$ and is disjoint from $S_-$. To prove that this learning map $f$ has the required properties, we consider the set system

where $\triangle$ denotes the symmetric difference of sets. It was shown in the exercises that $\cal F\triangle C$ has the same VC-dimension as $\cal F$. By the $\varepsilon$-net corollary, a random sample of $N$ elements of $D$ is an $\varepsilon$-net for the family $\cal F\triangle C$, with probability at least $1-\varepsilon$. This easily implies that the learning map $f$ has the required property.

The top-down implication was shown in the exercices. See also Chernikov's notes.

Transversals and Helly-type properties

Transversals

Definition Fix a set system $\cal F$ on a domain $D$.

• A transversal $T$ is a set $T\subseteq D$ that intersects every $F\in\cal F$
• The transversal number of $\cal F$ is the smallest size of a transversal, and is denoted $\tau(\cal F)$
• A packing $\cal G$ is a set $\cal G\subseteq \cal F$ of pairwise disjoint sets.
• The packing number is the largest size of a packing, and is denoted $\nu(\cal F)$.

Clearly $\tau(\cal F)\ge \nu(\cal F)$. It is NP-hard to compute $\tau(\cal F)$ and $\nu(\cal F)$. For this reason, we sometimes use the following, approximate notions.

Definition Fix a set system $\cal F$ on a finite domain $D$.

• A fractional transversal $T$ is a function $f: D\to[0,1]$ such that for every $F\in\cal F$ we have

Its total weight is $\sum_{x\in D}f(x)$.

• The fractional transversal number of $\cal F$ is the infimum of the total weights of all fractional transversals, and is denoted $\tau^*(\cal F)$.
• A fractional packing $\cal G$ is a function $g:\cal F\to[0,1]$ such that for every $x\in D$ we have

Its total weight is $\sum_{F \in\cal F}g(F)$

• The fractional packing number is the supremum of the total weights of all fractional packings, and is denoted $\nu^*(\cal F)$.

The following lemma is straightforward.

Lemma For every set system $\cal F$ on a finite domain $D$ we have:

The following fact is a consequence (or restatement) of the duality theorem for linear programs. It is an easy consequence of Farkas' lemma.

Fact For every set system $\cal F$ on a finite domain $D$ we have

Moreover, this number is rational, computable in polynomial time, and is attained both by a fractional transversal $f:D\to [0,1]$ with rational values, and by a fractional packing $g:\cal F\to[0,1]$ with rational values.

Corollary For every set system $\cal F$ on a finite domain $D$ with $\text{VCdim}(\cal F)=d$, we have:

Proof Follows from the existence of $\varepsilon$-nets of size $O(d)\frac 1 \varepsilon\log (\frac 1 \varepsilon)$. Namely, pick a fractional transversal $f:V\to [0,1]$ of total weight $r$, and normalize it to get a measure $\mu$ with $\mu(v)=f(v)/r$. For a set $F\in\cal F$ we have that $\sum_{x\in F}f(v)\ge 1$ since $f$ is a fractional transversal, so $\mu(F)\ge 1/r$.

Let $\varepsilon=1/r$. By the $\varepsilon$-net theorem there is an $\varepsilon$-net $T$ for $\mu$ on $\cal F$ of size $O(d)\cdot r\log r$. Since $\mu(F)\ge 1/r=\varepsilon$ for all $F\in\cal F$ and $T$ is an $\varepsilon$-net, it follows that $T$ intersects every $F\in\cal F$.

Helly-type theorems

Fact (Helly's Theorem)Fix $d\ge 1$.

Let $\cal F$ be a finite family of convex sets in $\mathbb R^d$. If any $d+1$ sets in $\cal F$ have a point in common, then $\cal F$ has a point in common.

Definition A family $\cal G$ has the $k$-Helly property if for every finite subfamily $\cal F\subset \cal G$, if every $k$ subsets of $\cal F$ have a point in common, then $\cal F$ has a point in common.

For instance, the family of convex subsets of $\mathbb R^{d}$ has the $(d+1)$-Helly property.

Families of bounded VC-dimension don't necessarily have the $k$-Helly property, for any finite $k$. For example, for an infinite set $V$, the family of all sets of the form $V-\{a\}$, for $a\in V$, has VC-dimension $2$, but does not have the $k$-Helly property, for all $k$.

However, families of bounded VC-dimension satisfy a related property.

Say that a family $\cal F$ has the $(p,q)$-property if among every $p$ subsets of $\cal F$, some $q$ among them have a point in common.

For example, the $k$-Helly property is the same as the $(k,k)$-property. Note that the conclusion in Helly's theorem is that $\cal F$ has a transversal of size $1$, that is $\tau(\cal F)\le 1$. The following is a generalization.

Fact (Alon,Kleitman). Let $p,q,d$ be integers with $p\ge q\ge d+1$. Then there is a number $N=N(p,q,d)$ such that for every finite family $\cal F$ of convex subsets of $\mathbb R^d$, if $\cal F$ has the $(p,q)$-property, then $\tau({\cal F})\le N$.

Now this statement generalizes to families of bounded VC-dimension, and can be derived from the proof of Alon and Kleitman, as observed by Matousek.

Fact (Alon,Kleitman and Matousek). Let $p,q,d$ be integers with $p\ge q\ge d+1$. Then there is a number $N=N(p,q,d)$ such that for every finite family $\cal F$ with $\text{VC-dim}^*(\cal F)<d+1$, if $\cal F$ has the $(p,q)$-property, then $\tau(\cal F)\le N$.

Recall that $\text{VC-dim}^*(\cal F)$ is the dual VC-dimension of $\cal F$, defined as the VC-dimension of $\cal F^*$, Equivalently, it is the maximal number $k$ of subsets in $\cal F$ such that every cell in the Venn diagram of those sets is nonempty (occupied by some element in the domain).

We reprove a duality result which is a corollary of the $(p,q)$-theorem. We present a self-contained proof.

Let $E\subset A\times B$ be a binary relation. For $a\in A$ denote $E(a):=\{b\in B|(a,b)\in E\}$ and for $b\in B$ denote $E^*(b):=\{a\in A|(a,b)\in E\}$. Define the VC-dimension of a binary relation $E$ as the maximum of the VC-dimension of two set systems:

Here's the duality result.

Theorem (Corollary of the $(p,q)$-theorem) For every $d$ there is a number $k\le O(d)$ with the following property. Let $E\subset A\times B$ be a binary relation with $\textup{VCdim}(E)\le d$, with $A,B$ finite. Then at least one of two cases holds:

• there is a set $B'\subset B$ with $|B'|\le k$ such that for all $a\in A$ we have $E(a)\cap B'\neq\emptyset$ (that is, $B'$ dominates $A$ wrt $E$), or
• there is a set $A'\subset A$ with $|A'|\le k$ such that for all $b\in B$ we have $E^*(b)\cap A'\neq A'$ (that is, $A'$ dominates $B$ wrt $\neg E$).

We first state a corollary of von Neumann's minimax theorem (also of Farkas' lemma, the Hahn-Banach theorem, or of the strong duality theorem for linear programming).

Theorem (Minimax Theorem) Let $E\subset A\times B$ be a binary relation with $A,B$ finite, and let $\alpha\in \R$. Then exactly one of the following two cases holds:

1. there is some probability distribution $\nu$ on $B$ such that $\nu(E(a))\ge \alpha$ holds for all $a\in A$
2. there is some probability distribution $\mu$ on $A$ such that $\mu(E^*(b))< \alpha$ holds for all $b\in B$.

Proof of Corollary of the $(p,q)$-theorem Set $\alpha:= 1/2$ and $\varepsilon:= 1/3$; the point is that $0<\alpha\pm\varepsilon<1$. Fix $d\in\N$, and let $k$ be the number from the VC-theorem, with $k\le O(\frac{d}{\varepsilon^2}\log(\frac {1}\varepsilon))=O(d)$. By the Minimax Theorem applied to $\alpha= 1/2$, one of the two cases below holds.

Case 1: There is some probability distribution $\nu$ on $B$ such that $\nu( E(a))\ge 1/2$ holds for all $a\in A$.

By the VC-theorem applied to $\varepsilon= 1/3$, there is a multiset $B'\subset B$ with $|B'|\le k$ such that

Pick $a\in A$. Since $\nu( E(a))\ge 1/2$, we have that $\textup{Av}_{B'}( E(a))>0$, so $B'\cap E(a)$ is nonempty. Therefore, the first condition in the statement is satisfied.

Case 2: There is some probability distribution $\mu$ on $A$ such that $\mu(E^*(b))< 1/2$ holds for all $b\in B$.