Combinatorics: The Rota Way Book

Preface ix

1 Sets, Functions, and Relations 1

1.1 Sets, Valuations, and Boolean Algebras 1

1.2 Partially Ordered Sets 9

1.3 Lattices 17

1.4 Functions, Partitions, and Entropy 28

1.5 Relations 44

1.6 Further Reading 52

2 Matching Theory 53

2.1 What Is Matching Theory? 53

2.2 The Marriage Theorem 54

2.3 Free and Incidence Matrices 62

2.4 Submodular Functions and Independent Matchings 67

2.5 Rado's Theorem on Subrelations 74

2.6 Doubly Stochastic Matrices 78

2.7 The Gale-Ryser Theorem 94

2.8 Matching Theory in Higher Dimensions 101

2.9 Further Reading 105

3 Partially Ordered Sets and Lattices 106

3.1 Möet;bius Functions 106

3.2 Chains and Antichains 126

3.3 Sperner Theory 136

3.4 Modular and Linear Lattices 147

3.5 Finite Modular and Geometric Lattices 161

3.6 Valuation Rings and Möet;bius Algebras 171

3.7 Further Reading 176

4 Generating Functions and the Umbral Calculus 178

4.1 Generating Functions 178

4.2 Elementary Umbral Calculus 185

4.3 Polynomial Sequences of Binomial Type 188

4.4 Sheffer Sequences 205

4.5 Umbral Composition and Connection Matrices 211

4.6 The Riemann Zeta Function 218

5 Symmetric Functions and Baxter Algebras 222

5.1 Symmetric Functions 222

5.2 Distribution, Occupancy, and the Partition Lattice 225

5.3 Enumeration Under a Group Action 235

5.4 Baxter Operators 242

5.5 Free Baxter Algebras 246

5.6 Identities in Baxter Algebras 253

5.7 Symmetric Functions Over Finite Fields 259

5.8 Historical Remarks and Further Reading 270

6 Determinants, Matrices, and Polynomials 272

6.1 Polynomials 272

6.2 Apolarity 278

6.3 Grace's Theorem 283

6.4 Multiplier Sequences 291

6.5 TotallyPositive Matrices 296

6.6 Exterior Algebras and Compound Matrices 303

6.7 Eigenvalues of Totally Positive Matrices 311

6.8 Variation Decreasing Matrices 314

6.9 Pólya Frequency Sequences 317

Selected Solutions 324

Bibliography 369

Index 389