In a proposition of graph isomorphism I find that for a generator $σ \in S$ (the set of generator of a group), edges can be added to a directed edge-colored graph $X(G)$ of color $σ$ corresponding to the cycle decomposition of $σ$.

I don't understand the process of adding color-edges to a directed edge-colored graph, where can I find such construction? Can any one provide an example?

The problem is found in a Ph.d. thesis. Before you go to the detail, you need 2 definitions:

We denote the set of G to H isomorphisms by $ISO(G, H)$. We say $G$ and $H$ are isomorphic (and write $G \cong H)$ if $ISO(G, H)$ is not empty.

Given two finite sets Ω and ∆, if $G ≤ Sym(Ω)$ and $H ≤ Sym(∆)$ are permutation groups, then a bijection $π: Ω \to ∆$ is a permutational isomorphism from $G$ to $H$ if $G^π = H$. We denote the set of all $G$ to $H$ permutational isomorphisms by $PISO(G, H)$.

Now see the proposition:

Proposition. Given two transitive permutation groups $G, H ≤ S_n$, and an isomorphism $φ \in ISO(G, H)$, we can list the (at most $n$) permutational isomorphisms $π \in PISO(G, H)$ corresponding to $φ$ in time $O(n^3)$.

Proof. Pick a set of generators $S ⊆ G$ for $G$; then $S^φ$ is the corresponding set of generators for $H$. We construct two directed edge-colored graphs $X(G)$, and $X(H)$, over the vertex set $[n]$.

For each generator $σ \in S$, we add to $X(G)$ edges of color $σ$ corresponding to the cycle decomposition of $σ$.

Similarly for every $σ \in S$, we add to $X(H)$ edges of color $σ$ corresponding to the cycle decomposition of $σ^φ ( \in S^φ )$.

(Graph) Isomorphisms of $X(G)$ and $X(H)$ are permutational isomorphisms between $G$ and $H$; and we can test isomorphism of these colored graphs in linear time. Recall that isomorphisms of colored graphs preserve the colors by definition.

To test isomorphism of these graphs, pick any vertex $x$ in $X(G)$, and run breadth first search starting at $x$ (because the groups are transitive, the choice will not matter). We assign to every vertex the unique word corresponding to the color of the path to that vertex in the BFS. Now repeat the same process for $X(H)$. If the labelings of the vertices do not yield a bijection, then reject. Otherwise check whether the bijection is indeed an isomorphism of the two graphs. The running time is linear in the size of the graphs.

To list all permutational isomorphisms corresponding to $φ$, we need to try every possible choice of root vertex $x$ for the $BFS$. Therefore the total running time will be n times linear in the size of the graphs. The graphs have $O(n^2)$ edges, since there is always a set of at most $2n$ generators. Therefore the total running time is $O(n^3)$.

  • $\begingroup$ Use $\sigma$ for $\sigma$. $\endgroup$
    – Shaun
    Jul 28 '21 at 14:03
  • $\begingroup$ @Shaun thanks but can you direct me where I can find such graph construction? $\endgroup$ Jul 28 '21 at 14:50
  • $\begingroup$ You're welcome. I'm afraid I don't know. $\endgroup$
    – Shaun
    Jul 28 '21 at 15:07

I feel like you're overthinking this; the proof is literally just telling you which edges to include.

Say that $n=6$ and $S$ consists of the permutations $\{\color{red}{(1\;2\;3)\;(4\;5\;6)}, \color{blue}{(1\;3\;5)\;(2\;4\;6)}\}$. Then the graph we construct has edges $$\{\color{red}{1\to 2},\color{red}{2\to 3},\color{red}{3\to 1}, \color{red}{4 \to 5}, \color{red}{5 \to 6}, \color{red}{6 \to 4}\}$$ in the color of the first permutation, and edges $$\{\color{blue}{1\to 3},\color{blue}{3\to 5},\color{blue}{5\to 1}, \color{blue}{2 \to 4}, \color{blue}{4 \to 6}, \color{blue}{6 \to 2}\}$$ in the color of the second permutation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.