The probabilistic method / / Noga Alon, Joel H. Spencer

• Record Nr.: UNINA9910830251503321
• Autore: Alon Noga
• Pubbl/distr/stampa: New York : , : Interscience Publishers, , [2000]; ©2000
• ISBN: 1-280-27276-7; 9786610272761; 0-470-31228-9; 0-471-72215-4
• Edizione: [Second edition.]
• Descrizione fisica: 1 online resource (322 p.)
• Collana: Wiley-Interscience series in discrete mathematics and optimization
• Disciplina: 511.6
• Soggetti: Combinatorial analysis; Probabilities
• Lingua di pubblicazione: Inglese
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Note generali: "A Wiley-Interscience publication."
• Nota di bibliografia: Includes bibliographical references (p. 283-293) and indexes.
• Nota di contenuto: 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 Recoloring; 3.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 Cycles; 6 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 Paradigm; 8.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 Laws; 10.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 Spaces; 13.2 Empty Triangles Determined by Points in the Plane
• Sommario/riassunto: The 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 well