PlanetMath: Hall's marriage theorem, proof of

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (210)
Orphanage
Unclass'd (1)
Unproven (473)
Corrections (34)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

proof of Hall's marriage theorem

(Proof)

We prove Hall's marriage theorem by induction on $\left\vert S\right\vert$ , the size of .

The theorem is trivially true for $\vert S\vert=0$ .

Assuming the theorem true for all $\left\vert S\right\vert<n$ , we prove it for $\left\vert S\right\vert=n$ .

First suppose that we have the stronger condition

$\displaystyle \left\vert\cup T\right\vert \ge \left\vert T\right\vert+1$

for all $\emptyset \ne T \subset S$ . Pick any $x\in S_n$ as the representative of

; we must choose an SDR from

$\displaystyle S' = \left\{S_1\setminus\{x\},\ldots,S_{n-1}\setminus\{x\}\right\}.$

But if

$\displaystyle \{S_{j_1}\setminus\{x\},...,S_{j_k}\setminus\{x\}\} = T'\subseteq S'$

then, by our assumption,

$\displaystyle \left\vert\cup T'\right\vert \ge \left\vert\cup_{i=1}^{k} S_{j_i}\right\vert-1 \ge k.$

By the already-proven case of the theorem for

we see that we can indeed pick an SDR for

Otherwise, for some $\emptyset\ne T \subset S$ we have the “exact” size

$\displaystyle \left\vert\cup T\right\vert=\left\vert T\right\vert.$

Inside

itself, for any $T'\subseteq T\subset S$ we have

$\displaystyle \left\vert\cup T'\right\vert\ge\left\vert T'\right\vert,$

so by an already-proven case of the theorem we can pick an SDR for

It remains to pick an SDR for $S\setminus T$ which avoids all elements of $\cup T$ (these elements are in the SDR for ). To use the already-proven case of the theorem (again) and do this, we must show that for any $T'\subseteq S\setminus T$ , even after discarding elements of $\cup T$ there remain enough elements in $\cup T'$ : we must prove

$\displaystyle \left\vert\cup T' \setminus \cup T\right\vert \ge \left\vert T'\right\vert.$

But

$\displaystyle \left\vert\cup T' \setminus \cup T\right\vert$	$\displaystyle = \left\vert\bigcup(T\cup T')\right\vert - \left\vert\cup T\right\vert \ge$	(1)
	$\displaystyle \ge \left\vert T\cup T'\right\vert - \left\vert T\right\vert =$	(2)
	$\displaystyle = \left\vert T\right\vert + \left\vert T'\right\vert - \left\vert T\right\vert = \left\vert T'\right\vert,$	(3)

using the disjointness of

and

. So by an already-proven case of the theorem, $S\setminus T$ does indeed have an SDR which avoids all elements of $\cup T$ .

This completes the proof.

Anyone with an account can edit this entry. Please help improve it!

"proof of Hall's marriage theorem" is owned by mps. [ full author list (2) | owner history (1) ]

(view preamble)

This object's parent.

Log in to rate this entry.
(view current ratings)

Cross-references: even, SDR, size, induction, Hall's marriage theorem

This is version 7 of proof of Hall's marriage theorem, born on 2002-06-06, modified 2005-07-11.
Object id is 3059, canonical name is ProofOfHallsMarriageTheorem.
Accessed 5453 times total.

Classification:

AMS MSC:

05D15 (Combinatorics :: Extremal combinatorics :: Transversal theory)

Pending Errata and Addenda

None.[ View all 4 ]

Discussion

forum policy

No messages.

Interact

post | correct | update request | add example | add (any)