Graphs that are locally the point-hyperplane antiflag graph of a projective space

A.E. Brouwer

2002-01-16

Abstract If H_{n} is the graph on the point-hyperplane antiflags of a projective space, where (x, X) is adjacent to (y, Y) when x ∈ Y and y ∈ X, then H_{n+1} is locally H_{n}. When n ≥ 3 there are no other connected locally H_{n} graphs.

1 Introduction

In [G], Ralf Gramlich proves for n ≥ 5 that the only connected locally H_{n} graphs are the graphs H_{n+1}. Moreover, that the same holds under a group-theoretical assumption for n ≥ 3. We remove the group-theoretical assumption (and fill a gap in that proof). [Seminar talk, 2002-01-16.]

2 The graphs H_{n}

Given a projective space S of projective dimension n, let H_{n} = H(S) be the graph of which the vertices are the point-hyperplane antiflags, that is, the pairs (x, X) where x is a point and X is a hyperplane in the projective space S, and x ∉ X, where (x, X) is adjacent to (y, Y) when x ∈ Y and y ∈ X.

2.1 H_{n+1} is locally H_{n}

Given a graph Γ, its local graph at a vertex γ is the graph induced by Γ on the set of neighbours of γ in Γ.

Now let S be a projective space with hyperplane X, and let X be the projective space induced on X by S. Let x be a point of S outside X. Then the local graph of H(S) at (x, X) is naturally isomorphic to H(X). Indeed, the map (y, Y) ↦ (y, X ∩Y) maps the set of neighbours of (x, X) in H(S) onto the vertex set of H(X). It is injective, the inverse is (a, A) ↦ (a, ⟨A, x⟩), and both map and inverse preserve adjacency.

2.2 μ-graphs

Given a graph Γ and a family of sets C = (C_{γ}) indexed by the vertices of Γ, the C-coclique extension of Γ is the graph of which the vertex set is the set of pairs (γ, c) with c ∈ C_{γ}, where (γ, c) is adjacent to (δ, d) when γ is adjacent to δ. This graph is called C ∗ Γ. In the particular case where all sets C_{γ} have the same cardinality q, we also denote the (isomorphism type of) this graph by q ∗ Γ.

Let ξ = (x, X) and η = (y, Y) be vertices of H_{n} = H(S). Then the graph M induced on the set of common neighbours of ξ and η is a coclique extension of a graph H(T ) for some projective space T of dimension n − 1 or n − 2 or n − 3.

Let us consider the possible cases. There are eight, or perhaps six, or really only four cases.

2.2.1 H_{n−1}

If x = y and X = Y then ξ = η and M is the local graph at ξ, isomorphic to H_{n−1} as we already observed.

2.2.2 H_{n−2}

If x ≠ y and X ≠ Y and ⟨x, y⟩ ∩ X ∩ Y = ∅, then M is naturally isomorphic to H(M) where M is the projective space induced on X ∩ Y. Indeed, the map (z, Z) ↦ (z, X ∩ Y ∩ Z) is an isomorphism, with inverse (a, A) ↦ (a, ⟨A, x, y⟩).

(Note that this covers four possible relations of ξ and η: (i) x ∈ Y and y ∈ X, (ii) x ∈ Y and y ∉ X, (ii)’ x ∉ Y and y ∈ Y, (iii) x ≠ y and X ≠ Y and x ∉ Y and y ∉ X and ⟨x, y⟩ ∩ X ∩ Y = ∅.)

2.2.3 q ∗ H_{n−2}

If x = y and X ≠ Y, or x ≠ y and X = Y, then M is naturally isomorphic to q ∗ H(M) where q + 1 is the cardinality of a projective line and M is a projective space of dimension n − 2.

Indeed, if x = y and X ≠ Y, then let M be the projective space induced on X ∩Y. The map (z, Z) ↦ (z, X ∩Y ∩Z) from M onto H(M) preserves adjacency and nonadjacency, and the inverse image of each vertex has cardinality q.

The case x ≠ y and X = Y is dual.

2.2.4 q^{2} ∗ H_{n−3}

