# Functions for "Graphs and their Groups" Transpositions := function(n) # Purpose: Find all transpositions in the symmetric group of degree n # Input: n - integer # # Output: T - set containing the transpositions # local k, m, T; T := []; for k in [1..n] do for m in [k+1..n] do AddSet(T, (k,m)); od; od; return T; end; RandomSubset := function(S, k) # Purpose: Find a random subset of S of size k # Input: S - set # k - integer # Output: R - random subset # local R; R := []; while Size(R) < k do AddSet(R, Random(S)); od; return R; end; AdjacentVertices := function(Graph, V) # Purpose : Find the vertices of Graph that are adjacent to V # Input: Graph - list of transpositions (edge set) # V - integer (vertex) # Output: Adj - set of vertices adjacent to V # # Note: The edges meeting V are the transpositions which move V # The adjacent edges are the images of V under these # transpositions # local Adj; Adj := Set(Filtered(Graph, e -> V^e <> V), f -> V^f); return Adj; end; Aut := function(Graph, n) # Purpose: Compute the group of the graph, Graph, with n vertices # Input: G - subset of the transpositions in Sn # n - integer # Output: Grp - subgroup of Sn # local Grp, S; Graph := Set(Graph); S := SymmetricGroup(n); Grp := Filtered(S, g -> Graph = Set(Graph, x -> x^g)); return Grp; end; BlackBox := function(n, k) # Purpose : Find a graph on n vertices and k edges. # Input : n, k - integers # Output : reps - list of transpositions # Note: The probability that the graph comes from a certain # conjugacy class is the same for every conjugacy class. # Further, local T, C, S, Orbs, rep; T := Transpositions(n); C := Combinations(T, k); S := SymmetricGroup(n); Orbs := Orbits(S,C,OnSets); rep := Random(Random(Orbs)); return rep; end;