/usr/share/gap/pkg/grape/htm/CHAP009.htm is in gap-grape 4r7+ds-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 | <html><head><title>[grape] 9 Partial Linear Spaces</title></head>
<body text="#000000" bgcolor="#ffffff">
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP008.htm">Previous</a>] [<a href = "theindex.htm">Index</a>]
<h1>9 Partial Linear Spaces</h1><p>
<P>
<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP009.htm#SECT001">PartialLinearSpaces</a>
<li> <A HREF="CHAP009.htm#SECT002">A research application of PartialLinearSpaces</a>
</ol><p>
<p>
Let <i>s</i> and <i>t</i> be positive integers. A <strong>partial linear space</strong>
(<i>P</i>,<i>L</i>), with <strong>parameters</strong> (<i>s</i>,<i>t</i>) consists of a set <i>P</i> of <strong>points</strong>,
together with a set <i>L</i> of (<i>s</i>+1)-subsets of <i>P</i> called <strong>lines</strong>,
such that every point is in exactly <i>t</i>+1 lines, and every pair of
distinct points is contained in at most one line. The <strong>point graph</strong>
of a partial linear space <i>S</i> having point-set <i>P</i> is the graph with
vertex-set <i>P</i> and having [<i>p</i>,<i>q</i>] an edge if and only if <i>p</i> ≠ <i>q</i> and
<i>p</i>,<i>q</i> are in a common line of <i>S</i>. Two partial linear spaces (<i>P</i>,<i>L</i>)
and (<i>P</i>′,<i>L</i>′) (with parameters (<i>s</i>,<i>t</i>)) are said to be <strong>isomorphic</strong>
if there is a bijection <i>P</i>→ <i>P</i>′ which induces a bijection <i>L</i>→ <i>L</i>′.
An <strong>automorphism</strong> of a partial linear space is an isomorphism onto itself.
The set of all automorphisms of a partial linear space <i>S</i> forms a group,
called the <strong>automorphism group</strong> of <i>S</i>.
<p>
GRAPE contains a function <code>PartialLinearSpaces</code> to determine and
classify partial linear spaces with given point graph and parameters.
In this chapter we describe this function, and also give a research
application of this function.
<p>
<p>
<h2><a name="SECT001">9.1 PartialLinearSpaces</a></h2>
<p><p>
<a name = "SSEC001.1"></a>
<li><code>PartialLinearSpaces( </code><var>ptgraph</var><code>, </code><var>s</var><code>, </code><var>t</var><code> )</code>
<li><code>PartialLinearSpaces( </code><var>ptgraph</var><code>, </code><var>s</var><code>, </code><var>t</var><code>, </code><var>nspaces</var><code> )</code>
<li><code>PartialLinearSpaces( </code><var>ptgraph</var><code>, </code><var>s</var><code>, </code><var>t</var><code>, </code><var>nspaces</var><code>, </code><var>printlevel</var><code> )</code>
<li><code>PartialLinearSpaces( </code><var>ptgraph</var><code>, </code><var>s</var><code>, </code><var>t</var><code>, </code><var>nspaces</var><code>, </code><var>printlevel</var><code>, </code><var>cliques</var><code> )</code>
<p>
This function classifies the partial linear spaces with given point
graph <var>ptgraph</var> and parameters (<var>s</var>,<var>t</var>). It makes use (indirectly)
of nauty <a href="biblio.htm#Nau90,MP14"><cite>Nau90,MP14</cite></a> or bliss <a href="biblio.htm#JK07"><cite>JK07</cite></a>.
<p>
The function <code>PartialLinearSpaces</code> returns a list of representatives
of distinct isomorphism classes of partial linear spaces with (simple)
point graph <var>ptgraph</var>, and parameters (<var>s</var>,<var>t</var>). The default is that
representatives for all isomorphism classes are returned.
<p>
The integer argument <var>nspaces</var> is optional, and has default value -1,
which means that representatives for all isomorphism classes are
returned. If <var>nspaces</var> is non-negative then exactly <var>nspaces</var>
representatives are returned if there are at least <var>nspaces</var>
isomorphism classes, otherwise representatives for all isomorphism
classes are returned.
<p>
In the output of this function, a partial linear space <var>S</var> is given
by its incidence graph <var>delta</var>. The point-vertices of <var>delta</var> are
1,...,<code></code><var>ptgraph</var><code>.order</code>, with the name of point-vertex <var>i</var> being the
name of vertex <var>i</var> of <var>ptgraph</var>. A line-vertex of <var>delta</var> is named by a
list (not necessarily ordered) of the point-vertex names for the points
on that line. We warn that this is a <strong>different</strong> naming convention to
versions of GRAPE before 4.1. The group <code></code><var>delta</var><code>.group</code> associated
with the incidence graph <var>delta</var> is the automorphism group of <var>S</var> acting
on point-vertices and line-vertices, and preserving both sets.
<p>
If <var>printlevel</var> is bound then it controls the print-level (default 0).
Permitted values for <var>printlevel</var> are 0,1,2.
<p>
If <var>cliques</var> is bound then it is assumed to be a list (without repeats)
of the (<i>s</i> +1)-cliques of <var>ptgraph</var>. If known, this can help the
function to run faster.
<p>
<pre>
gap> K7:=CompleteGraph(SymmetricGroup(7));;
gap> P:=PartialLinearSpaces(K7,2,2);
[ rec( isGraph := true, order := 14,
group := Group([ ( 1, 2)( 5, 6)( 9,11)(10,12),
( 1, 2, 3)( 5, 6, 7)( 9,11,13)(10,12,14),
( 1, 2, 3)( 4, 7, 6)( 9,12,14)(10,11,13),
( 1, 4, 7, 6, 2, 5, 3)( 8, 9,13,10,11,12,14) ]),
schreierVector := [ -1, 1, 2, 4, 4, 1, 3, -2, 4, 1, 1, 3, 4, 2 ],
adjacencies := [ [ 8, 9, 10 ], [ 1, 2, 3 ] ],
representatives := [ 1, 8 ],
names := [ 1, 2, 3, 4, 5, 6, 7, [ 1, 2, 3 ], [ 1, 4, 5 ], [ 1, 6, 7 ],
[ 2, 4, 6 ], [ 2, 5, 7 ], [ 3, 4, 7 ], [ 3, 5, 6 ] ],
isSimple := true ) ]
gap> Size(P[1].group);
168
gap> T:=ComplementGraph(JohnsonGraph(10,2));;
gap> P:=PartialLinearSpaces(T,4,6);;
gap> List(P,x->Size(x.group));
[ 216, 1512 ]
</pre>
<p>
<p>
<h2><a name="SECT002">9.2 A research application of PartialLinearSpaces</a></h2>
<p><p>
We now provide an extended example of the use of GRAPE which
illustrates a research application of the <code>PartialLinearSpaces</code> function.
<p>
First we give a definition. Let <i>s</i> and <i>t</i> be positive integers. A
<strong>partial geometry</strong> is a partial linear space with parameters (<i>s</i>,<i>t</i>) for
which there is an additional constant constant α > 0, such that,
for every line <i>l</i> and every point <i>p</i> not on <i>l</i>, there are exactly
α lines through <i>p</i> meeting <i>l</i> in some point.
<p>
Our example shows that the Haemers partial geometry <a href="biblio.htm#Hae81"><cite>Hae81</cite></a>
is uniquely determined (up to isomorphism) by its point graph, as is
the dual of the Haemers geometry (where the role of points and lines
are interchanged), and that each of these geoemetries has automorphism
group isomorphic to <i>A</i><sub>7</sub>.
<p>
We first construct and study the Hoffman-Singleton graph, using the
construction of Peter Cameron contained in <a href="biblio.htm#Cam99"><cite>Cam99</cite></a>. We then
construct the point graph of the Haemers partial geometry <a href="biblio.htm#Hae81"><cite>Hae81</cite></a>
(this partial geometry has (<i>s</i>,<i>t</i>)=(4,17) and α = 2). The vertices
of this point graph are the edges of the Hoffman-Singleton graph, and
two such vertices are adjacent in the point graph precisely when they
are at distance 2 in the edge-graph of the Hoffman-Singleton graph (see
<a href="biblio.htm#Hae81"><cite>Hae81</cite></a>). We then construct and classify (up to isomorphism)
all partial linear spaces with parameters (4,17) having point graph
isomorphic to that of the Haemers partial geometry. We find that
the Haemers partial geometry is the only possibility. It follows from
basic theory of partial geometries that the Haemers partial geometry is
uniquely determined up to isomorphism (as a partial geometry) by its point
graph. We also show that the dual of the Haemers partial geometry is also
uniquely determined by its point graph. Thus far, the only proof of these
results is by GRAPE. Our example also shows that the Haemers partial
geometry and its dual each has automorphism group isomorphic to <i>A</i><sub>7</sub>.
<p>
The total runtime (not including calls of nauty) was about 300
CPU-seconds on a Pentium II running at 350 MHz.
<p>
<pre>
gap> LoadPackage("grape");
true
gap>
gap> OnSetsRecursive:=function(x,g)
> if not IsList(x) then
> return x^g;
> else
> return Set(List(x, y->OnSetsRecursive(y,g)));
> fi;
> end;;
gap>
gap> HofSingAdjacency := function(x,y)
> #
> # This boolean function returns true iff x and y are
> # adjacent in the Hoffman-Singleton graph, in Peter Cameron's
> # construction.
> #
> if Size(x)=3 then # x is a 3-set
> if Size(y)=3 then # y is a 3-set
> return Intersection(x,y)=[]; # join iff disjoint
> else # y is a projective plane
> return x in y; # join iff x is a line of y
> fi;
> else # x is a projective plane
> if Size(y)=3 then # y is a 3-set
> return y in x; # join iff y is a line of x
> else # y is a projective plane
> return false; # don't join
> fi;
> fi;
> end;;
gap>
gap> projectiveplane:=
> Set([[1,2,4],[2,3,5],[3,4,6],[4,5,7],[1,5,6],[2,6,7],[1,3,7]]);;
gap>
gap> HofSingGraph:=Graph(AlternatingGroup(7),
> [[1,2,3], projectiveplane], OnSetsRecursive,
> HofSingAdjacency);;
gap> GlobalParameters(HofSingGraph);
[ [ 0, 0, 7 ], [ 1, 0, 6 ], [ 1, 6, 0 ] ]
gap> autgrp := AutGroupGraph(HofSingGraph);;
gap> Size(autgrp);
252000
gap> HofSingGraph := NewGroupGraph(autgrp,HofSingGraph);;
gap> pointgraph:=DistanceGraph( EdgeGraph(HofSingGraph), 2);;
gap> GlobalParameters(pointgraph);
[ [ 0, 0, 72 ], [ 1, 20, 51 ], [ 36, 36, 0 ] ]
gap> spaces:=PartialLinearSpaces(pointgraph,4,17);;
gap> Length(spaces);
1
gap> haemers:=spaces[1];;
gap> DisplayCompositionSeries(haemers.group);
G (3 gens, size 2520)
| A(7)
1 (0 gens, size 1)
gap> linegraph:=PointGraph(haemers, Adjacency(haemers,1)[1]);;
gap> spaces:=PartialLinearSpaces(linegraph,17,4);;
gap> Length(spaces);
1
gap> dualhaemers:=spaces[1];;
gap> DisplayCompositionSeries(dualhaemers.group);
G (4 gens, size 2520)
| A(7)
1 (0 gens, size 1)
</pre>
<p>
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP008.htm">Previous</a>] [<a href = "theindex.htm">Index</a>]
<P>
<address>grape manual<br>January 2016 (Debian 4r7+ds-3)
</address></body></html>
|