Finally, if X ≠ Y and ⟨x, y⟩ ∩ X ∩ Y = {s}, then M is naturally isomorphic to q^{2} ∗ H(M) where M is the projective space consisting of the subspaces of S containing s and contained in X ∩ Y. The map (z, Z) ↦ (⟨s, z⟩, X ∩ Y ∩ Z) preserves adjacency and nonadjacency, and the inverse image of each vertex has cardinality q^{2}.

2.3 Connectedness and diameter

Lemma 2.1 H_{n} is connected with diameter 2 for n ≥ 3. H_{2} is connected with diameter 3. H_{1} is disconnected, every component is reduced to a single edge. H_{0} is a single vertex. H_{−1} is empty.

Proof: Projective spaces have a dimension that is greater than or equal to −1, so we can consider H_{n} for n ≥ −1.

A projective space of dimension −1 has no points, so no point-hyperplane antiflags, and H_{−1} is empty.

A projective space of dimension 0 has a unique point, and a unique hyperplane (the empty set), so there is a unique antiflag, and H_{0} consists of a single vertex.

A projective space of dimension 1 is a projective line, and hyperplanes are points, so our graph has as vertices the ordered pairs of points (x, y), where (x, y) has a unique neighbour, namely (y, x). That is, H_{1} is a disjoint union of edges, and is not connected.

The above determination of the set of common neighbours of two vertices shows that that set contains at least H_{n−3}, so is nonempty for n ≥ 3. That is, H_{n} is connected with diameter 2 for n ≥ 3.

For n = 2 there are distinct vertices without common neighbours, but one immediately sees that if ξ and η are vertices without common neighbours then η has a neighbour ζ that does have a common neighbour with ξ, so H_{2} is connected with diameter 3. □

2.4 Recognition

Given the graph H_{n}, we can reconstruct the projective space it was derived from, up to duality.

Above we considered four possible relations between two vertices. Can these be distinguished? The maximal cliques in q ∗ H_{n} have cardinality n + 1. Any subset of a maximal clique of q ∗ H_{n} obtained by removing a single point is contained in q maximal cliques. In particular, given q ∗ H_{n} one can recognize the cardinal numbers q and n.

Thus, if n is finite and n ≥ 2, the four possible relations can be recognized. Otherwise, consider the relation between two distinct vertices ξ = (x, X) and η = (y, Y). If X = Y, then the set of common neighbours of ξ and η strictly contains the set of common neighbours of ξ and ζ for ζ = (y, Z) and Z ≠ Y. And similarly for the case x = y. On the other hand, when x ≠ y and X ≠ Y then the set of common neighbours of ξ and η does not properly contain some other set of common neighbours of two vertices. It follows that the relation “x = y or X = Y ” can be recognized, and then also the other three relations.

The graph on the vertex set of H_{n}, with n ≥ 2, where two distinct vertices are adjacent when they are in this relation “same point or same hyperplane”, has maximal cliques corresponding to “same point” and maximal cliques corresponding to “same hyperplane”. Each edge is in a unique maximal clique, and the graph on these maximal cliques, where two maximal cliques are adjacent when they meet, is connected and bipartite. Consequently, we can find two partitions of the vertex set of H_{n}, one where two vertices are in the same part when they have the same point, and one where they are in the same part when they have the same hyperplane.

If we arbitrarily pick one of these two partitions and call it the “same point” partition, then we have the points and hyperplanes and nonincidence of the underlying projective space, and hence can uniquely reconstruct the projective space.

This shows

Lemma 2.2 Suppose n ≥ 2. Then H_{n} has precisely two labelings with point-line antiflags of a projective space, where one is obtained from the other by interchanging points and hyperplanes. □

3 Locally H_{n} graphs

Theorem 3.1 For n ≥ 3, a connected locally H_{n} graph is an H_{n+1} graph.

A graph is said to be locally P when for each vertex the graph induced on its set of neighbours has property P.

Assume n ≥ 3 and consider a connected graph Γ such that for each vertex the graph induced on the set of its neighbours is isomorphic to H(S) for some projective space S (that may depend on the chosen vertex) of dimension at least 3. We shall construct a projective space T such that Γ is isomorphic to H(T ).

First of all, since all maximal cliques in H_{n} have the same cardinality n + 1, it follows that the dimensions of all local projective spaces are equal. Now the claim can be formulated as “a connected locally H_{n} graph is an H_{n+1} graph”.

