Geometriae Dedicata 75: 287–300, 1999. © 1999 Kluwer Academic Publishers. Printed in the Netherlands.

287

Near Polygons from Partial Linear Spaces BART DE BRUYN? and FRANK DE CLERCK Department of Pure Mathematics and Computer Algebra, University of Ghent, Galglaan 2, B-9000 Gent, Belgium. e-mail: [email protected], [email protected] (Received: 1 December 1997) Abstract. We construct a nondegenerate near polygon from a partial linear space without isolated points. We also prove that the points of a near polygon at distance at most 2 from a fixed point induce a near polygon, which is related to the class of the near polygons obtained from the construction. We give also a characterization of the near polygons of Hamming type in terms of parallelism. Mathematics Subject Classifications (1991): 51E30, 51E12, 05B25. Key words: near polygon, partial linear space.

1. Some Definitions and Properties An incidence structure is a triple S = (P , L, I) with P (the point set) a nonempty set and L (the set of lines) a (possible empty) set and I a symmetric incidence relation between those sets. Although the incidence relation is symmetric, we will write, in order not to overload the notation, I ⊆ P × L or even use ‘∈’ as incidence relation. The incidence structures which we will consider here are all finite. If x is a point, then 0i (x) denotes the set of all points at distance i from x (in the point graph). We will denote 0(x) = 01 (x). 1.1.

DEFINITIONS

(1) An incidence structure is called a partial linear space if the following conditions are satisfied. (a) Every line L ∈ L is incident with at least two points. (b) Two different points are incident with at most one line. (2) A partial linear space is called degenerate if there is a point incident with exactly one line. Every such point is called superthin. Notice that the definition of degeneracy is not conform to other definitions given in the literature (e.g., degenerate polar spaces). However, this yields no confusion in the sequel. (3) An incidence structure of points and lines is connected if its point graph is connected. ? Research Assistant of the Fund for Scientific Research – Flanders (Belgium).

Corr.

INTERPRINT: J.N.B. geom1668 (geomkap:mathfam) v.1.15 201244.tex; 16/04/1999; 8:01; p.1

288

BART DE BRUYN AND FRANK DE CLERCK

(4) A near polygon S is a partial linear space satisfying the following conditions. (a) The diameter of the point graph 0 of S is finite. (b) For every point p and every line L, there is a unique point q on L, nearest to p (nearest with respect to the distance d( . , . ) in 0).

(5)

(6) (7)

(8)

(9)

If d is the diameter of 0 then S is called a near 2d-gon. Although a near 0gon has only one point and no lines, it is by our definition not degenerate. A near 2-gon consists of one line with a number (> 2) of points on it, hence it is degenerate. The (nondegenerate) near quadrangles are just the (nondegenerate) generalized quadrangles (see [6]), which themselves are members of the family of the generalized polygons (see for instance [9]). The point-line dual of a nondegenerate generalized quadrangle is again a nondegenerate generalized quadrangle. If A and B are two sets of points of a partial linear space, then the distance between those sets is defined as d(A, B) := min d(a, b), where a, respectively b, ranges over all elements of A, respectively B. If A = {p}, then we also write d(p, B) instead of d({p}, B). An ovoid of a generalized quadrangle is a set of points such that every line meets the set in exactly one point. The (u × v)-grid is the generalized quadrangle with point set {xij |1 6 i 6 u, 1 6 j 6 v} and with line set {L1 , . . . , Lu , M1 , . . . , Mv }. Incidence is as follows: xij I Lk ⇔ i = k and xij I Mk ⇔ j = k. If u = v, then the grid is called symmetric. The point-line dual of a grid is called a dual grid. If a nondegenerate generalized quadrangle is neither a grid nor a dual grid, then it has an order (s, t), i.e., every line is incident with exactly s + 1 points and every point is incident with exactly t + 1 lines. Such a generalized quadrangle is sometimes denoted by GQ(s, t). A thin near polygon is a near polygon with the property that every line is incident with exactly two points, hence we can consider these geometries as graphs. In this point of view the thin near polygons are exactly the connected bipartite graphs. A dual grid is a thin near polygon. A regular near 2d-gon S (d > 0) is a near 2d-gon satisfying the following conditions. (a) S has order (s, t). (b) |0i−1 (x) ∩ 0(y)| = ti + 1 depends only on i = d(x, y) for all points x and y.

(10) If S1 = (P1 , L1 , I1 ) and S2 = (P2 , L2 , I2 ) are two partial linear spaces, then the direct product of S1 and S2 is the partial linear space S = (P , L, I) with P = P1 ×P2 and L = (P1 ×L2 )∪(L1 ×P2 ). The point (x, y) is incident with the line (a, L) ∈ P1 × L2 if and only if x = a and y I2 L and it is incident with the line (M, b) ∈ L1 × P2 if and only if y = b and x I1 M. We denote S also with S1 × S2 . Let d1 ( · , · ), d2 ( · , · ) and d( · , · ) denote the distances in S1 , S2

