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

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
imported>WikiSysop
Line 25: Line 25:


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


Line 31: Line 31:
: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>.
: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|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 04:21, 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].
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].

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
  • 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.
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.


Sperner system