Cocliques in the Kneser graph on point-hyperplane flags

aeb et al.

2007-06-17

Let V be a vector space of finite dimension n over F_{q}, with n > 0, and consider in the associated projective space P V the flags (P, H) consisting of an incident point-hyperplane pair, and call two such flags (P, H) and (P′, H′) adjacent when P ∉ H′ and P′ ∉ H.

Goal: find the chromatic number of this graph Γ.

Subgoal: find the largest cocliques, or all cocliques.

Progress so far: (i) chromatic number for n ≤ 3, (ii) all maximal cocliques for n ≤ 4, (iii) all largest cocliques.

People somehow involved: Tim, Jan, Andries, Aart, Arjeh, others?

1 Rank 1 matrices

Represent points by column vectors p and hyperplanes by row vectors h, then a point-hyperplane pair can be represented by the rank 1 matrix ph, and an incident point-hyperplane pair by the rank 1 matrix ph with hp = 0, that is, with tr ph = 0.

Given two incident point-hyperplane pairs x = ph and x′ = p′h′, they are nonadjacent when (hp′)(h′p) = 0, i.e., when tr xx′ = 0.

Thus, finding the maximal cocliques is equivalent to finding the intersection of the maximal totally isotropic subspaces for the symmetric bilinear form (x, y) = tr xy with the space of trace 0 rank-1 matrices.

2 Chamber-type maximal cocliques

Let F = (X_{1}, ..., X_{n−1}) be a chamber (maximal flag) in P V, that is, X_{i} is a subspace of V of vector space dimension i for all i, and X_{i} ⊆ X_{j} for i ≤ j. From F we construct the coclique C_{F} = {(P, H) | ∃i : P ⊆ X_{i} ⊆ H}. This coclique is maximal, and |C_{F} | = 1 + 2q + 3q^{2} + ... + (n − 1)q^{n−2}.

Theorem 1 Each coclique C satisfies |C| ≤ 1 + 2q + 3q^{2} + ... + (n − 1)q^{n−2}, and equality holds only if C = C_{F} for some chamber F.

3 The thin case

For q = 1 the graph can be identified with N := \binom{n}{2} copies of K_{2}, so every maximal coclique has size N and there are 2^{N} maximal cocliques. The graph is bipartite and has chromatic number 2.

4 Maximal cocliques

Let C be a maximal coclique.

Let f(n) = 1+2q +3q^{2} +...+(n−1)q^{n−2} = ((n−1)q^{n} −nq^{n−1} +1)/(q −1)^{2}. We show that |C| ≤ f(n). Proof by induction on n. For n = 1 the only

hyperplane is empty, and |C| = 0.

Lemma 2 Let U be a subspace of dimension m of V, with 0 < m < n. (i) If C contains all flags (P, H) with P ⊆ U ⊆ H, then |C| ≤ f(n). (ii) Otherwise, there is a flag (Q, K) ∈ C with Q ⊈ U and U ⊈ K, and the

number of (P, H) in C with P ⊆ U ⊆ H is at most \frac{q^{m}−1}{q−1}.\frac{q^{n−m}−1}{q−1} − q^{n−2}.

Proof (i) The coclique C does not contain any (P, H) with P ⊈ U and U ⊈ H. The number of (P, H) with P ⊆ U ⊆ H equals \frac{q^{m}−1}{q−1}.\frac{q^{n−m}−1}{q−1}. The number of (P, H) with P ⊈ U is at most f(n − m)q^{m}. (Indeed, these

have U ⊆ H, and we can look at the quotient V/U, mapping (P, H) to ((P + U)/U, H/U), finding at most f(n − m) flags there. Now each H/U has a single preimage H, and each (P + U)/U has q^{m} preimages P.)

Similarly, the number of (P, H) with U ⊈ H is at most f(m)q^{n−m}. (Indeed, these have P ⊆ U, and we can look at the subspace U, mapping (P, H) to (P, H ∩ U), finding at most f(m) flags there. Now each P has a single preimage P, and each H ∩ U has q^{n−m} preimages H.)

Altogether |C| ≤ \frac{q^{m}−1}{q−1}.\frac{q^{n−m}−1}{q−1} + f(n − m)q^{m} + f(m)q^{n−m} = f(n).

(ii) If there were no such (Q, K), we could add all (P, H) with P ⊆ U ⊆ H to C, but C is maximal. There are q^{m−1}.q^{n−m−1} flags (P, H) with P ⊆ U ⊆ H and P ⊈ K and Q ⊈ H. □