201244.tex; 16/04/1999; 8:01; p.2

289

NEAR POLYGONS FROM PARTIAL LINEAR SPACES

and S respectively, then d((x1 , y1 ), (x2 , y2 )) = d1 (x1 , x2 ) + d2 (y1 , y2 ). Hence if Si (i ∈ {1, 2}) is a near 2 di -gon then the direct product S = S1 × S2 is a near 2(d1 + d2 )-gon. Since S1 × S2 ' S2 × S1 and (S1 × S2 ) × S3 ' S1 × (S2 × S3 ), also the direct product of k > 1 partial linear spaces S1 , . . . , Sk is well-defined. A near polygon is of Hamming type if it is the direct product of a number of lines. 1.2.

MOTIVATION AND OVERVIEW

How many near polygons are there? If we ask nothing extra about the structure of the near polygons then the examples are really abundant. In the next section we will describe three constructions which slightly alter the structure of a partial linear space. If the partial linear space we start with is a nondegenerate near polygon then successive application of constructions (1) and (2) yields infinitely many degenerate near polygons. Moreover, the nondegenerate near polygon we started with, can be found back from the degenerate ones by successive application of the (inverse) construction (3). This shows that a more interesting question is: how many nondegenerate near polygons are there? The answer to this question is the same, i.e., the examples are very abundant. Theorem 4 (which is a generalization of a result which was already mentioned before in the literature) gives a way to construct many examples. In Section 2 we will construct an infinite class of nondegenerate near polygons. They have the main property that they contain a point which is at distance at most 2 from all the other points. In Section 3 we prove that, conversely, all the near polygons with this main property (up to some trivial exceptions) yield by successive application of construction (3) a near polygon of Section 2, hence we have a characterization. To determine under which conditions construction (2), applied to a near polygon, would yield again a near polygon, we introduce the concept of parallelism. In Section 4 we give a characterization of the Hamming near polygons in terms of parallelism. 1.3.

THE NONDEGENERATE SUPPORT OF A FINITE PARTIAL LINEAR SPACE

Let S = (P , L, I) be a partial linear space. We give now three constructions slightly altering the structure of S. Constructions (1) and (2) increase the ‘amount’ of degeneracy, while the inverse construction (3) reduces this amount. Construction (3) can then be used to define the nondegenerate support of S. (1) Assume p ∈ P , then we denote by Sp = (Pp , Lp , Ip ) the following partial linear space: Pp = P ∪ {(∞)},

where (∞) 6 ∈ P ;

Lp = L ∪ {[∞]},

where [∞] 6 ∈ L;

Ip = I ∪ {(p, [∞]), ((∞), [∞])}.

201244.tex; 16/04/1999; 8:01; p.3

290

BART DE BRUYN AND FRANK DE CLERCK

(2) Assume L ∈ L, then we denote by SL = (PL , LL , IL ) the following partial linear space: PL = P ∪ {(∞)},

where (∞) 6 ∈ P ;

LL = L; IL = I ∪ {((∞), L)}. (3) Assume that p ∈ P is a superthin point incident with the line L, then we denote by S p = (P p , Lp , Ip ) the following partial linear space: P p = P − {p}; Lp = L − {L}

if L has length 2, while Lp = L in the other case;

Ip = I ∩ (P p × Lp ). Suppose that p1 is a superthin point of a partial linear space S. If p2 is a superthin point of S p1 , then (S p1 )p2 is again a partial linear space. Repeating this argument, one finally finds a nondegenerate partial linear space (. . . (S p1 ) . . .)pl , which is called the nondegenerate support of S. We prove now that this is a good definition, i.e., that it is independent of the order in which the superthin points are considered. Proof. We may suppose that S is connected, otherwise one can reason on each connected component. Suppose that we obtain two nondegenerate partial linear spaces S 0 = (. . . (S p1 ) . . .)pk and S 00 = (. . . (S q1 ) . . .)ql . Here p1 and q1 are superthin points of S and pi (1 < i 6 k) and qj (1 < j 6 l) are superthin points of (. . . (S p1 ) . . .)pi−1 and (. . . (S q1 ) . . .)qj−1 respectively. Suppose pi 6 ∈ {q1 , . . . , ql } with i the smallest integer with that property, then pi is not a superthin point of S 00 . If pi is contained in two lines L and M of S 00 , then at least one of these lines, say L, is not a line of (. . . (S p1 ) . . .)pi−1 . Let r 6 = pi be a point of S 00 on L. Then r 6 ∈ {q1 , . . . , ql } and r = pi 0 with i 0 < i, a contradiction. Hence, S 00 is the near 0-gon with unique point pi (since there are no lines through pi ). Hence we may assume that S 0 is not isomorphic to a near 0-gon and using the same reasoning as above, we may conclude that qj ∈ {p1 , . . . , pk } for all j ∈ {1, . . . , l}. This implies however that P − {pi } = {q1 , . . . , ql } ⊆ {p1 , . . . , pk }, a contradiction. Hence {p1 , . . . , pk } = {q1 , . . . , ql } = A. Now S 0 and S 00 have the same points (namely the points not in A) and the same lines (namely the lines of S having at least 2 points not in A), which implies that S 0 and S 00 are isomorphic. 2 Remark. If p is a superthin point of a near polygon S, then S p is again a near polygon. Hence, the nondegenerate support of a near polygon is again a near polygon. If p is an arbitrary point of a near polygon S, then Sp is also a near polygon. Under certain circumstances, also construction (2) yields a near polygon, but first we need to introduce the concept parallelism.

