Combinatorics (Fall 2010)/Finite set systems

Systems of Distinct Representatives (SDR)

A system of distinct representatives (SDR) (also called a transversal) for a sequence of (not necessarily distinct) sets [math]\displaystyle{ S_1,S_2,\ldots,S_m }[/math] is a sequence of distinct elements [math]\displaystyle{ x_1,x_2,\ldots,x_m }[/math] such that [math]\displaystyle{ x_i\in S_i }[/math] for all [math]\displaystyle{ i=1,2,\ldots,m }[/math].

Hall's marriage theorem

Hall's Theorem (SDR)

The sets [math]\displaystyle{ S_1,S_2,\ldots,S_m }[/math] have a system of distinct representatives (SDR) if and only if [math]\displaystyle{ \left|\bigcup_{i\in I}S_i\right|\ge |I| }[/math] for all [math]\displaystyle{ I\subseteq\{1,2,\ldots,m\} }[/math].

The condition that [math]\displaystyle{ \left|\bigcup_{i\in I}S_i\right|\ge |I| }[/math] for all [math]\displaystyle{ I\subseteq\{1,2,\ldots,m\} }[/math] is also called the Hall's condition.

Proof. The necessity of Hall's condition for the existence of SDR is obvious. Suppose that [math]\displaystyle{ x_1\in S_1, x_2\in S_2,\ldots,x_m\in S_m }[/math] is an SDR. [math]\displaystyle{ \forall I\subseteq\{1,2,\ldots,m\}, \bigcup_{i\in I}S_i\supseteq \{x_i\mid i\in I\} }[/math] thus [math]\displaystyle{ \left|\bigcup_{i\in I}S_i\right|\ge | \{x_i\mid i\in I\}|=|I| }[/math]. Now we prove the sufficiency of Hall's condition by induction on [math]\displaystyle{ m }[/math]. When [math]\displaystyle{ m=1 }[/math], the theorem trivially holds. Now assume the theorem hold for any integer smaller than [math]\displaystyle{ m }[/math]. We show the theorem hold for [math]\displaystyle{ m }[/math]. A subcollection of sets [math]\displaystyle{ \{S_i\mid i\in I\} }[/math], [math]\displaystyle{ |I|\lt m\, }[/math], is called a critical family if [math]\displaystyle{ \left|\bigcup_{i\in I}S_i\right|=|I| }[/math]. Case.1: There is no critical family, i.e. for each [math]\displaystyle{ I\subset\{1,2,\ldots,m\} }[/math], [math]\displaystyle{ \left|\bigcup_{i\in I}S_i\right|\gt |I| }[/math]. Take [math]\displaystyle{ S_m }[/math] and choose an arbitrary [math]\displaystyle{ x\in S_m }[/math] as its representative. Remove [math]\displaystyle{ x }[/math] from all other sets by letting [math]\displaystyle{ S'_i=S_i\setminus \{x\} }[/math] for [math]\displaystyle{ 1\le i\le m-1 }[/math]. Then for all [math]\displaystyle{ I\subseteq\{1,2,\ldots,m-1\} }[/math], [math]\displaystyle{ \left|\bigcup_{i\in I}S_i'\right|\ge \left|\bigcup_{i\in I}S_i\right|-1\ge |I| }[/math]. Due to the induction hypothesis, [math]\displaystyle{ S_1,\ldots,S_m }[/math] have an SDR, say [math]\displaystyle{ x_1\in S_1,\ldots,x_{m-1}\in S_{m-1} }[/math]. It is obvious that none of them equals [math]\displaystyle{ x }[/math] because [math]\displaystyle{ x }[/math] is removed. Thus, [math]\displaystyle{ x_1,\ldots,x_{m-1} }[/math] and [math]\displaystyle{ x\, }[/math] form an SDR for [math]\displaystyle{ S_1,S_2,\ldots,S_m }[/math]. Case.1: There is a critical family, i.e. [math]\displaystyle{ \exists I\subset\{1,2,\ldots,m\}, |I|\lt m }[/math], such that [math]\displaystyle{ \left|\bigcup_{i\in I}S_i\right|=|I| }[/math]. Suppose [math]\displaystyle{ S_{m-k+1},\ldots, S_m }[/math] are such a collection of [math]\displaystyle{ k\lt m }[/math] sets. Hall's condition certainly holds for these sets. Since [math]\displaystyle{ k\lt m }[/math], due to the induction hypothesis, there is an SDR for the sets, say [math]\displaystyle{ x_{m-k+1}\in S_{m-k+1},\ldots,x_m\in S_m }[/math]. Again, remove the [math]\displaystyle{ k }[/math] elements from the remaining sets by letting [math]\displaystyle{ S'_i=S_i\setminus\{x_{m-k+1},\ldots,x_m\} }[/math] for [math]\displaystyle{ 1\le i\le m-k }[/math]. By the Hall's condition, for any [math]\displaystyle{ I\subseteq\{1,2,\ldots,m-k\} }[/math], writing that [math]\displaystyle{ S=\bigcup_{i\in I}S_i\cup\bigcup_{i=m-k+1}^m S_i }[/math], [math]\displaystyle{ \left|S\right|\ge |I|+k }[/math], thus [math]\displaystyle{ \left|\bigcup_{i\in I}S_i'\right|\ge |S|-\left|\bigcup_{i=m-k+1}^m S_i\right|\ge |I| }[/math]. Due to the induction hypothesis, there is an SDR for [math]\displaystyle{ S_1,\ldots, S_{m-k} }[/math], say [math]\displaystyle{ x_1\in S_1,\ldots, x_{m-k}\in S_{m-k} }[/math]. Combining it with the SDR [math]\displaystyle{ x_{m-k+1},\ldots, x_{m} }[/math] for [math]\displaystyle{ S_{m-k+1},\ldots, S_{m} }[/math], we have an SDR for [math]\displaystyle{ S_{1},\ldots, S_{m} }[/math]. [math]\displaystyle{ \square }[/math]

