Combinatorics (Fall 2010)/Finite set systems: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop |
||
| Line 8: | Line 8: | ||
::<math>\left|\bigcup_{i\in I}S_i\right|\ge |I|</math> for all <math>I\subseteq\{1,2,\ldots,m\}</math>. | ::<math>\left|\bigcup_{i\in I}S_i\right|\ge |I|</math> for all <math>I\subseteq\{1,2,\ldots,m\}</math>. | ||
}} | }} | ||
==== 2-factor of regular graph ==== | |||
==== Doubly stochastic matrices ==== | ==== Doubly stochastic matrices ==== | ||
| Line 16: | Line 18: | ||
==== Cuckoo hashing ==== | ==== Cuckoo hashing ==== | ||
=== König-Egerváry theorem === | |||
{{Theorem|Theorem (König 1931; Egerváry 1931)| | {{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. | :In any bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover. | ||
}} | }} | ||
=== Menger's theorem === | |||
{{Theorem|Theorem (Menger 1927)| | {{Theorem|Theorem (Menger 1927)| | ||
: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 a<math>s</math>-<math>t</math> separating set. | :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 a<math>s</math>-<math>t</math> separating set. | ||
Revision as of 13:40, 17 October 2010
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
2-factor of regular graph
Doubly stochastic matrices
Theorem (Birkhoff 1949; von Neumann 1953) - Every doubly stochastic matrix is a convex combination of permutation matrices.
Cuckoo hashing
König-Egerváry 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.
Menger's theorem
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.