Combinatorics: The Rota Way

by Joseph P. S. Kung , Gian-Carlo Rota , Catherine H. Yan

• ISBN13: 9780521737944
• ISBN10: 052173794X
• Edition: 1st
• Format: Paperback
• Copyright: 2009-02-09
• Publisher: Cambridge University Press

Summary

Written by two of Gian-Carlo Rota's former students, this book is based on notes from his courses and on personal discussions with him. Topics include sets and valuations, partially ordered sets, distributive lattices, partitions and entropy, matching theory, free matrices, doubly stochastic matrices, Moebius functions, chains and antichains, Sperner theory, commuting equivalence relations and linear lattices, modular and geometric lattices, valuation rings, generating functions, umbral calculus, symmetric functions, Baxter algebras, unimodality of sequences, and location of zeros of polynomials. Many exercises and research problems are included, and unexplored areas of possible research are discussed. This book should be on the shelf of all students and researchers in combinatorics and related areas.

Author Biography

Gian-Carlo Rota was one of the most original and colorful mathematicians of the twentieth century. His work on the foundations of combinatorics focused on revealing the algebraic structures that lie behind diverse combinatorial areas and created a new area of algebraic combinatorics. His graduate courses influenced generations of students. Joseph P.S. Kung is a professor of mathematics at the University of North Texas. He is currently an editor-in-chief of Advances in Applied Mathematics. Gian-Carlo Rota (1932-1999) was a professor of applied mathematics and natural philosophy at the Massachusetts Institute of Technology. He was a member of the National Academy of Science. He was awarded the 1988 Steele Prize of the American Mathematical Society for his 1964 paper "On the Foundations of Combinatorial Theory I. Theory of Moumlet;bius Functions." He was a founding editor of Journal of Combinatorial Theory. Catherine H. Yan is a professor of mathematics at Texas AM University. Prior to that, she was a Courant Instructor at New York University and a Sloan Fellow.

Table of Contents

Preface	p. ix
Sets, Functions, and Relations	p. 1
Sets, Valuations, and Boolean Algebras	p. 1
Partially Ordered Sets	p. 9
Lattices	p. 17
Functions, Partitions, and Entropy	p. 28
Relations	p. 44
Further Reading	p. 52
Matching Theory	p. 53
What Is Matching Theory?	p. 53
The Marriage Theorem	p. 54
Free and Incidence Matrices	p. 62
Submodular Functions and Independent Matchings	p. 67
Rado's Theorem on Subrelations	p. 74
Doubly Stochastic Matrices	p. 78
The Gale-Ryser Theorem	p. 94
Matching Theory in Higher Dimensions	p. 101
Further Reading	p. 105
Partially Ordered Sets and Lattices	p. 106
Möbius Functions	p. 106
Chains and Antichains	p. 126
Sperner Theory	p. 136
Modular and Linear Lattices	p. 147
Finite Modular and Geometric Lattices	p. 161
Valuation Rings and Möbius Algebras	p. 171
Further Reading	p. 176
Generating Functions and the Umbral Calculus	p. 178
Generating Functions	p. 178
Elementary Umbral Calculus	p. 185
Polynomial Sequences of Binomial Type	p. 188
Sheffer Sequences	p. 205
Umbral Composition and Connection Matrices	p. 211
The Riemann Zeta Function	p. 218
Symmetric Functions and Baxter Algebras	p. 222
Symmetric Functions	p. 222
Distribution, Occupancy, and the Partition Lattice	p. 225
Enumeration Under a Group Action	p. 235
Baxter Operators	p. 242
Free Baxter Algebras	p. 246
Identities in Baxter Algebras	p. 253
Symmetric Functions Over Finite Fields	p. 259
Historical Remarks and Further Reading	p. 270
Determinants, Matrices, and Polynomials	p. 272
Polynomials	p. 272
Apolarity	p. 278
Grace's Theorem	p. 283
Multiplier Sequences	p. 291
Totally Positive Matrices	p. 296
Exterior Algebras and Compound Matrices	p. 303
Eigenvalues of Totally Positive Matrices	p. 311
Variation Decreasing Matrices	p. 314
Pólya Frequency Sequences	p. 317
Selected Solutions	p. 324
Bibliography	p. 369
Index	p. 389
Table of Contents provided by Ingram. All Rights Reserved.