Orbit Stabilizer

Pointwise Stabilizer #

Given a permutation group \(\Gamma \subseteq Sym(\Omega)\) and a point of the domain \(\omega \in \Omega\) (i.e., a vertex of the graph), the pointwise stabilizer \(\Gamma_{(\omega)}\) restricts the group to precisely those that do not move \(\omega\) around. In other words, it stabilizes or fixes the point \(\omega\). Formally, we define \(\Gamma_{(\omega)} := \lbrace \varphi \in \Gamma \thickspace \vert \thickspace \varphi(\omega) = \omega \rbrace\).

On a graph, the pointwise stabilizer corresponds precisely to coloring a vertex of a graph with its own color (see our description of vertex colors).

In the first graph above, no point is stabilized. In the second one, the orange vertex is stabilized, whereas in the last one the red and orange vertex are stabilized. We call a chain of consecutively stabilized points, such as the red and orange vertex, a (partial) base. Note how in the last graph, no symmetries are left – the pointwise stabilizer of the red and orange vertex is trivial. In this case, we call the base complete

Feeding a Schreier structure #

We compute chains of pointwise stabilizer using the Schreier-Sims algorithm. The class random_schreier contains a rudimentary implementation of the random Schreier-Sims algorithm, as used internally by the solver itself. There is a simple way to feed the automorphisms of a graph into the structure: the hook schreier_hook does the job, as is shown in the example below.

// 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 a random schreier structure with number of vertices
dejavu::groups::random_schreier rschreier(n);

// when computing automorphisms, we can feed them directly into the
// schreier structure with a schreier_hook
dejavu::hooks::schreier_hook hook(rschreier);
dejavu::solver d;
d.automorphisms(&g, hook.get_hook());

// rschreier now contains all found automorphisms of g

The structure can then be inspected and manipulated as described below.

Orbits and Generators #

We can quite easily set a base (AKA a chain of stabilized points) for a given Schreier structure. For example, if we want to set a base of 0, 4, 7, we can do this as follows:

// we need a vector containing the new base
std::vector<int> base = {0, 4, 7};

// now we set the base
rschreier.set_base(base);

There is two ways to retrieve orbits from the structure. Firstly, if we are only interested in the orbit of the fixed point (i.e., before fixing the point), this can be done quite efficiently as follows:

// orbit at base position 1 of fixed point (4)
std::vector<int> test_orbit = s.get_fixed_orbit(1);

Now, test_orbit contains all points in the orbit of 4. Note that the information is readily available in the stored structure.

However, if we are interested in the entire orbit partition at a certain point, more information has to be computed. This can be done with the following method:

orbit orbits(n);
rschreier.get_stabilizer_orbit(1, orbits);

This fills the orbits structure with an orbit partition. Note that the information may be incomplete, in particular in case the Schreier structure is used with an incomplete base.