# Bound on the size of Permutation Set for Isomorphism

$\textbf{Claim :}$ $G, H$ are partitioned into sub-graphs $\{ G_1,G_2 \cdots G_x \}$ and $\{ H_1,H_2 \cdots H_x \}$ . For each $G_i$ we constructed a set permutation, $\beta_i$ such that $\exists \pi \in \beta_i, G_i^{\pi} \simeq H_i$.$\pi$ is a part of $P$ such that $G^P=H$. Each $\beta_i$ has maximum $\beta$ permutations. Isomorphism test of $G,H$ can be done determined in $O((x \times \beta)^c)$ time where $c$ is a constant provided that $P$ exists as described as above .

$\textbf{Proof:}$

An algorithmic proof is presented here. The computational complexity of of finding $P$ is polynomial in $\beta$.

We construct the generating set of automorphism group of $H$ using $\beta_k$, for all $k$. As we know, constructing generating set of automorphism group of $H$ is a GI complete problem . So, we try to construct the generating set of $Aut(H)$ . The technique used in the paper  by E. Luks can used here.

Notation:

From now on, $G, H$ are adjacency matrices of graphs $G, H$ respectively. $H_k, G_k$ are blocks or sub-matrices of matrix $H, G$ respectively. The adjacency matrix of graph $H_k \cup H_e$ is $M_{(k,e)}$ where $M_{(k,e)} =\left( \begin{array}{ccc} H_e & R_{k,e} \\ R_{k,e}^{T} & H_k\\ \end{array} \right)$, where, $R_{k,e}$ is the non symmetric sub-matrix of adjacency matrix $H$. Here, $R_{k,e}$ represents edges between $H_k, H_e$. Similarly, $S_{k,e}$ represents edges between $G_k, G_e$. $$H = \begin{bmatrix} H_{(x)} & R_{(x, x-1)} & R_{(x,x-2)} & \dots & \dots & R_{(x,1)} \\ R_{(x,x-1)} & H_{(x-1)} & R_{(x-1,x-2)} & \dots & \dots & R_{(x-1,1)} \\ \vdots & \vdots & \vdots & \ddots & \ddots & \vdots \\ R_{(x,1)} & R_{(x-1,1)} & R_{(x-2,1)} & \dots & \dots &H_{1} \end{bmatrix}$$

For simplicity, we assume $\beta \leq n^{3}$.

The outline of the algorithm to construct generating set:

At $1^{st}$ iteration -

Step 1. Construct all possible direct product $(\pi_1 \times \pi_2)$ where $\pi_1 \in \beta_1$ and $\pi_2 \in \beta_2$.

There are $| \beta_1 | \times | \beta_2| < n^{9}$ direct products (permutations). All these permutations (direct products) form set $\gamma_1$. Each element of $\gamma_1$ is a permutation that acts on graph $H_1 \cup H_2$.

Step 2. Construct/find -

$\alpha_1 =\{ \pi \in \gamma_1 | (M_{(1,2)}^{\pi}= M_{(1,2)}) \land ( R_{1,2}^{\pi} = S_{1,2}) \land (H_1^{\pi} = G_1) \land (H_2^{\pi} = G_2) \}$

$\alpha_1$ is the set of automorphisms of matrix $M_{(1,2)}$. $|\alpha_1| < n^{9}$.There are two possible cases-

Case 1: If $|\alpha_1| =1$, then for each $\pi_1 \in \beta_1$, there is only one permutation $\pi_2 \in \beta_2$. So, there could be maximum $n^{2}$ permutations in $\gamma_1$ but only one permutation could be included in $\alpha_1$.

Case 2: If $|\alpha_1| >1$, we would be able to construct a generating set $\mathcal{S}_1$ of an automorphism group of $Aut(M_{(1,2)})$ Note, that if $\exists \pi_a \in Aut(H)$ such that it acts on vertices of $H_1 \cup H_2$, then $\pi_a \in \langle \mathcal{S}_1 \rangle =Aut(M_{(1,2)})$. So, when we construct direct product of $\mathcal{S}_1$ and another set, $\pi_a$ can be found in the resulting generating set. See Theorem 7, on page 31 of .The theorem showed how to obtain the automorphism group of an arbitrary graph from the intersection of a specific permutation group with a direct product of symmetric groups.

Step 3. Now, we construct the generating set $\mathcal{S}_1$ from $\alpha_1$. This construction of generating set can be done in polynomial time (see , page 40, theorem 9). From , we find that $|\mathcal{S}_1| \leq log(n!)$ . $\mathcal{S}_1$ is the generating set of automorphism of $H_1 \cup H_2$ .

Step 4. We start $2^{nd}$ iteration, for $\beta_3, \mathcal{S}_1$ (instead of $\beta_2$), $M_{(2,3)}$ where $M_{(2,3)} =\left( \begin{array}{ccc} H_3 & R_{2,3} \\ R_{2,3}^{T} & H_2 \\ \end{array} \right)$. We find $\gamma_2, \alpha_2$ repeating steps $1,2$ and construct $\mathcal{S}_2$ (repeating step $3$) which is the generating set of automorphism of graph $H_1 \cup H_2 \cup H_3$. Note that, $|\mathcal{S}_2| \leq log(n!)$ .