201244.tex; 16/04/1999; 8:01; p.4

291

NEAR POLYGONS FROM PARTIAL LINEAR SPACES

1.4.

PARALLELISM

The next theorem gives the two possible relations between two lines of a near polygon. THEOREM 1 ([3]). The following two cases can appear for lines L and M of a near polygon. (1) There exists a unique point p on L and a unique point q on M such that d(l, m) = d(l, p) + d(p, q) + d(q, m) for all points l on L and m on M. (2) There exists an i ∈ N such that d(l, M) = d(m, L) = i for all points l on L and m on M. DEFINITION. Two lines are called parallel (k) if they satisfy condition (2) of the previous theorem. The relation k is most of the time not an equivalence relation, see the last section for more about this. Remark. If p is a superthin point of a near polygon which is incident with L, then every line M 6 = L is nonparallel to L. Indeed, if (p, q, . . .) is a shortest path from p to M, then p, q ∈ L and d(q, M) = d(p, M) − 1. If L has more than two points then this line is also a line of S p and every line K 6 = L of S p is nonparallel to L (in S p ). Otherwise, every point of K would have the same distance to p (in S). LEMMA 1. Let S = (P , L, I) be a near polygon. If L ∈ L is a line which is not parallel to any other line M 6 = L, then SL is a near polygon. Proof. Choose a point p and a line M of SL . If p 6 = (∞), then the distance between p and any point of M is not changed by adding (∞) to P . If p = (∞), we may suppose that M 6 = L. Let α and β be the unique points of L and M such that d(m, l) = d(l, α) + d(α, β) + d(β, m) yields for all points l of L and m of M. The point β is now the unique point of M nearest (in SL ) to (∞). COROLLARY 1 . If p ∈ P is a superthin point which is incident with the line L, then SL is a near polygon.

1.5.

SOME BASIC DEFINITIONS AND BASIC RESULTS

We recall some of the basic definitons (see, for instance, [8]) that will be important for the sequel. Let S = (P , L, I) be a near polygon. A subset X of P is called a subspace if all the points of a line L are in X as soon as two of those points are in X. Every such X induces an incidence structure S 0 = (X, L0 , I0 ), where L0 is the set of lines having all their points in X and I0 = I ∩ (X × L0 ). Let x be a fixed point of a near polygon S. Then the subset Pxi = {p ∈ P | d(x, p) 6 i} is a subspace. For, take a line L which has two points α and

201244.tex; 16/04/1999; 8:01; p.5

292

BART DE BRUYN AND FRANK DE CLERCK

β in common with Pxi . Since d(x, α) 6 i and d(x, β) 6 i, it follows that there must be a point γ on L such that d(x, γ ) 6 i − 1. Hence, every point of L has distance at most i to x. Let Lix be the set of lines having distance at most i − 1 from x then Sxi = (Pxi , Lix , Iix ) with Iix = I ∩ (Pxi × Lix ) is a partial linear space and is called the i-neighbourhood of x. A subset X of P is called geodetically closed whenever X is a subspace, and all points of a shortest path from p ∈ X to q ∈ X are as well contained in X. The set X is called a quad whenever X is geodetically closed and X induces a nondegenerate generalized quadrangle (since no confusion is possible, this generalized quadrangle will also be called a quad). Finally, we call a subset X of the point set classical if for every point x there is a unique point πX (x) ∈ X such that d(x, y) = d(x, πX (x)) + d(πX (x), y) for all y ∈ X. One easily checks that every classical set X is necessarily geodetically closed. The existence of quads will be very important for the rest of this paper, moreover the so-called point-quad relation will be used implicitely, for instance to define dual polar spaces. For reasons of completeness, we recall the relevant theorems, for the proofs see [7] and [8]. THEOREM 2 . Let x and y be two points of a near polygon at mutual distance 2. If x and y have two common neighbours c and d such that the line xc contains at least three points, then x and y are in a unique quad. THEOREM 3 (the point-quad relation). If p is a point of S and Q a quad, then just one of the following cases occurs. (1) There is a unique point q ∈ Q such that d(p, r) = d(p, q) + d(q, r) for all points r ∈ Q. In this case (p, Q) is called classical. (2) The points of Q which are nearest to p form an ovoid of Q. In this case (p, Q) is called ovoidal. (3) The quad Q induces a dual grid. Let A be the set of points of Q at smallest distance k from p. Let B, respectively C, denote those points of Q, that have distance k + 1, respectively k + 2 to p. Then – |A| > 2 and |C| > 1, – B and A ∪ C are the two maximal cocliques of the point graph of Q. In this case (p, Q) is called thin ovoidal. An important class of near polygons are the dual polar spaces. We only mention here that they were characterized (see [4]) as those near polygons satisfying the following two conditions. (1) Every two points at mutual distance 2 are contained in a quad. (2) All point-quad relations are classical. EXAMPLES. Here are some examples of classical sets in a near polygon.

