## General informations

## Summary

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 un- related
(with respect to inclusion) subsets of a finite set? This theorem stimulated
the development of a fast growing theory dealing with extremal 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 (e.g. flow theory and
polyhedral combinatorics), from linear algebra (e.g. Jordan decompositions,
Lie algebra representations, and eigenvalue methods), from probability theory
(e.g. limit theorems), and from enumerative combinatorics (e.g. Möbius
inversion). Studying Sperner theory means learning many important techniques
in discrete mathematics and combinatorial optimization on a particular theme.
## Contents

- Preface
- 1 Introduction
- 1.1 Sperner's theorem
- 1.2 Notation and terminology
- 1.3 The main examples

- 2 Extremal problems for finite sets
- 2.1 Counting in two different ways
- 2.2 Partitions into symmetric chains
- 2.3 Exchange operations and compression
- 2.4 Generating families
- 2.5 Linear independence
- 2.6 Probabilistic methods

- 3 Profile-polytopes for set families
- 3.1 Full hereditary families and the antiblocking type
- 3.2 Reduction to the circle
- 3.3 Classes of families arising from Boolean expressions

- 4 The flow-theoretic approach in Sperner theory
- 4.1 The Max-Flow Min-Cut Theorem and the Min-Cost Flow Algorithm
- 4.2 The k-cutset problem
- 4.3 The k-family problem and related problems
- 4.4 The variance problem
- 4.5 Normal posets and flow morphisms
- 4.5 Product theorems

- 5 Matchings, symmetric chain orders, and the partition lattice
- 5.1 Definitions, main properties, and examples
- 5.2 More part Sperner theorems and the Littlewood-Offord problem
- 5.3 Coverings by intervals and sc-orders
- 5.4 Semisymmetric chain orders and matchings

- 6 Algebraic methods in Sperner theory
- 6.1 The full rank property and Jordan functions
- 6.2 Peck posets and the commutation relation
- 6.3 Results for modular, geometric, and distributive lattices
- 6.4 The independence number of graphs and the Erdös-Ko-Rado
Theorem
- 6.5 Further algebraic methods to prove intersection theorems

- 7 Limit theorems and asymptotic estimates
- 7.1 Central and local limit theorems
- 7.2 Optimal representations and limit Sperner theorems
- 7.3 An asymptotic Erdös-Ko-Rado Theorem

- 8 Macaulay posets
- 8.1 Macaulay posets and shadow minimization
- 8.2 Existence theorems for Macaulay posets
- 8.3 Optimization problems for Macaulay posets
- 8.4 Some further numerical and existence results for chain products
- 8.5 Sperner families satisfying additional conditions in chain
products

- Notation
- Bibliography
- Index

Prof. Dr. Konrad Engel, 15.05.97
(konrad.engel@mathematik.uni-rostock.de)
Back to Homepage
of the Department of Mathematics at the University of Rostock