<html><head><title>[grape] 10 Auxiliary Functions</title></head>
<body text="#000000" bgcolor="#ffffff">
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP009.htm">Previous</a>] [<a href = "theindex.htm">Index</a>]
<h1>10 Auxiliary Functions</h1><p>
<P>
<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP010.htm#SECT001">Steve Linton's Function SmallestImageSet
<li> <A HREF="CHAP010.htm#SECT002">Exact Set-cover</a>
</ol><p>
<p>
This chapter documents some auxiliary functions used in GRAPE,
which may be of wider interest.
<p>
<p>
<h2><a name="SECT001">10.1 Steve Linton's Function SmallestImageSet
<p><p>
<a name = "SSEC001.1"></a>
<li><code>SmallestImageSet( </code><var>G</var><code>, </code><var>S</var><code> )</code>
<li><code>SmallestImageSet( </code><var>G</var><code>, </code><var>S</var><code>, </code><var>H</var><code> )</code>
<p>
Let <var>G</var> be a permutation group on <var>{1,...,n}</var>, and let <var>S</var>
be a subset of <var>{1,...,n}</var>. Then this function returns the
lexicographically least set in the <var>G</var>-orbit of <var>S</var>, with respect to the
action <code>OnSets</code>, without explicitly computing this (possibly huge) orbit.
<p>
Thus, if <var>C</var> is a list of subsets of <var>{1,...,n}</var> and we
want to determine a set of (canonical) representatives for the
distinct <var>G</var>-orbits of the elements of <var>C</var>, we can do this as
<code>Set(</code><var>C</var><code>,c->SmallestImageSet(</code><var>G</var><code>,c))</code>.
<p>
If the setwise stabilizer in <var>G</var> of <var>S</var> is known, then this should be
given as the optional third parameter, to avoid the recomputation of
this stabilizer.
<p>
The function <code>SmallestImageSet</code> was written by Steve Linton, based
on his algorithm described in <a href="biblio.htm#Lin04"><cite>Lin04</cite></a>.
<p>
<pre>
gap> J:=JohnsonGraph(12,5);;
gap> OrderGraph(J);
792
gap> G:=J.group;;
gap> Size(G);
479001600
gap> S:=[67,93,100,204,677,750];;
gap> SmallestImageSet(G,S);
[ 1, 2, 22, 212, 242, 446 ]
</pre>
<p>
<p>
<h2><a name="SECT002">10.2 Exact Set-cover</a></h2>
<p><p>
<a name = "SSEC002.1"></a>
<li><code>GRAPE_ExactSetCover( </code><var>G</var><code>, </code><var>blocks</var><code>, </code><var>n</var><code> )</code>
<li><code>GRAPE_ExactSetCover( </code><var>G</var><code>, </code><var>blocks</var><code>, </code><var>n</var><code>, </code><var>H</var><code> )</code>
<p>
Suppose <var>n</var> is a non-negative integer, <var>G</var> is a permutation group
on <var>{1,...,n}</var>, <var>blocks</var> is a list of non-empty subsets
of <var>{1,...,n}</var>, and the optional parameter <var>H</var> (default:
<code>Group(())</code>) is a subgroup of <var>G</var>.
<p>
Then this function returns an <var>H</var>-invariant exact
set-cover of <var>{1,...,n}</var>, consisting of elements from the union of
<code>Orbits(</code><var>G</var><code>,</code><var>blocks</var><code>,OnSets)</code>, if such a cover exists,
and returns <code>fail</code> otherwise. An exact set-cover is given as a set of
sets forming a partition of <var>{1,...,n}</var>.
<p>
<pre>
gap> G:=PSL(2,5);;
gap> GRAPE_ExactSetCover(G,[[1,2,3]],6);
fail
gap> G:=PGL(2,5);;
gap> GRAPE_ExactSetCover(G,[[1,2,3]],6);
[ [ 1, 2, 3 ], [ 4, 5, 6 ] ]
gap> n:=280;;
gap> G:=OnePrimitiveGroup(NrMovedPoints,n,Size,604800*2);
J_2.2
gap> gamma:=First(GeneralizedOrbitalGraphs(G),x->VertexDegrees(x)=[135]);;
gap> omega:=CliqueNumber(gamma);
28
gap> blocks:=CompleteSubgraphsOfGivenSize(ComplementGraph(gamma),n/omega,2);;
gap> Collected(List(blocks,Length));
[ [ 10, 2 ] ]
gap> H:=SylowSubgroup(G,7);;
gap> partition:=GRAPE_ExactSetCover(G,blocks,n,H);;
gap> Collected(List(partition,Length));
[ [ 10, 28 ] ]
gap> Union(partition)=[1..n];
true
</pre>
<p>
<p>
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP009.htm">Previous</a>] [<a href = "theindex.htm">Index</a>]
<P>
<address>grape manual<br>September 2025
</address></body></html>
¤ Dauer der Verarbeitung: 0.25 Sekunden
(vorverarbeitet)
¤
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
