Erdős-Ko-Rado sets of flags of finite sets (Q2154325)

A flag of a finite set \(S\) is a set \(f\) of non-empty proper subsets of \(S\) such that \(A\subseteq B\) or \(B\subseteq A\) for all \(A,B\in f\). For a flag \(f\), the set \(\{|A| : A \in f\}\) is called the type of \(f\). Two flags \(f\) and \(f'\) are in general position (with respect to the set \(S\)), when for all \(A\in f\) and \(B\in f'\) we have \(A\cap B =\emptyset\) or \(A\cup B = S\). In the paper, sets of flags of a fixed type that are mutually not in general position are investigated. In particular, in several non-trivial cases, the largest cardinality of such sets of flags is given. For this, graphs were defined whose vertices are flags of a set \(S\) of a given type \(T\), and two vertices are adjacent when the corresponding flags are in general position; such graphs are denoted by \(\Gamma(S, T)\), or \(\Gamma(n, T)\) in the case when \(S=[n]\), where \([n]:=\{1,\ldots,n\}\). With this notation, the problem to find the largest cardinality of sets of flags of \(S\) of type \(T\) which are mutually not in general position is equivalent to determining the independence number of the graph \(\Gamma(S, T)\). For example, it is shown that for positive integers \(b\) and \(n\) and every non-empty subset \(T\) of \([n]\) with \(\max(T) + 3b \leq 2n < 4b\), the independence number of the graph \(\Gamma(n, T \cup \{b\})\) is equal to \(\binom{n-1}{b}\cdot |V(\Gamma(b, T))|\), where \(V(\Gamma(b, T))\) denotes the set of vertices of the graph \(\Gamma(b, T)\).