Quelle  hamilcyc.g   Sprache: unbekannt

# This file was created from hamilcyc.xml, do not edit!
#############################################################################
##
#W  hamilcyc.g        Hamiltonian cycles in finite groups       Thomas Breuer
##
#Y  Copyright (C)  2009,   Lehrstuhl D für Mathematik,  RWTH Aachen,  Germany
##


#############################################################################
##
##  The examples use the GAP Character Table Library
##  and the GAP Library of Tables of Marks,
##  so we first load these packages in the required versions.
##
if not CompareVersionNumbers( GAPInfo.Version, "4.5" ) then
     Error( "need GAP in version at least 4.5" );
   fi;
LoadPackage( "ctbllib", "1.2", false );
LoadPackage( "tomlib", "1.1.1", false );


#############################################################################
##
#F  IsGeneratorsOfTransPermGroup( <G>, <list> )
##
##  Let <G> be a finite group that acts *transitively* on its moved points,
##  and <list> a list of elements in <G>.
##
##  'IsGeneratorsOfTransPermGroup' returns 'true' if the permutations in
##  <list> generate <G>, and 'false' otherwise.
##  The main point is that the return value 'true' requires the group
##  generated by 'list' to be transitive, and the check for transitivity
##  is much cheaper than the test whether this group is equal to 'G'.
##
##  (The same function is used also in another examples file,
##  do not use 'BindGlobal'.)
##
IsGeneratorsOfTransPermGroup:= function( G, list )
    local S;
    if not IsTransitive( G ) then
      Error( "<G> must be transitive on its moved points" );
    fi;
    S:= SubgroupNC( G, list );
    return IsTransitive( S, MovedPoints( G ) )
           and Size( S ) = Size( G );
end;;


#############################################################################
##
#F  VertexDegreesGeneratingGraph( <G>, <classes>, <normalsubgroups> )
##
##  Let <G> be a finite group that acts *transitively* on its moved points,
##  <classes> be the list of conjugacy classes of <G>
##  (in order to prescribe an ordering of the classes),
##  and <normalsubgroups> be a list of proper normal subgroups of <G>.
##
##  'VertexDegreesGeneratingGraph' returns the matrix $d(g_i, g_j^G)$,
##  with rows and columns indexed by nonidentity class representatives
##  ordered as in the list <classes>.
##  (The class containing the identity element may be contained in
##  'classes'.)
##
BindGlobal( "VertexDegreesGeneratingGraph",
    function( G, classes, normalsubgroups )
    local nccl, matrix, cents, powers, normalsubgroupspos, i, j, g_i,
          nsg, g_j, gen, pair, d, pow;
    if not IsTransitive( G ) then
      Error( "<G> must be transitive on its moved points" );
    fi;
    classes:= Filtered( classes,
                        C -> Order( Representative( C ) ) <> 1 );
    nccl:= Length( classes );
    matrix:= [];
    cents:= [];
    powers:= [];
    normalsubgroupspos:= [];
    for i in [ 1 .. nccl ] do
      matrix[i]:= [];
      if IsBound( powers[i] ) then
        # The i-th row equals the earlier row 'powers[i]'.
        for j in [ 1 .. i ] do
          matrix[i][j]:= matrix[ powers[i] ][j];
          matrix[j][i]:= matrix[j][ powers[i] ];
        od;
      else
        # We have to compute the values.
        g_i:= Representative( classes[i] );
        nsg:= Filtered( [ 1 .. Length( normalsubgroups ) ],
                        i -> g_i in normalsubgroups[i] );
        normalsubgroupspos[i]:= nsg;
        cents[i]:= Centralizer( G, g_i );
        for j in [ 1 .. i ] do
          g_j:= Representative( classes[j] );
          if IsBound( powers[j] ) then
            matrix[i][j]:= matrix[i][ powers[j] ];
            matrix[j][i]:= matrix[ powers[j] ][i];
          elif not IsEmpty( Intersection( nsg, normalsubgroupspos[j] ) )
               or ( Order( g_i ) = 2 and Order( g_j ) = 2
                    and not IsDihedralGroup( G ) ) then
            matrix[i][j]:= 0;
            matrix[j][i]:= 0;
          else
            # Compute $d(g_i, g_j^G)$.
            gen:= 0;
            for pair in DoubleCosetRepsAndSizes( G, cents[j],
                            cents[i] ) do
              if IsGeneratorsOfTransPermGroup( G,
                     [ g_i, g_j^pair[1] ] ) then
                gen:= gen + pair[2];
              fi;
            od;
            matrix[i][j]:= gen / Size( cents[j] );
            if i <> j then
              matrix[j][i]:= gen / Size( cents[i] );
            fi;
          fi;
        od;
        # For later, provide information about algebraic conjugacy.
        for d in Difference( PrimeResidues( Order( g_i ) ), [ 1 ] ) do
          pow:= g_i^d;
          for j in [ i+1 .. nccl ] do
            if not IsBound( powers[j] ) and pow in classes[j] then
              powers[j]:= i;
              break;
            fi;
          od;
        od;
      fi;
    od;
    return matrix;
end );