This lemma already implies an asymptotic version of our desired bound.

Corollary 3 The coclique bound holds for fixed n and sufficiently large q.

Proof Let (P_{i}, H_{i}) (i ∈ I) be a collection of flags in C, such that the P_{i} span V and the H_{i} have empty intersection. Assume that for each nonempty proper subset J of I there is a j ∈ J and an i ∈ I \ J such that P_{j} ⊈ H_{i}.

An arbitrary flag (P, H) in the coclique C defines the subset J = {j ∈ I | P_{j} ⊆ H}. For each i ∈ I \ J we have P ⊆ H_{i}. Since the H_{i} have empty intersection, the set J is nonempty. Since the P_{j} span V, the set J is a proper subset of I. Pick j ∈ J and i ∈ I \ J with P_{j} ⊈ H_{i}. We can go to the quotient V/P_{j}, and from P + P_{j} we can uniquely retrieve P_{j} = (P + P_{j}) ∩ H_{i}, so that the number of flags that belong to this J is at most f(n − 1). But then the total number of flags is at most 2^{|I|}f(n − 1).

Remains to pick such a set (P_{i}, H_{i}) (i ∈ I) with bounded I. Take a basis for the span of C, i.e., a maximal set of linearly independent flags (rank 1 matrices).

Then |I| ≤ n^{2} − 1. If the points P_{i} do not span V, they all lie in a hyperplane H, and that case was settled already. Similarly, the case where the H_{i} have non-empty intersection is OK. Given a nonempty proper subset J of I, put U := ⋂_{i∈I\J} H_{i}. If all P_{j} (j ∈ J) are contained in U, then again we are in a case that was settled. Indeed, suppose there is a flag (Q, K) ∈ C with Q ⊈ U and U ⊈ K. Pick a hyperplane H_{i} containing U but not Q and a point P_{j} contained in U but not in K. Now (h_{i}q)(kp_{j}) ≠ 0, but h_{i}(p_{m}h_{m})p_{j} = 0 for all m ∈ I (because h_{m}p_{j} = 0 for m ∉ J, and h_{i}p_{m} = 0 for m ∈ J), contradiction. □

Let Y have codimension 1 in V, and consider for point-hyperplane flags (P, G) in Y in how many ways they extend to flags (P, H) ∈ C (where G = H ∩ Y). Clearly, this number is either 0 or 1 or q, and if it is q then also (P, Y) ∈ C.

Lemma 4 (i) Let Y have codimension 1 in V, and suppose that the two pointhyperplane flags (P, G′) and (P, G′′) in Y both extend to q flags (P, H) ∈ C. Then all point-hyperplane flags (P, G) in Y with G ⊃ G′ ∩ G′′ extend to q flags (P, H) ∈ C.

(ii) Let Y have codimension 1 in V, and suppose that the two point-hyperplane flags (P′, G) and (P′′, G) in Y both extend to q flags (P, H) ∈ C. Then all pointhyperplane flags (P, G) in Y with P ⊂ P′ + P′′ extend to q flags (P, H) ∈ C.

Proof (i) If G = H ∩ Y and (P, H) ∉ C, then there is a flag (Q, K) ∈ C with P ⊈ K and Q ⊈ H. Now (P, G′) extends to (P, H_{i}) (i = 1, 2) and (P, G′′) extends to (P, H_{i}) (i = 3, 4), and H_{1} ∩ H_{2} ∩ H_{3} ∩ H_{4} = G′ ∩ G′′ ⊂ G ⊂ H so Q ⊈ H_{j} for some j, say j = 1, and hence P ⊆ K, contradiction.

(ii) This part is obvious. □

...rest to be added...

5 Very low dimensions

For n = 1 the graph has no vertices, there is a single maximal coclique namely the empty set of size 0. The chromatic number is 0.

For n = 2 the graph is the complete graph on q + 1 vertices, there are q + 1 maximal cocliques {(P, P)}, each of size 1. The chromatic number is q + 1.

For n = 3 there are two types of maximal cocliques. There are the cocliques C_{F} of size 2q + 1, and the cocliques {(P_{i}, L_{i})|i = 0, 1, 2} where the three points P_{i} form a triangle, and the line L_{i} is the span P_{i} + P_{i+1}. For the chromatic number, see below.

For n = 4 see below.

6 Chromatic number for the projective plane

There are two types of maximal coclique for the plane: the cocliques C_{F} (of size 2q + 1) where F is a flag (P, L), and the triangle (of size 3).

6.1 Colorings using colors C_{F} only

