Cocliques in the Kneser graph on line-plane flags in \(\mathrm{PG}(4, q)\) (Q722306)

A clique \(C\) in an undirected graph is a subset of vertices of graph such that every two distinct vertices are adjacent. This is equivalent to the condition that the induced graph, induced by \(C\) is a complete graph. A coclique \(\bar{C}\) in an undirected graph is a subgraph whose complement is a clique \(C\), i.e. an independent set. The Kneser graph \(K(n,k)\) is a graph whose vertices are the \(k\)-element subsets of a set of \(n\) elements, and two vertices are adjacent if and only if the two corresponding sets are disjoint. In this paper, the authors determine the independence number of the Kneser graph on line-plane flags in the projective space \(\mathrm{PG}(4,q)\) and also classify the corresponding maximum-size cocliques. The problem studied in this paper is a special case of a variation of the Erdős-Ko-Rado theme. The work is structured into five sections. In Section 1, the graph \(\Gamma\) is presented that has independence number \((q^2+q+1)(q^3+2q^2+q+1)\). The authors present four ways for the construction of cocliques of size \((q^2+q+1)(q^3+2q^2+q+1)\) in Section 2. In the rest of the paper the authors show that these four ways are the maximum-sized cocliques in \(\Gamma\), thus the authors obtain the following result: the independence number of \(\Gamma\) is \((q^2+q+1)(q^3+2q^2+q+1)\) and the maximum-sized cocliques are precisely the four ways presented in Section 2.