#############################################################################
##
#A  PrimitivePermutationCharacters( <tbl> )
##
##  For an ordinary character table <tbl> for which either the value of one
##  of the attributes 'Maxes' or 'UnderlyingGroup' is stored or the table of
##  marks is contained in the GAP library of tables of marks,
##  'PrimitivePermutationCharacters' returns the list of all primitive
##  permutation characters of <tbl>.
##  Otherwise 'fail' is returned.
##
##  We use 'InstallOtherMethod' not 'InstallMethod' because another test file
##  declares the same attribute and installs the same method.
##
DeclareAttribute( "PrimitivePermutationCharacters",
                     IsCharacterTable );
InstallOtherMethod( PrimitivePermutationCharacters,
    [ IsCharacterTable ],
    function( tbl )
    local maxes, i, fus, poss, tom, G;
    if HasMaxes( tbl ) then
      maxes:= List( Maxes( tbl ), CharacterTable );
      for i in [ 1 .. Length( maxes ) ] do
        fus:= GetFusionMap( maxes[i], tbl );
        if fus = fail then
          fus:= PossibleClassFusions( maxes[i], tbl );
          poss:= Set( fus,
            map -> InducedClassFunctionsByFusionMap(
                       maxes[i], tbl,
                       [ TrivialCharacter( maxes[i] ) ], map )[1] );
          if Length( poss ) = 1 then
            maxes[i]:= poss[1];
          else
            return fail;
          fi;
        else
          maxes[i]:= TrivialCharacter( maxes[i] )^tbl;
        fi;
      od;
      return maxes;
    elif HasFusionToTom( tbl ) then
      tom:= TableOfMarks( tbl );
      maxes:= MaximalSubgroupsTom( tom );
      return PermCharsTom( tbl, tom ){ maxes[1] };
    elif HasUnderlyingGroup( tbl ) then
      G:= UnderlyingGroup( tbl );
      return List( MaximalSubgroupClassReps( G ),
                   M -> TrivialCharacter( M )^tbl );
    fi;
    return fail;
end );


#############################################################################
##
#F  LowerBoundsVertexDegrees( <classlengths>, <prim> )
##
##  For two lists <classlengths> of the conjugacy class lengths and <prim> of
##  all primitive permutation characters of a group $G$, say,
##  'LowerBoundsVertexDegrees' returns a matrix <delta> such that
##  '<delta>[i][j] = '$\delta(s, g^G)$ holds,
##  for $s$ and $g$ in the 'i+1'-st and 'j+1'-st class of $G$,
##  respectively.
##
##  So the row sums in <delta> are the values $\delta(s)$.
##
LowerBoundsVertexDegrees:= function( classlengths, prim )
    local sizes, nccl;
    nccl:= Length( classlengths );
    return List( [ 2 .. nccl ],
             i -> List( [ 2 .. nccl ],
                    j -> Maximum( 0, classlengths[j] - Sum( prim,
                    pi -> classlengths[j] * pi[j] * pi[i]
                              / pi[1] ) ) ) );