The first stage of the proof shows how an arbitrary choice between “same point” and “same hyperplane” at one vertex implies such a choice at a neighbouring vertex, and then a simple connectedness argument shows that there is a global such choice. The next stage of the proof shows how points seen locally at one vertex can be identified with points seen locally at some of its neighbours, and again a simple connectedness argument shows that there are global points and global hyperplanes, and we have the objects of which the H_{n+1} is supposed to be built. Verification of Pasch’ axiom shows that we have a projective space, and then everything follows.

Notation: γ ∼ δ says that the vertices γ and δ are adjacent. N(γ) denotes the set of neighbours of γ, and more generally N(γ, δ, ...) denotes the set of common neighbours of all of γ, δ, ... (or, sometimes, the graph induced on that set).

3.1 Transport of local choice to a neighbour

Let γ ∼ δ. Then N(γ, δ) carries the structure of an H_{n−1} in precisely two (dual) ways. A choice between the relations “same point” and “same hyperplane” on N(γ) induces such a choice on N(γ, δ) and then on N(δ). Let us call this “transporting the choice from γ to δ”.

Now let γ, δ, ϵ be three pairwise adjacent vertices. Since N(γ, δ, ϵ) carries the structure of an H_{n−2} and hence contains two vertices in the relation “same point or same hyperplane”, if we transport the choice from γ to δ, then from δ to ϵ, and then from ϵ to γ, we find the original choice again.

So, if it is possible to prove that Γ is simply connected, that is, that every circuit is a sum of triangles, then it follows that there is a consistent global choice.

3.2 Transport of local structure to a neighbour

Let γ ∼ δ and suppose that N(γ) and N(δ) each have been labeled with the pointhyperplane antiflags in some projective space, in such a way that the concepts “same point” induced on N(γ, δ) by the labelings of N(γ) and N(δ) coincide.

Locally at γ, the vertex δ is represented by a pair (d, D)_{γ}, and the common neighbours of γ and δ are the pairs (r, R)_{γ} with r ∈ D and d ∈ R. Locally at δ, the vertex γ is represented by a pair (c, C)_{δ}, and the common neighbours of γ and δ are the pairs (s, S)_{δ} with s ∈ C and c ∈ S. Since the projective structure is uniquely determined (because n ≥ 3) there is an isomorphism between both labelings of N(γ, δ). If ϕ is the corresponding mapping of the point sets, then this isomorphism sends (r, R)_{γ} to (ϕ(r), ⟨ϕ(R ∩ D), c⟩)_{δ}.

3.3 Simple connectedness

Proposition 3.2 Γ is simply connected and has diameter 2.

This is easy for n ≥ 5, almost as easy for n = 4, and requires some effort for n = 3.

First the case n ≥ 5.

Lemma 3.3 Suppose n ≥ 5. Given four vertices α, β, γ, δ of Γ with α ∼ β ∼ γ ∼ δ, there is a vertex ρ of Γ adjacent to each of α, β, γ, δ. In particular, Γ is simply connected and has diameter 2.

Proof: Locally at γ, the vertices β and δ are represented by pairs (b, B)_{γ} and (d, D)_{γ}, and the common neighbours of β, γ, δ are represented by pairs (r, R)_{γ} with r ∈ B ∩ D and R ⊇ ⟨b, d⟩. Transporting this structure to β, where γ is represented by (c, C)_{β}, we see that the common neighbours of β, γ, δ are represented by pairs (s, S)_{β} with s ∈ U, S ⊇ L, where U is a subspace of C of codimension at most one (in C), and L is a subspace of dimension at most one containing c. These vertices will be also adjacent to α = (a, A)_{β} when s ∈ U ∩ A and S ⊇ ⟨L, a⟩. And such vertices do exist: given subspaces X, Y, it is always possible to find a point in X and a hyperplane on Y missing that point, unless X ⊆ Y. Here X = U ∩ A has codimension at most three, so dimension at least two, and Y = ⟨L, a⟩ has dimension at most two, and X ≠ Y because ⟨L, a⟩ contains a, and U ∩ A does not. □

Next n = 4.

Lemma 3.4 Suppose n = 4. Given four vertices α, β, γ, δ of Γ with α ∼ β ∼ γ ∼ δ, either N(α, β, γ, δ) ≠ ∅, or there is a vertex γ′ ∈ N(β, γ, δ) such that N(α, β, γ′, δ) ≠ ∅. In particular, Γ is simply connected and has diameter 2.