A natural first problem to consider is that of covering the vertex set with cocliques of type C_{F}. We show that such a covering has size at least (q +1)(q +1− \sqrt{q}), and there are infinitely many examples with equality. (Thanks to Aart.)

Our job is to find a smallest set of flags (P_{i}, L_{i}) (1 ≤ i ≤ t) such that for any flag (Q, M) either Q is one of the P_{i} or M is one of the L_{i} (or both).

Let X be the set of points that do not occur as P_{i}, and Y the set of lines that do not occur as L_{i}. Then there are no edges between X and Y in the bipartite point-line incidence graph of the plane. Now a standard interlacing result (today, see ipm.pdf, Corollary 4.8) yields (q + 1)^{2}|X|.|Y | ≤ q(q^{2} + q + 1 − |X|)(q^{2} + q + 1 − |Y |), which says that (q + 1)^{2}(q^{2} + q + 1 − t)^{2} ≤ qt^{2}, that is, t ≥ (q + 1)(q + 1 − \sqrt{q}), as claimed.

For any q there is a covering of size t = q^{2} + 1. (Take a flag (P, L), and let X be the set of points not on L and Y the set of lines not on P. Then X ∪ Y induces a regular bipartite graph and has a matching of size q^{2}.)

When q is an even power of 2, there is a covering of size t = (q+1)(q+1−\sqrt{q}). (Take a (0, \sqrt{q})-arc and its exterior lines.)

6.2 The general case

Now go back to the original problem. We show that it is never necessary to use triangles: given a coloring using triangles we can find a coloring with the same number of colors and fewer triangles.

Each proper subset of a triangle is also contained in a C_{F}, so if a triangle cannot be replaced by a C_{F} then all three flags are covered by the triangle only, not by some other coclique. In particular, the three flags in the opposite triangle (with flags (X_{i}, X_{i−1} + X_{i}) instead of flags (X_{i}, X_{i} + X_{i+1})) are also covered by triangles only, not by flags C_{F}.

Let X be a point incident with the m triangle edges X + X_{i} (1 ≤ i ≤ m). Remove the m triangles involved (each with a unique flag (X, X + X_{i})) and replace them with the m sets C_{F_{i}} with F_{i} = (X_{i}, X + X_{i}). This yields a new coloring with as many colors and fewer triangles.

This shows that (q + 1)(q + 1 − \sqrt{q}) ≤ χ ≤ q^{2} + 1, where the lower bound holds with equality infinitely often. (The upper bound holds with equality for q = 2, 3.)

7 Projective 3-space

Let us first give the classification of the maximal cocliques ordered by size, and describe their structure below. There are ten types, each a single orbit of P GL(4, q). Write K := (q^{3} + q^{2} + q + 1)(q^{2} + q + 1)(q + 1), so that P GL(4, q) has order q^{6}(q −1)^{3}K. The number N of maximal cocliques of a given type is of course a divisor of |P GL(4, q)|, and |P GL(4, q)|/N is the size of the stabilizer.

type  size  number  note
1  3q^{2} + 2q + 1  K
2, 2′ q^{2} + 4q + 1  \frac{1}{3}q^{3}K
3  4q + 2  q^{5}K
4  2q + 4  (q − 1)q^{6}K
5, 5′  q + 5  \frac{1}{3}(q − 1)^{2}q^{6}K
6a  6  \frac{1}{4}(q − 1)^{2}q^{6}K
6b  6  (q − 1)^{3}q^{6}K
6c  6  \frac{1}{3}(q − 1)^{3}q^{6}K for p ≠ 2 only
7  7  \frac{1}{21}(q − 1)^{3}q^{6}K for p = 2 only

Types 2′ and 5′ are the duals of 2 and 5, respectively. The cocliques of type 6c are maximal only for p ≠ 2, but for p = 2, these 6-cocliques extend to the 7-cocliques of type 7. For q = 1 only types 1, 2, 2′, 3 occur (and altogether there are 64 maximal cocliques).

Geometric description of these types:

(1) C_{F} for some chamber F.

(2) All (P, H_{0}) for a fixed plane H_{0}, and in the residue of H_{0} a triangle.

(3) Pick three planes H_{0}, J_{0}, K_{0} meeting in a point S, and pick a point R in J_{0} ∩ H_{0} distinct from S, and a point T in H_{0} ∩ K_{0} distinct from S. The coclique consists of the flags (P, H_{0}) with P ⊂ H_{0} ∩ K_{0}, and the flags (Q, K_{0}) with Q ⊂ J_{0} ∩ K_{0}, and the flag (R, J_{0}), and the flags (T, H) with R + T ⊂ H, and the flags (S, H) with S + T ⊂ H.