end;;


#############################################################################
##
#F  LowerBoundsVertexDegreesOfClosure( <classlengths>, <bounds> )
##
##  Given the list <classlengths> of conjugacy class lengths for the group
##  $G$ and a matrix <bounds> of the values $d^{(i)}(s, g^G)$ or
##  $\delta^{(i)}(s, g^G)$,
##  as is returned by 'VertexDegreesGeneratingGraph' or
##  'LowerBoundsVertexDegrees',
##  the following function returns the corresponding matrix of the values
##  $d^{(i+1)}(s, g^G)$ or $\delta^{(i+1)}(s, g^G)$, respectively.
##
LowerBoundsVertexDegreesOfClosure:= function( classlengths, bounds )
    local delta, newbounds, size, i, j;
    delta:= List( bounds, Sum );
    newbounds:= List( bounds, ShallowCopy );
    size:= Sum( classlengths );
    for i in [ 1 .. Length( bounds ) ] do
      for j in [ 1 .. Length( bounds ) ] do
        if delta[i] + delta[j] >= size - 1 then
          newbounds[i][j]:= classlengths[ j+1 ];
        fi;
      od;
    od;
    return newbounds;
end;;


#############################################################################
##
#F  CheckCriteriaOfPosaAndChvatal( <classlengths>, <bounds> )
##
##  Let <classlengths> be list of conjugacy class lengths of a group $G$,
##  say, and <bounds> be a matrix of the values $d^{(i)}(s, g^G)$ or
##  $\delta^{(i)}(s, g^G)$,
##  as is returned for example by 'LowerBoundsVertexDegrees' or
##  'LowerBoundsVertexDegreesOfClosure'.
##
##  'CheckCriteriaOfPosaAndChvatal' returns a record with the following
##  components.
##
##  'badForPosa':
##      the list of those pairs $[ L_k, U_k ]$ with the property
##      $L_k \leq U_k$,
##
##  'badForChvatal':
##      the list of pairs of lower and upper bounds of nonempty intervals
##      where Chvátal's criterion may be violated, and
##
##  'data':
##      the sorted list of triples $[ \delta(g_k), |g_k^G|, \iota(k) ]$,
##      where $\iota(k)$ is the row and column position of $g_k$
##      in the matrix <bounds>.
##
##  The generating graph $\Gamma(G)$ satisfies Pósa's criterion
##  if the 'badForPosa' component is empty;
##  the graph satisfies Chvátal's criterion if the 'badForChvatal'
##  component is empty.
##
##  The ordering of class lengths must of course be compatible with the
##  ordering of rows and columns of the matrix,
##  and the identity element of $G$ must belong to the first entry in the
##  list of class lengths.
##
CheckCriteriaOfPosaAndChvatal:= function( classlengths, bounds )
    local size, degs, addinterval, badForPosa, badForChvatal1, pos,
          half, i, low1, upp2, upp1, low2, badForChvatal, interval1,
          interval2;
    size:= Sum( classlengths );
    degs:= List( [ 2 .. Length( classlengths ) ],
                 i -> [ Sum( bounds[ i-1 ] ), classlengths[i], i ] );
    Sort( degs );
    addinterval:= function( intervals, low, upp )
      if low <= upp then
        Add( intervals, [ low, upp ] );
      fi;
    end;
    badForPosa:= [];
    badForChvatal1:= [];
    pos:= 1;
    half:= Int( size / 2 ) - 1;
    for i in [ 1 .. Length( degs ) ] do
      # We have pos = c_1 + c_2 + \cdots + c_{i-1} + 1
      low1:= Maximum( pos, degs[i][1] );  # L_i
      upp2:= Minimum( half, size-1-pos, size-1-degs[i][1] ); # U'_i
      pos:= pos + degs[i][2];
      upp1:= Minimum( half, pos-1 ); # U_i
      low2:= Maximum( 1, size-pos ); # L'_i
      addinterval( badForPosa, low1, upp1 );
      addinterval( badForChvatal1, low2, upp2 );
    od;
    # Intersect intervals.
    badForChvatal:= [];
    for interval1 in badForPosa do
      for interval2 in badForChvatal1 do
        addinterval( badForChvatal,
                     Maximum( interval1[1], interval2[1] ),
                     Minimum( interval1[2], interval2[2] ) );
      od;
    od;
    return rec( badForPosa:= badForPosa,
                badForChvatal:= Set( badForChvatal ),
                data:= degs );