Proof: Things go as before, and we want to find s ∈ U ∩ A and S ⊇ ⟨L, a⟩, where this time U is a subspace of C of dimension at least two. Now there will not be such an (s, S)_{β} precisely when U ∩A is a line contained in the plane ⟨L, a⟩, that is, when U ∩ A = ⟨L, a⟩ ∩ A. Since c ∈ L and U ⊆ C, if ⟨c, a⟩ ∩ A ∩ C = ∅, then certainly N(α, β, γ, δ) ≠ ∅.

Otherwise, replace γ by γ′ ∈ N(β, γ, δ). The requirement on γ′ = (c′, C′)_{β} is c′ ∈ U, C′ ⊇ L, c′ ∉ C′ and ⟨c′, a⟩ ∩ A ∩ C′ = ∅. We can pick c′ ∈ U \ ⟨L, a⟩ (since c ∈ L and c ∉ U). Next pick C′ on L not containing the two points c′ and ⟨c′, a⟩ ∩ A. And we are done. □

Finally, n = 3. First some preparation.

Suppose ξ, η ∈ N(α). Let us call the relation of ξ and η bad, locally at α, when every maximal clique in N(α, ξ, η) has size n − 2 (that is, when N(α, ξ, η) is q^{2} ∗ H_{n−3}), and good otherwise.

Clearly, if α ∼ β, and ξ, η ∈ N(α, β), then the relation of ξ and η is bad at β if and only if it is bad at α.

Similarly, if α ∼ β, and ξ, η ∈ N(α, β), then the relation of ξ and η is “same point or same hyperplane” at β if and only if it is “same point or same hyperplane” at α. (Also this can be recognized from the maximal cliques on α and β inside N(ξ, η).)

Lemma 3.5 Suppose n = 3.

(i) Let α, β, γ, δ be vertices of Γ with α ∼ β ∼ γ ∼ δ. If the relation of β and δ is bad at γ, then there is a β′ ∈ N(α, β, γ) such that the relation of β′ and δ is good at γ.

(ii) Let α, β, γ, δ be vertices of Γ such that the relation of β and δ is good at γ. Then there is a path of length at most 3 in N(β, δ) joining γ to a neighbour of α.

(iii) Γ is simply connected and has diameter 2.

Proof: (i) Locally at γ, the relation between β = (b, B)_{γ} and δ = (d, D)_{γ} is bad when ⟨b, d⟩ ∩ B ∩ D ≠ ∅. The common neighbours of α, β, γ are labeled by pairs (s, S)_{γ} with s ∈ U and S ⊇ L for certain subspaces U, L where U has dimension at least one and is contained in B, and L has dimension at most one and contains b. (In particular, U ≠ L.) Thus, we need a pair (s, S)_{γ} with s ∈ U, S ⊇ L, s ∉ S, and ⟨s, d⟩ ∩ S ∩ D = ∅. Pick s ∈ U \ L. Pick for S a plane on L that misses the two points s and ⟨s, d⟩ ∩ D.

(ii) Now move the view and look locally at β. We see α = (a, A)_{β}, and γ = (c, C)_{β}. The common neighbours of β, γ, δ are labeled by pairs (r, R)_{β} with r ∈ U and R ⊇ L for certain subspaces U, L where U has dimension at least one and is contained in C, and L has dimension at most one and contains c.

If U and L are not both lines, then β and γ are in the relation ”same point or hyperplane” at γ, and there is a path of length at most 2 in N(β, δ) from γ to a neighbour of α. Indeed, suppose U is a plane, that is, U = C. (The other case is dual.) There is a common neighbour of α, β, γ, δ if we can find r, R with r ∈ A ∩ C and R ⊇ ⟨a, L⟩ and r ∉ R. This is possible, unless A ∩ C ⊆ ⟨L, a⟩, so that in particular A ∩ C ∩ ⟨a, c⟩ ≠ ∅. If this happens, then first shift γ to γ′ = (c′, C′)_{β}. Pick c′ ∈ C \ L and C′ on L not containing either of the points c′ and ⟨a, c′⟩ ∩ A, and we are done.