201244.tex; 16/04/1999; 8:01; p.6

293

NEAR POLYGONS FROM PARTIAL LINEAR SPACES

– – – – –

{p} with p ∈ P . The set of the points on a line. A quad in a dual polar space. A quad not containing an ovoid. Let S1 and S2 be two near polygons. For every point p of S1 , the set {(p, x) | x is a point of S2 } is a classical set of the near polygon S1 × S2 .

The result of the following theorem is mentioned in [1] in the case where X1 and X2 are both classical. THEOREM 4. Let S1 = (P1 , L1 , I1 ) and S2 = (P2 , L2 , I2 ) be two near polygons. Let X1 , respectively X2 , be a classical subset of P1 , respectively a subspace of S2 . Denote by di ( · , · ), i ∈ {1, 2}, the distance in Si . Suppose that there is a bijection α: X1 7 → X2 such that d2 (α(x), α(y)) = d1 (x, y) for all points x, y ∈ X1 . Then the partial linear space obtained by identifying the corresponding points and lines in X1 and X2 is a near polygon, which we denote by S[S1 , S2 , X1 , X2 , α]. Proof. Choose in S[S1 , S2 , X1 , X2 , α] a point p and a line L. We want to prove that there is a unique point on L nearest to p. We define d( · , · ) as the distance in S[S1 , S2 , X1 , X2 , α]. We consider three cases. (1) Assume that p and L both belong to the same near polygon Si (i = 1, 2). As d2 (α(x), α(y)) = d1 (x, y) for all points x, y ∈ X1 , there exists for any two points a and b from Pi (i = 1, 2) a shortest path from a to b only containing points of Si and, hence, d(a, b) = di (a, b) (i = 1, 2). This implies that L contains a unique point nearest to p. (2) Assume that p ∈ P1 while L ∈ L2 . Let l1 , l2 be two points such that d(p, l1 ) = d(p, l2 ) = d(p, L). Since X1 is a classical subset, there exists a shortest path from p to li , that contains the point πX1 (p). Hence l1 = l2 is the unique point of L nearest to πX1 (p) (in S2 ). (3) Finally assume p ∈ P2 while L ∈ L1 . Let l1 and l2 be two different points of L such that d(p, l1 ) = d(p, l2 ) = d(p, L). Define si = πX1 (li ). Since X1 is a classical subset, there exists a shortest path from p to li containing the point si . If s1 = s2 then l1 and l2 are two different points on L, and both are nearest to s1 , a contradiction. If s1 6 = s2 then, since X1 is classical, d(s1 , s2 ) = 1 and d(l1 , s1 ) = d(l2 , s2 ). Denote by s3 the unique point of s1 s2 nearest to p, then s1 6 = s3 6 = s2 . Let l3 denote the unique point of L, for which d(l1 , s1 ) = d(l2 , s2 ) = d(l3 , s3 ). Now, there exists a path of length d(p, l2 ) − 1 from p to l3 , a contradiction. 2

2. Construction of Near Polygons from Partial Linear Spaces The construction in this section is rather technical, it was found as follows. First, we noticed that the two-neighbourhood of a near polygon is again a near polygon.

201244.tex; 16/04/1999; 8:01; p.7

294

BART DE BRUYN AND FRANK DE CLERCK

