Cocliques in the Kneser graph on line-plane flags in \(\mathrm{PG}(4, Q)\)
type: Item
instance of: scholarly article
title: Cocliques in the Kneser graph on line-plane flags in \(\mathrm{PG}(4, Q)\)
zbMATH Open document ID: 1399.05120
author: Aart Blokhuis
author: Andries E. Brouwer
published in: Combinatorica
publication date: 2018-07-23T00:00:00Z
review text: 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.
reviewed by: Eleonor Ciurea
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 51E20
Mathematics Subject Classification ID: 05D05
zbMATH DE Number: 6909471
zbMATH Keywords: extremal problems
zbMATH Keywords: independent sets
zbMATH Keywords: cliques
zbMATH Keywords: combinatorial structures in finite projective spaces
MaRDI profile type: Publication
full work available at URL: s00493-016-3438-2
OpenAlex ID: W2466850915
cites work: Cocliques in the Kneser graph on the point-hyperplane flags of a projective space
cites work: Maximal cocliques in the Kneser graph on point-plane flags in \(\mathrm{PG}(4,q)\)
cites work: INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
cites work: The Erdős-Ko-Rado theorem for vector spaces
DOI: 10.1007/S00493-016-3438-2
description: scientific article; zbMATH DE number 6909471