Symmetry

Symmetries are what this library is all about. Here, we describe some of the basic concepts surrounding symmetries on graphs.

What are symmetries? #

Symmetries (AKA automorphisms) are bijections on the vertices of graphs, mapping the graph back to itself. In other words, a symmetry is a mapping of vertices that preserves the connections between vertices. If we apply a symmetry to a graph, the resulting graph will have the same structure as the original one.

Formally, given a graph \(G = (V, E)\), a bijection \(\varphi : V \to V\) is a symmetry of \(G\) if and only if it satisfies \(\varphi((V, E)) = (V, E)\). The set of all symmetries is a permutation group under the composition operation. We call this group the automorphism group of G, denoted as \(Aut(G)\). In particular, this means that the set of symmetries of a graph is closed under composition.

Let us look more closely at a symmetry of a graph.

Using cycle notation, a symmetry is expressed as a product of disjoint cycles. A cycle is simply a sequence of elements that are cyclically permuted. To keep things brief, we always omit cycles of length 1, as these vertices are simply fixed (mapped to themselves) in the permutation.

Let’s break down the notation and illustrate it with an example. In cycle notation, the symmetry above is written as \(( 3 \; 4 )\). Vertex 3 goes to 4, and 4 goes back to 3. All other vertices (0, 1, 2, 5, 6) are fixed and thus omitted.

Storing Symmetry #

Writing out all the symmetries for a graph is not only tedious, but also very inefficient. There can be an exponential amount of symmetries for a given graph. However, there is always a way to write down the symmetries in a compact way using the power of generating sets.

A generating set, is a subset of the symmetries that, through the use of exhaustively composing the symmetries of the set, will result in the entire group. For the example graph above, a potential generating set is \( S = \{( 3 \; 4 ), ( 1 \; 2 )( 4 \; 6 )( 3 \; 5 )\}\). We denote that it generates the entire group with \( \langle S \rangle = Aut(G) \).

On the technical side, storing and working with symmetries can be conveniently achieved using the classes automorphism_workspace and stored_automorphism.

// let's say we stored an automorphism here
dejavu::groups::stored_automorphism automorphism;

// let's say our graph has n vertices
dejavu::groups::automorphism_workspace workspace(n);

// load the stored automorphism into the workspace
workspace.load(aw);

// now, we can conveniently access and manipulate the automorphism
std::cout << "5 maps to " << workspace[5] << std::endl;

Loading the stored automorphism \(\varphi\) in particular runs in time \( \mathcal{O}(\text{supp}(\varphi)) \). The workspace contains several features to efficiently access and manipulate automorphisms (see the documentation).

Orbits #

Let us now describe the concept of orbits. The concept of orbits helps us address the question of whether two vertices in a graph can be interchanged by a symmetry.

An orbit is a partition of the vertices of a graph. Two vertices are in the same orbit, if and only if one can be reached from the other by applying symmetries of the graph. (If two vertices belong to different orbits, there is no symmetry that can swap them.) We can illustrate the orbit partition through coloring a graph, where each color represents an orbit.

In the above example, the red vertices form an orbit, the orange ones, and the blue ones. Formally, the orbits are \( \Delta(G) := \{\{0\}, \{1,2\}, \{3,4,5,6\} \} \).

In the library, it is easy to compute the orbits of a graph. The class orbit can represent the orbit partition of a graph. It contains methods to inspect and manipulate an orbit partition.

// let's say we have a graph with n vertices and m edges
dejavu::static_graph g;
g.initialize_graph(n, m); 
// (insert definition of graph here...)

// initialize an orbit structure with number of vertices
dejavu::groups::orbit orbits(n);
    
// when computing automorphisms, we can feed them directly into the
// orbit partition with an orbit_hook
dejavu::hooks::orbit_hook hook(orbits);
dejavu::solver d;
d.automorphisms(&g, hook.get_hook());

// orbits now contains the orbit partition for found automorphisms of g

We can then access the orbit partition by, for example, calling orbits.are_in_same_orbit(v1, v2), which tells us whether v1 and v2 are in the same orbit. The class also contains methods to give a canonical representative for an orbit, retrieve the orbit size, and more. For a more thorough technical description, please see the documentation.