05549nam 2200709 450 991083025150332120220609165021.01-280-27276-797866102727610-470-31228-90-471-72215-4(CKB)111087027121374(EBL)221331(OCoLC)475926461(SSID)ssj0000227841(PQKBManifestationID)11221899(PQKBTitleCode)TC0000227841(PQKBWorkID)10270162(PQKB)11463163(MiAaPQ)EBC221331(MiAaPQ)EBC5567044(Au-PeEL)EBL5567044(PPN)152533427(EXLCZ)9911108702712137420220308d2000 uy 0engur|n|---|||||txtccrThe probabilistic method /Noga Alon, Joel H. SpencerSecond edition.New York :Interscience Publishers,[2000]©20001 online resource (322 p.)Wiley-Interscience series in discrete mathematics and optimization"A Wiley-Interscience publication."0-471-65398-5 0-471-37046-0 Includes bibliographical references (p. 283-293) and indexes.Dedication; Preface; Acknowledgments; Contents; Part I: METHODS; 1 The Basic Method; 1.1 The Probabilistic Method; 1.2 Graph Theory; 1.3 Combinatorics; 1.4 Combinatorial Number Theory; 1.5 Disjoint Pairs; 1.6 Exercises; The Probabilistic Lens: The Erdős-Ko-Rado Theorem; 2 Linearity of Expectation; 2.1 Basics; 2.2 Splitting Graphs; 2.3 Two Quickies; 2.4 Balancing Vectors; 2.5 Unbalancing Lights; 2.6 Without Coin Flips; 2.7 Exercises; The Probabilistic Lens: Brégman's Theorem; 3 Alterations; 3.1 Ramsey Numbers; 3.2 Independent Sets; 3.3 Combinatorial Geometry; 3.4 Packing; 3.5 Recoloring3.6 Continuous Time3.7 Exercises; The Probabilistic Lens: High Girth and High Chromatic Number; 4 The Second Moment; 4.1 Basics; 4.2 Number Theory; 4.3 More Basics; 4.4 Random Graphs; 4.5 Clique Number; 4.6 Distinct Sums; 4.7 The Rödl Nibble; 4.8 Exercises; The Probabilistic Lens: Hamiltonian Paths; 5 The Local Lemma; 5.1 The Lemma; 5.2 Property B and Multicolored Sets of Real Numbers; 5.3 Lower Bounds for Ramsey Numbers; 5.4 A Geometric Result; 5.5 The Linear Arboricity of Graphs; 5.6 Latin Transversals; 5.7 The Algorithmic Aspect; 5.8 Exercises; The Probabilistic Lens: Directed Cycles6 Correlation Inequalities6.1 The Four Functions Theorem of Ahlswede and Daykin; 6.2 The FKG Inequality; 6.3 Monotone Properties; 6.4 Linear Extensions of Partially Ordered Sets; 6.5 Exercises; The Probabilistic Lens: Turán 's Theorem; 7 Martingales and Tight Concentration; 7.1 Definitions; 7.2 Large Deviations; 7.3 Chromatic Number; 7.4 Two General Settings; 7.5 Four Illustrations; 7.6 Talagrand's Inequality; 7.7 Applications of Talagrand's Inequality; 7.8 Kim-Vu Polynomial Concentration; 7.9 Exercises; The Probabilistic Lens: Weierstrass Approximation Theorem; 8 The Poisson Paradigm8.1 The Janson Inequalities8.2 The Proofs; 8.3 Brun's Sieve; 8.4 Large Deviations; 8.5 Counting Extensions; 8.6 Counting Representations; 8.7 Further Inequalities; 8.8 Exercises; The Probabilistic Lens: Local Coloring; 9 Pseudorandomness; 9.1 The Quadratic Residue Tournaments; 9.2 Eigenvalues and Expanders; 9.3 Quasi Random Graphs; 9.4 Exercises; The Probabilistic Lens: Random Walks; Part II: TOPICS; 10 Random Graphs; 10.1 Subgraphs; 10.2 Clique Number; 10.3 Chromatic Number; 10.4 Branching Processes; 10.5 The Giant Component; 10.6 Inside the Phase Transition; 10.7 Zero-One Laws10.8 ExercisesThe Probabilistic Lens: Counting Subgraphs; 11 Circuit Complexity; 11.1 Preliminaries; 11.2 Random Restrictions and Bounded-Depth Circuits; 11.3 More on Bounded-Depth Circuits; 11.4 Monotone Circuits; 11.5 Formulae; 11.6 Exercises; The Probabilistic Lens: Maximal Antichains; 12 Discrepancy; 12.1 Basics; 12.2 Six Standard Deviations Suffice; 12.3 Linear and Hereditary Discrepancy; 12.4 Lower Bounds; 12.5 The Beck-Fiala Theorem; 12.6 Exercises; The Probabilistic Lens: Unbalancing Lights; 13 Geometry; 13.1 The Greatest Angle among Points in Euclidean Spaces13.2 Empty Triangles Determined by Points in the PlaneThe leading reference on probabilistic methods in combinatorics-now expanded and updatedWhen it was first published in 1991, The Probabilistic Method became instantly the standard reference on one of the most powerful and widely used tools in combinatorics. Still without competition nearly a decade later, this new edition brings you up to speed on recent developments, while adding useful exercises and over 30% new material. It continues to emphasize the basic elements of the methodology, discussing in a remarkably clear and informal style both algorithmic and classical methods as wellWiley-Interscience series in discrete mathematics and optimization.Combinatorial analysisProbabilitiesCombinatorial analysis.Probabilities.511.6Alon Noga66369Spencer Joel H.MiAaPQMiAaPQMiAaPQBOOK9910830251503321Probabilistic method924317UNINA