Materials collected in this book were meant to be presented at the Extremal Sets Systems Seminar of the Alfréd Rényi Institute of Mathematics. The main focus is placed on maximizing the cardinality of a family of sets satisfying some prescribed properties. The authors pay great attention to present a large range of proof techniques used in dealing with finite sets systems and give an extensive survey of recent results. Although ordinary graphs are 2-uniform families, extremal graph theory is outside the scope of this book. Ramsey-type theorems and coding theory are also avoided. The intended audience includes (1) students eager to learn the central topics on a graduate level; (2) university professors offering courses on extremal combinatorics; (3) researchers refreshing their knowledge and learning recent developments in the field.
Chapter 1 is an overview of basic results in extremal finite set theory, e.g. Sperner’s theorem, the Erdős-Ko-Rado theorem, the Kruskal-Katona theorem, LYM-inequality, isoperimetric ineqalities, and their generalizations. Multiple proofs are provided to illustrate major techniques used in this field, such as shifting, the permutation method, and the polynomial method.
The attempt to find extremal families usually follows the determination of the maximum value of an extremal problem. A stability result then states that every family of almost extremal size possesses structures similar to the extremal families. Chapter 2 deals with a large variety of intersection theorems starting with a stability result of the Erdős-Ko-Rado theorem.
More-part Sperner families are discussed in Chapter 3. The classical Dedekind’s problem asks for the number of antichains in the power set of an \(n\)-element set. The determination of the aysmptotics of this number is useful in many areas. Upper bounds are proved in this chapter. This chapter ends with the latest progress on the well-known Frankl’s conjecture on union-closed families.
Chapter 4 addresses problems related to random versions of Sperner’s theorem and the Erdős-Ko-Rado theorem. Random subfamilies of the power set or \(k\)-uniform families are considered such that every set belongs to the family with probability \(p\) independently from all other sets. Topics discussed include largest intersecting families and the largest antichain, etc.
Chapter 5 gives generalizations of the well-known theorem of Turán in extremal graph theory to the context of hypergraphs. Versions covered include complete forbidden hypergraphs, graph-based forbidden hypergraphs, and hypergraph-based forbidden hypergraphs. Bounds on the Turán number or Turán density of specific hypergraphs are established. Various proof methods are described and some are briefly sketched, such as supersaturation, flag algebras, hypergraph regularity, and spectral method.
For a property \(\mathcal{P}\), a family is \(\mathcal{P}\)-saturated if that family satisfies property \(\mathcal{P}\), yet any addition of a new set to that family would fail to satisfy property \(\mathcal{P}\). In this context, interest lies in the smallest size of saturated families. Chapter 6 is devoted to saturation problems, including saturated hypergraphs, weak saturation, and saturating \(k\)-Sperner families.
Chapter 7 presents results in a rapidly growing area in extremal finite set theory. Note that any property described in the language of ordered sets can be translated to a property of set families. If a poset does not contain a weak copy of a poset \(P\), then it is callled \(P\)-free. A weak copy is the image of an order-preserving map from \(P\) to the target poset. Katona and Tarján introduced the problem of determining \(\operatorname{La}(n,P)\), the largest size of a \(P\)-free family in the power set of an \(n\)-element set. It is still an open problem to show that \(\pi(P) = \lim_{n \to \infty} \operatorname{La}(n,P)/{\binom{n}{\lfloor n/2 \rfloor}}\) exists for every poset \(P\). The main conjecture asserts that \(\pi(P)\) exists and is equal to the highest consecutive levels in the power set such that those levels form a \(P\)-free family. Investigations around this conjecture are surveyed. Induced versions of forbidden subposet problems are discussed, too. Finally, the reader’s attention is directed to problems of finding the maximum number of copies of a poset \(Q\) in families that do not contain a given poset \(P\).
The VC-dimension is a very useful notion having a lot of applications. The well-known Sauer lemma gives an upper bound on the size of a family having a prescribed upper bound on its VC-dimension. Chapter 8 begins with the task of characterizing equality cases in the Sauer lemma. Then special configurations that appear as traces are sought after.
Motivated by problems in combinatorial search theory, corresponding notions in set families are discussed in Chapter 9. They include families that are totally separable, \(d\)-separable, \(d\)-union-free, \(d\)-cover-free, and totally \(r\)-thin. In the case that answers to queries might be erroneous, modified models are treated. Finally, compromises can be worked out between adaptive and non-adaptive search algorithms.
The book concludes with a comprehensive bibliography of 556 items. This makes it a convenient reference book for people interested in the latest developments in extremal finite set theory.