请输入您要查询的字词:

 

单词 HallsMarriageTheoremProofOf
释义

Hall’s marriage theorem, proof of


We prove Hall’s marriage theoremMathworldPlanetmath by inductionMathworldPlanetmath on |S|, the size of S.

The theorem is trivially true for |S|=0.

Assuming the theorem true for all |S|<n, we prove it for |S|=n.

First suppose that we have the stronger condition

|T||T|+1

for all TS. Pick any xSn as the representative of Sn; we must choose an SDR from

S={S1{x},,Sn-1{x}}.

But if

{Sj1{x},,Sjk{x}}=TS

then, by our assumptionPlanetmathPlanetmath,

|T||i=1kSji|-1k.

By the already-proven case of the theorem for S we see that we can indeed pick an SDR for S.

Otherwise, for someTS we have the “exact” size

|T|=|T|.

Inside T itself, for any TTS we have

|T||T|,

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

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

|TT||T|.

But

|TT|=|(TT)|-|T|(1)
|TT|-|T|=(2)
=|T|+|T|-|T|=|T|,(3)

using the disjointness of T and T. So by an already-proven case of the theorem, ST does indeed have an SDR which avoids all elements of T.

This the proof.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 22:21:52