implement Godsil's s.r.g.'s on q^3 vertices

dimpase commented 4 years ago

Godsil (1992) constructs strongly regular (v,k,l,mu)-graphs with v=q³, for a prime power q, and r | q+1 with

k=(q-1)((q+1)²/r -q), l=r((q+1)/r-1)³ +r-3, mu=((q+1)/r-1)((q+1)²/r-q), by taking the neighbourhood of certain antipodal cover of K_{q³+1}.

The latter are constructed by taking GQ(q,q²) with a spread S, removing all the edges inside the lines of S, and taking the antipodal quotient by a group generated by the element of order r fixing each line of S setwise.

GQ(q,q²) comes from the group GO^-(6,q), and S is left invariant by a subgroup GU(3,q).

Component: graph theory

Keywords: strongly regular graph, srg

Author: Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/29495

dimpase commented 4 years ago

comment:1

This is how to construct GU(3,q) in GO^-(6,q) in GAP, for q=8. Here these 513 lines are forming the spread we are after, etc

# C. D. Godsil,
# Krein covers of complete graphs,
# Australasian J. Comb. 6 (1992) 245-255.

LoadPackage("grape");
U:=Group(Union(GeneratorsOfGroup(GU(3,8)), [DiagonalMat(Z(64)^7*[1,1,1])]));
# GU(3,8)
F:=GF(GF(8),2);
# AsField( GF(2^3), GF(2^6) )
B:=Basis(F);
# CanonicalBasis( AsField( GF(2^3), GF(2^6) ) )
mo:=BlowUpIsomorphism(U,B);;
g:=Image(mo);;
spread:=Orbit(g,Z(2)*[[1,0,0,0,0,0],[0,1,0,0,0,0]],OnSubspacesByCanonicalBasis);;
Size(spread);
# 513
pts:=Orbit(g,Z(2)*[1,0,0,0,0,0],OnLines);;
s:=8;; t:=65;; # GQ(s,t), t=s^2.
Size(pts);
# 4617 (s+1)(st+1)
l:=Orbit(g,Z(2)*[[1,0,0,0,0,0],[0,0,0,0,1,0]],OnSubspacesByCanonicalBasis);;
Length(l);
# 32832 - should give the lines of GQ, together with the spread 
s:=Subspaces(VectorSpace(GF(8),l[1]),1);
L:=List(s,x->Position(pts,GeneratorsOfVectorSpace(x)[1]));
sspread:=Subspaces(VectorSpace(GF(8), Z(2)*[[1,0,0,0,0,0],[0,1,0,0,0,0]]),1);
Lspread:=List(sspread,x->Position(pts,GeneratorsOfVectorSpace(x)[1]));
a:=Action(g,pts,OnLines);
h:=Stabilizer(a,1);
G:=Position(pts,Z(2)*[1,0,0,0,0,0]);
#aL:=Union(Orbit(a,Set(L), OnSets), Orbit(a,Set(Lspread), OnSets));
G:=NullGraph(a);
for k in L do
if k<>L[1] then
AddEdgeOrbit(G,[L[1],k]);
AddEdgeOrbit(G,[k,L[1]]);
fi;
od;

if 1=0 then # otherwise we'll get GQ
for k in Lspread do
if k<>L[1] then
AddEdgeOrbit(G,[Lspread[1],k]);
AddEdgeOrbit(G,[k,Lspread[1]]);
fi;
od;
fi;
Print(GlobalParameters(G));
q:=List(Orbits(Group(a.2^3),[1..Length(pts)]),Set);

QG:=Graph(a,q,OnSets,function(x,y) return
  x<>y and []<>Intersection(Adjacency(G,x[1]),y); end);
Print(GlobalParameters(QG));
ii:=InducedSubgraph(QG,Adjacency(QG,1));; # the missing SRG
Print(GlobalParameters(ii));

mkoeppe commented 4 years ago

comment:2

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

mkoeppe commented 3 years ago

comment:4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

dimpase commented 2 years ago

Changed keywords from strongy regular graph to strongly regular graph

dimpase commented 2 years ago

Changed keywords from strongly regular graph to strongly regular graph, srg

sagemath / sage

implement Godsil's s.r.g.'s on q^3 vertices #29495