Combinatorics (Fall 2010)/Finite set systems: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop |
||
Line 22: | Line 22: | ||
*König-Egerváry theorem: in a bipartite graph, the maximum number of edges in a matching equals the minimum number of vertices in a vertex cover. | *König-Egerváry theorem: 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: the minimum number of vertices separating two given vertices in a graph equals the maximum number of vertex-disjoint paths between the two vertices. | *Menger's theorem: 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: the minimum number of chains | *Dilworth's theorem: the minimum number of chains which cover a partially ordered set equals the maximum number of elements in an antichain. | ||
{{Theorem|Theorem (König 1931; Egerváry 1931)| | {{Theorem|Theorem (König 1931; Egerváry 1931)| |
Revision as of 04:30, 20 October 2010
Systems of Distinct Representatives (SDR)
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 sets [math]\displaystyle{ S_1,S_2,\ldots,S_m }[/math] have a system of distinct representatives (SDR) if and only if
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].
- A bipartite graph [math]\displaystyle{ G(U,V,E) }[/math] has a matching of [math]\displaystyle{ U }[/math] if and only if
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: 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: 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: the minimum number of chains which cover a partially ordered set equals the maximum number of elements in an antichain.
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.
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].
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.
Chains and antichains
Symmetric chains
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.