<p>You're missing the emptyset $\emptyset$ which is connected to all $b$'s. To get an  automorphism, you select a subset $T\subseteq \{1,...,k\}$ of even cardinality and then swaps $a_i$ with $b_i$ for each $i\in T$ and then adjusts the sets in the middle. In your example the graph is $$(a_1,\{12\}),(a_2,\{12\}),(b_1,\emptyset),(b_2,\emptyset).$$</p>

<p>Still in your example if $T=\emptyset$ you don't need to do anything and if 
$T=\{1,2\}$ the automorphism is given by swapping $a_1$ with $b_1$, $a_2$ with $b_2$ and $\{1,2\}$ with $\emptyset$.</p>

<p>Now for the general case, we need to show that there is always a way of adjusting the middle vertices. We know that $T$ has even cardinality. So let $|T|=2r$. We just need to show that such an 
automorphism exists if $|T|=2$ since otherwise we can apply the composition of $r$ automorphisms corresponding to partitioning $T$ into $r$ subsets of size $2$. Thus assume $T=\{i,j\}$.  Then the automorphism swaps $a_i$ with $b_i$, 
$a_j$ with $b_j$, each middle vertex $S$ such that $S\cap\{i,j\}=\emptyset$ with the middle vertex $S\cup \{i,j\}$ (this can be seen in your example), and each subset $S$ such that $S\cap \{i,j\}=\{i\}$ with the subset such that $S\cap \{i,j\}= \{j\}$ (This you can see for $k=3$). Notice that this swapping process is an automorphism since for an index $p\neq \{i,j\}$ the edge relation between $a_p$, $b_p$ and these swapped vertices is completely preserved, and clearly the edge relation between $a_i,a_j,b_i,b_j$ is properly adjusted. </p>

<p>Finally to see that these are the only possible automorphisms, notice that each $a_i,b_i$ is colored with its own color. So they cannot be mapped to another pair $a_j,b_j$. Also notice that it is not possible to have an automorphism that maps an middle vertex to a middle vertex without swapping some $a_i$ with some $b_j$. $\square$   </p>

CC BY-SA 3.0
2012-12-09T05:32:17.710Z
In general how can we show that we can always *adjust the sets in the middle* and get the desired automorphism? Core of my problem is actually that.
DurgaDatta
CC BY-SA 3.0
2012-12-09T10:52:40.743Z
Hi, I added the construction of the automorphisms. Hope it helps.
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2012-12-09T12:53:28.467Z
Thank you. This does not look "immediate" to me. I am very new to research. Is this a bad signal for me?
DurgaDatta
CC BY-SA 3.0
2012-12-09T13:25:33.203Z
"Is this a bad signal for me?" Absolutely not. I think to the contrary that your skepticism is a very good signal. Some day this kinds of things will probably be immediate for you too :)
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2012-12-10T04:55:48.147Z
Is it true that, for a index set $T$ (for each $i \in T$ of which are are interchanging $a_i$ and $b_i$) index set of a middle vertex $S$ get transformed to $S \Delta T$ (symmetric difference)?
DurgaDatta
CC BY-SA 3.0
2012-12-08T16:18:34.790Z
2012-12-09T11:04:31.260Z
2012-12-09T11:04:31.260Z
Mateus de Oliveira Oliveira
<p>In the famous counter example for graph isomorphism via Weisfeiler-Lehman (WL) method the following gadget was constructed in <a href="http://www.cs.yale.edu/publications/techreports/tr626.pdf">this paper</a> by Cai, Furer and Immerman.
They construct a graph $X_k = (V_k, E_k)$ given by</p>

<p>$V_k = A_k \cup B_k \cup M_k \\ \text{ where } \\
\quad A_k = \{a_i \mid 1 \leq i \leq k\}, \\
\quad B_k =\{b_i \mid 1 \leq i \leq k\}, \mbox{ and } \\
\quad  M_k = \{ m_S \mid S \subseteq \{1,2,\ldots, k\},\ |S| \text{ is even} \}\\
E_k =\{(m_S,a_i) \mid  i \in S\} \cup  \{(m_S, b_i)\mid i \notin S\}$</p>

<p>One of the lemmas in the paper (lemma 3.1 page 6 )  states that if we color the vertices $a_i$ and $b_i$ with color $i$ then $|Aut(X_k)| = 2^{k-1}$ (color has to be preserved by the automorphism) where each automorphism corresponds to interchanging $a_i$ and $b_i$ for each $i$ in some subsets $S$ of $\{1,2,\ldots, k\}$ of even cardinality. They say that the proof is immediate. But I fail to see how even in the case of $k= 2$. In $X_2 \ (a_1, m_{\{1,2\}})$ is an edge but if we have automorphism which interchanges $a_1, b_1$ and $a_2, b_2$ the above edge gets transformed to $(b_1, m_{\{1,2\}})$ which is not an edge. So that should not be an automorphism. </p>

<p>I would like to understand what is my misunderstanding.</p>

