A generalized quadrangle is an incidence structure of points and lines such that
These axioms are self-dual, and therefore the incidence structure dual to a $GQ$ is again a $GQ$.
The smallest interesting example has as points the 15 edges of $K_6$ and as lines the 15 1-factors of $K_6$; each edge is incident with the three 1-factors that contain it. A $GQ$ is thick if each point is on at least three lines and each line contains at least three points. If a $GQ$ is thick then it is point and line regular, this means there are integers $s$ and $t$ such that each point lies on exactly $t+1$ lines and each line contains exactly $s+1$ points. Our example above is a $GQ(2,2)$, traditionally denoted by $W(2)$.
Associated to an incidence structure we have a point graph, a line graph and an incidence graph. For $W(2)$ the point and line graphs are isomorphic to $L(K_6)$ (which is very easy to check); the incidence graph is a bipartite cubic graph on 30 vertices with diameter four and girth eight. It is known as Tutte's 8-cage. For a thick $GQ$, both the point and line graphs are strongly regular.
We describe how to construct a family of $GQ$'s denoted by $W(q)$, where $q$ is a primes power. We will accompany the description with the code for $W(3)$.
Let $V$ be the vector space of dimension four over $GF(q)$. Its 1-dimensional subspaces will be the points of our generalized quadrangle. To define the lines we want a non-degenerate alternating form on $V$; this is given by an invertible matrix $S$ with diagonal entries zero such that $S+S^T=0$. (So if $q$ is odd, then $S$ is skew symmetric; if $q$ is even it's symmetric with zero diagonal.) A subspace $U$ of $V$ is isotropic if \[ u^THv = 0 \] for all $u$, $v$ in $U$. All 1-dimensional subspaces of $V$ are isotropic and the lines of $W(q)$ will be the 2-dimensional isotropic subspaces.
Time for some actual work. We define our form:
def beta(u,v): return u*v+u*v -u*v -u*v
and create our points and lines:
V = VectorSpace( GF(3), 4) pnts = [u for u in V.subspaces(1)] lines = [sub for sub in V.subspaces(2)\ if beta(sub.matrix(),sub.matrix())==0]
Two points $u$ and $v$ are collinear if $\beta(u,v)=0$. Two lines $L$ and $M$ are incident if
(L != M) and (L.intersection(M) != V.zero_subspace()) # not tested
or if they are not equal and
det( L.matrix().stack(M.matrix)) == 0 # not tested
Elements of our vector space $V$ are "mutable", so not hashable, and therefore cannot be used as vertices of a graph. This is easily circumvented:
adj = lambda i,j: beta(pnts[i],pnts[j])==0 W3 = Graph([range(len(pnts)),adj], loops=False)
We can check that $W3$ is connected and regular, and that it has exactly three eigenvalues (obvious in the factored characteristic polynomial):
W3.is_connected(), W3.is_regular(), W3.am().fcp()
(True, True, (x - 12) * (x + 4)^15 * (x - 2)^24)
The lines of the $GQ$ correspond to the cliques of maximal size, which we can find by
cliques = W3.cliques_maximum()
We get the point graph of the dual $GQ$ by
adj = lambda i,j: i != j and det( lines[i].matrix().stack(lines[j].matrix())) == 0 W3d = Graph( [range(len(lines)), adj])
As expected $W3d$ is not isomorphic to $W3$, but it is strongly regular with the same parameters.
dp = distance_partition( W3, W3.vertices()) W3.is_equitable( dp, quotient_matrix=True)
[ 0 12 0] [ 1 2 9] [ 0 4 8]
dp = distance_partition( W3d, W3d.vertices()) W3d.is_equitable( dp, quotient_matrix=True)
[ 0 12 0] [ 1 2 9] [ 0 4 8]