Day 5• A Gem of Combinatorics
組合わせ論の宝石– Proof of Dilworth’s theorem– Some Young diagram combinatorics
ヤング図形の組合せ論Recall the last lecture and try
the homework solution
復習と宿題確認Partially Ordered Set (poset)
半順序集合(ポセット）• Given a set S, a relation > is called a partial
order if it satisfies the following axioms– If x > y and y> z then x>z (transitive)– x >y and y<x if and only if x=y (anti-symmetric)
推移律と反対称性を持つ関係を半順序、それを持つ集合を半順序集合と呼ぶ• 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• A chain in a poset A is a sequence ofelements a(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)ababcabacadcdbcabd

acdabcdbdcdbcd

ababcabacadcdbcabd

acdabcdbdcdbcd

Dilworth’s theorem
ディルワースの定理• Dilworth’s theorem: μ（A)=τ（A)A beautiful “duality” of chain and antichain
チェインと反チェインの間の双対性を示す
美しい関係Dilworth’s theorem• Dilworth’s theorem: μ（A)=τ（A)Applications:• Covering-matching duality (done)
被覆とマッチングの双対性• Hall’s marriage theorem 結婚定理 (done)
A Quiz on switching network スイッチ結合クイズ• Revisit Erdos-Szekeles theorem– エルデシューセケレシュ定理再訪• Theory of Young tableaux (without proofs)

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| - δ
δを|A|-|N(A)|の最大とすると、最大マッチングのサイズは|V|-δ
δ＝0なら結婚定理と一致• 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 parallelconnection irrelevant to the way ofconnection.
Hint: Show that δ(A) ≦10 for any A.

Proof of Dilworth’s theorem• 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 elementin M(i). Then, x(1),x(2),…,x(k) is an antichain.
μ（A)のサイズのチェイン分割があったとき、チェインの極大効果元たちはアンチチェインになるProof of Dilworth’s theorem• μ（A)=τ（A)– Show μ（A)≧τ（A) by induction 帰納法で証明
1 . 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.

What mathematicians do• If two series of values are same, then, find anidentity of functions.
• If two sets has the same cardinality, find a
canonical one-to-one correspondence.
二つの集合が同じ大きさなら、自然な一対一対応を見つけよう– Cantor defined “cardinality” via one-to-onecorrespondence• |The set of integers | = |The set of rational numbers|
since there is no one-to-one correspondence• |The set of integers| < |The set of real numbers|

Revisit Erdos-Szekeles• Reduce “infinite” to “finite”– Set of n points in the plane: infinitely many
– Poset patter only depends on ranking.
– Thus, only depends on the permutation.
点列の代わりに置換を考えよう• Finitely many, since the number of permutationsof n points is n!

• If there is another set of n! elements, we
may find a nice canonical one-to-one
correspondence.

Young diagram• Graphical representation of a partition of anumber– (3), (2,1), (111)– (4), (3,1), (2,2), (2,1,1),(1,1,1,1)

Young tableau(ヤング盤）• Write 1 to n into diagram with increasing
way in rows and columns– (3), (2,1), (111)

11

2

3

1

2

3

A strange relation: 1+ 22 + 1 = 6 =3!

123

2
3

Young tableau(4), (3,1), (2,2), (2,1,1),(1,1,1,1)
1 + 32 + 22+32 + 1 = 24 = 4!
1231413243123412234123413244113234123244

Robinson-Schensted-Knuth
correspondence• There is a canonical one-to one
correspondence between permutations
and pair of young tableaux of same shape
置換と、同じ形のYoung盤の間に一対一対応がある– Used in Group theory, Number theory,
Algebraic Geometry, etc.

Algorithm• Reference: Donald Knuth, The art ofcomputer programming, Vol 3 sorting andsearching. （Bible of computer science)– コンピュータ科学の｢聖書」のような本です– 日本語の本：寺田至 ｢ヤング図形のはなし」• Algorithm will be given on the blackboard.
• Properties• The length of longest increasing (decreasing )subchain  width (height) of the diagram• If σ corresponds to (P(σ), Q(σ））、Then,（P(σ-1), Q(σ-1 )) = (Q(σ）,P(σ))