the probabilistic method

《the probabilistic method》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、CHAPTERSIXTheProbabilisticMethodTheprobabilisticmethodisawayofprovingtheexistenceofobjects.Theunderlyingprincipleissimple:toprovetheexistenceofanobjectwithcertainproperties,wedemonstrateasamplespaceofobjectsinwhichtheprobabilityispositivethatarandomlyselectedobjecthastherequiredproperties.Ifth

2、eprobabilityofselectinganobjectwiththerequiredpropertiesispositive,thenthesamplespacemustcontainsuchanobject,andthereforesuchanobjectexists.Forexample,ifthereisapositiveprobabilityofwinningamillion-dollarprizeinaraffle,thentheremustbeatleastoneraffleticketthatwinsthatprize.Althoughthebasicprin

3、cipleoftheprobabilisticmethodissimple,itsapplicationtospecificproblemsofteninvolvessophisticatedcombinatorialarguments.Inthischapterwestudyanumberoftechniquesforconstructingproofsbasedontheprobabilisticmethod,startingwithsimplecountingandaveragingargumentsandthenintroducingtwomoreadvancedtools

4、,theLovaszlocallemmaandthesecondmomentmethod.Inthecontextofalgorithmswearegenerallyinterestedinexplicitconstructionsofobjects,notmerelyinproofsofexistence.Inmanycasestheproofsofexistenceobtainedbytheprobabilisticmethodcanbeconvertedintoefficientrandomizedconstructionalgorithms.Insomecases.thes

5、eproofscanbeconvertedintoefficientdeterministicconstructionalgorithms:thisprocessiscalledderandomiz.ation,sinceitconvertsaprobabilisticargumentintoadeterministicone.Wegiveexamplesofbothrandomizedanddeterministicconstructionalgorithmsarisingfromtheprobabilisticmethod.6.1.TheBasicCountingArgumen

6、tToprovetheexistenceofanobjectwithspecificproperties,weconstructanappropriateprobabilityspaceSofobjectsandthenshowthattheprobabilitythatanobjectinSwiththerequiredpropertiesisselectedisstrictlygreaterthan0.Forourfirstexample,weconsidertheproblemofcoloringtheedgesofagraphwithtwocolorssothatthere

7、arenolargecliqueswithalledgeshavingthesamecolor.Let1266.1THEBASICCOUNTINGARGUMENTK11beacompletegraph(withallG)edges)onnvertices.AcliqueofkverticesinK11isacompletesubgraphKk.Theorem6.1:{f(�)2-(D+l<1,thenitispossibletocolortheedgesqfK11H'