automorfisme dalam gadget Cai-Furer-Immerman

Dalam contoh tandingan terkenal untuk isomorfisme grafik melalui metode Weisfeiler-Lehman (WL), gadget berikut ini dibuat dalam makalah ini oleh Cai, Furer dan Immerman. Mereka membangun sebuah grafik diberikan oleh$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\}$

Salah satu lemmas di koran (lemma 3.1 halaman 6) menyatakan bahwa jika kita mewarnai simpul dan b i dengan warna i kemudian | A u t ( X k ) | = 2 k - 1 (warna harus dipertahankan oleh automorfisme) di mana masing-masing automorfisme sesuai dengan penukaran a i dan b i untuk masing-masing i dalam beberapa himpunan bagian S dari { 1 , 2 , ... , k $a_i$$b_i$$i$$|Aut(X_k)| = 2^{k-1}$$a_i$$b_i$$i$$S$$\{1,2,\ldots, k\}$bahkan kardinalitas. Mereka mengatakan bahwa buktinya langsung. Tapi saya gagal melihat bagaimana bahkan dalam kasus . Dalam X 2 ( a 1 , m { 1 , 2 } ) adalah sebuah edge tetapi jika kita memiliki automorfisme yang menukar a 1 , b 1 dan a 2 , b 2 tepi di atas ditransformasikan menjadi ( 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\}})$yang bukan merupakan keunggulan. Jadi itu seharusnya tidak menjadi automorfisme.

Saya ingin mengerti apa kesalahpahaman saya.

Anda melewatkan Emptyset yang terhubung ke semua b 's. Untuk mendapatkan automorphism, Anda memilih subset T ⊆ { 1 , . . . , k } bahkan kardinalitas dan kemudian menukar a i dengan b i untuk setiap i ∈ T dan kemudian menyesuaikan set di tengah. Dalam contoh Anda grafiknya adalah ( a 1 , { 12 } ) , ( a 2 , { 12 } ) $\emptyset$$b$$T\subseteq \{1,...,k\}$$a_i$$b_i$$i\in T$

Masih dalam contoh Anda jika Anda tidak perlu melakukan apa-apa dan jika T = { 1 , 2 } automorphism diberikan dengan menukar sebuah 1 dengan b 1 , a 2 dengan b 2 dan { 1 , 2 } dengan ∅ .$T=\emptyset$$T=\{1,2\}$$a_1$$b_1$$a_2$$b_2$$\{1,2\}$$\emptyset$

Sekarang untuk kasus umum, kita perlu menunjukkan bahwa selalu ada cara untuk menyesuaikan simpul tengah. Kita tahu bahwa bahkan memiliki kardinalitas. Jadi, biarkan | T | = 2 r . Kita hanya perlu menunjukkan bahwa automorfisme semacam itu ada jika | T | = 2 karena jika tidak kita dapat menerapkan komposisi r automorfisme yang sesuai dengan partisi T menjadi r himpunan bagian ukuran 2 . Jadi asumsikan T = { i , j } . Kemudian automorphism yang swap a i dengan$T$$|T|=2r$$|T|=2$$r$$T$$r$$2$$T=\{i,j\}$$a_i$ , a j dengan b j , setiap sudut tengah S sehingga S ∩ { i , j } = ∅ dengan tengah simpul S ∪ { i , j } (ini dapat dilihat dalam contoh Anda), dan masing-masing bagian S seperti bahwa S ∩ { i , j } = { i } dengan himpunan bagian sehingga 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\}$ (Ini dapat Anda lihat untuk k = 3 ). Perhatikan bahwa proses swapping ini adalah automorphism karena bagi indeks p ≠ { i , j } hubungan tepi antara sebuah p , b p dan ini simpul bertukar benar-benar dipertahankan, dan jelas hubungan tepi antara suatu i , a j , b i , b j benar disesuaikan.$S\cap \{i,j\}= \{j\}$$k=3$$p\neq \{i,j\}$$a_p$$b_p$$a_i,a_j,b_i,b_j$

Akhirnya untuk melihat bahwa ini adalah satu-satunya automorfisme yang mungkin, perhatikan bahwa setiap diwarnai dengan warnanya sendiri. Sehingga mereka tidak dapat dipetakan ke sepasang a j , b j . Juga melihat bahwa itu tidak mungkin untuk memiliki automorphism yang memetakan titik tengah ke titik tengah tanpa swapping beberapa sebuah i dengan beberapa b j . $a_i,b_i$$a_j,b_j$$a_i$$b_j$$\square$