Sperner Theory (Encyclopedia of Mathematics and its Applications, No. 65)

The Starting Point Of This Book Is Sperner's Theorem, Which Answers The Question: What Is The Maximum Possible Size Of A Family Of Pairwise (with Respect To Inclusion) Subsets Of A Finite Set? This Theorem Stimulated The Development Of A Fast Growing Theory Dealing With External Problems On Finite Sets And, More Generally, On Finite Partially Ordered Sets. This Book Presents Sperner Theory From A Unified Point Of View, Bringing Combinatorial Techniques Together With Methods From Programming, Linear Algebra, Lie-algebra Representations And Eigenvalue Methods, Probability Theory, And Enumerative Combinatorics. Researchers And Graduate Students In Discrete Mathematics, Optimisation, Algebra, Probability Theory, Number Theory, And Geometry Will Find Many Powerful New Methods Arising From Sperner Theory. Konrad Engel. Includes Bibliographical References And Index. Cover......Page 1 Title Page......Page 6 Copyright Page......Page 7 Contents......Page 8 Preface......Page 10 1.1 Sperner's theorem......Page 14 1.2 Notation and terminology......Page 17 1.3 The main examples......Page 22 2.1 Counting in two different ways......Page 29 2.2 Partitions into symmetric chains......Page 42 2.3 Exchange operations and compression......Page 46 2.4 Generating families......Page 63 2.5 Linear independence......Page 74 2.6 Probabilistic methods......Page 84 3 Profile-polytopes for set families......Page 97 3.1 Full hereditary families and the antiblocking type......Page 99 3.2 Reduction to the circle......Page 103 3.3 Classes of families arising from Boolean expressions......Page 106 4 The flow-theoretic approach in Sperner theory......Page 129 4.1 The Max-Flow Min-Cut Theorem and the Min-Cost Flow Algorithm......Page 130 4.2 The A>cutset problem......Page 138 4.3 The A:-family problem and related problems......Page 144 4.4 The variance problem......Page 153 4.5 Normal posets and flow morphisms......Page 161 4.6 Product theorems......Page 179 5.1 Definitions, main properties, and examples......Page 192 5.2 More part Sperner theorems and the Littlewood-Offord problem......Page 200 5.3 Coverings by intervals and sc-orders......Page 207 5.4 Semisymmetric chain orders and matchings......Page 211 6 Algebraic methods in Sperner theory......Page 221 6.1 The full rank property and Jordan functions......Page 222 6.2 Peck posets and the commutation relation......Page 242 6.3 Results for modular, geometric, and distributive lattices......Page 261 6.4 The independence number of graphs and the Erdos-Ko-Rado Theorem......Page 289 6.5 Further algebraic methods to prove intersection theorems......Page 308 7.1 Central and local limit theorems......Page 317 7.2 Optimal representations and limit Sperner theorems......Page 330 7.3 An asymptotic Erdos-Ko-Rado Theorem......Page 341 8 Macaulay posets......Page 345 8.1 Macaulay posets and shadow minimization......Page 346 8.2 Existence theorems for Macaulay posets......Page 364 8.3 Optimization problems for Macaulay posets......Page 369 8.4 Some further numerical and existence results for chain products......Page 380 8.5 Sperner families satisfying additional conditions in chain products......Page 391 Notation......Page 403 Bibliography......Page 408 Index......Page 426 This book presents Sperner theory from a unified point of view, bringing combinatorial techniques together with methods from programming (flow theory and polyhedral combinatorics), from linear algebra (Jordan decompositions, Lie-algebra representations and eigenvalue methods), from probability theory (limit theorems), and from enumerative combinatorics (Mobius inversion). Researchers in discrete mathematics, optimization, algebra, probability theory, number theory, and geometry will find many powerful new methods arising from Sperner theory Emphasises the powerful methods arising from the fusion of combinatorial techniques with programming, linear algebra, and probability theory