Cocliques in the Kneser graph on ( n − 1 , n ) (n-1,n) -flags of PG ( 2 n , q ) \PG(2n,q)
Philipp Heering · 2026
Read Cocliques in the Kneser graph on ( n − 1 , n ) (n-1,n) -flags of PG ( 2 n , q ) \PG(2n,q) by Philipp Heering (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-09769.txt.
Introduction
Philipp Heering studies largest sets of pairwise non opposite flags in a finite projective space, viewed as a Kneser graph. The flags pair a smaller subspace with a larger one that contains it. Using a matching theorem for vector spaces, he finds the biggest cocliques when the field is large enough. A stability result comes with the answer, settling a stated conjecture.
Catalog record
| CREATOR | Philipp Heering |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31593 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.09769
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Cocliques in the Kneser graph on ( n − 1 , n ) (n-1,n) -flags of PG ( 2 n , q ) \PG(2n,q) Philipp Heering Abstract Abstract In the finite projective space PG (2n,q) we consider flags of type (n-1,n) , that is, pairs (A,B) consisting of an (n-1) -space A and an n -space B that are incident. Two such flags (A_{1},B_{1}) and (A_{2},B_{2}) are opposite if A_{1}\cap B_{2}=A_{2}\cap B_{1}=\emptyset . Let \Gamma_{2n} be the graph whose vertices are the flags of type (n-1,n) of PG (2n,q) , with two vertices being adjacent if the corresponding flags are opposite. Using the Erdős-Matching theorem for vector spaces shown by Ihringer, we determine, for q large enough, the largest cocliques of \Gamma_{2n} and obtain a stability result. This EKR-type theorem proves a conjecture of D’haeseleer, Metsch and Werner. Keywords: Erdős-Ko-Rado, generalized Kneser graph, coclique MSC (2020): 05C69, 51E20, 05C35 1 Introduction Consider the projective space \PG(2n,q) of dimension 2n . An i -space of \PG(2n,q) is a subspace of \PG(2n,q) with projective dimension i , in particular a 0 -space is a point, a 1 -space is a line and so on. Now, consider an (n-1) -space A and an n -space B of \PG(2n,q) . If A is contained in B , we call (A,B) an (n-1,n) -flag of \PG(2n,q) . Two such flags (A_{1},B_{1}) and (A_{2},B_{2}) are called opposite if A_{1}\cap B_{2}=A_{2}\cap B_{1}=\emptyset . For n\geq 2 let \Gamma_{2n} be the graph whose vertices are the (n-1,n) -flags of \PG(2n,q) , with two vertices being adjacent if the corresponding flags are opposite. We want to study cocliques of \Gamma_{2n} . This research falls under the umbrella of Erdős-Ko-Rado (EKR) problems and similar problems have been studied [ 2 , 3 , 5 , 13 , 17 ] . In fact, the problem we are concerned with is a direct generalization of previous work. Cocliques of \Gamma_{2n} were studied by Blokhuis and Brouwer [ 4 ] for n=2 and by Metsch and Werner [ 16 ] for n=3 . Out of all the EKR problems for flags, the problem for chambers of spherical buildings has enjoyed the most attention in recent years. In [ 6 , 7 , 11 ] the largest EKR sets for chambers of odd dimensional projective spaces were characterized for q large enough. On the other hand, for the EKR problem on chambers of even dimensional projective spaces very few results are known. The case \PG(2,q) is probably folklore. The case \PG(4,q) was solved in [ 12 ] for q large. However, the proof of [ 12 ] regarding the EKR problem for chambers of \PG(4,q) , relies on a description of the largest cocliques of \Gamma_{2n} for n=2 [ 4 ] . In particular [ 12 ] relies also on the existence of a stability version of the results of [ 4 ] , which can be found in [ 8 ] . This suggests that studying the largest cocliques of \Gamma_{2n} may be helpful when attacking the EKR problem for chambers of \PG(2n,q) . Next up, we describe large cocliques for \Gamma_{2n} . Example 1.1 . (a) Let H be a hyperplane of \PG(2n,q) and let X be either (i) a point of H , or (ii) an (2n-2) -space incident with H . Now, let \mathcal{F} be the set of all (n-1,n) -flags such that for every (A,B)\in\mathcal{F} we have B\subseteq H , or A is incident with X and H . (b) Let P be a point of \PG(2n,q) and let X be either (i) a hyperplane incident with P , or (ii) a line incident with P . Now, let \mathcal{F} be the set of all (n-1,n) -flags such that for every (A,B)\in\mathcal{F} we have P\subseteq A , or B is incident with X and P . It was already observed in Theorem 5.1 of [ 4 ] that the construction of Example 1.1 does not contain opposite flags, i.e. the construction yields a coclique of \Gamma_{2n} . Observe that parts (a) and (b) of Example 1.1 are dual to one another. There is also some form of duality between the parts (i) and (ii) . Consider for example case (a) , then X is either a point or a hyperplane of H . Next up, we want to count how many flags are in a set \mathcal{F} as described in Example 1.1 as a warmup. Beforehand, we recall here the definition of the Gaussian coefficient. \displaystyle{\begin{bmatrix}b\\ a\end{bmatrix}_{q}}=\begin{cases}\displaystyle\prod_{i=1}^{a}\frac{q^{b-a+i}-1}{q^{i}-1}&\text{if $0\leq a\leq b$,}\\ 0&\text{otherwise.}\end{cases} We remark that we expect the reader to be moderately familiar with combinatorics in projective spaces. The term {\begin{bmatrix}b\\ a\end{bmatrix}_{q}} is a q -polynomial of degree a(b-a) , so in particular {\begin{bmatrix}b\\ a\end{bmatrix}_{q}} is \mathcal{O}(q^{a(b-a)}) . Now, we count the size of the set \mathcal{F} as described in Example 1.1 (a)(i) and remark that duality implies that all constructions described in Example 1.1 have the same size. The number of n -spaces incident with a hyperplane H of \PG(2n,q) is {\begin{bmatrix}2n\\ n+1\end{bmatrix}_{q}} . Each such n -space contains exactly {\begin{bmatrix}n+1\\ 1\end{bmatrix}_{q}} many (n-1) -spaces. The number of (n-1) -spaces incident with the point X and the hyperplane H is {\begin{bmatrix}2n-1\\ n-1\end{bmatrix}_{q}} . Each such (n-1) -space is incident with exactly q^{n} many n -spaces that are not contained in H . Thus the set in question has size {\begin{bmatrix}2n\\ n+1\end{bmatrix}_{q}}{\begin{bmatrix}n+1\\ 1\end{bmatrix}_{q}}+{\begin{bmatrix}2n-1\\ n-1\end{bmatrix}_{q}}q^{n} . In order to state our main result we need one more definition. \displaystyle f(n,q):=\left\{\begin{array}[]{ll}3{\begin{bmatrix}n\\ 1\end{bmatrix}_{q}}{\begin{bmatrix}2n-2\\ n-2\end{bmatrix}_{q}}&\text{if $n\geq 4$ and $q\geq 4$,}\\ q^{5}+2q^{4}+3q^{3}+2q^{2}+q+1&\text{if $n=3$,}\end{array}\right. Theorem 1.2 . For n\geq 3 let \Gamma_{2n} be the graph whose vertices are the (n-1,n) -flags of \PG(2n,q) , with two vertices being adjacent if the corresponding flags are opposite. For q large enough compared to n , a maximal coclique \mathcal{F} of \Gamma_{2n} falls into exactly one of the following categories. (a) |\mathcal{F}|={\begin{bmatrix}2n\\ n-1\end{bmatrix}_{q}}{\begin{bmatrix}n+1\\ 1\end{bmatrix}_{q}}+{\begin{bmatrix}2n-1\\ n-1\end{bmatrix}_{q}}q^{n} and \mathcal{F} is one of the structures described in Example 1.1 . (b) |\mathcal{F}|\leq{\begin{bmatrix}2n\\ n-1\end{bmatrix}_{q}}{\begin{bmatrix}n+1\\ 1\end{bmatrix}_{q}}+f(n,q)\cdot q^{n} and there is either a hyperplane H , such that \mathcal{F} contains all flags (A,B) with B\subseteq H , or there is a point P such that \mathcal{F} contains all flags (A,B) with P\subseteq A . (c) |\mathcal{F}| is at most \mathcal{O}(q^{n^{2}+n-2}) . It is quickly checked that f(n,q)<{\begin{bmatrix}2n-1\\ n-1\end{bmatrix}_{q}} for large q , as {\begin{bmatrix}2n-1\\ n-1\end{bmatrix}_{q}} is a q -polynomial of degree (n-1)n , whereas f(n,q) is a q -polynomial of degree (n-1)+(n-2)n=(n-1)n-1 . For n=3 the theorem follows from [ 16 ] . We remark that it is possible to derive a more explicit bound in case (c) from our proof. As this would add only marginal insight but substantially complicate the paper, we omit this. It is noteworthy that our proof uses the EKR and Hilton-Milner Theorems for vector spaces. The key ingredient, however, is the Erdős-Matching Theorem for vector spaces, which was proven by Ihringer in 2021. In 2023 the chromatic number of \Gamma_{2n} was determined modulo a conjecture by D’haeseleer, Metsch and Werner [ 9 ] . Theorem 1.2 is precisely the confirmation that their conjecture is true. Therefore, by proving Theorem 1.2 we immediately get the following. Corollary 1.3 . For q large enough, the chromatic number of \Gamma_{2n}