This two-neighbourhood can define another partial linear space (see the proof of Theorem 6). In this section we do the converse construction; indeed, the idea is to reconstruct the two-neighbourhood from this partial linear space. Notice that the class of near polygons constructed in this section can also be found by successive application of Theorem 4. The required near polygons are a degenerate generalized quadrangle, a thin near polygon and (several) nondegenerate generalized quadrangles. In this section, we suppose that G = (A, B, I) is a partial linear space with the property that every point is incident with at least one line. We may and will suppose that the lines of B are sets of points. Let G∗ be the geometry obtained out of G by deleting all the lines of length 2 and call Ci (1 6 i 6 n) the point sets of the connected components of G∗ . For every i with 1 6 i 6 n we can choose a natural number si = s(Ci ) > 1 as follows. – If |Ci | = 1, choose si > 1 at random. – If |Ci | > 1, choose si > 1 such that for every L ∈ B (L ⊆ Ci ) |L| > 3, there exists a GQ(si , |L| − 1). Clearly si = 1 is always a feasible choice for si . For every L ∈ B with |L| > 3, we define s(L) = s(Ci ) where Ci is the component containing L. For every p ∈ A, we define s(p) = s(Ci ), where Ci is the component containing p. Now we will define a partial linear space S = (P , L, I0 ) where I0 is inclusion. The elements of P are as follows: (1) (∞); (2) (p, i) with p ∈ A and 1 6 i 6 s(p); (3) (L, i) with L ∈ B and 1 6 i 6 k(L), here k(L) > 1 is at random if s(p) = 1 for all points p on L, k(L) = s(p1 )·s(p2 ) if L = {p1 , p2 } and s(p1 )·s(p2 ) > 1, k(L) = [s(L)]2 (|L| − 1) if |L| > 2 and s(L) 6 = 1. The lines of L are obtained as follows: (1) {(∞)} ∪ {(p, i)|1 6 i 6 s(p)} is a line for every p ∈ A; (2) Consider a line L ∈ B with |L| = 2, L = {p1 , p2 }, s(p1 ) · s(p2 ) > 1. The set {(∞)} ∪ {(p1 , i)|1 6 i 6 s(p1 )} ∪ {(p2 , i)|1 6 i 6 s(p2 )} ∪ {(L, i)|1 6 i 6 s(p1 ) × s(p2 )} counts (s(p1 ) + 1) · (s(p2 ) + 1) points, so we can give it the structure of an (s(p1 ) + 1) × (s(p2 ) + 1)-grid by introducing s(p1 ) + s(p2 ) + 2 lines; two of those lines were already defined in (1). (3) Consider a line L ∈ B with |L| = tL + 1 > 3 and s(L) 6 = 1. The set {(∞)} ∪ {(p, i)|p ∈ L, 1 6 i 6 s(L)} ∪ {(L, i)|1 6 i 6 [s(L)]2 tL } counts (1 + s(L)) · (1 + s(L)tL ) elements, so we can give it the structure of a GQ(s(L), tL ) by introducing (1 + tL )(1 + s(L)tL ) lines; 1 + tL of those lines were already defined in (1). (4) Consider a line L ∈ B for which s(p) = 1 for every point p on L. The set {(∞)} ∪ {(p, 1)|p ∈ L} ∪ {(L, i)|1 6 i 6 k(L)} can be given the structure of

201244.tex; 16/04/1999; 8:01; p.8

NEAR POLYGONS FROM PARTIAL LINEAR SPACES

295

a dual grid with {(p, 1)|p ∈ L} and ({(∞)} ∪ {(L, i)|1 6 i 6 k(L)}) as two maximal cocliques of the point graph. (5) All the other lines have length 2 and look like {(p, 1), (L, i)} with – p ∈ A − L, – s(p) = 1, – s(q) = 1 for all points q on L, – p and L are contained in the same component of G, – 1 6 i 6 k(L). Contrary to the lines of types (1), (2), (3) and (4), we can decide here whether we add them or not. THEOREM 5. The incidence structure S is a nondegenerate near polygon. Proof. Let x denote the point (∞). For every y at distance 2 from x, we define the set S(x, y) = {L ∈ L | x ∈ L and L contains a point collinear with y}. Note that if m is a point collinear with y but at distance 2 from x, then S(x, y) = S(x, m). Let p be a point and L be a line of S, then we have to prove that there exists a unique point on L nearest to p. This is certainly true if p ∈ L or p = x. So, suppose that p 6 = x and p 6 ∈ L. The following statements are trivial or are readily obtained. – If d(p, x) = 1 and x ∈ L, then x is the unique point of L nearest to p. – If d(p, x) = 1 and x 6 ∈ L, let a be the point of L at distance 1 from x and b any other point of L. If xp ∈ S(x, b), then there exists a unique point of L at distance 1 from p. If xp 6 ∈ S(x, b), then a has distance 2 to p and every other point of L has distance 3 to p. – If d(p, x) = 2, x ∈ L, L ∈ S(x, p) then there exists a unique point of L at distance 1 from p. – If d(p, x) = 2, x ∈ L, L 6 ∈ S(x, p), then x has distance 2 to p and every other point of L has distance 3 to p. – If d(p, x) = 2, x 6 ∈ L, let a be the point of L collinear with x and b any other point of L. If d(p, L) = 1, then there exists a unique point of L at distance 1 from p. Suppose therefore that d(p, L) > 2. If S(x, b) ∩ S(x, p) 6 = ∅, then there exists a unique point of L at distance 2 from p, all the other points have distance 3 to p. If S(x, b) ∩ S(x, p) = ∅, then a has distance 3 to p and every other point of L has distance 4 to p. 2 Remark. If G is not connected, then S is isomorphic to an S[S1 , S2 , {x}, {x}, 1{x} ], where x is a common point of the near polygons S1 and S2 and 1{x} denotes the identity map on the set {x}. 3. The i-Neighbourhood of a Point For some ‘nice’ classes of near polygons, it is shown that all the i-neighbourhoods are near polygons, an example shows however that this is not always the case. The

