资源描述：
《The Probabilistic Method(概率图论专着)（Alon 2 2000）.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、THEPROBABILISTICMETHODTHEPROBABILISTICMETHODSecondedition,March2000,TelAvivandNewYorkNogaAlon,DepartmentofMathematics,RaymondandBeverlySacklerFacultyofExactSciences,TelAvivUniversity,TelAviv,Israel.JoelH.Spencer,CourantInstituteofMathematicalSciences,NewYorkUniversity,NewYork,USAAWiley
2、-IntersciencePublicationJOHNWILEY&SONS,INC.NewYork/Chichester/Weinheim/Brisbane/Singapore/TorontoToNuritandMaryAnnPrefaceTheProbabilisticMethodhasrecentlybeendevelopedintensivelyandbecameoneofthemostpowerfulandwidelyusedtoolsappliedinCombinatorics.Oneofthemajorreasonsforthisrapiddevelo
3、pmentistheimportantroleofrandomnessinTheoreticalComputerScience,aÞeldwhichisrecentlythesourceofmanyintriguingcombinatorialproblems.TheinterplaybetweenDiscreteMathematicsandComputerSciencesuggestsanalgorithmicpointofviewinthestudyoftheProbabilisticMethodinCombinatoricsandthisistheapproa
4、chwetriedtoadoptinthisbook.Themanuscriptthusincludesadiscussionofalgorithmictechniquestogetherwithastudyoftheclassicalmethodaswellasthemoderntoolsappliedinit.TheÞrstpartofthebookcontainsadescriptionofthetoolsappliedinprobabilisticarguments,includingthebasictechniquesthatuseexpectationa
5、ndvariance,aswellasthemorerecentapplicationsofMartingalesandCorrelationInequalities.Thesecondpartincludesastudyofvarioustopicsinwhichprobabilistictechniqueshavebeensuccessful.Thispartcontainschaptersondiscrepancyandrandomgraphs,aswellasonseveralareasinTheoreticalComputerScience;Circuit
6、Complexity,ComputationalGeometry,andDerandomizationofrandomizedalgorithms.Scatteredbetweenthechaptersaregemsdescribedundertheheading"TheProbabilisticLens".Theseareelegantproofsthatarenotnecessarilyrelatedtothechaptersafterwhichtheyappearandcanbeusuallyreadseparately.ThebasicProbabilist
7、icMethodcanbedescribedasfollows:inordertoprovetheexistenceofacombinatorialstructurewithcertainproperties,weconstructanappropriateprobabilityspaceandshowthatarandomlychosenelementinthisspacehasthedesiredpropertieswithpositiveprobability.ThismethodhasbeeninitiatedviiviiiPREFACEbyPaulEr
