# 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: g = graphs.AffineOrthogonalPolarGraph(4,3,"-")                            # needs sage.libs.gap
sage: g.is_isomorphic(graphs.BrouwerHaemersGraph())                             # needs sage.libs.gap
True

>>> 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: # 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)

>>> 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: # 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

>>> 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


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: 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)

>>> from sage.all import *
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: G = graphs.CossidentePenttilaGraph(3)     # optional - gap_package_grape
sage: G.is_strongly_regular(parameters=True)    # optional - gap_package_grape
(56, 10, 0, 2)

>>> 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: G = graphs.CossidentePenttilaGraph(5)     # optional - gap_package_grape
sage: G.is_strongly_regular(parameters=True)    # optional - gap_package_grape
(378, 52, 1, 8)

>>> 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: # 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)

>>> 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)


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)

>>> 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: 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)

>>> 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: # 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)

>>> 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: g = graphs.NonisotropicOrthogonalPolarGraph(8,2,'+')                      # needs sage.libs.gap
sage: g.is_strongly_regular(parameters=True)                                    # needs sage.libs.gap
(120, 63, 30, 36)

>>> 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: # 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)

>>> 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: # 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)

>>> 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: 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)

>>> 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

EXAMPLES:

using the built-in construction:

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)

>>> 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)


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)

>>> 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: # 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

>>> 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: # 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)

>>> 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: 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])

>>> 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: 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

>>> 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: 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)

>>> 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)


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: # needs sage.combinat sage.rings.finite_rings
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)

>>> from sage.all import *
>>> # needs sage.combinat sage.rings.finite_rings
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)


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)

>>> 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: # 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)

>>> 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

EXAMPLES:

sage: t = graphs.TaylorTwographSRG(3); t                                        # needs sage.rings.finite_rings
Taylor two-graph SRG: Graph on 28 vertices
sage: t.is_strongly_regular(parameters=True)                                    # needs sage.rings.finite_rings
(28, 15, 6, 10)

>>> from sage.all import *
>>> t = graphs.TaylorTwographSRG(Integer(3)); t                                        # needs sage.rings.finite_rings
Taylor two-graph SRG: Graph on 28 vertices
>>> t.is_strongly_regular(parameters=True)                                    # needs sage.rings.finite_rings
(28, 15, 6, 10)

sage.graphs.generators.classical_geometries.UnitaryDualPolarGraph(m, q)[source]#

Return the Dual Unitary Polar Graph $$U(m,q)$$.

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

INPUT:

• m, q – integers; $$q$$ must be a prime power

EXAMPLES:

The point graph of a generalized quadrangle (see Wikipedia article Generalized_quadrangle, [PT2009]) of order (8,4):

sage: G = graphs.UnitaryDualPolarGraph(5,2); G  # long time                     # needs sage.libs.gap
Unitary Dual Polar Graph DU(5, 2); GQ(8, 4): Graph on 297 vertices
sage: G.is_strongly_regular(parameters=True)    # long time                     # needs sage.libs.gap
(297, 40, 7, 5)

>>> from sage.all import *
>>> G = graphs.UnitaryDualPolarGraph(Integer(5),Integer(2)); G  # long time                     # needs sage.libs.gap
Unitary Dual Polar Graph DU(5, 2); GQ(8, 4): Graph on 297 vertices
>>> G.is_strongly_regular(parameters=True)    # long time                     # needs sage.libs.gap
(297, 40, 7, 5)


Another way to get the generalized quadrangle of order (2,4):

sage: G = graphs.UnitaryDualPolarGraph(4,2); G                                  # needs sage.libs.gap
Unitary Dual Polar Graph DU(4, 2); GQ(2, 4): Graph on 27 vertices
sage: G.is_isomorphic(graphs.OrthogonalPolarGraph(6,2,'-'))                     # needs sage.libs.gap
True

>>> from sage.all import *
>>> G = graphs.UnitaryDualPolarGraph(Integer(4),Integer(2)); G                                  # needs sage.libs.gap
Unitary Dual Polar Graph DU(4, 2); GQ(2, 4): Graph on 27 vertices
>>> G.is_isomorphic(graphs.OrthogonalPolarGraph(Integer(6),Integer(2),'-'))                     # needs sage.libs.gap
True


A bigger graph:

sage: G = graphs.UnitaryDualPolarGraph(6,2); G   # not tested (long time)
Unitary Dual Polar Graph DU(6, 2): Graph on 891 vertices
sage: G.is_distance_regular(parameters=True)     # not tested (long time)
([42, 40, 32, None], [None, 1, 5, 21])

>>> from sage.all import *
>>> G = graphs.UnitaryDualPolarGraph(Integer(6),Integer(2)); G   # not tested (long time)
Unitary Dual Polar Graph DU(6, 2): Graph on 891 vertices
>>> G.is_distance_regular(parameters=True)     # not tested (long time)
([42, 40, 32, None], [None, 1, 5, 21])

sage.graphs.generators.classical_geometries.UnitaryPolarGraph(m, q, algorithm='gap')[source]#

Return the Unitary Polar Graph $$U(m,q)$$.

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

INPUT:

• m, q – integers; $$q$$ must be a prime power

• algorithm – string (default: "gap"); if set to ‘gap’ then the computation is carried via GAP library interface, computing totally singular subspaces, which is faster for large examples (especially with $$q>2$$). Otherwise it is done directly.

EXAMPLES:

sage: # needs sage.libs.gap
sage: G = graphs.UnitaryPolarGraph(4,2); G
Unitary Polar Graph U(4, 2); GQ(4, 2): Graph on 45 vertices
sage: G.is_strongly_regular(parameters=True)
(45, 12, 3, 3)
sage: graphs.UnitaryPolarGraph(5,2).is_strongly_regular(parameters=True)
(165, 36, 3, 9)
sage: graphs.UnitaryPolarGraph(6,2)     # not tested (long time)
Unitary Polar Graph U(6, 2): Graph on 693 vertices

>>> from sage.all import *
>>> # needs sage.libs.gap
>>> G = graphs.UnitaryPolarGraph(Integer(4),Integer(2)); G
Unitary Polar Graph U(4, 2); GQ(4, 2): Graph on 45 vertices
>>> G.is_strongly_regular(parameters=True)
(45, 12, 3, 3)
>>> graphs.UnitaryPolarGraph(Integer(5),Integer(2)).is_strongly_regular(parameters=True)
(165, 36, 3, 9)
>>> graphs.UnitaryPolarGraph(Integer(6),Integer(2))     # not tested (long time)
Unitary Polar Graph U(6, 2): Graph on 693 vertices