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='+')#
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 ifsign is not None
, and odd otherwiseq
– integer; a power of a prime number, as \(F_q\) must existsign
– string (default:"+"
); must be equal to"+"
,"-"
, orNone
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
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)
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
- sage.graphs.generators.classical_geometries.AhrensSzekeresGeneralizedQuadrangleGraph(q, dual=False)#
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 numberdual
– boolean (default:False
); whether to return the collinearity graph of \(AS(q)\) or of the dual \(AS(q)\) (whenTrue
)
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)
- sage.graphs.generators.classical_geometries.CossidentePenttilaGraph(q)#
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)
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)
- sage.graphs.generators.classical_geometries.HaemersGraph(q, hyperoval=None, hyperoval_matching=None, field=None, check_hyperoval=True)#
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 arbitraryhyperoval_matching
of the points (i.e. partitioning into size two parts) ofhyperoval
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 twohyperoval_matching
– ifNone
(default), pair each \(i\)-th point ofhyperoval
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)^*\). IfNone
(default), the classical hyperoval obtained from a conic is used. See the documentation ofT2starGeneralizedQuadrangleGraph()
, for more information.field
– an instance of a finite field of order \(q\), must be provided ifhyperoval
is providedcheck_hyperoval
– boolean (default:True
); whether to checkhyperoval
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)
supplying your own hyperoval_matching:
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)
- sage.graphs.generators.classical_geometries.NonisotropicOrthogonalPolarGraph(m, q, sign='+', perp=None)#
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 notNone
, then we assume that \(q=5\) and return the graph of the points \(x\) satisfying \(F(x)=\pm 1\) ifsign="+"
, respectively \(F(x) \in \{2,3\}\) ifsign="-"
, with adjacency given by orthogonality w.r.t. \(F\) (cf. Sect 7.D of [BL1984]). Otherwise return the graph of nongenerate hyperplanes of typesign
, 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 vectorspaceq
– a power of a prime number, the size of the underlying fieldsign
– 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)
\(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)
\(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)
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)
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)
- sage.graphs.generators.classical_geometries.NonisotropicUnitaryPolarGraph(m, q)#
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)
- sage.graphs.generators.classical_geometries.Nowhere0WordsTwoWeightCodeGraph(q, hyperoval=None, field=None, check_hyperoval=True)#
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 twohyperoval
– 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 fieldfield
. Each point ofhyperoval
must be a length 3 vector overfield
with 1st non-0 coordinate equal to 1. By default,hyperoval
andfield
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 ifhyperoval
is provided.check_hyperoval
– boolean (default:True
); whether to checkhyperoval
for correctness or not
See also
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)
supplying your own hyperoval:
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)
- sage.graphs.generators.classical_geometries.OrthogonalDualPolarGraph(e, d, q)#
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 graphq
– 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
REFERENCES:
See [BCN1989] pp. 274-279 or [VDKT2016] p. 22.
- sage.graphs.generators.classical_geometries.OrthogonalPolarGraph(m, q, sign='+')#
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 powersign
– 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)
- sage.graphs.generators.classical_geometries.SymplecticDualPolarGraph(m, q)#
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])
- sage.graphs.generators.classical_geometries.SymplecticPolarGraph(d, q, algorithm=None)#
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
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)
- sage.graphs.generators.classical_geometries.T2starGeneralizedQuadrangleGraph(q, dual=False, hyperoval=None, field=None, check_hyperoval=True)#
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 twodual
– boolean (default:False
); whether to return the graph of \(T_2^*(O)\) or of the dual \(T_2^*(O)\) (whenTrue
)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 fieldfield
. Each point ofhyperoval
must be a length 4 vector overfield
with 1st non-0 coordinate equal to 1. By default,hyperoval
andfield
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 ifhyperoval
is providedcheck_hyperoval
– boolean (default:True
); whether to checkhyperoval
for correctness or not
EXAMPLES:
using the built-in construction:
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)
supplying your own hyperoval:
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)
- sage.graphs.generators.classical_geometries.TaylorTwographDescendantSRG(q, clique_partition=False)#
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 inTaylorTwographSRG()
, 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 numberclique_partition
– boolean (default:False
); when set toTrue
, 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)
- sage.graphs.generators.classical_geometries.TaylorTwographSRG(q)#
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
See also
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)
- sage.graphs.generators.classical_geometries.UnitaryDualPolarGraph(m, q)#
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)
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
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])
- sage.graphs.generators.classical_geometries.UnitaryPolarGraph(m, q, algorithm='gap')#
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 poweralgorithm
– 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