<graph-theory><graph-algorithms><graph-isomorphism><algebraic-complexity>
automorphism in Cai-Furer-Immerman gadgets
DurgaDatta
# automorphism in Cai-Furer-Immerman gadgets

(Asked by: username_0 on 2012-12-08)

In the famous counter example for graph isomorphism via Weisfeiler-Lehman (WL) method the following gadget was constructed in [this paper](http://www.cs.yale.edu/publications/techreports/tr626.pdf) by Cai, Furer and Immerman.
They construct a graph $X\_k = (V\_k, E\_k)$ given by

$V\_k = A\_k \cup B\_k \cup M\_k \\ \text{ where } \\
\quad A\_k = \{a\_i \mid 1 \leq i \leq k\}, \\
\quad B\_k =\{b\_i \mid 1 \leq i \leq k\}, \mbox{ and } \\
\quad M\_k = \{ m\_S \mid S \subseteq \{1,2,\ldots, k\},\ |S| \text{ is even} \}\\
E\_k =\{(m\_S,a\_i) \mid i \in S\} \cup \{(m\_S, b\_i)\mid i \notin S\}$

One of the lemmas in the paper (lemma 3.1 page 6 ) states that if we color the vertices $a\_i$ and $b\_i$ with color $i$ then $|Aut(X\_k)| = 2^{k-1}$ (color has to be preserved by the automorphism) where each automorphism corresponds to interchanging $a\_i$ and $b\_i$ for each $i$ in some subsets $S$ of $\{1,2,\ldots, k\}$ of even cardinality. They say that the proof is immediate. But I fail to see how even in the case of $k= 2$. In $X\_2 \ (a\_1, m\_{\{1,2\}})$ is an edge but if we have automorphism which interchanges $a\_1, b\_1$ and $a\_2, b\_2$ the above edge gets transformed to $(b\_1, m\_{\{1,2\}})$ which is not an edge. So that should not be an automorphism.

I would like to understand what is my misunderstanding.

**Tags:** graph-theory, graph-algorithms, graph-isomorphism, algebraic-complexity


---

## 1 answers

### Answer by username_1 on 2012-12-08. Score: 6 | Accepted answer

You're missing the emptyset $\emptyset$ which is connected to all $b$'s. To get an automorphism, you select a subset $T\subseteq \{1,...,k\}$ of even cardinality and then swaps $a\_i$ with $b\_i$ for each $i\in T$ and then adjusts the sets in the middle. In your example the graph is $$(a\_1,\{12\}),(a\_2,\{12\}),(b\_1,\emptyset),(b\_2,\emptyset).$$

Still in your example if $T=\emptyset$ you don't need to do anything and if
$T=\{1,2\}$ the automorphism is given by swapping $a\_1$ with $b\_1$, $a\_2$ with $b\_2$ and $\{1,2\}$ with $\emptyset$.

Now for the general case, we need to show that there is always a way of adjusting the middle vertices. We know that $T$ has even cardinality. So let $|T|=2r$. We just need to show that such an
automorphism exists if $|T|=2$ since otherwise we can apply the composition of $r$ automorphisms corresponding to partitioning $T$ into $r$ subsets of size $2$. Thus assume $T=\{i,j\}$. Then the automorphism swaps $a\_i$ with $b\_i$,
$a\_j$ with $b\_j$, each middle vertex $S$ such that $S\cap\{i,j\}=\emptyset$ with the middle vertex $S\cup \{i,j\}$ (this can be seen in your example), and each subset $S$ such that $S\cap \{i,j\}=\{i\}$ with the subset such that $S\cap \{i,j\}= \{j\}$ (This you can see for $k=3$). Notice that this swapping process is an automorphism since for an index $p\neq \{i,j\}$ the edge relation between $a\_p$, $b\_p$ and these swapped vertices is completely preserved, and clearly the edge relation between $a\_i,a\_j,b\_i,b\_j$ is properly adjusted.

Finally to see that these are the only possible automorphisms, notice that each $a\_i,b\_i$ is colored with its own color. So they cannot be mapped to another pair $a\_j,b\_j$. Also notice that it is not possible to have an automorphism that maps an middle vertex to a middle vertex without swapping some $a\_i$ with some $b\_j$. $\square$

> **Comments:**
> **username_0**: In general how can we show that we can always *adjust the sets in the middle* and get the desired automorphism? Core of my problem is actually that.  
> **username_1**: Hi, I added the construction of the automorphisms. Hope it helps.  
> **username_0**: Thank you. This does not look "immediate" to me. I am very new to research. Is this a bad signal for me?  
> **username_1**: "Is this a bad signal for me?" Absolutely not. I think to the contrary that your skepticism is a very good signal. Some day this kinds of things will probably be immediate for you too :)  
> **username_0**: Is it true that, for a index set $T$ (for each $i \in T$ of which are are interchanging $a_i$ and $b_i$) index set of a middle vertex $S$ get transformed to $S \Delta T$ (symmetric difference)?  

---

