automorphisme dans les gadgets Cai-Furer-Immerman

Dans le célèbre contre-exemple de l'isomorphisme des graphes via la méthode de Weisfeiler-Lehman (WL), le gadget suivant a été construit dans cet article par Cai, Furer et Immerman. Ils construisent un graphe donné par$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\}$

L'un des lemmes de l'article (lemme 3.1 page 6) déclare que si nous colorions les sommets et b i avec la couleur i alors | A u t ( X k ) | = 2 k - 1 (la couleur doit être préservée par l'automorphisme) où chaque automorphisme correspond à l'échange d' un i et d'un b i pour chaque i dans certains sous-ensembles S de { 1 , 2 , … , k $a_i$$b_i$$i$$|Aut(X_k)| = 2^{k-1}$$a_i$$b_i$$i$$S$$\{1,2,\ldots, k\}$de même cardinalité. Ils disent que la preuve est immédiate. Mais je ne vois pas comment même dans le cas de . Dans X 2 ( a 1 , m { 1 , 2 } ) est une arête mais si nous avons un automorphisme qui échange a 1 , b 1 et a 2 , b 2 l'arête ci-dessus se transforme en ( 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\}})$ce qui n'est pas un bord. Cela ne devrait donc pas être un automorphisme.

Je voudrais comprendre quel est mon malentendu.

Vous manquez l'ensemble is qui est connecté à tous les b . Pour obtenir un automorphisme, vous sélectionnez un sous - ensemble T ⊆ { 1 , . . . , k } de cardinalité paire, puis échange a i avec b i pour chaque i ∈ T , puis ajuste les ensembles au milieu. Dans votre exemple, le graphique est ( a 1 , { 12 } ) , ( a 2 , { 12 } ) $\emptyset$$b$$T\subseteq \{1,...,k\}$$a_i$$b_i$$i\in T$

Toujours dans votre exemple si vous n'avez rien à faire et si T = { 1 , 2 } l'automorphisme est donné en échangeant a 1 avec b 1 , a 2 avec b 2 et { 1 , 2 } avec ∅ .$T=\emptyset$$T=\{1,2\}$$a_1$$b_1$$a_2$$b_2$$\{1,2\}$$\emptyset$

Maintenant, pour le cas général, nous devons montrer qu'il existe toujours un moyen d'ajuster les sommets du milieu. Nous savons que a même une cardinalité. Alors laisse | T | = 2 r . Il suffit de montrer qu'un tel automorphisme existe si | T | = 2 car sinon on peut appliquer la composition de r automorphismes correspondant au partitionnement de T en r sous-ensembles de taille 2 . Supposons donc T = { i , j } . Ensuite, l'automorphisme échange un i avec$T$$|T|=2r$$|T|=2$$r$$T$$r$$2$$T=\{i,j\}$$a_i$ , a j avec b j , chaque sommet moyen S tel que S ∩ { i , j } = ∅ avec le sommet moyen S ∪ { i , j } (cela peut être vu dans votre exemple), et chaque sous-ensemble S tel que S ∩ { i , j } = { i } avec le sous-ensemble tel que 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\}$ (Cela, vous pouvez le voir pour k = 3 ). Notez que ce processus d'échange est un automorphisme car pour un indice p ≠ { i , j } la relation de bord entre a p , b p et ces sommets échangés est complètement préservée, et clairement la relation de bord entre a i , a j , b i , b j est correctement réglé.$S\cap \{i,j\}= \{j\}$$k=3$$p\neq \{i,j\}$$a_p$$b_p$$a_i,a_j,b_i,b_j$

Enfin pour voir que ce sont les seuls automorphismes possibles, notez que chacun est coloré avec sa propre couleur. Ils ne peuvent donc pas être mappés sur une autre paire a j , b j . Notez également qu'il n'est pas possible d'avoir un automorphisme qui mappe un sommet moyen à un sommet moyen sans échanger certains a i avec certains b j . $a_i,b_i$$a_j,b_j$$a_i$$b_j$$\square$