Combinatorics (Fall 2010)/Finite set systems
Systems of Distinct Representatives (SDR)
Hall's marriage 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].
- The sets [math]\displaystyle{ S_1,S_2,\ldots,S_m }[/math] have a system of distinct representatives (SDR) if and only if
Doubly stochastic matrices
Theorem (Birkhoff 1949; von Neumann 1953) - Every doubly stochastic matrix is a convex combination of permutation matrices.
Cuckoo hashing
Min-max theorems
- König-Egerváry theorem
- Menger's theorem
- Dilworth's theorem
Theorem (König 1931; Egerváry 1931) - In any bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.
Theorem (Menger 1927) - 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 a[math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] separating set.
Theorem (Dilworth 1950) - 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.
Chains and antichains
Symmetric chains
Sperner's theorem
Hypergraph coloring
Theorem (Erdős 1963) - Let [math]\displaystyle{ \mathcal{F} }[/math] be a [math]\displaystyle{ k }[/math]-uniform. If [math]\displaystyle{ |\mathcal{F}|\lt 2^{k-1} }[/math] then [math]\displaystyle{ \mathcal{F} }[/math] is 2-colorable.
Lovász local lemma
Colorings
Theorem (Erdős-Lovász 1975) - Let [math]\displaystyle{ \mathcal{F} }[/math] be a [math]\displaystyle{ k }[/math]-uniform. If every member of [math]\displaystyle{ \mathcal{F} }[/math] intersects at most [math]\displaystyle{ 2^{k-3} }[/math] other members, then [math]\displaystyle{ \mathcal{F} }[/math] is 2-colorable.