Encontrar buracos ímpares nos gráficos de Paley circulantes

13

Os gráficos de Paley P q são aqueles cujo conjunto de vértices é dado pelo campo finito GF (q), para potências primárias q≡1 (mod 4), e onde dois vértices são adjacentes se e somente se diferem por 2 para alguns a ∈ GF (q). No caso em que q é primo, o campo finito GF (q) é apenas o conjunto de números inteiros módulo q.

Num artigo recente , Maistrelli e Penman mostram que o único gráfico de Paley perfeito (com um número cromático igual ao tamanho da sua maior camarilha) é o de nove vértices. Isso implica, em particular, que nenhum dos gráficos de Paley P q são perfeitos para q prime.

O Teorema Forte do Gráfico Perfeito afirma que um gráfico G é perfeito se, e somente se, G e seu complemento não tiverem orifícios ímpares (um subgrafo induzido que é um ciclo de comprimento ímpar e tamanho pelo menos 5.) Os gráficos de Paley de primeira ordem são: auto-complementar e imperfeito; portanto, eles devem conter orifícios ímpares.

Questão. Para q≡1 (mod 4) prime, existe um algoritmo poli (q) para encontrar um furo ímpar em P q ? Existe um algoritmo polylog (q)? Aleatoriedade e conjecturas teóricas populares são permitidas.

Niel de Beaudrap
fonte

Respostas:

10

Eu acredito que existe um algoritmo poli (q) conhecido. Meu entendimento do algoritmo de Chudnovsky, Cornuéjols, Liu, Seymour e Vušković, "Reconhecendo gráficos de Berge", Combinatorica 2005 , é que ele encontra um buraco ímpar ou um anti-buraco estranho em qualquer gráfico não perfeito em tempo polinomial. Os autores escrevem na página 2 de seu artigo que o problema de encontrar buracos ímpares nos gráficos que os contêm permanece aberto, porque as etapas 1 e 3 de seu algoritmo encontram buracos, mas a etapa 2 pode encontrar um anti-furo. No entanto, no caso dos gráficos de Paley, se você encontrar um anti furo, basta multiplicar todos os vértices nele por um não resíduo para transformá-lo em um buraco ímpar.

Como alternativa, por analogia com o gráfico Rado, para cada k deve haver um N, de modo que os gráficos de Paley em N ou mais vértices devem ter a propriedade extension: para qualquer subconjunto com menos de k vértices e qualquer coloração 2 do subconjunto, existe outro vértice adjacente a todos os vértices de uma classe de cores e não adjacente a todos os vértices da outra classe de cores. Nesse caso, para k = 5, você pode construir um ímpar de 5 buracos com avidez no tempo polinomial por etapa. Talvez essa direção seja esperançosa para um algoritmo poli (log (q))? Se funcionar, mostraria pelo menos que existem pequenos buracos estranhos, aparentemente um pré-requisito necessário para encontrá-los rapidamente.

Na verdade, não me surpreenderia se o algoritmo a seguir fosse um poli (log (q)): se q for menor que alguma constante fixa, procure a resposta, caso contrário, crie avidamente um buraco de 5 buracos pesquisando sequencialmente os números 0, 1, 2, 3, ... para vértices que podem ser adicionados como parte de um 5 orifícios parciais. Mas talvez provar que ele funcione no tempo poli (log (q)) exija alguma teoria profunda dos números.

Pelos resultados de Chung, Graham e Wilson, "Gráficos quasi-aleatórios", Combinatorica 1989, o seguinte algoritmo aleatório resolve o problema em um número constante esperado de tentativas quando q é primo: se q for suficientemente pequeno, se q for suficientemente pequeno, procure a resposta, caso contrário, escolha repetidamente um conjunto aleatório de cinco vértices, verifique se eles formam um furo ímpar e, em caso afirmativo, devolva-o. Mas eles não dizem se funciona quando q não é um primo, mas um poder primo, então talvez você precise ter mais cuidado nesse caso.

David Eppstein
fonte
Referências que mostram que os gráficos de Paley têm a propriedade de extensão: os gráficos de Paley satisfazem todos os axiomas de adjacência de primeira ordem Andreas Blass, Geoffrey Exoo, Frank Harary, J. Graph. º. 1981 e Gráficos que contêm todos os gráficos pequenos, Bollobas e Thomason, Eur. J. Combin. 1981. Infelizmente, parece que não tenho acesso por assinatura a nenhum deles, então não posso dizer muito mais sobre o que há neles.
precisa
O algoritmo em [Chudnovsky + Cornuéjols + Liu + Seymour + Vušković] está realmente na página 4 do artigo; mas obrigado pelo ponteiro! Também acho o resultado [Cheung + Graham + Wilson] um tanto espantoso; Eu vou investigar isso.
Niel de Beaudrap
Lendo o resultado [Cheung + Graham + Wilson]: eles descrevem nas páginas 359-360 que os gráficos de Paley de primeira ordem são pseudo-aleatórios em seu sentido. Se bem entendi, sua sugestão é que todos os subgráficos rotulados induzidos por cinco vértices (dos quais existem muitos finitos e que, obviamente, incluem várias amostras de 5 orifícios) ocorram aproximadamente com a mesma frequência; isso parece apoiar sua descrição de um algoritmo de tempo constante. Eu daria +10 se pudesse. Muito Obrigado!
Niel de Beaudrap