automorfizm w gadżetach Cai-Furer-Immerman

W słynnym kontrprzykładzie dla izomorfizmu grafów metodą Weisfeiler-Lehman (WL) następujący gadżet został skonstruowany w tym artykule przez Cai, Furer i Immerman. Konstruują wykres podany przez$X_k = (V_k, E_k)$

$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\}$

Jednym z lematów w papierze (lemat 3.1 strona 6) stwierdza, że jeśli mamy pokolorować wierzchołki ja i b I z kolor i wtedy | A u t ( X k ) | = 2 k - 1 (kolor ma być zachowana przez automorfizm), w którym każdy automorfizm odpowiada zamianę I a b I do siebie i w pewnych podgrupach S z { 1 , 2 , ... , k }$a_i$$b_i$$i$$|Aut(X_k)| = 2^{k-1}$$a_i$$b_i$$i$$S$$\{1,2,\ldots, k\}$nawet liczności. Mówią, że dowód jest natychmiastowy. Ale nie widzę, jak nawet w przypadku . W X 2 ( z 1 , m { 1 , 2 } ) jest krawędzią, lecz jeśli mamy automorfizm które węzłów 1 , b 1 i o 2 , b 2 powyżej krawędź zostaje przekształcony ( b 1 , m { 1 , 2, }$k= 2$$X_2 \ (a_1, m_{\{1,2\}})$$a_1, b_1$$a_2, b_2$$(b_1, m_{\{1,2\}})$co nie jest krawędzią. To nie powinien być automorfizm.

Chciałbym zrozumieć, jakie jest moje nieporozumienie.

Brakuje pustego zestawu który jest podłączony do wszystkich b . Aby uzyskać automorfizmem należy wybrać podzbiór T ⊆ { 1 , . . . , K } choćby liczności, a następnie zamienia się I z b I dla każdego I ∈ T , a następnie dostosowuje zestawy w środku. W twoim przykładzie wykres to ( a 1 , { 12 } ) , ( a 2 , { 12 } ) $\emptyset$$b$$T\subseteq \{1,...,k\}$$a_i$$b_i$$i\in T$

Jeszcze w Twojej przykład jeśli nie trzeba nic robić, a jeśli T = { 1 , 2 } automorfizmem jest przez zamianę do 1 z b 1 , 2 z b 2 i { 1 , 2 } z ∅ .$T=\emptyset$$T=\{1,2\}$$a_1$$b_1$$a_2$$b_2$$\{1,2\}$$\emptyset$

Teraz w ogólnym przypadku musimy pokazać, że zawsze istnieje sposób dostosowania środkowych wierzchołków. Wiemy, że ma nawet liczność. Więc pozwól | T | = 2 r . Musimy tylko pokazać, że taki automorfizm istnieje, jeśli | T | = 2, ponieważ w przeciwnym razie możemy zastosować skład r automorfizmów odpowiadających podziałowi T na r podzbiorów wielkości 2 . Załóżmy zatem, że T = { i , j } . Następnie automorfizmem zamienia ja z$T$$|T|=2r$$|T|=2$$r$$T$$r$$2$$T=\{i,j\}$$a_i$ , J z b J każdy środkowy wierzchołek S, tak, że S ∩ { i , j } = ∅ środkowym wierzchołku S ∪ { i , j } (co można zobaczyć w przykładzie), i każdy podzbiór S np że S ∩ { i , j } = { i } z podzestawem takim, że S ∩ { i , j $b_i$$a_j$$b_j$$S$$S\cap\{i,j\}=\emptyset$$S\cup \{i,j\}$$S$$S\cap \{i,j\}=\{i\}$ (widać to dla k = 3 ). Należy zauważyć, że proces ten zamiana jest automorfizmem ponieważ dla Indeksu p ≠ { i , j } stosunek krawędzi pomiędzy a p , b p i te zamienione wierzchołki są całkowicie zachowane, a wyraźnie związek krawędzi pomiędzy a I , w j , b I , b j jest odpowiednio wyregulowany.$S\cap \{i,j\}= \{j\}$$k=3$$p\neq \{i,j\}$$a_p$$b_p$$a_i,a_j,b_i,b_j$

$a_i,b_i$$a_j,b_j$$a_i$$b_j$$\square$