COMBINATORICS
1 Introduction 1 2 Preliminaries 9 21 Convexity 9 22 Polynomial Approximations 23 23 Polynomials with Real Roots 28 24 H-Stable Polynomials 31 25 D-Stable Polynomials 38 3 Permanents 47 31 Permanents 47 32 Permanents of Non-negative Matrices and H-Stable Polynomials 52 33 The van der Waerden Inequality and Its Extensions 55 34 The Bregman–Minc Inequality and Its Corollaries 58 35 Matrix Scaling 64 36 Permanents of Complex Matrices 72 37 Approximating Permanents of Positive Matrices 78 38 Permanents of a-Conditioned Matrices and Permutations with Few Cycles 85 39 Concluding Remarks 88 4 Hafnians and Multidimensional Permanents 93 41 Hafnians 93 42 Concentration of Hafnians of a-Conditioned Doubly Stochastic Matrices 101 43 Hafnians and Pfaffians 107 44 Multidimensional Permanents 116 45 Mixed Discriminants 129 46 A Version of Bregman–Minc Inequalities for Mixed Discriminants 135 5 The Matching Polynomial 145 51 Matching Polynomial 145 52 Correlation Decay for the Matching Polynomial 150 53 Matching Polynomials of Bipartite Graphs 158 54 The Bethe-Entropy Lower Bound 166 55 Hypergraph Matching Polynomial 174 6 The Independence Polynomial 181 61 The Independence Polynomial of a Graph 181 62 The Independence Polynomial of Regular Graphs 189 63 Correlation Decay for Regular Trees 196 64 Correlation Decay for General Graphs 205 65 The Roots on and Near the Real Axis 216 66 On the Local Nature of Independent Sets 224 7 The Graph Homomorphism Partition Function 229 71 The Graph Homomorphism Partition Function 229 72 Sharpening in the Case of a Positive Real Matrix 238 73 Graph Homomorphisms with Multiplicities 244 74 The Lee–Yang Circle Theorem and the Ising Model 258 8 Partition Functions of Integer Flows 269 81 The Partition Function of 0-1 Flows 269 82 The Partition Function of Integer Flows 273 83 Approximate Log-Concavity 278 84 Bounds for the Partition Function 284 85 Concluding Remarks: Partition Functions for Integer Points in Polyhedra 286 References 293