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

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


=== Sperner's theorem ===
=== Sperner's theorem ===
== Hypergraph coloring ==
{{Theorem|Theorem (Erdős 1963)|
:Let <math>\mathcal{F}</math> be a <math>k</math>-uniform. If <math>|\mathcal{F}|<2^{k-1}</math> then <math>\mathcal{F}</math> is 2-colorable.
}}
=== Lovász local lemma ===
=== Colorings ===
{{Theorem|Theorem (Erdős-Lovász 1975)|
:Let <math>\mathcal{F}</math> be a <math>k</math>-uniform. If every member of <math>\mathcal{F}</math> intersects at most <math>2^{k-3}</math> other members, then <math>\mathcal{F}</math> is 2-colorable.
}}

Revision as of 06:01, 18 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].

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