Families of graphs derived from classical geometries over finite fields¶

These include graphs of polar spaces, affine polar graphs, graphs related to Hermitean unitals, graphs on nonisotropic points, etc.

The methods defined here appear in sage.graphs.graph_generators.

sage.graphs.generators.classical_geometries.AffineOrthogonalPolarGraph(d, q, sign='+')[source]¶

Return the affine polar graph \(VO^+(d,q),VO^-(d,q)\) or \(VO(d,q)\).

Affine Polar graphs are built from a \(d\)-dimensional vector space over \(F_q\), and a quadratic form which is hyperbolic, elliptic or parabolic according to the value of sign.

Note that \(VO^+(d,q),VO^-(d,q)\) are strongly regular graphs, while \(VO(d,q)\) is not.

For more information on Affine Polar graphs, see Affine Polar Graphs page of Andries Brouwer’s website.

INPUT:

d – integer; d must be even if sign is not None, and odd otherwise
q – integer; a power of a prime number, as \(F_q\) must exist
sign – string (default: '+'); must be equal to '+', '-', or None to compute (respectively) \(VO^+(d,q),VO^-(d,q)\) or \(VO(d,q)\)

Note

The graph \(VO^\epsilon(d,q)\) is the graph induced by the non-neighbors of a vertex in an Orthogonal Polar Graph \(O^\epsilon(d+2,q)\).

EXAMPLES:

The Brouwer-Haemers graph is isomorphic to \(VO^-(4,3)\):

Sage

sage: g = graphs.AffineOrthogonalPolarGraph(4,3,"-")                            # needs sage.libs.gap
sage: g.is_isomorphic(graphs.BrouwerHaemersGraph())                             # needs sage.libs.gap
True

Python

>>> from sage.all import *
>>> g = graphs.AffineOrthogonalPolarGraph(Integer(4),Integer(3),"-")                            # needs sage.libs.gap
>>> g.is_isomorphic(graphs.BrouwerHaemersGraph())                             # needs sage.libs.gap
True

Some examples from Brouwer’s table or strongly regular graphs:

Sage

sage: # needs sage.libs.gap
sage: g = graphs.AffineOrthogonalPolarGraph(6,2,"-"); g
Affine Polar Graph VO^-(6,2): Graph on 64 vertices
sage: g.is_strongly_regular(parameters=True)
(64, 27, 10, 12)
sage: g = graphs.AffineOrthogonalPolarGraph(6,2,"+"); g
Affine Polar Graph VO^+(6,2): Graph on 64 vertices
sage: g.is_strongly_regular(parameters=True)
(64, 35, 18, 20)

Python

>>> from sage.all import *
>>> # needs sage.libs.gap
>>> g = graphs.AffineOrthogonalPolarGraph(Integer(6),Integer(2),"-"); g
Affine Polar Graph VO^-(6,2): Graph on 64 vertices
>>> g.is_strongly_regular(parameters=True)
(64, 27, 10, 12)
>>> g = graphs.AffineOrthogonalPolarGraph(Integer(6),Integer(2),"+"); g
Affine Polar Graph VO^+(6,2): Graph on 64 vertices
>>> g.is_strongly_regular(parameters=True)
(64, 35, 18, 20)

When sign is None:

Sage

sage: # needs sage.libs.gap
sage: g = graphs.AffineOrthogonalPolarGraph(5,2,None); g
Affine Polar Graph VO^-(5,2): Graph on 32 vertices
sage: g.is_strongly_regular(parameters=True)
False
sage: g.is_regular()
True
sage: g.is_vertex_transitive()
True

Python

>>> from sage.all import *
>>> # needs sage.libs.gap
>>> g = graphs.AffineOrthogonalPolarGraph(Integer(5),Integer(2),None); g
Affine Polar Graph VO^-(5,2): Graph on 32 vertices
>>> g.is_strongly_regular(parameters=True)
False
>>> g.is_regular()
True
>>> g.is_vertex_transitive()
True

sage.graphs.generators.classical_geometries.AhrensSzekeresGeneralizedQuadrangleGraph(q, dual=False)[source]¶

Return the collinearity graph of the generalized quadrangle \(AS(q)\), or of its dual

Let \(q\) be an odd prime power. \(AS(q)\) is a generalized quadrangle (Wikipedia article Generalized_quadrangle) of order \((q-1,q+1)\), see 3.1.5 in [PT2009]. Its points are elements of \(F_q^3\), and lines are sets of size \(q\) of the form

\(\{ (\sigma, a, b) \mid \sigma\in F_q \}\)
\(\{ (a, \sigma, b) \mid \sigma\in F_q \}\)
\(\{ (c \sigma^2 - b \sigma + a, -2 c \sigma + b, \sigma) \mid \sigma\in F_q \}\),

where \(a\), \(b\), \(c\) are arbitrary elements of \(F_q\).

INPUT:

q – a power of an odd prime number
dual – boolean (default: False); whether to return the collinearity graph of \(AS(q)\) or of the dual \(AS(q)\) (when True)

EXAMPLES:

Sage