Step 5. We keep repeating above four processes, until we find the set $\mathcal{S}_{(x-1)}$ which is the generating set of automorphism of graph $H_1 \cup H_2 \cup H_3 \dots \cup H_x=H$. Note that, $|\mathcal{S}_{(x-1)}|\leq log(n!)$, since $\langle \mathcal{S}_{(x-1)} \rangle= Aut(H) \leq S_n$.

Detecting Isomorphism: We repeat the process of construction of $\mathcal{S}_{(x-1)}$ for graph $G$ and obtain set $\mathcal{R}_{(x-1)}$. I assumed, that the oracle that gave $\beta_k$, would provide permutation sets for $G$ also.

Once we generate generating sets of $G, H$, we can decide isomorphism betwen them .

## References:

Mathon, Rudolf. ,A note on the graph isomorphism counting problem, Inform. Process. Lett. 8 (1979), no. 3, 131–132.

 Luks , Eugene M. , Isomorphism of graphs of bounded valence can be tested in polynomial time, Journal of Computer and System Sciences, Volume 25, Issue 1, (1982), Pages 42-65.

Hoffmann, Christoph M. ,Group-Theoretic Algorithms and Graph Isomorphism.

 Miller, Gary L. ,On the $n^{\log_2(n)}$ Isomorphism Technique.

Edit This was the answer to the first revision of the question:

The proof must be incorrect, since the statement itself is incorrect. Take for example $G_1=H_1=0$, $G_2=H_2=0$, $R_1=S_1=0$. Then $\beta_1$ is the symmetric group on $n_1$ symbols, $\beta_2$ is the symmetric group on $n_2$ symbols, $T=\max(n_1!,n_2!)$, and $|Y_1|=n_1!\cdot n_2! > T$ for $n_1,n_2>1$.

Jim's first reaction to this answer was to delete his question (ee revision history). Then he asked me to explain "redundant element", which I did happily. He answered That is not what I meant by "redundant", without any attempt to explain what "redundant element" means from his point of view. Instead he rewrote the question to ask something quite different, and left the comment below that my answer no longer fits the rewritten question.

Let me try to comment (I turned the answer to a community wiki, because a comment is not an answer) on the current revision (3) of the question. First of all, the author is not fluent in English or mathematics:

Consider all $\pi_{l} \in \beta_{l}$ which are true for $\gamma_{\pi_{l}}$

Here $\pi_{l}$ is a permutation and $\gamma_{\pi_{l}}$ is a set, so this sentence doesn't make sense. Maybe he means that $\gamma_{\pi_{l}}$ is non-empty?

But it gets worse:

Consider all $\pi_{l} \in \beta_{l}$ which are true for $\gamma_{\pi_{l}}$, say, this set is $\alpha_j$ where $1\leq j \leq z$, $z$ is the total number of $\alpha_j$. By definition, $\beta_{l}$ is partitioned into $z$ disjoint sets $\{ \alpha_1 , \alpha_2 ,\cdots \alpha_z \}$ and $\beta_i$ is also partitioned into $w$ disjoint sets.

It is completely unclear why $\beta_{l}$ should be partitioned by definition into $z$ disjoint sets. In the initial version of the question, we get some idea how this partition is intended, but the sets which occur there (based on the sets created for different $\pi_{i} \in \beta_{i}$) are never shown to be disjoint, let alone a partition of $\beta_{l}$.

And it doesn't get better further if you continue to read the purported proof. This text is simply missing the clarity and definitiveness required for mathematical statements and mathematical proofs.

The interactions of Jim with Morgan Rodgers (who also wrote an answer) indicate that discussing his proof attempts with Jim's is unlikely to lead to productive results. Therefore I wrote a small C++ program to allow Jim to experiment a bit with his ideas, and expressed the hope that he tries to compile it and tries to play with it a bit. I haven't heard back from him on this one yet...

• It is my responsibility to write a post properly. As Thomas Klimpel pointed out, I am not good at English, Math. So, some confusion was created by me. I have added an explanation about partition, please, see that. – Michael Jan 25 '16 at 17:34
• Thomas: given the developments that have happened in the linked chatroom for the last four months, do you think that the negative outlook presented in this answer is still justified? I mean that you are painting a fairly off-putting picture, and if this isn't a picture that still applies, perhaps you would consider updating the answer for posterity? – Eric Stucky May 30 '16 at 16:08
• @EricStucky , Please note that I have changed=edited my post a few times., TK is a busy forum member, it is not possible for him to keep track all the time. So, its ok. Perhaps, you would care to join the discussion, Do you have anything to say regarding the post? – Michael May 31 '16 at 0:27