So, we may now assume that U and L are both lines, and since β and δ have good relation at γ, these lines are disjoint. If a ∉ C then replace γ by γ′ ∈ N(β, γ, δ) with γ′ = (c′, C′)_{β} and a ∈ C′. That is possible: take C′ = ⟨a, L⟩ and c′ ∈ U \ C′.

So, we now assume that a ∈ C and produce a path of length at most 2 in N(β, δ) from γ to a neighbour of α.

Since the relation of β and δ is good at γ, there is a 3-clique {γ_{1}, γ_{2}, γ_{3}} with γ = γ_{1} in N(β, δ). Let γ_{i} = (c_{i}, C_{i})_{β}. There are lines L_{i} and U_{i} (i = 1, 2, 3) such that L_{i} ∩ U_{i} = ∅ and L_{i} contains c_{i} and U_{i} is contained in C_{i}, and the common neighbours of β, γ_{i}, δ are labeled (r, R)_{β} with r ∈ U_{i} and R ⊇ L_{i} and r ∉ R. In particular, this holds for γ_{j} with j ≠ i, so c_{j} ∈ U_{i} and L_{i} ⊆ C_{j} for j ≠ i. The c_{i} and C_{i} are distinct, since c_{i} ∈ C_{j} while c_{j} ∉ C_{j}, so if {i, j, k} = {1, 2, 3}, then U_{i} ∩ U_{j} = {c_{k}}, and U_{i} ∩ C_{j} = {c_{k}}.

We are looking for a pair (r, R)_{β} with r ∈ A ∩ U_{i} and R ⊇ ⟨a, L_{i}⟩ and r ∉ R. If this fails, then A ∩ U_{i} ⊆ ⟨a, L_{i}⟩ (i = 1, 2, 3). We have a ∈ C_{1}, so for i = 2, 3 we have ⟨a, L_{i}⟩ ⊆ C_{1}, and hence A ∩ U_{i} ⊆ C_{1} ∩ U_{i} = {c_{j}} ({i, j} = {2, 3}). So, A contains c_{2}, c_{3}, and hence U_{1} ⊆ A. Now U_{1} = A ∩ U_{1} ⊆ ⟨a, L_{1}⟩, which is impossible since U_{1} and L_{1} are disjoint. □

3.4 The existence of global points

Now that Γ is simply connected, we can and do choose the labelings of all local graphs in such a way that for any two adjacent vertices the relations “same point” induced on the set of their common neighbours coincide.

The next step is to construct global points. Let us say that two vertices α and β represent the same point when they have a common neighbour γ, and are in the relation “same point” locally at γ.

We first show that the relation does not depend on the common neighbour γ chosen. When γ ∼ δ, and α, β ∈ N(γ, δ), then we already saw that α, β are in the relation “same point” locally at γ if and only if they are in that relation locally at δ. Now apply induction:

Lemma 3.6 Let α and β be in the relation “same point” locally at some vertex γ, and let δ ∈ N(α). Then there is a path is N(α, β) joining γ to a neighbour of δ. In particular, N(α, β) is connected, and α and β are in the relation “same point” locally at every common neighbour.

Proof: Consider the path δ ∼ α ∼ γ ∼ β. If n ≥ 4 then we are done by Lemmas 3.3, 3.4. If n = 3, note that the relation of α and β is not bad at γ, and we are done by Lemma 3.5. □

Next, we have to show that representing the same point is an equivalence relation.

Lemma 3.7 Let α ∼ β ∼ γ ∼ δ ∼ ϵ where locally at β the vertices α and γ represent the same point, and locally at δ the vertices γ and ϵ represent the same point. Then there is a vertex ρ ∈ N(α, ϵ) such that locally at ρ the vertices α and ϵ represent the same point.

Proof: Since Γ has diameter 2, we can find a common neighbour ρ of α and ϵ. By the previous lemma we can shift β and δ, hence may assume that β, δ ∈ N(ρ). Now locally at β we see α = (a, A)_{β}, γ = (c, C)_{β}, ρ = (r, R)_{β}, where a = c and a ∈ R. It follows that the relation of γ and ρ is not bad at γ, and hence there is a path of length at most 3 in N(γ, ρ) joining β to δ. If β ∼ β′ is the first step in that path, then we can find α′ ∈ N(β, β′, ρ) so that locally at ρ the vertices α and α′ represent the same point, and locally at β′ the vertices α′ and γ represent the same point. Indeed, if β′ = (b′, B′)_{β}, then take α′ = (a′, A′)_{β} where a′ = a = c and A′ contains r, b′ but not a′. Now walk along the path to δ and reach the desired conclusion. □

