/^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 8 (2015) 55-67
Polarity graphs revisited
Martin Bachraty
Comenius University, Bratislava, Slovakia
Jozef Siran
Open University, Milton Keynes, U.K., and Slovak University of Technology, Bratislava, Slovakia
Received 29 August 2013, accepted 2 March 2014, published online 22 April 2014
Abstract
Polarity graphs, also known as Brown graphs, and their minor modifications are the largest currently known graphs of diameter 2 and a given maximum degree d such that d - 1 is a prime power larger than 5. In view of the recent interest in the degree-diameter problem restricted to vertex-transitive and Cayley graphs we investigate ways of turning the (non-regular) polarity graphs to large vertex-transitive graphs of diameter 2 and given degree.
We review certain properties of polarity graphs, giving new and shorter proofs. Then we show that polarity graphs of maximum even degree d cannot be spanning subgraphs of vertex-transitive graphs of degree at most d + 2. If d - 1 is a power of 2, there are two large vertex-transitive induced subgraphs of the corresponding polarity graph, one of degree d - 1 and the other of degree d - 2. We show that the subgraphs of degree d - 1 cannot be extended to vertex-transitive graphs of diameter 2 by adding a relatively small non-edge orbital. On the positive side, we prove that the subgraphs of degree d - 2 can be extended to the largest currently known Cayley graphs of given degree and diameter 2 found by Siagiova and the second author [J. Combin. Theory Ser. B 102 (2012), 470-473].
Keywords: Graph, polarity graph, degree, diameter, automorphism, group, vertex-transitive graph, Cayley graph.
Math. Subj. Class.: 05C25
E-mail addresses: mato4247@gmail.com (Martin Bachraty), j.siran@open.ac.uk (Jozef Siran) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
55
Ars Math. Contemp. 8 (2015) 149-162
1 Introduction
A graph of diameter 2 and maximum degree d can have at most d2 + 1 vertices. This can be seen by rooting the graph at a vertex of maximum degree and observing that the vertex set of the graph is the union of vertices at distance 0,1 and 2 from the root, giving the estimate 1 + d + d(d - 1) = d2 +1, also known as the Moore bound for diameter 2. Suchagraphof order d2 + 1 exists if and only if d =2,3,7 and possibly 57, by the classical result of [9]. Examples for the first three degrees - the pentagon, the Petersen graph and the Hoffman-Singleton graph - are unique, and existence of a graph of diameter 2, degree 57 and order 572 + 1 = 3250 is still an open problem. For all other values of d > 4 it is known [5] that the largest order of a graph of diameter 2 and maximum degree d is at most d2 - 1, but by [11] examples of graphs of that order are known only for d = 4, 5. Investigation of large graphs of given degree and diameter in general is part of the well known degree-diameter problem, surveyed in [11].
If d = q +1 where q is prime power such that q > 7, the largest currently known order of a graph of diameter 2 and maximum degree d is d2 - d +1 if q is odd and d2 - d +2 if q is even. Examples of graphs of such order, missing the Moore bound only by d and d - 1, are the polarity graphs B(q) for odd q and their minor modifications for even q; both will be described in the next section. Extensions of polarity graphs by adding Hamilton cycles and maximum matchings taken from the complement were considered in [15] and give graphs of maximum degree d, diameter 2 and order at least d2 - 2d1'525 for every sufficiently large d. This shows that the Moore bound can be met at least asymptotically for all sufficiently large degrees.
The polarity graphs B(q) were first introduced in 1962 by Erdos and Renyi [6] and later in 1966 independently by Brown [3] (and considered again by Erdos, Renyi and Sos [7]) in connection with asymptotic determination of the largest number of edges in a graph of a given order without cycles of length four. The notation B(q) is derived from the fact that in the degree-diameter research community these graphs have also been known as Brown graphs after their second independent discoverer. Properties of polarity graphs have been studied in considerable detail in [12], including determination of the automorphism group of these graphs and their important subgraphs. Since polarity graphs are not regular, they cannot be vertex-transitive; nevertheless they have a relatively large automorphism group which has three orbits on vertices. The role of polarity graphs in the degree-diameter problem was realized later (cf. [11]) and their modification in the case when q is a power of two comes from [5] and [4].
In view of the recent advances in constructions of large vertex-transitive graphs with given degree and diameter [11] it is of interest to ask if one can modify polarity graphs to obtain large vertex-transitive graphs of a given degree and diameter 2 for an infinite set of degrees. We will consider modifications by inserting new edges into a polarity graph or into an induced subgraph of a polarity graph.
It is unclear if extending polarity graphs by Hamilton cycles and maximum matchings [15] can ever produce vertex-transitive graphs. In Section 4 we show that it is not possible to extend a polarity graph B(q) for odd q > 37 to a vertex-transitive graph by increasing its maximum degree by two. Regarding subgraphs, the graph B(q) for q a power of 2 contains two large vertex-transitive induced subgraphs, one of degree q and order q2 and the other of degree q - 1 and order q(q - 1). We prove that the first subgraph cannot be extended to a vertex-transitive graph of diameter 2 by adding non-edge orbitals induced by the smallest
M. Bachraty and J. Siran: Polarity graphs revisited
57
transitive group of automorphisms of the graph. In contrast with this, the second subgraph is shown to be isomorphic to the Cayley graph discovered in [14], which is extendable to a Cayley graph of diameter 2 and degree d' + O^Vd7) for d' = q — 1 and which shows that the Moore bound for diameter 2 can be approached at least asymptotically. This equips the construction of [14] with a strong geometric flavour. Presentation of these results is preceded in Section 2 by a description of polarity graphs and their properties and in Section 3 by a study of symmetry properties of polarity graphs. In the final Section 5 we discuss possible generalizations.
2 Polarity graphs and their structure
Let q be a prime power and let F = GF(q) be the Galois field of order q. We let PG(2, q) denote the standard projective plane over F, with points represented by projective triples, that is, equivalence classes [a] of triples a = (ai,a2,a3) = (0,0,0) of elements of F, where two triples are equivalent if they are a non-zero multiple of each other. If a = (a1, a2, a3), we will simply write [a] = [a1, a2, a3]. The vertex set of the polarity graph B(q) is the set of all the q2 + q +1 points of PG(2, q), and two distinct vertices [a] and [b], where a = (a1, a2, a3) and b = (b1, b2, b3), are adjacent in B(q) if the corresponding triples are orthogonal, that is, if abT = a1b1 + a2b2 + a3b3 = 0. In the terminology of projective geometry this means that distinct vertices [a] and [b] are adjacent if and only if, in the projective plane PG(2, q), the point [a] lies on the line with homogeneous coordinates [b] and the point [b] lies on the line with homogeneous coordinates [a].
Parsons [12] derived a number of facts on the structure of polarity graphs. We will now give alternative proofs to some of the results of [12] we will need later. Our proofs are much shorter and are based on known facts about projective planes as presented in [8].
Let [a] = [a1, a2, a3] be a vertex of B (q). Identification of neighbours of [a] amounts to determining the solutions (x1, x2,x3) of the linear equation axT = a1x1 + a2x2 + a3x3 = 0. This equation has q2-1 non-zero solutions that represent (q2 — 1)/(q-1) = q+1 distinct projective points, which are different from [a] if and only if aaT = a2 + a2 + a3 = 0. It follows that a vertex [a] has q or q +1 neighbours in B(q) according to whether aaT is equal to zero or not. The projective triples [a] of PG(2, q) such that aaT = 0 are precisely those lying on the quadric xxT = 0, which is non-degenerate (and hence a conic) if and only if q is odd. Accordingly, the vertices [a] such that aaT = 0 will be called quadric vertices.
Lemma 2.1. The graph B(q) contains exactly q + 1 quadric vertices.
Proof. If q is odd, this is Theorem 5.21(i) of [8]. If q is even, a vertex [a1, a2, a3] is quadric if and only if a2 + a2 + a3 = 0, which is in characteristic 2 equivalent to a1 + a2 + a3 = 0, and there are exactly (q2 — 1)/(q — 1) = q + 1 such projective triples in this case. □
The vertex set of B(q) is thus a disjoint union of the set V of q2 vertices of degree q + 1 and the set W of q +1 quadric vertices, lying on the quadric xxT = 0. Let V1 be the subset of V comprising all vertices adjacent to at least one quadric vertex and let V2 = V\V1. With this notation we now present further structural information on the polarity graphs B(q) which we will use later.
58
Ars Math. Contemp. 8 (2015) 149-162
Proposition 2.2. For every prime power q the graph B(q) has the following properties:
(i)	The set W ofquadric vertices is independent.
(ii)	Each pair of vertices of V (adjacent or not) are connected by a unique path of length 2, while no edge incident to a quadric vertex is contained in any triangle; in particular, B(q) has diameter 2.
(iii)	If q is odd, then every vertex of Vi is adjacent to exactly two quadric vertices, and |Vi| = q(q +1)/2, |V2| = q(q - 1)/2.
(iv)	If q is odd, then the subgraphs of B(q) induced by V1 and V2 are regular of degree (q — 1)/2 and (q + 1)/2, respectively.
(v)	If q is even, then |V1| = q2 and V2 is empty; moreover, V1 contains a vertex v adjacent to all quadric vertices and every vertex in V1 \{v} is adjacent to exactly one quadric vertex and the subgraph of B(q) induced by the set V1\{v} is regular of degree q.
Proof. Let [a] = [a1, a2, a3] and [b] = [b1, b2, b3] be two distinct vertices of B(q), adjacent or not. Since the vectors a and b are linearly independent over F, the solution space of the linear system axT = 0, bxT = 0 has dimension one. It follows that no pair of quadric vertices can be adjacent and that every pair of distinct vertices are connected by exactly one path of length two, proving (i) and (ii). Note that (ii) also follows from the property of PG(2, q) that any two points lie on a unique line.
Let q be odd. Invoking Chapters 7 and 8 of [8], the set W forms a conic and hence an oval. By Corollary 8.2 of [8] applied to the oval W, every vertex of V1 and V2 corresponds to a line of PG(2, q) containing exactly two points of W (a bisecant) or no point of W (an external line), respectively, and |V1| = q(q + 1)/2, |V2| = q(q — 1)/2, which proves (iii). Table 8.1 of [8] shows that a bisecant contains (q — 1)/2 points each lying on exactly two lines determined by projective coordinates corresponding to a vertex in W, while an external line contains (q + 1)/2 points each of which lies on no line determined by projective coordinates corresponding to a vertex in W. This exactly translates to (iv).
If q is even, the q +1 vertices of W have the form [a1, a2, a3] with a1 + a2 + a3 =0. The vertex v = [1,1,1] adjacent to every vertex of W is, in the terminology of [8], the nucleus of W. By Corollary 8.8 of [8] on vertices different from the nucleus, every vertex of V1 is incident to exactly one vertex of W and V2 = 0, proving (v).	□
We note that the authors of [5] and [4] observed that, for q even, one may extend the polarity graph B(q) by adding a vertex and making it incident to all vertices in W; the new graphs will still have diameter 2.
3 Polarity graphs and their automorphisms
The automorphism group of B(q) was determined in [12]. Here we give a different and shorter proof, including a more detailed discussion on groups. The idea is to relate the polarity graphs B(q) to the point-line incidence graph of PG(2, q). We will represent the points and lines of PG(2, q) by projective triples (vectors) of F3 as in the case of vertices of B(q), except that points will be represented by row vectors and lines will be represented by column vectors (distinguished by the 'transpose' superscript). In this notation, a point [a] lies on a line [bT] in PG(2, q) if and only if abT = 0. The involution 6 on the union of the
M. Bachraty and J. Siran: Polarity graphs revisited
59
point set and the line set of PG(2, q) that interchanges [x] with [xT ] is the standard polarity of PG(2, q). The point-line incidence graph I(q) of PG(2, q) is the bipartite graph whose vertex set is the union of the point and line sets of PG(2, q), with a vertex [a] adjacent to a vertex [bT] if and only if the point [a] lies on the line [bT], that is, abT = 0. Observe that the standard polarity 0 is an automorphism of the bipartite graph I(q), interchanging its two vertex-parts.
The fundamental theorem of projective geometry (see e.g. [8]) tells us that the subgroup of all automorphisms of the graph I(q) that fix each of its two vertex parts setwise is isomorphic to the extension PrL(3, q) of the 3-dimensional projective linear group PGL(3, q) over F by the group of Galois automorphisms of F over the prime field of F. Elements of PrL(3, q) are pairs (A, y), where A e PGL(3, q) can be identified with an invertible 3 x 3 matrix over F and y e Gal(F). The action of such an element (A, y) on vertices [x] and [yT] of I(q) is given by first applying A via the assignment [x] ^ [xA] and [yT] ^ [A-1yT] and then applying y to all elements of the resulting projective triples.
We continue with a remark regarding orthogonal groups. By the 3-dimensional projective orthogonal group PGO(3, q) we mean the factor group of the subgroup of GL(3, q) consisting of orthogonal matrices by the centre of this subgroup (trivial if q is even and isomorphic to Z2 if q is odd). In characteristic 2 our definition is different from what appears to be a more usual way of introducing an orthogonal group in terms of preservation of a bilinear form and having an irreducible action on a vector space; nevertheless we hope that no confusion will arise.
The obvious extension PrO(3, q) of PGO(3, q) by Gal(F) acts on B(q) as a group of automorphisms. Indeed, an element of PrO(3, q) can be identified with a pair (A, y) as above, but this time with A being a 3 x 3 orthogonal matrix, that is, such that AT = A-1, with the obvious identification of A with -A if q is odd. The action is simply given by (A, y)[x] = [y(xA)], and it preserves edges of B(q) since xyT = 0 is equivalent to (xA)(yA)T = 0 by orthogonality of A. We begin by showing that that there are no other automorphisms of B(q).
Theorem 3.1. For every prime power q the automorphism group of the polarity graph B(q) is isomorphic to PrO(3, q).
Proof. Every automorphism a of B(q) induces an automorphism a of I(q) given by a[x] = a[x] and a[xT] = (a[x])T for every projective triple [x]. By the Fundamental theorem of projective geometry and our earlier discussion, the automorphism a may be represented by an action of a pair (A, y) representing an element of PrL(3, q), given by a[x] = [y(xA)] and a[xT] = [y(A-1xT)] for all projective triples [x]. But since a[x] = a[x] and a[xT] = (a[x])T, we have (a[x])T = a[xT] and hence [y(xA)]T = [y(A-1xT)]. As this is valid for all pairs (A, y), we have [xA]T = [A-1xT] for all projective triples [x]. Letting x be successively equal to (1,0,0), (0,1,0), (0,0,1), (1,1,0) and (1,0,1) one concludes that A-1 = SAT for some non-zero S e F. Taking determinants yields 1 = |SATA| = S3|A|2 and this is an equation between elements of the (cyclic) multiplicative group F * of F.
We will show that there is a y e F* such that y2 = S. This is obvious if q is even (since in such a case every element of F* has a unique square root), or if S = 1. If q is odd and S = 1, then 1 = S3|A|2 implies that a third power of S =1 is equal to 1 or to a second power of |A| 1 if |A| = 1. This is, in the cyclic group F* of even order q - 1, possible
60
Ars Math. Contemp. 8 (2015) 149-162
only if q - 1 is divisible by 3 and there is a 7 G F * such that S = 72 (and, in the second case, if |A| = 7-3). In all circumstances we therefore have a 7 G F* such that S = 72.
The matrix AY = 7 A is orthogonal, i.e., A-1 — A^. Since all our calculations are done with projective triples, the action of the original automorphism a may equivalently be described by a[x] = [^(xA7)] and a[xT] = [^>(A-1 xT)] for all projective triples [x], where the pair (AY, y>) represents an element of PrO(3, q) as a subgroup of PrL(3, q). This shows that every automorphism of B (q) is induced by an element of PrO(3, q). Since this group acts on B(q) as we saw earlier, the result follows.	□
It is known (cf. [8]) that PGO(3, q) = PGL(2, q) and PrO(3, q) = PrL(2, q) for every prime power q. Theorem 3.1 thus implies that if q = pn where p is a prime, then the graph B(q) has exactly nq(q2 - 1) automorphisms.
The groups PrO(3, q) and PGO(3, q) obviously preserve the sets W, V1 and V2 and the sets W, {v} and V1\{v}, depending on whether q is odd or even; it is easy to show that these sets are, in fact, orbits of PGO(3, q) on the vertices of B(q). Corollary 7.15 of [8] tells us that the group PGO(3, q) is triply transitive on W. For odd q the analysis of [12] shows that PGO(3, q) acts arc-transitively on the subgraphs induced by the vertex set V1 and V2. We can say much more if q is even, extending the last result of Section 6 of [12]. Let B0(q) be the subgraph of B(q) induced by the set V0 = Vl\{v}.
Theorem 3.2. If q is a power of 2, the automorphism group of the graph B0(q) is isomorphic to PrO(3,q). Moreover, if q > 4, the smallest subgroup of PrO(3, q) acting transitively on vertices of B0(q) is the group PGO(3, q), which also acts regularly on arcs of B0(q). In particular, B0(q) is a vertex-transitive non-Cayley graph if q > 2.
Proof. For every w G W let Nw be the set of neighbours of w in B(q) distinct from v. Part (v) of Proposition 2.2 implies that the sets Nw (w G W) form a partition of the vertex set of B0 (q). In the subgraph B0 (q) the distance of any two vertices is greater than 2 if and only if the two vertices are in the same set Nw for some w g W .It follows that any automorphism of B0(q) preserves the partition {Nw; w G W} and hence extends to an automorphism of the entire polarity graph B(q). Consequently, by Theorem 3.1, the automorphism group of B0(q) is isomorphic to PrO(3, q); this was also noted in Section 6 of [12].
The rest of the proof will address the smallest group transitive on vertices of B0 (q). It is easy to check that B0(2) is isomorphic to a complete graph of order 3, admitting a regular action of a subgroup of PrO(3, q) = S3 isomorphic to Z3. From now on we therefore assume that q > 4.
By the remark after Theorem 3.1 we know that PrO(3, q) = PrL(2, q), and for q = 2n with n > 2 we have PrL(2, q) = SL(2, q) x Zn, the split extension being defined by the natural action of Zn = Aut(GF(q)) on SL(2, q). In what follows we will, for simplicity of the arguments, identify the group PrO(3, q) with the group G = SL(2, q) x Zn. We also let K = SL(2, q) and note that K is normal in G.
Suppose that H is a subgroup of G acting transitively on the vertex set of B0 (q). Letting H0 = H n K and observing that H0 is normal in H, from the second group isomorphism theorem we have H/H0 = HK/K. It follows that the order of H/H0 is a divisor of n. On the other hand, the transitivity assumption on H implies that the order of H is a multiple of q2 - 1, the number of vertices of B0(q). These two facts imply that |H0| = t(q2 - 1)/n for some positive integer t. Since H0 has now been identified with a subgroup of K =
M. Bachraty and J. Siran: Polarity graphs revisited
61
SL(2, q), the task reduces to identification of subgroups of the group SL(2, q) = PSL(2, q), q = 2n, of order t(q2 - 1)/n.
We will show that PSL(2, q) admits no such proper subgroup H0 if n > 2, using Dickson's classification of subgroups of PSL(2, q) for q = 2n as displayed in [13]. By this classification, subgroups of PSL(2, q) split into four classes: (a) cyclic and dihedral subgroups, (b) affine subgroups, (c) subgroups isomorphic to A4 or A5 for n even, and (d) subgroups of the form PSL(2,2m) where m is a divisor of n. We analyse the cases separately, recalling that throughout we assume q = 2n and n > 2.
(a)	Cyclic and dihedral subgroups. The largest order of a subgroup of PSL(2, q) that is cyclic or dihedral is 2(q + 1). It is easy to see that 2(q +1) < t(q2 - 1)/n for n > 3 and all t > 1; if n = 2 then t has to be even and then the same inequality holds. It follows that H0 cannot be cyclic or dihedral.
(b)	Affine subgroups. The largest order of an affine subgroup of PSL(2, q) is q(q - 1) and the second largest order of such a subgroup is Jq(Jq - 1) if n is even. If q(q - 1) = t(q2 - 1)/n, then nq = t(q + 1) and q + 1 would have to divide n, a contradiction. For the second largest order, observe that Jq(Jq - 1) < q +1 < (q2 - 1)/n, the last inequality being a consequence of n > q - 1. We conclude that H0 cannot be affine.
(c)	The groups A4, A5. We may eliminate A4 since its order is 12 and the order of B0(22) is 15. Since the order of B0(24) is 28 -1, the only feasible value of n for H0 = A5 is n = 2. In this case, however, A5 = PSL(2,22) and so H0 would not be a proper subgroup of PSL(2,22).
(d)	Subgroups PSL(2, 2m) where m | n. Let H0 = PSL(2, 2m) for m a proper divisor of n. If n G {2,3}, then m = 1 and the order of PSL(2, 2) is too small for H0 to be transitive on vertices of B0(2n). If n > 4, then the largest order of such a subgroup H0 is at most Jq(q - 1). It is easy to check, however, that Jq(q - 1) < (q2 - 1)/n for n > 4, giving a contradiction again.
The above arguments show that, for q = 2n and n > 2, the smallest subgroup of PrO(3,q) = PrL(2, q) transitive on vertices of Bo(q) is the group PGO(3, q) = PSL(2, q). It is a matter of routine to check that this group is, in fact, regular on the arc set of B0(q). Combining the two facts we conclude that B0(q) is an arc-transitive (and, of course, vertex-transitive) non-Cayley graph for all n > 2.	□
4 Vertex-transitive graphs from polarity graphs?
Polarity graphs are, of course, not vertex-transitive. Being the largest currently known examples of graphs of maximum degree q + 1 and diameter 2, however, it is interesting to ask if one cannot add "a few" edges to a polarity graph to obtain a vertex-transitive graph. In [15] it was shown that it is impossible to construct a vertex-transitive graph of degree q+1 which would contain B(q) as a spanning subgraph. We extend this result to the degree q + 3 for odd q > 37.
Theorem 4.1. For any odd prime power q > 37 there is no vertex-transitive graph of degree q + 3 which contains the polarity graph B(q) as a spanning subgraph.
Proof. Let B = B(q) and let B' be a graph containing B as a spanning subgraph. Let E and E' be the edge set of B and B', respectively; edges of the set E and E'\E will be called old and new, respectively. Suppose now that B' is a vertex-transitive graph of degree
62
Ars Math. Contemp. 8 (2015) 149-162
q+3. Let u, v be vertices of B such that e = uv is a new edge and let N(u) and N(v) be the set of neighbours of u and v in B. From the fact that any two distinct non-adjacent vertices of B are joined by a unique path of length 2 it follows that there is a unique vertex, say, w, in N(u) n N(v). If |N(u)| = |N(v)|, the set of all old edges joining the set N(u)\{w} with the set N(v)\{w} forms a perfect matching between the two sets. If not, then |N(u) | and |N(v) | differ by one. Without loss of generality, if |N(u) | = |N(v) | + 1, then exactly one neighbour of u, say, t, is joined to w. In this case there is a perfect matching between the sets N(u)\{w, t} and N(v)\{w}. It follows that any new edge e = uv is contained in a set Se of quadrangles such that (1) |Se| > q - 1, and (2) any two quadrangles in Se share just the edge e and its end-vertices u, v.
An edge e G E' will be called thick if there exists a set Se of quadrangles with the properties (1) and (2) above. Note that this definition does not require e to be new, but the fact we have derived above implies that every new edge is thick. By the assumed vertex-transitivity, every vertex of B' must be incident to the same number, say, t, of thick edges. Since the degree of B' is supposed to be q + 3, every vertex in W is incident to at least three thick edges, so that t > 3. If t = 3, the three thick edges are all new and every vertex in V would be incident to exactly two new thick edges and one old thick edge. This would mean that there is a perfect matching on V formed by old thick edges, which is impossible since | V | = q2 and q is odd. It follows that t > 4, every vertex in W is incident to at least one old thick edge and every vertex in V is incident to at least two old thick edges.
Properties of B imply that for any vertex v G V2 the subgraph of B induced by the set N(v) is a perfect matching of (q + 1)/2 edges. Vertex-transitivity of B' then implies that for every vertex w G W the subgraph of B' induced by the set N'(w) of all q + 3 neighbours of w in B' contains a subset E!w of (q + 1)/2 mutually independent edges. Note that since there were no edges in N(w) in the graph B, all the edges in E'w must be new. At most three edges of E'w join a vertex from N(w) with a vertex in N'(w)\N(w), and so the subgraph of B' induced by the set N(w) contains a subset Ew c E'w of least (q +1)/2 - 3 = (q - 5)/2 new edges. Since any two neighbourhoods of vertices of W in the graph B intersect in exactly one vertex, the sets of new edges Ew , w G W, are mutually disjoint. For counting, imagine that every new edge consists of two new half-edges incident to the corresponding end-vertices. The q(q + 1)/2 vertices of Vl, each incident with two new half-edges, are incident to a total of q(q + 1) new half-edges. At least (q + 1)(q - 5) of these are 'absorbed' by vertices of Vl since the sets Ew, w g W, are pairwise disjoint and N (w) c Vl for every w G W .It follows that there are at most (q + 1)q - (q + 1)(q - 5) = 5(q + 1) new edges that join vertices of Vl with vertices outside Vl. In particular, there are at most 5(q + 1) new edges between Vl and V2.
We know that every vertex w G W is incident to an old thick edge; let e = wv be such an edge, v G Vl. Let Se be a set of quadrangles with the properties (1) and (2) introduced earlier. At most 3 quadrangles of Se can contain a new edge incident with w, at most 2 such quadrangles can contain a new edge incident with v, and since v has at most (q - 1)/2 + 2 neighbours from Vl in the graph B', at most (q - 1)/2 + 2 quadrangles in Se contain a new edge having both end-vertices in Vl . Note that in each quadrangle containing three old edges the fourth edge must be new. Consequently, there are at least (q - 1) - ((q - 1)/2 + 7) = (q - 15)/2 quadrangles in Se containing at least one new edge joining a vertex in Vl with a vertex in V2. Since our considerations are valid for every vertex w G W, the neighbourhoods N (w) in the graph B intersect just in one vertex, and every vertex in Vl is incident to two new edges, we conclude that there are at least
M. Bachraty and J. Siran: Polarity graphs revisited
63
((q + 1)(q - 15)/2)/2 new edges joining V1 with V2. But we have seen earlier that the number of such edges is at most 5(q + 1). Thus, (q + 1)(q - 15)/4 < 5(q + 1), that is, q < 35, contrary to our assumption that q > 37.	□
Another obvious method to create large vertex-transitive graphs from polarity graphs is to take a large vertex-transitive subgraph of B(q) and try to extend it to a vertex-transitive graph of diameter 2 by adding edges. The hottest candidate for this is the subgraph B0 (q) if q is a power of 2, which we have encountered in the previous section.
Theorem 3.2, however, is bad news for adding edges to B0(q) to produce a vertex-transitive graph of diameter two. Namely, the most natural approach would be to take the smallest group H acting transitively on the set of vertices of B0(q) and identify the smallest possible number of H-orbits of non-adjacent pairs of vertices so that making these pairs adjacent would yield a graph of diameter 2 with B0(q) as a spanning subgraph. But by Theorem 3.2, for q > 4 the smallest such subgroup H is isomorphic to PGO(3, q), acting transitively and with vertex stabilisers of order q. It follows that an orbit furnishing new edges would increase the degree of the resulting graph by at least q. This would make the resulting graph uninteresting from the point of view of the degree-diameter problem.
Before continuing let us comment on the isomorphism of the groups PGO(3, q) and PGL(2, q), mentioned after the proof of Theorem 3.1. In [8] an isomorphism of the two groups is given, induced by the quadratic form x" + xix3. While for odd q such a form is equivalent to x" + x" + x" which we have been using, this is not true for even q since for q a power of 2 the form x1 + x" + x" is degenerate. It is easy to check that, with respect to this form, all elements of PGO(3, q) for q even have the form
1 + a	1 + c	1 + a + c
1+b 1+d 1+b+d K1 + a + b 1 + c + d 1 + a + b + c + dj
where a, b, c, d G F = GF(q) and ad + bc = 1, which implies that (a, b) = (0,0). Then, for even q, one may check that the mapping ^ : PGO(3, q) ^ PGL(2, q) given by
1 + a	1 + c	1 + a + c \
1+b 1+d 1+b+d i ^ (da
1 + a + b 1 + c+ d 1 + a + b + c+ d	d b
is a group isomorphism. We will use its inverse in the proof of our last two result.
In contrast with Theorem 3.2, there exists a subgroup of PGO(3, q) that is transitive on the set V* = Vo \ {[t, t, 1], t G GF(q)}; let B*(q) be the subgraph of Bo(q) induced by the set V*. Our last result shows that we can construct large Cayley graphs of diameter 2 and degree d = q + O(^q) by adding edges to B*(q). Since the order of B*(q) is q(q - 1) = d" - O(d3/"), the resulting graphs will be asymptotically approaching the Moore bound.
Theorem 4.2. For every even prime power q there exists a Cayley graph of diameter 2 and degree q + O(^q) with B*(q) as a spanning subgraph.
Proof. Let H be the subgroup of PGO(3, q) formed by all the matrices as in (4) for which a + b + c + d = 0. It is straightforward to check that |H| = q(q - 1) and that H acts regularly on the vertex set of the graph B*(q). It follows that B*(q) is a Cayley graph
64
Ars Math. Contemp. 8 (2015) 149-162
Cay(H, X) for the group H and some inverse-closed generating set X c H such that |X| = q - 1, which is the degree of B*(q).
In order to create a Cayley graph of diameter 2 from B*(q) by adding O(^q) edges it is sufficient to show that one can extend the generating set X to a set X' D X by adding O(^q) elements of H. Since we are dealing with a Cayley graph, it is sufficient to check distances from one particular vertex u, say, u = [1,0,0]. Compared with the graph B(q), in our new graph B*(q) the vertex u lost two neighbours, namely, v1 = [0,1,1] and v2 = [0,0,1]. We consider the effect caused by losing the two neighbours separately.
Since uv1 is not an edge of B* (q), we lost the paths of length 2 joining u with vertices in the subset U1 of B*(q) of the form [1,t,t], t € F, t = 0,1. Consider the subgroup
H1 < H formed by the matrices ^-1( Jg), g € F*, where
J = ( 5 0
Jg = U + g-1 g-1
It may be verified that H1 = F* and H1 acts regularly on the set U1 U {u}. Geometrically, H1 can be identified with the group of homologies (that is, central-axial collineations with a non-incident center-axis pair) with centre v1 and axis vv2. Since F* is Abelian (in fact, cyclic), there exists an inverse-closed set X1 of at most	elements such that the
Cayley graph Cay(H1, X1) with vertex set U1 U {u} has diameter 2.
The effect of the missing edge uv2 is that we lost the paths of length 2 joining u with vertices in the subset U2 of B*(q) of the form [a + 1, a, 0], a € F*. Let now H2 < H be the subgroup of H consisting of the matrices ^-1(La), a € F+, where
a +1 a a a +1
Obviously, H2 = F + and H2 is easily seen to be a regular permutation group on the set U2 U {u}. From the point of view of geometry, H2 can be identified with the group of elations (central-axial collineations with an incident center-axis pair) with centre [1,1,0] and axis vv2. Again, it is well known that there exists an inverse-closed set X2 of at most [2yq] elements, making Cay(H2, X2) a graph of diameter 2 with vertex set U2 U {u}.
It is now easy to check that the graph Cay(H, X') with X' = X U X1 U X2 has the required properties.	□
Cayley graphs of diameter 2, order q(q - 1) and degree q + O(^q) for even q have been recently constructed in [14] as follows. For q a power of 2 and F = GF(q) consider the one-dimensional affine group Gq = AGL(1,q) ~ F + x F*, with elements written as pairs (g, a), g € F*, and a € F+ and with multiplication in the form (g, a)(h, b) = (gh, ah + b) for g, h € F* and a, b € F +. The set Yq = {(y2, y); y € F*} is an inverse-closed generating set of Gq. The graphs of [14] are formed by taking the Cayley graph Cay(Gq, Yq) and adding a suitable set of further	generators to Yq.
Our last result shows that, quite surprisingly, the Cayley graphs Cay(Gq, Yq) from [14] are isomorphic to the graphs B* (q). This gives the construction of [14] a strong geometric flavour.
Theorem 4.3. If q is a power of 2, the graph Cay(Gq, Yq) is isomorphic to B*(q).
M. Bachraty and J. Siran: Polarity graphs revisited
65
Proof. We will use the notation introduced in the proof of Theorem 4.2, by which the graph B* (q) is isomorphic to the Cayley graph Cay (H, X). It may be checked that every element of H can be written as a product ^-1( Jg La) with g G F* and a G F + . Let us identify this product with the ordered pair [g, a]. One easily verifies that in this identification the multiplication o of elements of H is represented in the form [g, a] o [h, 6] = [gh, ah-2 + 6]. A further composition of the mapping (JgLa) ^ [g, a] with ^ : [g, a] ^ (g-2, a) establishes an isomorphism H = Gq.
It remains to analyse the generating set X, which is uniquely determined by the elements of H that take a fixed vertex of B* (q) to all its neighbours; in what follows our fixed vertex will be u = [1,0,0]. Now, multiplication of the row vector (1,0,0) by the matrix ^-1( JgLa) yields the vector (1 + ag, 1 + g + ag, 1 + g). This means that the element of H encoded [g, a] takes the vertex u onto the vertex [1 + ag, 1 + g + ag, 1 + g] of B* (q). Since the neighbours of u in B*(q) have the form [0,1, s] for s G F, s = 1, the elements of H taking u to the neighbours of u are encoded by pairs [t-1, t] for t G F *. The generating set X of H thus consists, in our representation, of all the pairs [t-1, t], where t G F*. Composition with the mapping ^ introduced earlier finally establishes the isomorphism from the Cayley graph Cay(H, X) onto the Cayley graph Cay(Gq, Yq) of [14].	□
5 Remarks
Adjacency in polarity graphs B(q) has been defined by means of the standard dot product. For odd q the standard dot product is just a special case of a symmetric non-singular bilinear form. What happens if one uses a more general form instead? Following [2], for an odd prime power q let Q be a non-singular quadratic form over F3 where F = FG(q), and let P(x, y) = Q(x + y) - Q(x) - Q(y) be the corresponding non-singular symmetric bilinear form. We now may let Bp(q) be the graph on the same vertex set as B(q), but with two distinct vertices [a] and [6] adjacent if P(a, 6) = 0. It is known, however (see e.g. [2, 8]), that in dimension 3 and for odd q, all non-singular quadratic forms are equivalent and their equivalence is induced by linear transformations (i.e., by change of bases). It follows that for odd q all such graphs Bp(q) are isomorphic to B(q), with isomorphisms being provided by the corresponding linear transformations. Of course, such a correspondence between quadratic forms and bilinear forms fails in characteristic 2.
Another way of generalizing polarity graphs is to define them on more general finite projective planes. Recall that a finite projective plane P is a collection of a finite number of points and lines such that every two points are incident with a unique line, every two lines are incident with a unique point, and there are four points no three of which are incident with a line. It is well known that for any such P there is an integer n such that any line is incident with precisely n +1 points and, dually, any point is incident with exactly n +1 lines. One then speaks about a projective plane of order n, and it is then easy to show that the number of points and the number of lines are both equal to n2 + n +1. (An outstanding conjecture in finite geometry is that the order of a finite projective plane must be a prime power.)
Suppose now that P has a polarity, that is, a bijection n from the point set onto the line set of P with the property that for every two points A and B, A is incident with n(B) if and only if B is incident with n(A). We may then define the generalized polarity graph Bpn with vertex set equal to the point set of P and with two distinct points A and B adjacent if A is incident with n(B). This graph obviously has diameter 2 by the properties
67
Ars Math. Contemp. 8 (2015) 149-162
of the projective plane. Observe that if P = PG(2, q) is the standard projective plane as introduced in Section 2 and if one considers the standard polarity n interchanging projective vectors with their transposes, then the graph Bp,n coincides with the polarity graph B(q). It is of interest to point out that if P is a (general) finite projective plane of order n with a polarity n, then, by [1], the number m(n) of self-conjugate points (those incident with their n-images) satisfies m(n) > n +1, and if m(n) > n +1 then n is a square and every prime divisor of n divides m(n) - 1. Since the corresponding generalized polarity graph Bp,n has exactly m(n) vertices of degree n and all the remaining vertices have degree n +1 it follows that for n = q, where q is an even power of a prime, the graph Bp,n need not be isomorphic to B(q). Investigation of such a generalization of polarity graphs may lead to interesting results.
We conclude by commenting on vertex-transitive extensions of polarity graphs. In general, by a vertex-transitive closure of a graph G we will understand any vertex-transitive supergraph of G on the same vertex set. We may then define dvt(G) to be the smallest degree of a vertex-transitive closure of G. In this terminology, our Theorem 4.1 says that dvt(Bq) > q + 5 for any odd prime power q > 37. Determining or at least estimating dvt(G) for arbitrary graphs G appears to be an interesting problem on its own.
Acknowledgement. The authors would like to thank an anonymous referee for carefully reading the manuscript, suggesting important improvements and providing geometric insight into the groups used in Section 4.
The second author acknowledges support from the VEGA Research Grants 1/0871/11, 1/0065/13 and 1/0007/14, the APVV Research Grants 0223-10 and 0136-12, as well as the APVV support as part of the EUROCORES Programme EUROGIGA, project GREGAS, ESF-EC-0009-10, financed by the European Science Foundation.
References
[1]	R. Baer, Polarities in finite projective planes, Bull. Amer. Math. Soc. 52 (1946), 77-93.
[2]	S. Ball and Z. Weiner, An Introduction to Finite Geometry, Preprint (2011).
[3]	W. G. Brown, On graphs that do not contain a Thomsen graph, Canad. Math. Bull. 9 (1966), 281-285.
[4]	C. Delorme, Examples of products giving large graphs with given degree and diameter, Discrete Applied Math. 37-38 (1992), 157-167.
[5]	P. Erdos, S. Fajtlowicz and A. J. Hoffman, Maximum degree in graphs of diameter 2, Networks 10 (1980), 87-90.
[6]	P. Erd6s and A. Renyi, On a problem in the theory of graphs, Magyar Tud. Akad. Mat. Kutato Int. Kozl. 7 (1962), 623-641.
[7]	P. ErdSs, A. Renyi and V. T. S6s, On a problem of graph theory, Studia Sci. Math. Hungar. 1 (1966), 215-235.
[8]	J. Hirschfeld, Projective geometries over finite fields, Oxford University Press, 1998.
[9]	A. J. Hoffman and R. R. Singleton, On Moore graphs with diameter 2 and 3, IBM J. Res. Develop. 4 (1960), 497-504.
[10] B. Huppert, Endliche Gruppen 1, Springer, 1967.
M. Bachraty and J. Siran: Polarity graphs revisited
105
[11]	M. Miller and J. Siráñ, Moore graphs and beyond: A survey of the degree-diameter problem, Electronic J. Combin. (2013), Dynamic survey DS14.
[12]	T. D. Parsons, Graphs from projective planes, Aequat. Math. 14 (1976), 167-189.
[13]	J. De Saedeleer and D. Leemans, On the rank two geometries of the groups PSL(2, q): part I, ArsMath. Contemp. 3 (2010), 177-192.
[14]	J. Siagiova and J. Siran, Approaching the Moore bound for diameter two by Cayley graphs, J. Combin. Theory Ser. B 102 (2012), 470-473.
[15]	J. Siran, J. Siagiova and M. Zdimalova, Large graphs of diameter two and given degree, in: Proc. IWONT 2010, Univ. Politecnica de Catalunya, 2011, 347-359.