Erdős-Ko-Rado with conditions on the minimum complementary degree (Q1763872)

The starting point of the paper under review is the Erdős-Ko-Rado theorem, which gives a bound on the size of an intersecting set system \(\mathcal F\) of \(k\)-element subsets of an \(n\)-element set \(X\) (with \(2k < n\)), where the extremal \(\mathcal F\) consists of all \(k\)-sets containing a fixed element. Here results of \textit{P. Frankl} [J. Comb. Theory, Ser. A 46, 252-263 (1987; Zbl 0661.05002)] and \textit{A. J. W. Hilton} and \textit{E. C. Milner} [Q. J. Math., Oxf. II. Ser. 18, 369-384 (1967; Zbl 0168.26205)] are generalized. The main result is a characterization of complementary degree condition maximal (CDCM) and strict complementary degree condition maximal (SCDCM) intersecting families, where the minimum complementary degree \(c({\mathcal F})\) of an intersectig system \(\mathcal F\) is the minimum over all \(i\in X\) of the number of sets in \(\mathcal F\) not containing \(i\) and \(\mathcal F\) is CDCM if, whenever \({\mathcal H}\subseteq X^{(k)}\) is intersecting, \(c({\mathcal H})\geq c({\mathcal F})\Rightarrow| {\mathcal H}| \leq| {\mathcal F}| \), and \(\mathcal F\) is SCDCM if it is CDCM and equality holds on the right of the implication only if it holds on the left. The characterization is in terms of a representation of \(c(\mathcal F)\) as sums of certain binomial coefficients (cascade representation). The number of isomorphically distinct systems \(\mathcal F\) which are SCDM is shown to be a Catalan number, and the number which are CDM is expressed as a sum of Catalan numbers. A detailed example illustrating the ideas of the paper, as well as a graphical interpretation of the main results is provided.