Literatura sobre uma abordagem ingênua ao isomorfismo de grafos através da inspeção de polinômios de matrizes de adjacência

Descrevo uma abordagem ao isomorfismo gráfico que provavelmente tem falsos positivos e estou curioso para saber se há literatura indicando que ele não funciona.

Dadas duas matrizes de adjacência , um método reconhecidamente ingênuo de verificar se há isomorfismo é verificar se, para cada linha de , existe uma linha de que é uma permutação da linha , denotada por . Um pouco mais rigorosa é a questão, existe um "isomorfismo local" para o qual para todas as linhas. A produção de um isomorfismo local pode ser feita em tempo polinomial, construindo uma matriz com ; então eu G v G u G [ u ] ∼ H [ v ] π G [ u ] ∼ H [ π ( u ) ] n × n A A [ u , v ] = ( G [ u ] ∼ H [ v ] ) G $G, H$$u$$G$$v$$G$$u$$G[u] \sim H[v]$$\pi$$G[u] \sim H[\pi(u)]$$n\times n$$A$$A[u,v] = (G[u]\sim H[v])$$G$$H$são localmente isomórficas se tem uma cobertura de ciclo e toda cobertura de ciclo é um isomorfismo local.$A$

Todos os gráficos regulares enganam esse método, obviamente, portanto, uma abordagem um pouco menos ingênua é calcular os poderes das matrizes e verificar se há isomorfismo local, explorando o fato que você tem várias matrizes configurando quando encontrar uma potência tal que e verificando a cobertura do ciclo apenas no final. Uma abordagem ainda menos ingênua é encontrar um conjunto de polinômios, de fato um conjunto de circuitos aritméticos, e definir A [u, v] = 0 quando encontramos qualquer polinômio p com p (G) [u] \ u \ sim \ ( H) [v] .Um [ u , v ] = $G^2, H^2, G^3, H^3,\ldots$$A[u,v] = 0$A [ u , v ] = $G^k[u]\not\sim H^k[v]$$A[u,v]=0$p ( G ) [ u ] ≁ p ( H ) [ v $p$$p(G)[u]\not\sim p(H)[v]$

Isso me parece uma abordagem incrivelmente ingênua do isomorfismo de grafos, por isso tenho certeza de que alguém já o investigou e provou um teorema como

Thm Para infinitamente muitas $n$ existem nonisomorphic $n\times n$ matrizes $G, H$ e uma permutação $\pi$ de tal modo que para cada polinio $p$ , $p(G)$ e $p(H)$ são localmente isomorfo pelo que permutação: $p(G)\overset{\pi}{\sim}p(H)$ .

Pergunta: Existe tal teorema? Eu olhei na literatura e não consigo encontrá-lo.

Se existe um limite no grau que é polinomial em tal que para cada duas matrizes não isomórficas, o isomorfismo local é refutado calculando , ou se houver uma família de polinômios facilmente computável , cada um com comprimento delimitado polinomialmente, mas possivelmente com grau exponencial, então temos um algoritmo P para isomorfismo de gráfico. Se tais polinômios (ou circuitos aritméticos) são fáceis de adivinhar, então temos um algoritmo coRP . Se sempre existe uma (família de) circuitos aritméticos para testemunhar isomorfismo não local, isso gera um algoritmo coNP .n G 1 , H 1 , … , G p o l y ( n ) , H p o l y ( n ) p 1 , … , p $k$$n$$G^1, H^1, \ldots, G^{poly(n)}, H^{poly(n)}$$p_1, \ldots ,p_k$

Observe que podemos evitar o problema de as entradas de matrizes de alta potência aumentarem muito computando os polinômios em campos pequenos, por exemplo, computando-os modulos pequenos primos. Em um algoritmo coNP , o provador pode fornecer esses números primos.

Sim, existe esse teorema, mais ou menos. Basicamente, afirma que o procedimento Weisfeiler-Lehman k-dimensional inclui (ou seja, domina) todas as abordagens combinatórias conhecidas para o teste de isomorfismo gráfico. (Sua proposta concreta deve ser incluída no procedimento Weisfeiler-Lehman bidimensional, se não me engano.) Para cada k fixo, há uma classe de contra-exemplos do procedimento Weisfeiler-Lehman k-dimensional conhecido como Cai-Fürer Construção -Immerman.

Aprendi pela primeira vez o básico do procedimento Weisfeiler-Lehman e da construção Cai-Fürer-Immmerman de

http://users.cecs.anu.edu.au/~pascal/docs/thesis_pascal_schweitzer.pdf

Há muito mais para aprender sobre o procedimento Weisfeiler-Lehman do que o descrito aqui, mas pelo menos o tratamento da construção Cai-Fürer-Immmerman é completo e suficiente para o seu objetivo. " O Procedimento Weisfeiler-Lehman ", de Vikraman Arvind, é um breve ensaio recente que serve de convite para o tópico.

Talvez o ponto crucial a ser retirado da minha resposta seja que, se você encontrar um método de teste de isomorfismo puramente combinatório (como o descrito na sua pergunta), que não seja incluído (ou seja, dominado) pelo procedimento Weisfeiler-Lehman k-dimensional, então isso seria uma inovação por si só, independentemente de o método ser realmente útil.