Extremal Combinatorics

《Extremal Combinatorics》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ExtremalCombinatoricsStasysJukna==Draft==ContentsPart1.TheClassics1Chapter1.Counting31.Thebinomialtheorem32.Selectionwithrepetitions53.Partitions64.Doublecounting65.Theaveragingprinciple86.Theinclusion-exclusionprinciple10Exercises12Chapter2.AdvancedCountin

2、g171.Boundsonintersectionsize172.Graphswithno4-cycles183.Graphswithnoinduced4-cycles194.Zarankiewicz’sproblem215.Densityof0-1matrices236.TheLovász–Steintheorem25Exercises26Chapter3.ProbabilisticCounting291.Probabilisticpreliminaries292.Tournaments313.Univer

3、salsets324.Coveringbybipartitecliques325.2-colorablefamilies336.Thechoicenumberofgraphs34Exercises35Chapter4.ThePigeonholePrinciple371.Somequickies372.TheErdős–Szekerestheorem383.Mantel’stheorem394.Turán’stheorem405.Dirichlet’stheorem416.Swell-coloredgraphs

4、427.Theweightshiftingargument438.Schur’stheorem449.Ramseyantheoremsforgraphs4510.Ramsey’stheoremforsets47Exercises48Chapter5.SystemsofDistinctRepresentatives531.Themarriagetheorem532.Twoapplications543.Min–maxtheorems56iiiCONTENTS4.Matchingsinbipartitegraph

5、s56Exercises58Part2.ExtremalSetTheory61Chapter6.Sunflowers631.Thesunflowerlemma632.Modifications643.Applications65Exercises68Chapter7.IntersectingFamilies711.UltrafiltersandHellyproperty712.TheErdős–Ko–Radotheorem713.Fisher’sinequality724.Maximalintersectingfam

6、ilies735.Cross-intersectingfamilies74Exercises75Chapter8.ChainsandAntichains771.Decompositioninchainsandantichains772.Application:thememoryallocationproblem793.Sperner’stheorem804.TheBollobástheorem805.Strongsystemsofdistinctrepresentatives826.Union-freefam

7、ilies83Exercises84Chapter9.BlockingSetsandtheDuality871.Duality872.Theblockingnumber883.Helly-typetheorems894.Blockingsetsanddecisiontrees905.Blockingsetsandmonotonecircuits91Exercises95Chapter10.DensityandUniversality991.Densesets992.Hereditarysets1003.Mat

8、roidsandapproximation1014.TheKruskal–Katonatheorem1045.Universalsets1076.Paleygraphs1087.Fullgraphs110Exercises111Chapter11.WitnessSetsandIsolation1131.Bondy’stheorem1132.Averagewitnesses1143.Theisolat