On the maximum size of \((p,Q)\)-free families
For a given integer \(p\) and a subset \(Q\) of \(\{0,1,\dots,p\}\), a family \(\{A_1,\dots,A_p\}\) of subsets of a set \(X\) is called a \((p,Q)\)-system, if \(|\{i\mid x\in A_i\}|\in Q\). A family \(\mathcal F\) on a set \(X\) is called \((p,Q)\)-free if no \(p\) sets of \(\mathcal F\) form a \((p,Q)\)-system. Denote \(f(n,p,Q)=\max|\mathcal F|\), where \(n=|X|\) and the maximum is running over all \((p,Q)\)-free families on \(X\). The authors survey the known results for the cases \(f(n,p,Q)=o(2^n)\) and \(2^n-(2-c)^n < f(n,p,Q)\) and emphasize the middle zone \(2^{n-1}\leq f(n,p,Q) \leq (1-c)2^n\). They provide a number of lower and upper bounds for particular \(Q\)'s and also several sharp results.
scientific article; zbMATH DE number 1839000