Hall's Theorem (matching in bipartite graph)

A bipartite graph [math]\displaystyle{ G(U,V,E) }[/math] has a matching of [math]\displaystyle{ U }[/math] if and only if [math]\displaystyle{ \left|N(S)\right|\ge |S| }[/math] for all [math]\displaystyle{ S\subseteq U }[/math].

Doubly stochastic matrices

Theorem (Birkhoff 1949; von Neumann 1953)

Every doubly stochastic matrix is a convex combination of permutation matrices.

Proof. [math]\displaystyle{ \square }[/math]

Min-max theorems

• König-Egerváry theorem (König 1931; Egerváry 1931): in a bipartite graph, the maximum number of edges in a matching equals the minimum number of vertices in a vertex cover.
• Menger's theorem (Menger 1927): the minimum number of vertices separating two given vertices in a graph equals the maximum number of vertex-disjoint paths between the two vertices.
• Dilworth's theorem (Dilworth 1950): the minimum number of chains which cover a partially ordered set equals the maximum number of elements in an antichain.

König-Egerváry Theorem (graph theory form)

In any bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.

König-Egerváry Theorem (matrix form)

Let [math]\displaystyle{ A }[/math] be an [math]\displaystyle{ m\times n }[/math] 0-1 matrix. The maximum number of independent 1's is equal to the minimum number of rows and columns required to cover all the 1's in [math]\displaystyle{ A }[/math].

Menger's Theorem

Let [math]\displaystyle{ G }[/math] be a graph and let [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math] be two vertices of [math]\displaystyle{ G }[/math]. The maximum number of internally disjoint paths from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math] equals the minimum number of vertices in an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] separating set.

Chains and antichains

Dilworth's theorem

Dilworth's Theorem

Suppose that the largest antichain in the poset [math]\displaystyle{ P }[/math] has size [math]\displaystyle{ r }[/math]. Then [math]\displaystyle{ P }[/math] can be partitioned into [math]\displaystyle{ r }[/math] chains.

Application: Erdős-Szekeres Theorem

Erdős-Szekeres Theorem

A sequence of more than [math]\displaystyle{ mn }[/math] different real numbers must contain either an increasing subsequence of length [math]\displaystyle{ m+1 }[/math], or a decreasing subsequence of length [math]\displaystyle{ n+1 }[/math].

Proof by Dilworth's theorem (Original proof of Erdős-Szekeres) [math]\displaystyle{ \square }[/math]

Application: Hall's Theorem

Hall's Theorem

The sets [math]\displaystyle{ S_1,S_2,\ldots,S_m }[/math] have a system of distinct representatives (SDR) if and only if [math]\displaystyle{ \left|\bigcup_{i\in I}S_i\right|\ge |I| }[/math] for all [math]\displaystyle{ I\subseteq\{1,2,\ldots,m\} }[/math].

Proof by Dilworth's theorem [math]\displaystyle{ \square }[/math]