201244.tex; 16/04/1999; 8:01; p.9

296

BART DE BRUYN AND FRANK DE CLERCK

two-neighbourhoods (which are always near polygons) are related to the class of near polygons obtained from the construction in Section 2. THEOREM 6. Assume S = (P , L, I) is a near polygon and x is a fixed point of P . Define the following sets: V2 = {y ∈ P | d(x, y) = 2 and |0(x) ∩ 0(y)| > 2}, V1 = {z ∈ P | ∃y ∈ V2 such that z ∈ 0(x) ∩ 0(y)}, P 0 = {x} ∪ V1 ∪ V2 ; then P 0 is a subspace. If P 0 6 = {x}, then the partial linear space S 0 = (P 0 , L0 , I0 ) induced by P 0 is a nondegenerate near polygon which can be constructed using the method of Section 2. Proof. Consider a line L having two of its points, say α and β, in P 0 . We may suppose that L contains at least three points. If x is incident with L, then we may suppose that α ∈ V1 . So, there exists a point y ∈ V2 such that α is a common neighbour of x and y. The points x and y determine a quad Q. Hence, for every point γ 6 = x of L there exists a point y 0 of V2 ∩ Q such that γ is a common neighbour of x and y 0 . If x is not incident with L, we may suppose that d(x, α) = 2. The points x and α determine a quad and once again it is clear that every point of L belongs to V1 or V2 . S Call A1 the set of lines of L0 which are incident with x, B1 = y∈V2 {{L ∈ A1 | d(y, L) = 1}} and let I1 be the natural incidence. The incidence structure (A1 , B1 , I1 ) is not necessarily a partial linear space, as illustrated by the following example.

Figure 1.

But, when every element of V2 is incident with a line (of L0 ) of length at least 3, then (A1 , B1 , I1 ) is a partial linear space. Indeed, every two different quads are disjoint or are intersecting in a point or a line. If (A1 , B1 , I1 ) is not a partial linear space, then the lines of type (5) from Section 2 are necessary. In this case we will construct inductively a number of incidence structures (Ai , Bi , Ii ), 1 6 i 6 n, having the same connected components of (A1 , B1 , I1 ) and such that (An , Bn , In ) is a partial linear space. If (Ai , Bi , Ii ) is a partial linear space, let n = i. In the other case, we choose L, L0 ∈ Bi such that L 6 = L0 and |L ∩ L0 | > 2. We may suppose that L0 −L 6 = ∅. Take M ∈ L∩L0 and define L00 = {M}∪(L0 −L), Ai+1 = Ai , Bi+1 = (Bi ∪ {L00 }) − {L0 } and Ii+1 as the natural incidence. Since the number of flags (i.e. incident point-line pairs) decreases if i increases, this procedure will finally stop.

201244.tex; 16/04/1999; 8:01; p.10

NEAR POLYGONS FROM PARTIAL LINEAR SPACES

297

Now, one can use the connected partial linear space (An , Bn , In ) for the construction given in Section 2 and it is possible to find back S 0 that way. The generalized quadrangles different from the dual grids used in this construction (lines of types (2) and (3)) are the quads (different from dual grids) of S through x. The dual grids (lines of type (4) in the construction) and the lines of type (5) have to be chosen in such a way that the remaining (thin) lines of S 0 are present. As a consequence, S 0 is a nondegenerate near polygon. 2 LEMMA 2. The nondegenerate support of Sx2 is S 0 . Proof. If y ∈ P with d(x, y) = 2 and y 6 ∈ V2 , then there is a unique line through y which belongs to L2x . Hence y does not belong to the nondegenerate support of Sx2 . If z ∈ P with d(x, z) = 1 and z 6 ∈ V1 , then z does not belong to the nondegenerate support of Sx2 as otherwise this would imply the existence of a point u ∈ V2 , collinear with z. 2 COROLLARY 2 . If S is a near 2d-gon which satisfies d(x, y) 6 2 for all y ∈ P , then its nondegenerate support, if not a single point, can be obtained by the construction of Section 2. THEOREM 7. The partial linear space Sx2 is a near polygon. Proof. This follows immediately from the previous theorems, but we will give here another proof that makes no use of the rather technical construction of Section 2. Let d2 ( · , · ) denote the distance in Sx2 . Take any point p and any line L of Sx2 . Let p 0 denote the unique point of L nearest to p (in S). If d2 (p, L) = 0, there is nothing to prove. If d2 (p, L) = 1, then d(p, L) = 1 and p 0 is the unique point of L nearest to p (in Sx2 ). If d2 (p, L) = 2, then d(p, L) = 2 and p 0 is the unique point of L nearest to p (in Sx2 ). So we may suppose that d2 (p, L) = 3. This implies that d(p, x) = 2 and d(x, L) = 1. Let α denote the point of L which is collinear with x. Any path of length 6 2 between p and α is contained in Px2 , so d(p, α) = d2 (p, α) = 3. Let s denote another point of L for which d2 (p, L) = 3. Let (p, q, r, s) be a path in Sx2 connecting p and s. If d(x, q) = 1, then d(q, α) = 2 and d(q, s) = 2. So, there is a point β of L, collinear with q. The path (p, q, β) is contained in Px2 , a contradiction. If d(x, r) = 1, then since d(p, x) = 2 = d(p, r) there is a point γ of xr which is collinear with p. Now d(γ , α) = d(γ , s) = 2, so there is a point δ of L collinear with γ . The path (p, γ , δ) stays in Px2 , a contradiction. So we may suppose that d(x, p) = d(x, q) = d(x, r) = 2. There exists a point a on pq and a point b on qr such that d(x, a) = d(x, b) = 1. Since d(b, s) = 2 and d(b, α) 6 2, there exists a point c on L collinear with b. Now, the points q and x determine a quad. So, there is a point d of xb which is collinear with p. If α = c then xb = xα, so d is collinear with α, contradicting d(p, α) = 3. Suppose α 6 = c. Since d(d, α) = d(d, c) = 2, there exists a point e of L which is collinear with d. The path (p, d, e) is contained in Px2 , a contradiction. This proves that α is the unique point of L such that d2 (p, α) = 3. 2

