Cocliques in the Kneser graph on line-plane flags in PG(4, q)
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.
- Cocliques in the Kneser graph on the point-hyperplane flags of a projective space
- Maximal cocliques in the Kneser graph on plane-solid flags in \(\mathrm{PG}(6,q)\)
- On the chromatic number of \(q\)-Kneser graphs
- Erdős-Ko-Rado theorem, Grassmann graphs and \(p^s\)-Kneser graphs for vector spaces over a residue class ring
- The chromatic number of two families of generalized Kneser graphs related to finite generalized quadrangles and finite projective 3-spaces
- An EKR-theorem for finite buildings of type \(D_{\ell }\)
- The chromatic number of two families of generalized Kneser graphs related to finite generalized quadrangles and finite projective 3-spaces
- Maximal cocliques in the Kneser graph on plane-solid flags in \(\mathrm{PG}(6,q)\)
- On the chromatic number of two generalized Kneser graphs
- An algebraic approach to Erdős-Ko-Rado sets of flags in spherical buildings
- Maximal cocliques in the Kneser graph on point-plane flags in \(\mathrm{PG}(4,q)\)
- Cocliques in the Kneser graph on the point-hyperplane flags of a projective space
- The unique coclique extension property for apartments of buildings
- On the chromatic number of some generalized Kneser graphs
- Maximal cocliques and the chromatic number of the Kneser graph on chambers of \(\mathrm{PG}(3, q)\)
- On the largest independent sets in the Kneser graph on chambers of \(\mathrm{PG}(4, \mathrm{q})\)
This page was built for publication: Cocliques in the Kneser graph on line-plane flags in \(\mathrm{PG}(4, q)\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722306)