sage: g = graphs.AhrensSzekeresGeneralizedQuadrangleGraph(5); g
AS(5); GQ(4, 6): Graph on 125 vertices
sage: g.is_strongly_regular(parameters=True)
(125, 28, 3, 7)
sage: g = graphs.AhrensSzekeresGeneralizedQuadrangleGraph(5, dual=True); g
AS(5)*; GQ(6, 4): Graph on 175 vertices
sage: g.is_strongly_regular(parameters=True)
(175, 30, 5, 5)

Python

>>> from sage.all import *
>>> g = graphs.AhrensSzekeresGeneralizedQuadrangleGraph(Integer(5)); g
AS(5); GQ(4, 6): Graph on 125 vertices
>>> g.is_strongly_regular(parameters=True)
(125, 28, 3, 7)
>>> g = graphs.AhrensSzekeresGeneralizedQuadrangleGraph(Integer(5), dual=True); g
AS(5)*; GQ(6, 4): Graph on 175 vertices
>>> g.is_strongly_regular(parameters=True)
(175, 30, 5, 5)

sage.graphs.generators.classical_geometries.CossidentePenttilaGraph(q)[source]¶

Return the Cossidente-Penttila \(((q^3+1)(q+1)/2,(q^2+1)(q-1)/2,(q-3)/2,(q-1)^2/2)\)-strongly regular graph

For each odd prime power \(q\), one can partition the points of the \(O_6^-(q)\)-generalized quadrangle \(GQ(q,q^2)\) into two parts, so that on any of them the induced subgraph of the point graph of the GQ has parameters as above [CP2005].

Directly following the construction in [CP2005] is not efficient, as one then needs to construct the dual \(GQ(q^2,q)\). Thus we describe here a more efficient approach that we came up with, following a suggestion by T.Penttila. Namely, this partition is invariant under the subgroup \(H=\Omega_3(q^2)<O_6^-(q)\). We build the appropriate \(H\), which leaves the form \(B(X,Y,Z)=XY+Z^2\) invariant, and pick up two orbits of \(H\) on the \(F_q\)-points. One them is \(B\)-isotropic, and we take the representative \((1:0:0)\). The other one corresponds to the points of \(PG(2,q^2)\) that have all the lines on them either missing the conic specified by \(B\), or intersecting the conic in two points. We take \((1:1:e)\) as the representative. It suffices to pick \(e\) so that \(e^2+1\) is not a square in \(F_{q^2}\). Indeed, The conic can be viewed as the union of \(\{(0:1:0)\}\) and \(\{(1:-t^2:t) | t \in F_{q^2}\}\). The coefficients of a generic line on \((1:1:e)\) are \([1:-1-eb:b]\), for \(-1\neq eb\). Thus, to make sure the intersection with the conic is always even, we need that the discriminant of \(1+(1+eb)t^2+tb=0\) never vanishes, and this is if and only if \(e^2+1\) is not a square. Further, we need to adjust \(B\), by multiplying it by appropriately chosen \(\nu\), so that \((1:1:e)\) becomes isotropic under the relative trace norm \(\nu B(X,Y,Z)+(\nu B(X,Y,Z))^q\). The latter is used then to define the graph.

INPUT:

q – an odd prime power

EXAMPLES:

For \(q=3\) one gets Sims-Gewirtz graph.

Sage

sage: G = graphs.CossidentePenttilaGraph(3)     # optional - gap_package_grape
sage: G.is_strongly_regular(parameters=True)    # optional - gap_package_grape
(56, 10, 0, 2)

Python

>>> from sage.all import *
>>> G = graphs.CossidentePenttilaGraph(Integer(3))     # optional - gap_package_grape
>>> G.is_strongly_regular(parameters=True)    # optional - gap_package_grape
(56, 10, 0, 2)

For \(q>3\) one gets new graphs.

Sage

sage: G = graphs.CossidentePenttilaGraph(5)     # optional - gap_package_grape
sage: G.is_strongly_regular(parameters=True)    # optional - gap_package_grape
(378, 52, 1, 8)

Python

>>> from sage.all import *
>>> G = graphs.CossidentePenttilaGraph(Integer(5))     # optional - gap_package_grape
>>> G.is_strongly_regular(parameters=True)    # optional - gap_package_grape
(378, 52, 1, 8)

sage.graphs.generators.classical_geometries.HaemersGraph(q, hyperoval=None, hyperoval_matching=None, field=None, check_hyperoval=True)[source]¶

Return the Haemers graph obtained from \(T_2^*(q)^*\).

Let \(q\) be a power of 2. In Sect. 8.A of [BL1984] one finds a construction of a strongly regular graph with parameters \((q^2(q+2),q^2+q-1,q-2,q)\) from the graph of \(T_2^*(q)^*\), constructed by T2starGeneralizedQuadrangleGraph(), by redefining adjacencies in the way specified by an arbitrary hyperoval_matching of the points (i.e. partitioning into size two parts) of hyperoval defining \(T_2^*(q)^*\).

