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

From TCS Wiki
Jump to navigation Jump to search
← Older editNewer edit →
VisualWikitext
imported>WikiSysop
m Protected "Combinatorics (Fall 2010)/Finite set systems" ([edit=sysop] (indefinite) [move=sysop] (indefinite))
imported>WikiSysop
Line 2: Line 2:




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


=== König's theorem ===
{{Theorem|Hall's Theorem|
: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>.
}}
 
=== König-Egerváry theorem ===
{{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 ===
=== Menger's theorem ===
{{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.
}}


=== Birkhoff's theorem ===
=== Birkhoff's theorem ===
{{Theorem|Theorem (Birkhoff 1949; von Neumann 1953)|
:Every doubly stochastic matrix is a convex combination of permutation matrices.
}}


== Chains and Anti-chains ==
== Chains and Anti-chains ==

Revision as of 13:33, 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].

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.

Birkhoff's theorem

Theorem (Birkhoff 1949; von Neumann 1953)
Every doubly stochastic matrix is a convex combination of permutation matrices.

Chains and Anti-chains

Dilworth's theorem

Sperner's Theorem

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=Combinatorics_(Fall_2010)/Finite_set_systems&oldid=3611"