Multicoloured extremal problems (Q1883144): Difference between revisions

Let \({\mathcal A}_1,\dots,{\mathcal A}_k\) be set systems on the finite underlying set \(X\) which are called colours. A finite configuration of subsets of \(X\) with \(f\) elements is multicoloured (for this set of colours) if one can find a listing \(H_1,\dots,H_f\) of the configuration and a permutation \(\pi\) of \(\{1,\dots,k\}\) such that \(H_i\) belongs to \({\mathcal A}_{\pi(i)}\) for all \(i\). A very general extremal problem class can be formulated as follows: Assume there is a list of forbidden configurations, and a natural number \(k.\) Find \(k\) set systems, that is, \(k\) colours with maximum total number of elements such that there is no multicoloured forbidden configuration (for this set of colours). If \(k=2\) and the two colour families are the same then we may get back to the classical extremal problems: If the forbidden configuration is a two-element chain, then we have the Sperner problem, while two disjoint subsets give us the Erdős-Ko-Rado problem. If, in more generality, we have \(k\) identical colour classes and the forbidden configuration is a \(k\)-chain, then we get back to the classical Erdős problem on \(k\)-chains. The problem for two-uniform colour systems (graphs) was introduced by the second author and the third author (with others). The paper under review starts a systematic investigation of the general problem. Results on multicoloured chains, intersecting set systems and Sauer-Shelah type set systems are proved.