林慶澤

(廣州大學(xué) 物理與電子工程學(xué)院, 廣東 廣州 510006)

Erd?s-Ko-Rado定理的一個(gè)新證明

林慶澤

(廣州大學(xué) 物理與電子工程學(xué)院, 廣東 廣州 510006)

Erd?s-Ko-Rado定理是極值組合學(xué)里非?；A(chǔ)也非常重要的定理，它給出了自相交有限子集族里基數(shù)大小的上界的一個(gè)非常好的估計(jì)，在集合論和圖論等相關(guān)領(lǐng)域有很多應(yīng)用.證明方法很多，既有組合方面的，也有代數(shù)方面的.通過(guò)構(gòu)建某些集合族間的2種單射以及一些相關(guān)的性質(zhì)，諸如自相交性，給出了該定理的另一種證明方法.

組合學(xué);Erd?s-Ko-Rado定理;子集族;自相交性

0 引 言

Erd?s-Ko-Rado定理，簡(jiǎn)稱EKR定理，主要研究子集族的自相交性質(zhì),是研究有限集的自相交子集族的最原始成果,也是極值組合學(xué)理論中最重要的結(jié)論之一.近年來(lái),許多著名數(shù)學(xué)家研究了EKR定理及其各種推廣[1-3],例如，給出了EKR定理在各種偏序集上的極值結(jié)構(gòu)的刻畫(huà)[4]，通過(guò)研究偏序集的EKR性質(zhì)，進(jìn)而證明了Coxeter群的嚴(yán)格EKR性質(zhì)等[5].作為相交有限子集族基數(shù)大小的上界的一個(gè)非常好的估計(jì)，EKR定理為集合論、組合學(xué)、代數(shù)學(xué)和圖論等學(xué)科及其相關(guān)交叉學(xué)科的相關(guān)研究工作提供了很多極為有用的幫助.EKR定理由Erd?s、Ko及Rado3位數(shù)學(xué)家首次給出歸納證明[6]，之后數(shù)學(xué)家Katona利用代數(shù)里的循環(huán)置換給出了該定理的一個(gè)更簡(jiǎn)潔的證明[7].本研究通過(guò)構(gòu)建某些集合族間的2種單射以及一些相關(guān)的性質(zhì)，諸如自相交性和不變性等，給出了EKR定理的另一種證明方法.

1 預(yù)備知識(shí)

因此，命題成立.證畢.

其中，Δ(Ω，N2a)為集合Ω，N2a的對(duì)稱差.

2 Erd?s-Ko-Rado定理的證明

1)如1∈Ω1且1∈Ω2，則由定義6有Ψ(Ω1)≠Ψ(Ω2).

2)如1∈Ω1且1?Ω2，則只需證明Ω1≠Ψ(Ω2).令O2=Ω2N2a(Ω2).

所以，Ω1≠Ψ(Ω2).

3)如果1?Ω1且1?Ω2，若有a(Ω1)=a(Ω2)，則Ω1N2a(Ω1)≠Ω2N2a(Ω2)或者Ω1∩N2a(Ω1)≠Ω2∩N2a(Ω2)，從而Ψ(Ω1)≠Ψ(Ω2).現(xiàn)假設(shè)a(Ω1)>a(Ω2)，則由a(Ω2)的最大性可知|Ω1N2a(Ω1)|≠|(zhì)Ω2N2a(Ω1)|，從而Ω1N2a(Ω1)≠Ω2N2a(Ω1).故，Ψ(Ω1)≠Ψ(Ω2).

證畢.

綜上所述，命題的必要性部分得證.

證畢.

結(jié)合命題3和命題4，就得到了組合學(xué)里著名的Erd?s-Ko-Rado定理：

[1]Hurlbert G,Kamat V.Erd?s-Ko-Radotheoremsforchordalgraphsandtrees[J].J Comb Theory Ser A,2011,118(3):829-841.

[2]Frankl P,Graham R L.Intersectiontheoremsforvectorspaces[J].Eur J Comb,1985,6(2):183-187.

[3]Ellis D,Pilpel H.Intersectingfamiliesofpermutations[J].J Am Math Soc,2010,24(3):649-682.

[4]耿興波.與Erd?s-Ko-Rado定理相關(guān)的極值問(wèn)題[D].大連：大連理工大學(xué),2011.

[5]張俊.偏序集的Erd?s-Ko-Rado性質(zhì)及相關(guān)問(wèn)題[D].大連：大連理工大學(xué),2008.

[6]Erd?s P,Ko C,Rado R.Intersectiontheoremsforsystemsoffinitesets[J].Quart J Math Oxford Ser,1961,12(2):313-320.

[7]Katona G O H.AsimpleproofoftheErd?s-ChaoKo-Radotheorem[J].J Comb Theory Ser B,1972,13(2):183-184.

[8]Frankl P.Theshiftingtechniqueinextremalsettheory[C]//Proc11thBrCombConf.Cambridge,UK:Cambridge University Press,1987.

[9]Knuth D E.Theartofcomputerprogramming(Vol.4)[M].Boston:Addison-Wesley,2005.

New Proof on Erd?s-Ko-Rado Theorem

LINQingze

(School of Physics and Electronic Engineering, Guangzhou University, Guangzhou 510006, China)

Erd?s-Ko-Rado theorem is a very basic and very important theorem in the extremum combinatorics.It gives a very good estimate of the upper bound of the base size of self-intersecting families of subsets and has been applied in many related fields of set theory and graph theory.There are many methods,consisting of combinatorics and algebras,to prove this theorem.In this paper,by constructing two kinds of injections between some families of subsets and by studying some related properties such as self-intersections,the paper gives another proof on this theorem.

combinatorics;Erd?s-Ko-Rado theorem;family of subsets;self-intersection

1004-5422(2016)04-0342-03

2016-09-18.

林慶澤(1994 — )， 男， 碩士研究生， 從事集合論與代數(shù)學(xué)研究.

O157

A