end;;


#############################################################################
##
#F  HamiltonianCycleInfo( <classlengths>, <bounds> )
##
##  Let <classlengths> be list of conjugacy class lengths of a group $G$,
##  say, and <bounds> be a matrix of the values $d^{(i)}(s, g^G)$ or
##  $\delta^{(i)}(s, g^G)$,
##  as is returned for example by 'LowerBoundsVertexDegrees' or
##  'LowerBoundsVertexDegreesOfClosure'.
##
##  'HamiltonianCycleInfo' returns a string that describes the minimal $i$
##  with the property that the given bounds suffice to show that
##  $cl^{(i)}(\Gamma(G))$ satisfies Pósa's or Chvátal's criterion,
##  if such a closure exists.
##  If no closure has this property, the string '"no decision"' is returned.
##
HamiltonianCycleInfo:= function( classlengths, bounds )
    local i, result, res, oldbounds;
    i:= 0;
    result:= rec( Posa:= fail, Chvatal:= fail );
    repeat
      res:= CheckCriteriaOfPosaAndChvatal( classlengths, bounds );
      if result.Posa = fail and IsEmpty( res.badForPosa ) then
        result.Posa:= i;
      fi;
      if result.Chvatal = fail and IsEmpty( res.badForChvatal ) then
        result.Chvatal:= i;
      fi;
      i:= i+1;
      oldbounds:= bounds;
      bounds:= LowerBoundsVertexDegreesOfClosure( classlengths,
                   bounds );
    until oldbounds = bounds;
    if result.Posa <> fail then
      if result.Posa <> result.Chvatal then
        return Concatenation(
            "Chvatal for ", Ordinal( result.Chvatal ), " closure, ",
            "Posa for ", Ordinal( result.Posa ), " closure" );
      else
        return Concatenation( "Posa for ", Ordinal( result.Posa ),
            " closure" );
      fi;
    elif result.Chvatal <> fail then
      return Concatenation( "Chvatal for ", Ordinal( result.Chvatal ),
                            " closure" );
    else
      return "no decision";
    fi;
end;;


#############################################################################
##
#F  HamiltonianCycleInfoFromCharacterTable( <tbl> )
##
##  For a character table <tbl>, this function returns a string,
##  either '"no prim. perm. characters"' or the return value of
##  'HamiltonianCycleInfo' for the bounds computed from the primitive
##  permutation characters.
##
HamiltonianCycleInfoFromCharacterTable:= function( tbl )
    local prim, classlengths, bounds;
    prim:= PrimitivePermutationCharacters( tbl );
    if prim = fail then
      return "no prim. perm. characters";
    fi;
    classlengths:= SizesConjugacyClasses( tbl );
    bounds:= LowerBoundsVertexDegrees( classlengths, prim );
    return HamiltonianCycleInfo( classlengths, bounds );
end;;


#############################################################################
##
#F  HamiltonianCycleInfoFromGroup( <G> )
##
##  For a group <G>, this function returns a string,
##  the return value of 'HamiltonianCycleInfo' for the vertex degrees
##  computed from the group.
##
HamiltonianCycleInfoFromGroup:= function( G )
    local ccl, nsg, der, degrees, classlengths;
    ccl:= ConjugacyClasses( G );
    if IsPerfect( G ) then
      nsg:= [];
    else
      der:= DerivedSubgroup( G );
      nsg:= Concatenation( [ der ],
                IntermediateSubgroups( G, der ).subgroups );
    fi;
    degrees:= VertexDegreesGeneratingGraph( G, ccl, nsg );
    classlengths:= List( ccl, Size );
    return HamiltonianCycleInfo( classlengths, degrees );        
end;;


#############################################################################
##
#E