automorfismo em gadgets Cai-Furer-Immerman

12

No famoso exemplo de contador para isomorfismo de grafos através do método Weisfeiler-Lehman (WL), o seguinte dispositivo foi construído neste artigo por Cai, Furer e Immerman. Eles constroem um gráfico dado porXk=(Vk,Ek)

Vk=AkBkMk where Ak={ai1ik},Bk={bi1ik}, and Mk={mSS{1,2,,k}, |S| is even}Ek={(mS,ai)iS}{(mS,bi)iS}

Um dos lemas do papel (Lema 3.1 página 6) afirma que, se colorir os vértices e b i com a cor i então | A u t ( X k ) | = 2 k - 1 (cor tem de ser preservada pela automorphism) onde cada automorfismos corresponde a trocando um i e b i para cada i , em alguns subconjuntos S de { 1 , 2 , ... , k }aibii|Aut(Xk)|=2k1aibiiS{1,2,,k}de cardinalidade uniforme. Eles dizem que a prova é imediata. Mas não vejo como, no caso de . Em X 2 ( a 1 , m { 1 , 2 } ) é uma aresta, mas se tivermos um automorfismo que troque a 1 , b 1 e a 2 , b 2, a aresta acima será transformada em ( b 1 , m { 1 , 2 } )k=2X2 (a1,m{1,2})a1,b1a2,b2(b1,m{1,2})o que não é uma vantagem. Portanto, isso não deve ser um automorfismo.

Eu gostaria de entender qual é o meu mal-entendido.

DurgaDatta
fonte

Respostas:

6

Está faltando o conjunto vazio que está conectado a todos os b 's. Para se ter uma automorphism, você seleciona um subconjunto T { 1 , . . . , K } de cardinalidade mesmo e troca então um i com b i para cada i T e, em seguida, ajusta os conjuntos no meio. No seu exemplo, o gráfico é ( a 1 , { 12 } ) , ( a 2 , { 12 } ) ,bT{1,...,k}aibiiT

(a1,{12}),(a2,{12}),(b1,),(b2,).

Ainda no seu exemplo, se você não precisa fazer nada e se T = { 1 , 2 } o automorfismo é dado trocando a 1 com b 1 , a 2 com b 2 e { 1 , 2 } com .T=T={1,2}a1b1a2b2{1,2}

Agora, para o caso geral, precisamos mostrar que sempre há uma maneira de ajustar os vértices médios. Sabemos que tem até cardinalidade. Então vamos | T | = 2 r . Só precisamos mostrar que esse automorfismo existe se | T | = 2, caso contrário, podemos aplicar a composição de r automorfismos correspondentes à partição T em r subconjuntos de tamanho 2 . Assim, assuma T = { i , j } . Em seguida, a automorphism troca um i comT|T|=2r|T|=2rTr2T={i,j}ai , a j com b j , cada vértice do meio S tal que S { i , j } = com o vértice do meio S { i , j } (isso pode ser visto no seu exemplo) e cada subconjunto S como que S { i , j } = { i } com o subconjunto tal que S { i , j }biajbjSS{i,j}=S{i,j}SS{i,j}={i} (Isso você pode ver para k = 3 ). Observe que esse processo de troca é um automorfismo, pois para um índice p { i , j } a relação de aresta entre a p , b p e esses vértices trocados é completamente preservada, e claramente a relação de aresta entre a i , a j , b i , b j está ajustado corretamente.S{i,j}={j}k=3p{i,j}apbpai,aj,bi,bj

ai,biaj,bjaibj

Mateus de Oliveira Oliveira
fonte
Em geral, como podemos mostrar que sempre podemos ajustar os conjuntos no meio e obter o automorfismo desejado? O núcleo do meu problema é realmente isso.
precisa saber é o seguinte
Oi, eu adicionei a construção dos automorfismos. Espero que ajude.
Mateus de Oliveira Oliveira
Obrigado. Isso não parece "imediato" para mim. Eu sou muito novo para pesquisar. Este é um sinal ruim para mim?
precisa saber é o seguinte
"Este é um sinal ruim para mim?" Absolutamente não. Penso, ao contrário, que seu ceticismo é um sinal muito bom. Algum dia este tipo de coisas provavelmente será imediato para você também :)
Mateus de Oliveira Oliveira
TiTaibiSSΔT