View source for Combinatorics (Fall 2010)/Finite set systems

== Systems of Distinct Representatives (SDR)==


=== Hall's marriage theorem ===

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

{{Theorem|Hall's Theorem (matching in bipartite graph)|
:A bipartite graph <math>G(U,V,E)</math> has a matching of <math>U</math> if and only if
::<math>\left|N(S)\right|\ge |S|</math> for all <math>S\subseteq U</math>.
}}

==== Doubly stochastic matrices ====
{{Theorem|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.

{{Theorem|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.
}}

{{Theorem|König-Egerváry Theorem (matrix form)|
:Let <math>A</math> be an <math>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>A</math>.
}}



{{Theorem|Menger's Theorem|
:Let <math>G</math> be a graph and let <math>s</math> and <math>t</math> be two vertices of <math>G</math>. The ''maximum'' number of internally disjoint paths from <math>s</math> to <math>t</math> equals the ''minimum'' number of vertices in an <math>s</math>-<math>t</math> separating set.
}}

== Chains and antichains ==

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

{{Theorem|Definition|
:Let <math>|S|=n\,</math> and <math>\mathcal{F}\subseteq {S\choose k}</math>, <math>k<n\,</math>. 
:The '''shade''' of <math>\mathcal{F}</math> is defined to be
::<math>\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>\nabla\mathcal{F}</math> of <math>\mathcal{F}</math> consists of all subsets of <math>S</math> which can be obtained by adding an element to a set in <math>\mathcal{F}</math>.
:Similarly, the '''shadow''' of <math>\mathcal{F}</math> is defined to be
::<math>\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>\Delta\mathcal{F}</math> of <math>\mathcal{F}</math> consists of all subsets of <math>S</math> which can be obtained by removing an element from a set in <math>\mathcal{F}</math>.
}}

{{Theorem|Lemma (Sperner)|
:Let <math>|S|=n\,</math> and <math>\mathcal{F}\subseteq {S\choose k}</math>. Then
::<math>
\begin{align}
&|\nabla\mathcal{F}|\ge\frac{n-k}{k+1}|\mathcal{F}| &\text{ if } k<n\\
&|\Delta\mathcal{F}|\ge\frac{k}{n-k+1}|\mathcal{F}| &\text{ if } k>0.
\end{align}
</math>
}}

{{Prooftitle|Original proof of Sperner's theorem (shadowing)|
}}

{{Prooftitle|Second proof (double counting)| (Lubell 1966)
}}

=== The LYM inequality ===

{{Theorem|Theorem (Lubell, Yamamoto 1954; Meschalkin 1963)|
:Let <math>|S|=n</math> and <math>\mathcal{F}\subseteq 2^S</math> be an antichain. For <math>k=0,1,\ldots,n</math>, let <math>f_k=|\{A\in\mathcal{F}\mid |A|=k\}|</math>. Then
::<math>\sum_{A\in\mathcal{F}}\frac{1}{{n\choose |A|}}=\sum_{k=0}^n\frac{f_k}{{n\choose k}}\le 1</math>.
}}

{{Prooftitle|Another proof (the probabilistic method)|
}}

=== Symmetric chains ===

{{Theorem|Dilworth's Theorem|
:Suppose that the largest antichain in the poset <math>P</math> has size <math>r</math>. Then <math>P</math> can be partitioned into <math>r</math> chains.
}}