201244.tex; 16/04/1999; 8:01; p.11

298

BART DE BRUYN AND FRANK DE CLERCK

THEOREM 8. (1) If S is a thin near polygon, then Sxi is a thin near polygon, for every integer i. (2) If S is a generalized 2d-gon, then Sxi is a near polygon for every i ∈ N. (3) If S is a dual polar space, then Sxi is a near polygon for every i ∈ N. Proof. (1) The point graph of Sxi remains bipartite and connected. (2) We may suppose that 0 < i < d. In that case, Sxi is a degenerate near polygon, whose nondegenerate support is a point. (3) Let di (·, ·) be the distance in Sxi . It suffices to prove that d(p, q) = di (p, q) for all p, q ∈ Pxi . Clearly d(p, q) 6 di (p, q). Consider a path p = b0 , b1 , . . . , bk = q of length k = d(p, q) such that d(x, b0 )+· · ·+d(x, bk ) is minimal. If there exists an index j such that d(x, bj ) > i, then one of the following two cases certainly occurs. – There exists an index l such that d(x, bl ) = m, d(x, bl+1 ) = d(x, bl+2 ) = m + 1. Define Q as the quad through bl , bl+1 and bl+2 and define α as the unique point in Q nearest to x. It is impossible that α = bl , otherwise d(x, bl+2 ) = m + 2. The point α is collinear with bl and has distance m − 1 to x. Call β the point on bl α at distance 1 of bl+2 . The path (bl , bl+1 , bl+2 ) can be replaced by (bl , β, bl+2 ), a contradiction. – There exists an l such that d(x, bl ) = d(x, bl+2 ) = m, d(x, bl+1 ) = m + 1. Define Q as the quad through bl , bl+1 and bl+2 and define α as the unique point in Q nearest to x. The point α is a common neighbour of bl and bl+2 , so the path (bl , bl+1 , bl+2 ) can be replaced by (bl , α, bl+2 ), yielding a contradiction. 2 One might wonder whether Sxi is a near polygon for all choices of S, x and i. This is not the case, as shown in the following theorem. We refer to Section 13.6 of [2] for the construction of the regular near octagon involved. Uniqueness was proved in [5]. THEOREM 9. Let x be a point of the unique regular near octagon with parameters s = 2, t = 4, t2 = 0, t3 = 3, then Sx3 is not a near polygon. Proof. Let d3 ( · , · ) denote the distance in Sx3 . Let y ∈ 04 (x), {y1 , y2 } ⊂ 03 (x)∩ 0(y), y1 6 = y2 , y3 ∈ 0(y2 ) ∩ 02 (x) and let y4 be the third point of the line y3 y2 . Now y3 6 = y1 6 = y4 , d(y3 , y1 ) 6 = 1 6 = d(y4 , y1 ) since t2 = 0, d(y1 , y3 ) 6 = 2 since d(y1 , y4 ) 6 = 1, d(y1 , y4 ) 6 = 2 since d(y1 , y3 ) 6 = 1. So d(y1 , y3 ) = d(y1 , y4 ) = 3. There are four shortest paths (y1 , α, β, yi ) connecting y1 and yi (i = 3, 4). Since t − t3 = 1, only two of these paths can have d(x, α) = 4 or d(x, β) = 4. This means that d3 (y1 , y3 ) = d3 (y1 , y4 ) = 3, but d3 (y1 , y2 ) > 3, so Sx3 is not a near polygon. Remark. The interesting problem for which near polygons the i-neighbourhood is again a near polygon is still open.