(4) Pick a plane H_{0} and a line L_{0} in H_{0}, and a triangle P_{1}, P_{2}, P_{3} in H_{0} of which only the point P_{1} lies on L_{0}, and a point Q outside H_{0}. Put L_{i} = P_{i}+P_{i+1} (indices mod 3). The coclique consists of the flags (P, H_{0}) with P ⊂ L_{0} and the flags (P_{1}, H) with L_{1} ⊂ H, and the three flags (Q, L_{0} + Q), (P_{2}, L_{2} + Q), (P_{3}, L_{3} + Q).

(5) Pick a plane H_{0} and a line L_{0} in H_{0}, and a triangle P_{1}, P_{2}, P_{3} in H_{0} where none of the P_{i} lies on L_{0}, and a point Q outside H_{0}. Put L_{i} = P_{i} + P_{i+1} (indices mod 3). The coclique consists of the flags (P, H_{0}) with P ⊂ L_{0}, and the four flags (Q, L_{0} + Q), (P_{i}, L_{i} + Q) (i = 1, 2, 3).

(6A) Pick two skew lines L, M and three distinct points P, Q, R on L, and three distinct points A, B, C on M. The coclique consists of the six flags (P, B +P +Q), (Q, C +P +Q), (R, B +C +R), (A, A+P +Q), (B, A+B +Q), (C, A + C + P).

(6B) Pick a line L, and three distinct points P, Q, R on L, and pick three distinct points A, B, C not on L such that A, B, C are not collinear, but A, B, C, P are coplanar. The coclique again consists of the six flags (P, B + P + Q), (Q, C +P +Q), (R, B +C +R), (A, A+P +Q), (B, A+B +Q), (C, A+C +P).

(6C) Pick points X_{i}, Y_{i}, S, T (i = 1, 2, 3) represented by vectors x_{i}, y_{i}, s, t where the four vectors x_{i}, s are independent, and t = x_{1} + x_{2} + x_{3} + s, and y_{i} = x_{i} + x_{i+1} + s. The coclique consists of the six flags (X_{i}, X_{i} + X_{i+1} + S), (Y_{i+2}, X_{i} + X_{i+1} + Y_{i+2}) (i = 1, 2, 3).

(7) Pick a plane H_{0} and a point Q outside H_{0}. Pick a point P outside H_{0} and distinct from Q and a plane H on P, not on Q. The coclique consists of the flags in the orbit of the (P, H) under suitable a group element π of order 7 fixing the plane H_{0} and the point Q. Label the points of H_{0} with 0,1,2,3,4,5,6 such that π acts like i ↦ i + 1 (mod 7). Let H ∩ H_{0} = {1, 2, 4} and let (P + Q) ∩ H_{0} = {0}.

8 Dimension and lower bound

Instead of asking for the size of a maximal coclique, one can ask for the dimension of its span in the space of matrices of order n.

It is easy to get an upper bound \frac{1}{2}n^{2} for this dimension: The span of a maximal coclique C is totally isotropic for the symmetric bilinear form f(x, y) = tr xy. Now f is nondegenerate on the space of matrices of order n, and the subspace of matrices of trace 0 is ⟨I⟩^{⊥}. For p ∤ n it follows that dim⟨C⟩ ≤ \frac{1}{2}(n^{2} − 1) and for p | n that dim⟨C⟩ ≤ \frac{1}{2}n^{2}.

Maybe the truth is just 1 lower: for n = 3, 4, 5, 6 and q = 2 the largest dimension seen so far is 3, 7, 11, 17 (instead of 4, 8, 12, 18).

Concerning the lower bound for |C| and dim⟨C⟩, for n ≤ 5 the smallest seen is \binom{n}{2}, but for n = 6 there are examples with dim⟨C⟩ = 13 and |C| = 14.

At first sight the obvious lower bounds are linear in n.

9 Association scheme

We have a noncommutative 6-class association scheme, with the following seven relations between two flags (P, H) and (P′, H′): 0. (P, H) = (P′, H′), 1a. P = P′ and H ≠ H′, 1b. H = H′ and P ≠ P′, 2. not 0,1,1’ but P ∈ H′ and P′ ∈ H, 3a. P ∈ H′ but not P′ ∈ H, 3b. P′ ∈ H but not P ∈ H′, 4. Neither P ∈ H′ nor P′ ∈ H.

... add parameters and P and Q matrices for 4-class merged scheme ...