Hall's Theorem(marriage theorem) I{1,2,,m,UerS≥IIl S1:S2,...,Sm have a SDR case.2:there is a critical family in S1,S2,...Sm Say|Sm-k+1U…USml=k k<m due to I.H.Sm-+1,...,Sm have a SDR X=x1,..,x Si'-SX i=1,2,,m-k Ic{1,2,m-,UcIS≥I due to I.H. S1,...,Sm-k have a SDR Y={y1,...,Umk} X and Y form a SDR for S1,S2,...Sm
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. |Smk+1 ⇥ ··· ⇥ Sm| = k ⇤I ⇥ {1, 2,...,m k}, |I| ⇥ i⇥I S i due to I.H. X and Y form a SDR for S1, S2, ..., Sm Sm-k+1,..., Sm have a SDR X={x1, ..., xk} Si ’ = Si\X i = 1, 2, ..., m-k S⇥ 1,...,S⇥ mk have a SDR Y = {y1,...,ymk}
Hall's Theorem(marriage theorem) S1,S2,.,Sm have a SDR←→ IC{1,2,,m},UcS≥lIl
S1, S2,...,Sm have a SDR Hall’s Theorem (marriage theorem) ⇥I {1, 2,...,m}, ⇥ iI Si |I|
Min-Max Theorems Konig-Egervary theorem:in bipartite graph min vertex cover max matching Dilworth's theorem:in poset min chain-decomposition max antichain Menger's theorem:in graph min vertex-cut max vertex-disjoint paths
Min-Max Theorems • König-Egerváry theorem: in bipartite graph min vertex cover = max matching • Dilworth’s theorem: in poset min chain-decomposition = max antichain • Menger’s theorem: in graph min vertex-cut = max vertex-disjoint paths
Konig-Egervary theorem Theorem (Konig 1931,Egervary 1931) In a bipartite graph,the size of a maximum matching equals the size of a minimum vertex cover. matching:MCE no e1,e2EM share a vertex vertex cover:CC V alle∈E adjacent to some ve∈C
König-Egerváry theorem In a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover. Theorem (König 1931, Egerváry 1931) matching: M E no e1,e2∈M share a vertex vertex cover: C V all e∈E adjacent to some v∈C
Theorem (Konig 1931,Egervary 1931) In a bipartite graph,the size of a maximum matching equals the size of a minimum vertex cover. B matching: independent 1s do not share row/column B
In a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover. Theorem (König 1931, Egerváry 1931) A B 1 0 0 0 1 1 0 0 0 1 0 0 1 0 1 1 0 0 1 1 A B 1 1 1 1 independent 1s matching: do not share row/column