Combinatorics (Fall 2010)/Finite set systems: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
imported>WikiSysop
No edit summary
Line 1: Line 1:
== Systems of Distinct Representatives (SDR)==
== Systems of Distinct Representatives (SDR)==
 
A '''system of distinct representatives (SDR)''' (also called a '''transversal''') for a sequence of (not necessarily distinct) sets <math>S_1,S_2,\ldots,S_m</math> is a sequence of ''distinct'' elements <math>x_1,x_2,\ldots,x_m</math> such that <math>x_i\in S_i</math> for all <math>i=1,2,\ldots,m</math>.


=== Hall's marriage theorem ===
=== Hall's marriage theorem ===

Revision as of 01:54, 21 October 2010

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].
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.

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]

Symmetric chain decomposition

Theorem (de Bruijn et al 1952)
[math]\displaystyle{ 2^S }[/math] with [math]\displaystyle{ |S|=n }[/math] can be partitioned into at most [math]\displaystyle{ {n\choose \lfloor n/2\rfloor} }[/math] mutually disjoint symmetric chains.

Application: the memory allocation problem

Theorem (Lipski 1978)
There is a universal sequence for [math]\displaystyle{ [n] }[/math] of length at most [math]\displaystyle{ \frac{2}{\pi}2^n }[/math].

Sperner system

Theorem (Sperner 1928)
Let [math]\displaystyle{ |S|=n }[/math] and [math]\displaystyle{ \mathcal{F}\subseteq 2^S }[/math] be an antichain. Then
[math]\displaystyle{ |\mathcal{F}|\le{n\choose \lfloor n/2\rfloor} }[/math].

First proof (symmetric chain decomposition)

Proof of Sperner's theorem
[math]\displaystyle{ \square }[/math]

Second proof (shadowing)

Definition
Let [math]\displaystyle{ |S|=n\, }[/math] and [math]\displaystyle{ \mathcal{F}\subseteq {S\choose k} }[/math], [math]\displaystyle{ k\lt n\, }[/math].
The shade of [math]\displaystyle{ \mathcal{F} }[/math] is defined to be
[math]\displaystyle{ \nabla\mathcal{F}=\left\{A\in {S\choose k+1}\,\,\bigg|\,\, \exists B\in\mathcal{F}\mbox{ such that } B\subset A\right\} }[/math].
Thus the shade [math]\displaystyle{ \nabla\mathcal{F} }[/math] of [math]\displaystyle{ \mathcal{F} }[/math] consists of all subsets of [math]\displaystyle{ S }[/math] which can be obtained by adding an element to a set in [math]\displaystyle{ \mathcal{F} }[/math].
Similarly, the shadow of [math]\displaystyle{ \mathcal{F} }[/math] is defined to be
[math]\displaystyle{ \Delta\mathcal{F}=\left\{A\in {S\choose k+1}\,\,\bigg|\,\, \exists B\in\mathcal{F}\mbox{ such that } B\subset A\right\} }[/math].
Thus the shadow [math]\displaystyle{ \Delta\mathcal{F} }[/math] of [math]\displaystyle{ \mathcal{F} }[/math] consists of all subsets of [math]\displaystyle{ S }[/math] which can be obtained by removing an element from a set in [math]\displaystyle{ \mathcal{F} }[/math].
Lemma (Sperner)
Let [math]\displaystyle{ |S|=n\, }[/math] and [math]\displaystyle{ \mathcal{F}\subseteq {S\choose k} }[/math]. Then
[math]\displaystyle{ \begin{align} &|\nabla\mathcal{F}|\ge\frac{n-k}{k+1}|\mathcal{F}| &\text{ if } k\lt n\\ &|\Delta\mathcal{F}|\ge\frac{k}{n-k+1}|\mathcal{F}| &\text{ if } k\gt 0. \end{align} }[/math]
Proof of Sperner's theorem
(original proof of Sperner)
[math]\displaystyle{ \square }[/math]

Third proof (double counting)

Proof of Sperner's theorem
(Lubell 1966)
[math]\displaystyle{ \square }[/math]

The LYM inequality

Theorem (Lubell, Yamamoto 1954; Meschalkin 1963)
Let [math]\displaystyle{ |S|=n }[/math] and [math]\displaystyle{ \mathcal{F}\subseteq 2^S }[/math] be an antichain. For [math]\displaystyle{ k=0,1,\ldots,n }[/math], let [math]\displaystyle{ f_k=|\{A\in\mathcal{F}\mid |A|=k\}| }[/math]. Then
[math]\displaystyle{ \sum_{A\in\mathcal{F}}\frac{1}{{n\choose |A|}}=\sum_{k=0}^n\frac{f_k}{{n\choose k}}\le 1 }[/math].
Another proof (the probabilistic method)
[math]\displaystyle{ \square }[/math]
Proposition
[math]\displaystyle{ \sum_{A\in\mathcal{F}}\frac{1}{{n\choose |A|}}\le 1 }[/math] implies that [math]\displaystyle{ |\mathcal{F}|\le{n\choose \lfloor n/2\rfloor} }[/math].