201244.tex; 16/04/1999; 8:01; p.12

NEAR POLYGONS FROM PARTIAL LINEAR SPACES

299

4. The Relation Parallelism LEMMA 3 . Let Si , 1 6 i 6 k, be a number of near polygons and let S be their direct product. Then parallelism (k) is an equivalence relation in S if and only if it is an equivalence relation in each Si . Proof. We may suppose that k = 2, otherwise one can use induction. The result follows now by looking at the following remarks, which are readily obtained. (Here p, q denote points and L, M denote lines.) – The lines (p, M) and (L, q) are never parallel. – The lines (p, M) and (q, L) are parallel if and only if M and L are parallel. – The lines (L, q) and (M, p) are parallel if and only if L and M are parallel. 2 The next theorem is in [3]. THEOREM 10 . Let S be a near polygon with the property that every two points at distance 2 have at least two common neighbours, then S is the direct product of a number of near polygons having a constant length for the lines. COROLLARY 3 . Let S be a near polygon with the property that every two points at mutual distance 2 are contained in a quad. If every quad is a nonsymmetrical grid, then S is isomorphic to a direct product of k lines, which all have a different length. Hence, S is a near polygon of Hamming type. Proof. S is the direct product of k near polygons Sj , 1 6 j 6 k. The lines in a fixed Sj have a constant number of points on a line. As all quads are nonsymmetrical grids, it follows that Sj , 1 6 j 6 k is a line. 2 THEOREM 11 . If S is a near polygon, then the following conditions are equivalent. (1) S is a near polygon of Hamming type. (2) Parallelism is an equivalence relation and every two points at mutual distance 2 have at least two common neighbours. (3) For every point x and every line L, there is a unique line through x which is parallel to L. Proof. (1) ⇒ (2). Trivial. (2) ⇒ (3). If there were two lines M and M 0 through x parallel to L, then MkM 0 , a contradiction. We only need to show that there is at least one line through x parallel to L. Since S is connected and k is an equivalence relation, we may suppose that d(x, L) = 1. Let x 0 be the unique point of L which is collinear with x and let y 0 be any other point of L. If y is a common neighbour of x and y 0 , different from x, then xykL. (3) ⇒ (1). We prove by induction that for every two points at mutual distance i, there are exactly i points in 0i−1 (x) ∩ 0(y). This is true for i = 0 and i = 1,

201244.tex; 16/04/1999; 8:01; p.13

300

BART DE BRUYN AND FRANK DE CLERCK

so suppose i > 2. Let z be a neighbour of x having distance i − 1 to y. Let y1 , . . . , yi−1 be the i − 1 neighbours of y having distance i − 2 to z. Let N be the line through y parallel with xz and yi be the point of this line having distance i − 1 to x, then yj (1 6 j 6 i) are i different points collinear with y and having distance i − 1 to x. If yi+1 would be another point having these properties, then yyi+1 kxz, so yyi+1 = yyi and yi = yi+1 , a contradiction. If all lines of S have a constant number of points, then the near polygon is regular and has the same parameters as a regular near polygon of Hamming type. Hence, S is a regular near polygon of Hamming type, see Corollary 9.2.3 of [2]. If not all lines of S have a constant number of points, then the theorem follows from Lemma 3 and Theorem 10. 2

References 1. 2. 3. 4. 5. 6. 7. 8. 9.

Brouwer, A. E., Cohen, A. M., Hall, J. I. and Wilbrink, H. A.: Near polygons and Fischer spaces, Geom. Dedicata 49 (1994), 349–368. Brouwer, A. E., Cohen, A. M. and Neumaier, A.: Distance-Regular Graphs, Springer-Verlag, Berlin, 1989. Brouwer, A. E. and Wilbrink, H. A.: The structure of near polygons with quads, Geom. Dedicata 14 (1983), 145–176. Cameron, P. J.: Dual polar spaces, Geom. Dedicata 12 (1982), 75–86. Cohen, A. M. and Tits, J.: On generalized hexagons and a near octagon whose lines have three points, European J. Combin. 6 (1985), 13–27. Payne, S. E. and Thas, J. A.: Finite Generalized Quadrangles, Pitman Res. Notes Math. Ser. 110, Pitman, Boston, 1984. Shad, S. A. and Shult, E. E.: The near n-gon geometries, Unpublished, 1979. Shult, E. E. and Yanushka, A.: Near n-gons and line systems, Geom. Dedicata 9 (1980), 1–72. Thas, J. A.: Generalized polygons, in: F. Buekenhout (ed.), Handbook of Incidence Geometry, Buildings and Foundations, North-Holland, Amsterdam, 1995, Chap. 9, pp. 383–432.

201244.tex; 16/04/1999; 8:01; p.14