Day 4• A Gem of Combinatorics
組合わせ論の宝石– Dilworth’s theorem– Matching –Covering duality

Sperner system• Given a set S of size n, a family F ofsubsets S is called a Sperner system if nopair in F is in the inclusion relation, that is,there are no pair A, B in F such that A ⊂B
互いに包含関係にない集合の族• Example, the set of all subsets ofcardinality k is a Sperner system.
• Problem: Show that the largest Spernersystem has cardinality n C [n/2]• スペルナー系の最大の大きさはn C [n/2]であることを示せ

Proof by counting• Chain of sets: sequence of sets withinclusion relation
チェイン： 包含関係にある集合列• Given a Sperner system F, count the
number of pairs (A, C) such that A is in F
and C is a chain containing A.
Fに入るAとAを含むチェインCの対（A,C)を数える

Gem of Combinatorics
Chain, Antichain, Matching,
Covering, Independent Sets, andcombinatorial dualities

Partially Ordered Set (poset)• Given a set S, a relation > is called apartial order if it satisfies the follwoing
axioms– If x > y and y> z then x>z– x >y and y<x if and only if x=y• A set with a partial order is called a poset– Example 1. A set of numbers– Example 2. A set of points (in which order?)– Example 3. A set of subsets of a finite set S

Chain and antichain• Given a poset A, a chain of A is asequence of elementsa(1) < a(2) <….<a(k)• An antichain is a set of uncomparable
elements of A.
• μ（A): size of maximum antichain• τ（A): size of minimum chain partition of A
• Exercise: show that μ（A)≦τ（A)ababcabacadcdbcabdacdabcdbdcdbcd

ababcabacadcdbcabd

acd

abcdbdcdbcd

Another proof of Sperner’stheorem• If A is the powerr set P(S) of S, a Spernersystem is an antichain
もしAがSの部分集合全体の集合なら、スペルナ系はアンチチェインになる。
• Prove Sperner’s theorem from μ（A)≦τ（A)– Find a chain partition of size n C [n/2]Dilworth’s theorem• Dilworth’s theorem: μ（A)=τ（A)A beautiful “duality” of chain and antichain

Dilworth’s theorem• Dilworth’s theorem: μ（A)=τ（A)• Applications:
1. Covering-matching duality
2. Hall’s marriage theorem
A Quiz on interconnecting network

3. Refinment of Erdos-Szekeles theorem(next week??)
4. Young tableaux and its theory (withoutproofs)

Covering-matching duality• Consider a bipartite graph G=(V,W,E)• Matching : set of edges sharing no vertex.
– If V is set of men and W is set of women, a
set of married couples is a matching• Covering: set of vertices X such that everyedge has an endpoint in X
• Independent set: set of vertices Y suchthat none of them are adjacent• Exercise: An independent set is thecomplement of a coveringMatching-covering duality
Koenig’s Theorem: The maximum size ofmatching is the minimum size of covering
Does it has amatching of size 4?

Matching-covering duality
Koenig’s Theorem: The maximum size ofmatching is the minimum size of covering
Does it has amatching of size 4?
No, because it has acovering of size 3.

From Dilworth to Koenig
Consider the poset such that v<w if there isan edge (v,w) (from V to W).

From Dilworth to Koenig
Consider the poset such that v<w if there isan edge (v,w) (from V to W).
The minimum chain partition has
cardinarity |V|+|W|-|M|, where M is amaximum matching
An antichain is an independent set
The maximum independent has size
|V|+|W|-|C|, where C is the minimum
coverThus, |M| =|C| from Dilworth’s Th.

Hall’s marriage theorem• For G=(V, W,E) such that |V|≦|W|, it has
a complete matching (i.e.matching of size|V|) if and only if for any subset A of V,|N(A)| ≧|A| holds, where N(A) is theneighbor of A in G.
• Proof. (only if) is easy. (if) is from Koenig.
Suppose that the max matching has size
less than |V|. Then, there is a covering(V0,W0) of size at most |V|-1. Consider A =V – V0 to contradict |N(A)| ≧|A|

Suppose that the max matching has size
less than |V|. Then, there is a covering(V0,W0) of size at most |V|-1. Consider
A = V – V0 to contradict |N(A)| ≧|A|
Nodes in A can only connect tovertices in W0, since otherwise there
is an uncovered edge by the covering.

Thus,|N( A )| ≦ |W0| ≦|V|-1-|V0| ＜|A|

Refined marriage theorem• Let δ（A）＝|A|-|N(A)| and its maximum
among all subsets A of V is δ. Then, thesize of maximum matching is |V| - δ• Proof is an exercise

Quiz• There are 30 input lines connecting to 24
output lines. 10 inputs connects to only
one output line, 10 inputs to two lines, and10 inputs to four lines.
Each output line is connected to at mostthree input lines.
Prove that, we can establish 20 parallel
connection irrelevant to the way ofconnection.
Hint: Show that δ(A) ≦10 for any A.

Dilworth’s theorem: let us prove• Dilworth’s theorem: μ（A)=τ（A)• Definition: x ∈A is effective if there is anantichain of length μ(A) containing x.
• Lemma 1. Suppose that we have a chain
partition M(1),M(2)..,M(k) of A for k=μ（A）,
and let x(i) be the maximal effective
element in M(i). Then, x(1),x(2),…,x(k) is
an antichain.

Proof of Dilworth’s theorem• μ（A)=τ（A)– Show μ（A)≧τ（A) by induction1 . If |A| = 1, then easy
2. Remove a maximal element a from A to have A’=A - {a} : μ(A’) = τ(A’) = k by induction
3. Consider a maximum chain partition of A’, andfind x(1), x(2),..,x(k) of Lemma 1.
4. If a is not comparable to any x(i), fine (why?)
5. If a > x(1), - show at the blackboard.