This means that there are global points and hyperplanes, and we have nonincidence (namely, having nonempty intersection), and hence incidence. Remains to check that we have a projective space.

3.5 The projective space

We have global points, let us denote them [p], and global hyperplanes, let us denote them [H], both sets of vertices, equivalence classes for the “same point” or “same hyperplane” equivalence relations. Call [p] incident with [H] when [p] ∩ [H] = ∅.

Each vertex is in a unique global point, and a unique global hyperplane, so vertices can be identified with nonincident pairs ([p], [H]). (There cannot be two vertices with the same pair ([p], [H]), for locally at a common neighbour they would have the same point and the same hyperplane and hence be equal.)

Lemma 3.8

(i) If some vertex in [p] is adjacent to some vertex in [H], then [p] is incident with [H]. Conversely, if [p] is incident with [H] then every vertex in [p] is adjacent to some vertex in [H].

(ii) Some vertex in [p] is adjacent to some vertex in [q] if and only if p ≠ q.

Proof: (i) Suppose α, β ∈ [p] and β, γ ∈ [H]. We can walk in N(α, β) from an arbitrary common neighbour to a common neighbour that also is adjacent to a given neighbour of α. Thus, if α ∼ γ, then there is some vertex ρ adjacent to all of α, β, γ. Locally at ρ we see a contradiction.

Conversely, if [p] ∩ [H] = ∅, then pick π ∈ [p] and η ∈ [H] and a common neighbour ρ of both. Locally at ρ we see that [p] ∩ [H] ∩ N(ρ) = ∅, so that no vertex (p, H)_{ρ} exists, and consequently p ∈ H. Let π = (p, P)_{r}ho. Choose h ∈ P \ H, then so that π = (p, P)_{ρ} ∼ (h, H)_{ρ} ∈ [H].

(ii) Clearly, sets [p] are cocliques. Conversely, if [p] ∩ [q] = ∅, then look at a common neighbour of vertices in [p] and [q], and find an edge locally. □

That settled incidence. Next collinearity.

Lemma 3.9 Suppose [a], [b], [c] are three distinct global points. If some vertex α ∈ [a] has neighbours in both [b] and [c], then there is a triangle α ∼ β ∼ γ ∼ α with β ∈ [b] and γ ∈ [c].

Proof: Look locally in α. □

For distinct global points [b] and [c], let the global line on [b] and [c] be the set of all global points that are incident with all hyperplanes incident with both [b] and [c]. Then [a] is not on this global line when there is a global hyperplane [H] that meets [a] and is disjoint from [b] and [c], that is, when some point α ∈ [a] has neighbours in both [b] and [c]. Now the lemma says that this is a symmetric relation, and e.g. [b] is not on the global line on [a] and [c].

This shows that we have a linear space: a line is determined by any two of its vertices.

Locally, global lines look like local lines:

Lemma 3.10 If N(ρ) meets both [b] and [c], then it meets each global point on the global line on [b] and [c] in a local point, and these local points form a line in the local projective space.

Proof: Suppose [e] is on the global line on [b] and [c]. Then [e] is visible locally at ρ. Indeed, ρ determines a global hyperplane [H] that is disjoint from the global line, hence from [e], hence every vertex of [H], and in particular ρ, is adjacent to some vertex of [e]. So, locally we see all of the global line.

Suppose β ∈ N(ρ) ∩ [b] and γ ∈ N(ρ) ∩ [c]. Let β = (b, B)_{ρ} and γ = (c, C)_{ρ}. If r ∉ ⟨b, c⟩, then there is a vertex (r, R)_{ρ} where [R] is incident to both [b] and [c] but not [r]. Thus, upon hitting the global line with N(ρ) we only find points of the local line.

Remains to show that we find the full local line, and that not, for example, all global lines have size two.

References

[G] Ralf Gramlich, thesis, draft, Dec. 2001.