While [BL1984] gives the construction in geometric terms, it can be formulated, and is implemented, in graph-theoretic ones, of re-adjusting the edges. Namely, \(G=T_2^*(q)^*\) has a partition into \(q+2\) independent sets \(I_k\) of size \(q^2\) each. Each vertex in \(I_j\) is adjacent to \(q\) vertices from \(I_k\). Each \(I_k\) is paired to some \(I_{k'}\), according to hyperoval_matching. One adds edges \((s,t)\) for \(s,t \in I_k\) whenever \(s\) and \(t\) are adjacent to some \(u \in I_{k'}\), and removes all the edges between \(I_k\) and \(I_{k'}\).

INPUT:

q – a power of two
hyperoval_matching – if None (default), pair each \(i\)-th point of hyperoval with \((i+1)\)-th. Otherwise, specifies the pairing in the format \(((i_1,i'_1),(i_2,i'_2),...)\).
hyperoval – a hyperoval defining \(T_2^*(q)^*\). If None (default), the classical hyperoval obtained from a conic is used. See the documentation of T2starGeneralizedQuadrangleGraph(), for more information.
field – an instance of a finite field of order \(q\), must be provided if hyperoval is provided
check_hyperoval – boolean (default: True); whether to check hyperoval for correctness or not

EXAMPLES:

using the built-in constructions:

Sage

sage: # needs sage.combinat sage.rings.finite_rings
sage: g = graphs.HaemersGraph(4); g
Haemers(4): Graph on 96 vertices
sage: g.is_strongly_regular(parameters=True)
(96, 19, 2, 4)

Python

>>> from sage.all import *
>>> # needs sage.combinat sage.rings.finite_rings
>>> g = graphs.HaemersGraph(Integer(4)); g
Haemers(4): Graph on 96 vertices
>>> g.is_strongly_regular(parameters=True)
(96, 19, 2, 4)

supplying your own hyperoval_matching:

Sage

sage: # needs sage.combinat sage.rings.finite_rings
sage: g = graphs.HaemersGraph(4, hyperoval_matching=((0,5),(1,4),(2,3))); g
Haemers(4): Graph on 96 vertices
sage: g.is_strongly_regular(parameters=True)
(96, 19, 2, 4)

Python

>>> from sage.all import *
>>> # needs sage.combinat sage.rings.finite_rings
>>> g = graphs.HaemersGraph(Integer(4), hyperoval_matching=((Integer(0),Integer(5)),(Integer(1),Integer(4)),(Integer(2),Integer(3)))); g
Haemers(4): Graph on 96 vertices
>>> g.is_strongly_regular(parameters=True)
(96, 19, 2, 4)

sage.graphs.generators.classical_geometries.NonisotropicOrthogonalPolarGraph(m, q, sign='+', perp=None)[source]¶

Return the Graph \(NO^{\epsilon,\perp}_{m}(q)\).

Let the vectorspace of dimension \(m\) over \(F_q\) be endowed with a nondegenerate quadratic form \(F\), of type sign for \(m\) even.

\(m\) even: assume further that \(q=2\) or \(3\). Returns the graph of the points (in the underlying projective space) \(x\) satisfying \(F(x)=1\), with adjacency given by orthogonality w.r.t. \(F\). Parameter perp is ignored.
\(m\) odd: if perp is not None, then we assume that \(q=5\) and return the graph of the points \(x\) satisfying \(F(x)=\pm 1\) if sign="+", respectively \(F(x) \in \{2,3\}\) if sign="-", with adjacency given by orthogonality w.r.t. \(F\) (cf. Sect 7.D of [BL1984]). Otherwise return the graph of nongenerate hyperplanes of type sign, adjacent whenever the intersection is degenerate (cf. Sect. 7.C of [BL1984]). Note that for \(q=2\) one will get a complete graph.

For more information, see Sect. 9.9 of [BH2012] and [BL1984]. Note that the page of Andries Brouwer’s website uses different notation.

INPUT:

m – integer; half the dimension of the underlying vectorspace
q – a power of a prime number, the size of the underlying field
sign – string (default: '+'); must be either '+' or '-'

EXAMPLES:

\(NO^-(4,2)\) is isomorphic to Petersen graph:

Sage

sage: g = graphs.NonisotropicOrthogonalPolarGraph(4,2,'-'); g                   # needs sage.libs.gap
NO^-(4, 2): Graph on 10 vertices
sage: g.is_strongly_regular(parameters=True)                                    # needs sage.libs.gap
(10, 3, 0, 1)

Python

>>> from sage.all import *
>>> g = graphs.NonisotropicOrthogonalPolarGraph(Integer(4),Integer(2),'-'); g                   # needs sage.libs.gap
NO^-(4, 2): Graph on 10 vertices
>>> g.is_strongly_regular(parameters=True)                                    # needs sage.libs.gap
(10, 3, 0, 1)

\(NO^-(6,2)\) and \(NO^+(6,2)\):

Sage

sage: # needs sage.libs.gap
sage: g = graphs.NonisotropicOrthogonalPolarGraph(6,2,'-')
sage: g.is_strongly_regular(parameters=True)
(36, 15, 6, 6)
sage: g = graphs.NonisotropicOrthogonalPolarGraph(6,2,'+'); g
NO^+(6, 2): Graph on 28 vertices
sage: g.is_strongly_regular(parameters=True)
(28, 15, 6, 10)

Python

>>> from sage.all import *
>>> # needs sage.libs.gap
>>> g = graphs.NonisotropicOrthogonalPolarGraph(Integer(6),Integer(2),'-')
>>> g.is_strongly_regular(parameters=True)
(36, 15, 6, 6)
>>> g = graphs.NonisotropicOrthogonalPolarGraph(Integer(6),Integer(2),'+'); g
NO^+(6, 2): Graph on 28 vertices
>>> g.is_strongly_regular(parameters=True)
(28, 15, 6, 10)

\(NO^+(8,2)\):

Sage

sage: g = graphs.NonisotropicOrthogonalPolarGraph(8,2,'+')                      # needs sage.libs.gap
sage: g.is_strongly_regular(parameters=True)                                    # needs sage.libs.gap
(120, 63, 30, 36)

Python

>>> from sage.all import *
>>> g = graphs.NonisotropicOrthogonalPolarGraph(Integer(8),Integer(2),'+')                      # needs sage.libs.gap
>>> g.is_strongly_regular(parameters=True)                                    # needs sage.libs.gap
(120, 63, 30, 36)

Wilbrink’s graphs for \(q=5\):

Sage

sage: # needs sage.libs.gap
sage: g = graphs.NonisotropicOrthogonalPolarGraph(5,5,perp=1)
sage: g.is_strongly_regular(parameters=True)    # long time
(325, 60, 15, 10)
sage: g = graphs.NonisotropicOrthogonalPolarGraph(5,5,'-',perp=1)
sage: g.is_strongly_regular(parameters=True)    # long time
(300, 65, 10, 15)

Python

>>> from sage.all import *
>>> # needs sage.libs.gap
>>> g = graphs.NonisotropicOrthogonalPolarGraph(Integer(5),Integer(5),perp=Integer(1))
>>> g.is_strongly_regular(parameters=True)    # long time
(325, 60, 15, 10)
>>> g = graphs.NonisotropicOrthogonalPolarGraph(Integer(5),Integer(5),'-',perp=Integer(1))
>>> g.is_strongly_regular(parameters=True)    # long time
(300, 65, 10, 15)

Wilbrink’s graphs:

Sage

sage: # needs sage.libs.gap
sage: g = graphs.NonisotropicOrthogonalPolarGraph(5,4,'+')
sage: g.is_strongly_regular(parameters=True)
(136, 75, 42, 40)
sage: g = graphs.NonisotropicOrthogonalPolarGraph(5,4,'-')
sage: g.is_strongly_regular(parameters=True)
(120, 51, 18, 24)
sage: g = graphs.NonisotropicOrthogonalPolarGraph(7,4,'+'); g        # not tested (long time)
NO^+(7, 4): Graph on 2080 vertices
sage: g.is_strongly_regular(parameters=True)                         # not tested (long time)
(2080, 1071, 558, 544)

Python

>>> from sage.all import *
>>> # needs sage.libs.gap
>>> g = graphs.NonisotropicOrthogonalPolarGraph(Integer(5),Integer(4),'+')
>>> g.is_strongly_regular(parameters=True)
(136, 75, 42, 40)
>>> g = graphs.NonisotropicOrthogonalPolarGraph(Integer(5),Integer(4),'-')
>>> g.is_strongly_regular(parameters=True)
(120, 51, 18, 24)
>>> g = graphs.NonisotropicOrthogonalPolarGraph(Integer(7),Integer(4),'+'); g        # not tested (long time)
NO^+(7, 4): Graph on 2080 vertices
>>> g.is_strongly_regular(parameters=True)                         # not tested (long time)
(2080, 1071, 558, 544)

sage.graphs.generators.classical_geometries.NonisotropicUnitaryPolarGraph(m, q)[source]¶

Return the Graph \(NU(m,q)\).

This returns the graph on nonisotropic, with respect to a nondegenerate Hermitean form, points of the \((m-1)\)-dimensional projective space over \(F_q\), with points adjacent whenever they lie on a tangent (to the set of isotropic points) line. For more information, see Sect. 9.9 of [BH2012] and series C14 in [Hub1975].

INPUT:

m, q – integers; \(q\) must be a prime power

EXAMPLES:

Sage

sage: g = graphs.NonisotropicUnitaryPolarGraph(5,2); g                          # needs sage.libs.gap
NU(5, 2): Graph on 176 vertices
sage: g.is_strongly_regular(parameters=True)                                    # needs sage.libs.gap
(176, 135, 102, 108)

Python

>>> from sage.all import *
>>> g = graphs.NonisotropicUnitaryPolarGraph(Integer(5),Integer(2)); g                          # needs sage.libs.gap
NU(5, 2): Graph on 176 vertices
>>> g.is_strongly_regular(parameters=True)                                    # needs sage.libs.gap
(176, 135, 102, 108)

sage.graphs.generators.classical_geometries.Nowhere0WordsTwoWeightCodeGraph(q, hyperoval=None, field=None, check_hyperoval=True)[source]¶

Return the subgraph of nowhere 0 words from two-weight code of projective plane hyperoval.

Let \(q=2^k\) and \(\Pi=PG(2,q)\). Fix a hyperoval \(O \subset \Pi\). Let \(V=F_q^3\) and \(C\) the two-weight 3-dimensional linear code over \(F_q\) with words \(c(v)\) obtained from \(v\in V\) by computing

\[c(v)=(\langle v,o_1 \rangle,...,\langle v,o_{q+2} \rangle), o_j \in O.\]

\(C\) contains \(q(q-1)^2/2\) words without 0 entries. The subgraph of the strongly regular graph of \(C\) induced on the latter words is also strongly regular, assuming \(q>4\). This is a construction due to A.E.Brouwer [Bro2016], and leads to graphs with parameters also given by a construction in [HHL2009]. According to [Bro2016], these two constructions are likely to produce isomorphic graphs.

INPUT:

q – a power of two
hyperoval – a hyperoval (i.e. a complete 2-arc; a set of points in the plane meeting every line in 0 or 2 points) in \(PG(2,q)\) over the field field. Each point of hyperoval must be a length 3 vector over field with 1st non-0 coordinate equal to 1. By default, hyperoval and field are not specified, and constructed on the fly. In particular, hyperoval we build is the classical one, i.e. a conic with the point of intersection of its tangent lines.
field – an instance of a finite field of order \(q\); must be provided if hyperoval is provided
check_hyperoval – boolean (default: True); whether to check hyperoval for correctness or not

See also

is_nowhere0_twoweight()

EXAMPLES:

using the built-in construction:

Sage

sage: # needs sage.combinat sage.rings.finite_rings
sage: g = graphs.Nowhere0WordsTwoWeightCodeGraph(8); g
Nowhere0WordsTwoWeightCodeGraph(8): Graph on 196 vertices
sage: g.is_strongly_regular(parameters=True)
(196, 60, 14, 20)
sage: g = graphs.Nowhere0WordsTwoWeightCodeGraph(16)  # not tested (long time)
sage: g.is_strongly_regular(parameters=True)          # not tested (long time)
(1800, 728, 268, 312)

Python

>>> from sage.all import *
>>> # needs sage.combinat sage.rings.finite_rings
>>> g = graphs.Nowhere0WordsTwoWeightCodeGraph(Integer(8)); g
Nowhere0WordsTwoWeightCodeGraph(8): Graph on 196 vertices
>>> g.is_strongly_regular(parameters=True)
(196, 60, 14, 20)
>>> g = graphs.Nowhere0WordsTwoWeightCodeGraph(Integer(16))  # not tested (long time)
>>> g.is_strongly_regular(parameters=True)          # not tested (long time)
(1800, 728, 268, 312)

supplying your own hyperoval:

Sage

sage: # needs sage.combinat sage.rings.finite_rings
sage: F = GF(8)
sage: O = [vector(F,(0,0,1)),vector(F,(0,1,0))] + [vector(F, (1,x^2,x))
....:                                              for x in F]
sage: g = graphs.Nowhere0WordsTwoWeightCodeGraph(8,hyperoval=O,field=F); g
Nowhere0WordsTwoWeightCodeGraph(8): Graph on 196 vertices
sage: g.is_strongly_regular(parameters=True)
(196, 60, 14, 20)

Python

>>> from sage.all import *
>>> # needs sage.combinat sage.rings.finite_rings
>>> F = GF(Integer(8))
>>> O = [vector(F,(Integer(0),Integer(0),Integer(1))),vector(F,(Integer(0),Integer(1),Integer(0)))] + [vector(F, (Integer(1),x**Integer(2),x))
...                                              for x in F]
>>> g = graphs.Nowhere0WordsTwoWeightCodeGraph(Integer(8),hyperoval=O,field=F); g
Nowhere0WordsTwoWeightCodeGraph(8): Graph on 196 vertices
>>> g.is_strongly_regular(parameters=True)
(196, 60, 14, 20)

sage.graphs.generators.classical_geometries.OrthogonalDualPolarGraph(e, d, q)[source]¶

Return the dual polar graph on \(GO^e(n,q)\) of diameter \(d\).

The value of \(n\) is determined by \(d\) and \(e\).

The graph is distance-regular with classical parameters \((d, q, 0, q^e)\).

INPUT:

e – integer; type of the orthogonal polar space to consider; must be \(-1, 0\) or \(1\)
d – integer; diameter of the graph
q – integer; prime power; order of the finite field over which to build the polar space

EXAMPLES:

Sage

sage: # needs sage.libs.gap
sage: G = graphs.OrthogonalDualPolarGraph(1,3,2)
sage: G.is_distance_regular(True)
([7, 6, 4, None], [None, 1, 3, 7])
sage: G = graphs.OrthogonalDualPolarGraph(0,3,3)        # long time
sage: G.is_distance_regular(True)                       # long time
([39, 36, 27, None], [None, 1, 4, 13])
sage: G.order()                                         # long time
1120

Python

>>> from sage.all import *
>>> # needs sage.libs.gap
>>> G = graphs.OrthogonalDualPolarGraph(Integer(1),Integer(3),Integer(2))
>>> G.is_distance_regular(True)
([7, 6, 4, None], [None, 1, 3, 7])
>>> G = graphs.OrthogonalDualPolarGraph(Integer(0),Integer(3),Integer(3))        # long time
>>> G.is_distance_regular(True)                       # long time
([39, 36, 27, None], [None, 1, 4, 13])
>>> G.order()                                         # long time
1120

REFERENCES:

See [BCN1989] pp. 274-279 or [VDKT2016] p. 22.

sage.graphs.generators.classical_geometries.OrthogonalPolarGraph(m, q, sign='+')[source]¶

Return the Orthogonal Polar Graph \(O^{\epsilon}(m,q)\).

For more information on Orthogonal Polar graphs, see the page of Andries Brouwer’s website.

INPUT:

m, q – integers; \(q\) must be a prime power
sign – string (default: '+'); must be '+' or '-' if \(m\) is even, '+' (default) otherwise

EXAMPLES:

Sage

sage: # needs sage.libs.gap
sage: G = graphs.OrthogonalPolarGraph(6,3,"+"); G
Orthogonal Polar Graph O^+(6, 3): Graph on 130 vertices
sage: G.is_strongly_regular(parameters=True)
(130, 48, 20, 16)
sage: G = graphs.OrthogonalPolarGraph(6,3,"-"); G
Orthogonal Polar Graph O^-(6, 3): Graph on 112 vertices
sage: G.is_strongly_regular(parameters=True)
(112, 30, 2, 10)
sage: G = graphs.OrthogonalPolarGraph(5,3); G
Orthogonal Polar Graph O(5, 3): Graph on 40 vertices
sage: G.is_strongly_regular(parameters=True)
(40, 12, 2, 4)
sage: G = graphs.OrthogonalPolarGraph(8,2,"+"); G
Orthogonal Polar Graph O^+(8, 2): Graph on 135 vertices
sage: G.is_strongly_regular(parameters=True)
(135, 70, 37, 35)
sage: G = graphs.OrthogonalPolarGraph(8,2,"-"); G
Orthogonal Polar Graph O^-(8, 2): Graph on 119 vertices
sage: G.is_strongly_regular(parameters=True)
(119, 54, 21, 27)

Python

>>> from sage.all import *
>>> # needs sage.libs.gap
>>> G = graphs.OrthogonalPolarGraph(Integer(6),Integer(3),"+"); G
Orthogonal Polar Graph O^+(6, 3): Graph on 130 vertices
>>> G.is_strongly_regular(parameters=True)
(130, 48, 20, 16)
>>> G = graphs.OrthogonalPolarGraph(Integer(6),Integer(3),"-"); G
Orthogonal Polar Graph O^-(6, 3): Graph on 112 vertices
>>> G.is_strongly_regular(parameters=True)
(112, 30, 2, 10)
>>> G = graphs.OrthogonalPolarGraph(Integer(5),Integer(3)); G
Orthogonal Polar Graph O(5, 3): Graph on 40 vertices
>>> G.is_strongly_regular(parameters=True)
(40, 12, 2, 4)
>>> G = graphs.OrthogonalPolarGraph(Integer(8),Integer(2),"+"); G
Orthogonal Polar Graph O^+(8, 2): Graph on 135 vertices
>>> G.is_strongly_regular(parameters=True)
(135, 70, 37, 35)
>>> G = graphs.OrthogonalPolarGraph(Integer(8),Integer(2),"-"); G
Orthogonal Polar Graph O^-(8, 2): Graph on 119 vertices
>>> G.is_strongly_regular(parameters=True)
(119, 54, 21, 27)

sage.graphs.generators.classical_geometries.SymplecticDualPolarGraph(m, q)[source]¶

Return the Symplectic Dual Polar Graph \(DSp(m,q)\).

For more information on Symplectic Dual Polar graphs, see [BCN1989] and Sect. 2.3.1 of [Coh1981].

INPUT:

m, q – integers; \(q\) must be a prime power, and \(m\) must be even

EXAMPLES:

Sage

sage: G = graphs.SymplecticDualPolarGraph(6,3); G       # not tested (long time)
Symplectic Dual Polar Graph DSp(6, 3): Graph on 1120 vertices
sage: G.is_distance_regular(parameters=True)            # not tested (long time)
([39, 36, 27, None], [None, 1, 4, 13])

Python

>>> from sage.all import *
>>> G = graphs.SymplecticDualPolarGraph(Integer(6),Integer(3)); G       # not tested (long time)
Symplectic Dual Polar Graph DSp(6, 3): Graph on 1120 vertices
>>> G.is_distance_regular(parameters=True)            # not tested (long time)
([39, 36, 27, None], [None, 1, 4, 13])

sage.graphs.generators.classical_geometries.SymplecticPolarGraph(d, q, algorithm=None)[source]¶

Return the Symplectic Polar Graph \(Sp(d,q)\).

The Symplectic Polar Graph \(Sp(d,q)\) is built from a projective space of dimension \(d-1\) over a field \(F_q\), and a symplectic form \(f\). Two vertices \(u,v\) are made adjacent if \(f(u,v)=0\).

See the page on symplectic graphs on Andries Brouwer’s website.

INPUT:

d, q – integers; note that only even values of \(d\) are accepted by the function
algorithm – string (default: None); if set to 'gap', then the computation is carried via GAP library interface, computing totally singular subspaces, which is faster for \(q>3\). Otherwise it is done directly.

EXAMPLES:

Computation of the spectrum of \(Sp(6,2)\):

Sage

sage: g = graphs.SymplecticPolarGraph(6, 2)
sage: g.is_strongly_regular(parameters=True)
(63, 30, 13, 15)
sage: set(g.spectrum()) == {-5, 3, 30}                                          # needs sage.rings.number_field
True

Python

>>> from sage.all import *
>>> g = graphs.SymplecticPolarGraph(Integer(6), Integer(2))
>>> g.is_strongly_regular(parameters=True)
(63, 30, 13, 15)
>>> set(g.spectrum()) == {-Integer(5), Integer(3), Integer(30)}                                          # needs sage.rings.number_field
True

The parameters of \(Sp(4,q)\) are the same as of \(O(5,q)\), but they are not isomorphic if \(q\) is odd:

Sage

sage: G = graphs.SymplecticPolarGraph(4, 3)
sage: G.is_strongly_regular(parameters=True)
(40, 12, 2, 4)

sage: # needs sage.libs.gap
sage: O = graphs.OrthogonalPolarGraph(5, 3)
sage: O.is_strongly_regular(parameters=True)
(40, 12, 2, 4)
sage: O.is_isomorphic(G)
False
sage: S = graphs.SymplecticPolarGraph(6, 4, algorithm='gap')    # not tested (long time)
sage: S.is_strongly_regular(parameters=True)                    # not tested (long time)
(1365, 340, 83, 85)

Python

>>> from sage.all import *
>>> G = graphs.SymplecticPolarGraph(Integer(4), Integer(3))
>>> G.is_strongly_regular(parameters=True)
(40, 12, 2, 4)

>>> # needs sage.libs.gap
>>> O = graphs.OrthogonalPolarGraph(Integer(5), Integer(3))
>>> O.is_strongly_regular(parameters=True)
(40, 12, 2, 4)
>>> O.is_isomorphic(G)
False
>>> S = graphs.SymplecticPolarGraph(Integer(6), Integer(4), algorithm='gap')    # not tested (long time)
>>> S.is_strongly_regular(parameters=True)                    # not tested (long time)
(1365, 340, 83, 85)

sage.graphs.generators.classical_geometries.T2starGeneralizedQuadrangleGraph(q, dual=False, hyperoval=None, field=None, check_hyperoval=True)[source]¶

Return the collinearity graph of the generalized quadrangle \(T_2^*(q)\), or of its dual

Let \(q=2^k\) and \(\Theta=PG(3,q)\). \(T_2^*(q)\) is a generalized quadrangle (Wikipedia article Generalized_quadrangle) of order \((q-1,q+1)\), see 3.1.3 in [PT2009]. Fix a plane \(\Pi \subset \Theta\) and a hyperoval \(O \subset \Pi\). The points of \(T_2^*(q):=T_2^*(O)\) are the points of \(\Theta\) outside \(\Pi\), and the lines are the lines of \(\Theta\) outside \(\Pi\) that meet \(\Pi\) in a point of \(O\).

INPUT:

q – a power of two
dual – boolean (default: False); whether to return the graph of \(T_2^*(O)\) or of the dual \(T_2^*(O)\) (when True)
hyperoval – a hyperoval (i.e. a complete 2-arc; a set of points in the plane meeting every line in 0 or 2 points) in the plane of points with 0th coordinate 0 in \(PG(3,q)\) over the field field. Each point of hyperoval must be a length 4 vector over field with 1st non-0 coordinate equal to 1. By default, hyperoval and field are not specified, and constructed on the fly. In particular, hyperoval we build is the classical one, i.e. a conic with the point of intersection of its tangent lines.
field – an instance of a finite field of order \(q\), must be provided if hyperoval is provided
check_hyperoval – boolean (default: True); whether to check hyperoval for correctness or not

EXAMPLES:

using the built-in construction:

Sage

sage: # needs sage.combinat sage.rings.finite_rings
sage: g = graphs.T2starGeneralizedQuadrangleGraph(4); g
T2*(O,4); GQ(3, 5): Graph on 64 vertices
sage: g.is_strongly_regular(parameters=True)
(64, 18, 2, 6)
sage: g = graphs.T2starGeneralizedQuadrangleGraph(4, dual=True); g
T2*(O,4)*; GQ(5, 3): Graph on 96 vertices
sage: g.is_strongly_regular(parameters=True)
(96, 20, 4, 4)

Python

>>> from sage.all import *
>>> # needs sage.combinat sage.rings.finite_rings
>>> g = graphs.T2starGeneralizedQuadrangleGraph(Integer(4)); g
T2*(O,4); GQ(3, 5): Graph on 64 vertices
>>> g.is_strongly_regular(parameters=True)
(64, 18, 2, 6)
>>> g = graphs.T2starGeneralizedQuadrangleGraph(Integer(4), dual=True); g
T2*(O,4)*; GQ(5, 3): Graph on 96 vertices
>>> g.is_strongly_regular(parameters=True)
(96, 20, 4, 4)

supplying your own hyperoval:

Sage

sage: # needs sage.combinat sage.rings.finite_rings
sage: F = GF(4,'b')
sage: O = [vector(F,(0,0,0,1)),vector(F,(0,0,1,0))] + [vector(F, (0,1,x^2,x))
....:                                                  for x in F]
sage: g = graphs.T2starGeneralizedQuadrangleGraph(4, hyperoval=O, field=F); g
T2*(O,4); GQ(3, 5): Graph on 64 vertices
sage: g.is_strongly_regular(parameters=True)
(64, 18, 2, 6)

Python

>>> from sage.all import *
>>> # needs sage.combinat sage.rings.finite_rings
>>> F = GF(Integer(4),'b')
>>> O = [vector(F,(Integer(0),Integer(0),Integer(0),Integer(1))),vector(F,(Integer(0),Integer(0),Integer(1),Integer(0)))] + [vector(F, (Integer(0),Integer(1),x**Integer(2),x))
...                                                  for x in F]
>>> g = graphs.T2starGeneralizedQuadrangleGraph(Integer(4), hyperoval=O, field=F); g
T2*(O,4); GQ(3, 5): Graph on 64 vertices
>>> g.is_strongly_regular(parameters=True)
(64, 18, 2, 6)

sage.graphs.generators.classical_geometries.TaylorTwographDescendantSRG(q, clique_partition=False)[source]¶

Return the descendant graph of the Taylor’s two-graph for \(U_3(q)\), \(q\) odd.

This is a strongly regular graph with parameters \((v,k,\lambda,\mu)=(q^3, (q^2+1)(q-1)/2, (q-1)^3/4-1, (q^2+1)(q-1)/4)\) obtained as a two-graph descendant of the Taylor's two-graph \(T\). This graph admits a partition into cliques of size \(q\), which are useful in TaylorTwographSRG(), a strongly regular graph on \(q^3+1\) vertices in the Seidel switching class of \(T\), for which we need \((q^2+1)/2\) cliques. The cliques are the \(q^2\) lines on \(v_0\) of the projective plane containing the unital for \(U_3(q)\), and intersecting the unital (i.e. the vertices of the graph and the point we remove) in \(q+1\) points. This is all taken from §7E of [BL1984].

INPUT:

q – a power of an odd prime number
clique_partition – boolean (default: False); when set to True, return \(q^2-1\) cliques of size \(q\) with empty pairwise intersection. (Removing all of them leaves a clique, too), and the point removed from the unital.

EXAMPLES:

Sage

sage: # needs sage.rings.finite_rings
sage: g = graphs.TaylorTwographDescendantSRG(3); g
Taylor two-graph descendant SRG: Graph on 27 vertices
sage: g.is_strongly_regular(parameters=True)
(27, 10, 1, 5)
sage: from sage.combinat.designs.twographs import taylor_twograph
sage: T = taylor_twograph(3)                            # long time
sage: g.is_isomorphic(T.descendant(T.ground_set()[1]))  # long time
True
sage: g = graphs.TaylorTwographDescendantSRG(5)         # not tested (long time)
sage: g.is_strongly_regular(parameters=True)            # not tested (long time)
(125, 52, 15, 26)

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> g = graphs.TaylorTwographDescendantSRG(Integer(3)); g
Taylor two-graph descendant SRG: Graph on 27 vertices
>>> g.is_strongly_regular(parameters=True)
(27, 10, 1, 5)
>>> from sage.combinat.designs.twographs import taylor_twograph
>>> T = taylor_twograph(Integer(3))                            # long time
>>> g.is_isomorphic(T.descendant(T.ground_set()[Integer(1)]))  # long time
True
>>> g = graphs.TaylorTwographDescendantSRG(Integer(5))         # not tested (long time)
>>> g.is_strongly_regular(parameters=True)            # not tested (long time)
(125, 52, 15, 26)

sage.graphs.generators.classical_geometries.TaylorTwographSRG(q)[source]¶

Return a strongly regular graph from the Taylor’s two-graph for \(U_3(q)\), \(q\) odd

This is a strongly regular graph with parameters \((v,k,\lambda,\mu)=(q^3+1, q(q^2+1)/2, (q^2+3)(q-1)/4, (q^2+1)(q+1)/4)\) in the Seidel switching class of Taylor two-graph. Details are in §7E of [BL1984].

INPUT:

q – a power of an odd prime number