Combinatorics

VC-dimension

Set systems

A set system is a pair \((\mathcal{F},X)\) where \(\mathcal{F}\) is a family of sets defined on the ground set \(X\).

\textbf{Examples:}

1. All half-planes in the plane.
2. All convex sets in the plane.
3. All closed spheres in \(\mathcal{R}^3\)

We usually refer to a set system by denoting its family of sets \(\mathcal{F}\) and letting the ground set be implicitly defined.

Transversal

A transversal \(\mathcal{F}\) in a set system \((\mathcal{F},X)\) is a subset \(T \subset X\) that intersects all sets of \(\mathcal{F}\). The transversal number \(\tau(\mathcal{F})\) of the set system is the smallest possible cardinality of a tranversal.

Packing

A packing is a collection of disjoint subsets of \(\mathcal{F}\). The packing number of set system \(\mathcal{F}\) is the largest possible cardinality of a packing.

The concepts of packing and transversal are equivalent to those of maximum independent number and vertex cover in a graph.