Gewirtz graph

The graph is the subgraph of the Higman-Sims graph induced on the set of vertices at distance 2 from two adjacent vertices (and this construction shows the full group). Adding an identity matrix to its adjacency matrix yields a biplane 2-(56,11,2), first constructed by Hall, Lane & Wales (1970). This graph is subgraph of the M22 graph on 77 vertices, the Higman-Sims graph on 100 vertices, the U4(3) graph on 112 vertices, the McL graph on 275 vertices and the G2(4) graph on 416 vertices. b) An edge . There are 280 of these, forming a single orbit. The stabilizer of one is 32:Q8.2×2 with vertex orbit sizes 2+18+36. In PG(2,4) these can be identified with the unitals (AG(2,3) subplanes): the complement of the union of two disjoint hyperovals is a unital. The graph on the 280 edges, where two edges are adjacent when they are opposite edges of a quadrangle, is distance-transitive with intersection array {9,8,6,3;1,1,3,8} and spectrum 91 464 1105 (–3)90 (–5)20. Its automorphism group Aut (L3(4)) is three times larger than that of the Gewirtz graph. The uniqueness of this graph (given its parameters) was shown by Lambeck. c) A 16-coclique . There are 42 of these, forming a single orbit. The stabilizer of one is 24.S5 with vertex orbit sizes 16+40. In the Higman-Sims graph these are visible as point neighbourhoods. Also in PG(2,4) these 16-cocliques are visible: each point is in 16 of our hyperovals, and these hyperovals are mutually nonadjacent. Moreover, each hyperoval has six exterior lines forming a dual hyperoval, and disjoint hyperovals have disjoint dual hyperovals; it follows that the 21 lines of PG(2,4) also give 16-cocliques. The graph on the 16-cocliques, adjacent when disjoint, is the point-line incidence graph of PG(2,4). Distance 0,1,2,3 in this graph corresponds to an intersection of size 16,0,4,6, respectively. f) co-Heawood graph . (The co-Heawood graph is the point-line nonincidence graph of the Fano plane.) There are 120 of these, forming a single orbit. The stabilizer of one is L2(7):2×2 with vertex orbit sizes 7+7+42. Their presence can be seen from the M24 construction: if our Gewirtz graph consists of the octads starting 110, then fix an octad B starting 001. There are 7, 42, 7 octads in our graph that meet B in 4, 2, 0 vertices, respectively, and the 7+7 induces a co-Heawood graph. The involution in M24 that fixes B pointwise, and fixes the pair contained in all Gewirtz octads fixes the co-Heawood graph pointwise. There is no automorphism here interchanging the two 7-cocliques in the co-Heawood graph. g) Splits into two Coxeter graphs . The Gewirtz graph has 240 splits into two Coxeter graphs, forming a single orbit. The stabilizer of one split is L2(7):2 with vertex orbit sizes 28+28. These splits can be seen inside the Higman-Sims graph. It has splits into two Hoffman-Singleton graphs. Choosing an edge that meets both sides we find that the subgraph of the Higman-Sims graph far away from that edge is split into two Coxeter graph s. The Gewirtz graph has independence number 16 and chromatic number 4. The complement of the Gewirtz graph has independence number 2 and chromatic number 28.