Matching Theory
Matching Theory
System of Distinct Representatives (Transversal) system of distinct representatives(SDR) for sets S1,S2,...,Sm distinct x1,c2,·,xm xi∈Si for i=1,2,...m
System of Distinct Representatives system of distinct representatives (SDR) for sets S1, S2,...,Sm distinct x1, x2,...,xm xi Si for i =1, 2, ..., m (Transversal)
Marriage Problem Does there exist an SDR for S1,S2,.,Sm? m girls Si:boys that girl i likes "Is there a way of marrying these m girls?
Marriage Problem Does there exist an SDR for S1, S2,...,Sm ? m girls Si : boys that girl i likes “Is there a way of marrying these m girls?
S1,S2,...,Sm have a SDR dinstinct x1∈S1,c2∈S2,.,cm∈Sm VIC{1,2,.,m, UcS≥|{x|i∈Il≥I. distinct
S1, S2,...,Sm have a SDR ⇥ dinstinct x1 S1, x2 S2,...,xm Sm ⇥I {1, 2,...,m}, ⇥ iI Si |{x |I|. i | i ⇥ I}| distinct
S,S2,.,Sm have a SDR→ VI C{1,2,...,m},Uier S:
S1, S2,...,Sm have a SDR ⇥I {1, 2,...,m}, ⇥ iI Si |I|
Hall's Theorem(marriage theorem) S1:S2;...,Sm have a SDR VI C{1,2,...,m},Uier Si
S1, S2,...,Sm have a SDR Hall’s Theorem (marriage theorem) ⇥I {1, 2,...,m}, ⇥ iI Si |I|
Hall's Theorem(graph theory form) A bipartite graph G(U,V,E)has a matching of U → IN(S)l≥ISI for all SCU matching:edge independent set MCE with no e1,e2EM share a vertex N(S)={v|]u∈S,uw∈E}
Hall’s Theorem (graph theory form) A bipartite graph G(U,V,E) has a matching of U |N(S)| ≥ |S| for all S⊆U U V matching: edge independent set M⊆E with no e1,e2∈M share a vertex N(S) = {v | ∃u∈S, uv∈E}
Hall's Theorem(marriage theorem) ∀I{1,2,,m,Uc1S≥lI1. S1:S2:...,Sm have a SDR critical family:S1,S2,...,k k<m k . =k i=1 Induction on m: m =1,trivial case.I:there is no critical family in S1,S2,...,Sm case.2:there is a critical family in S1,S2,...,Sm
S1, S2,...,Sm have a SDR Hall’s Theorem (marriage theorem) ⇥I {1, 2,...,m}, ⇥ iI Si |I|. Induction on m : m =1, trivial case.1: there is no critical family in S1, S2, ..., Sm case.2: there is a critical family in S1, S2, ..., Sm critical family: S1, S2,...,Sk ⇥ k i=1 Si = k k < m
Hall's Theorem(marriage theorem) IC{1,2,.,mh,lUeS≥I. >S1,S2,...,Sm have a SDR case.I:there is no critical family in S1,S2,...,Sm VI C {1,2,...,m}that I m,Uier Si take an arbitrary xESm as representative of Si remove Sm and x Si'=SAfx}i=1,2,...m-1 I{1,2,,m-1},UcS≥lI川 due to I.H.S1...,Sm-1 have a SDR {1,....m-1 1,...,m-1 and x form a SDR for S1,S2,...Sm
case.1: there is no critical family in S1, S2, ..., Sm take an arbitrary x∈Sm as representative of Sm remove Sm and x Si ’ = Si\{x} i = 1, 2, ..., m-1 ⌅I ⇥ {1, 2,...,m 1}, ⇥ i⇥I S i ⇤ |I| ⇥I {1, 2,...,m} that |I| |I| due to I.H. S1, S2,...,Sm have a SDR Hall’s Theorem (marriage theorem) ⇥I {1, 2,...,m}, ⇥ iI Si |I|. S⇥ 1,...,S⇥ m1 have a SDR {x1,...,xm1} x1,...,xm1 and x form a SDR for S1, S2, ..., Sm
Hall's Theorem(marriage theorem) IC{1,2,,m,JieI S≥|Il >S1;S2,...,Sm have a SDR case.2:there is a critical family in S1,S2,...,S say Sm-k+1U...USml=k k<m due to I.H.Sm-k+1,...,Sm have a SDR X=x1,...,x Si'-SX i=1,2,,m-k I{1,2,.,m-k}, Uim-k+1S:UUiEI S:k+ →UerS≥I
S1, S2,...,Sm have a SDR Hall’s Theorem (marriage theorem) ⇥I {1, 2,...,m}, ⇥ iI Si |I|. case.2: there is a critical family in S1, S2, ..., Sm say k < m due to I.H. Sm-k+1,..., Sm have a SDR X={x1, ..., xk} |Smk+1 ⇥ ··· ⇥ Sm| = k ⇤I ⇥ {1, 2,...,m k}, ⇥m i=mk+1 Si ⇥ i⇥I Si k + |I| |I| ⇥ i⇥I S i Si ’ = Si\X i = 1, 2, ..., m-k