Conjecturas implicando teorema de quatro cores

38

Teorema de quatro cores (4CT) afirma que todo gráfico plano é de quatro cores. Existem duas provas dadas por [Appel, Haken 1976] e [Robertson, Sanders, Seymour, Thomas 1997]. Ambas as provas são assistidas por computador e bastante intimidadoras.

Existem várias conjecturas na teoria dos grafos que implicam 4CT. A resolução dessas conjecturas provavelmente requer uma melhor compreensão das provas do 4CT. Aqui está uma dessas conjecturas:

Conjectura : Seja um gráfico plano, seja um conjunto de cores uma involução livre de ponto fixo. Seja tal queC f : C C L = ( L v : v V ( G ) )GCf:CCL=(Lv:vV(G))

  • v V|Lv|4 para todos evV
  • se então para todos , para todos . f ( α ) L v v V α CαLvf(α)LvvVαC

Em seguida, existe um -coloring do gráfico .GLG

Se você conhece tais conjecturas que implicam 4CT, liste-as uma em cada resposta. Não consegui encontrar uma lista abrangente dessas conjecturas.

Shiva Kintali
fonte
6
"Eles não tiveram um bug no Coq e nenhum raio cósmico voou pelo computador quando verificaram o teorema das quatro cores" é uma dessas conjecturas.
21313 Andrej Bauer
ref para a conjectura declarada?
vzn
Uma pergunta relacionada é perguntado sobre em mathoverflow: mathoverflow.net/q/189097/1345
Ian Agol

Respostas:

28

4CT é equivalente a:

Oleksandr Bondarenko
fonte
20

Outra verificação mecânica do teorema das quatro cores foi realizada por George Gonthier, da Microsoft Research Cambridge. A diferença com a prova dele é que todo o teorema foi declarado e verificado mecanicamente usando o assistente de prova Coq, enquanto as outras provas contêm apenas o cálculo do kernel escrito em Assembly Assembly e C, e, portanto, correm o risco de apresentar erros. A prova de Gonthier abrange tanto os aspectos de cálculo quanto os lógicos em apenas 60.000 linhas de Coq.

Dave Clarke
fonte
18

Veja T. Saaty, treze variações coloridas da conjectura de quatro cores de Guthrie, American Math. Monthly, 79 (1972) 2-43 para muitos exemplos.

Além disso, no livro de David Barnette, Map Coloring, Polyhedra, and the Four-Problem Problem, MAA, Dolciani Series, Volume 8, 1983, são apresentados muitos exemplos. Um resultado particularmente interessante no livro de Barnete é: Se é sempre possível truncar vértices de um poliedro convexo para produzir um poliedro convexo de 3 valentes, de modo que o número de lados de cada face seja um múltiplo de três, isso implica a verdade das conjecturas de quatro cores.

Joseph Malkevitch
fonte
12

No artigo Retraimentos Planares Absolutos e a Conjectura em Quatro Cores , Pavol Hell provou várias formulações equivalentes para o 4CT. Um deles tem a seguinte redação:

Todo gráfico planar é de 4 cores (The 4CT) se houver uma retração plana absoluta.

HGGr:V(G)V(H)r(v)=vvV(H)

Peng O
fonte
11

Todo gráfico planar cúbico sem ponte é colorido de 3 arestas. (Isso é equivalente a 4CT, devido a Tait.)

Andrew D. King
fonte
11

O artigo de Dror Bar-Natan, "Álgebras de Lie e o Teorema das Quatro Cores" (Combinatorica 17-1 (1997) 43-52, última atualização em outubro de 1999, arXiv: q-alg / 9606016 ) contém uma declaração atraente sobre álgebras de Lie equivalente a o Teorema das Quatro Cores. As noções que aparecem na declaração também aparecem na teoria dos invariantes do tipo finito de nós (invariantes de Vassiliev) e dos 3 variedades.

Gil Kalai
fonte
11

A proposição 2.4 deste documento http://www.sciencedirect.com/science/article/pii/0012365X9500109A# fornece outra formulação para o 4CT.

GΔ(G)GGΔ(G)GGΔ(G)Δ(G)


GK(G)GK(G)G
GK(G)

vb le
fonte
4
Você pode descrevê-lo aqui, para aqueles de nós que não têm acesso (ou como eu, temos preguiça de ativar a VPN para obter acesso)?
David Eppstein
9

Vale a pena ler a descrição de alto nível da prova automatizada de Gonthier, se você estiver procurando mais informações.

Yuri Matiyasevich estudou várias reformulações probabilísticas do Teorema das Quatro Cores, envolvendo correlações positivas entre duas noções de similaridade entre as cores. Suas provas de equivalência baseiam-se em um polinômio gráfico associado, que fornece outro provável ponteiro para conjecturas que implicam o teorema.

András Salamon
fonte
8

Acabei de ler em um artigo de Chalopin e Gonçalves (STOC '09) a seguinte conjectura de West:

Todo gráfico plano é o gráfico de interseção de segmentos no plano usando apenas quatro direções.

Como segmentos paralelos formam um conjunto independente nessa representação, essa conjectura implica o 4CT, mas talvez seja ainda mais forte.

A referência: oeste, problemas abertos . Boletim de Matemática Discreta SIAM J, 2 (1): 10-12, 1991.

RJK
fonte
6

Um snark é um gráfico cúbico conectado e sem ponte que não pode ser colorido com três arestas. Seguindo a Wikipedia, a conjectura de snark , generalizando o 4CT, é a seguinte:

Todo snark tem um subgráfico que pode ser formado a partir do gráfico de Petersen subdividindo algumas de suas arestas.

Novamente, de acordo com a Wikipedia, uma prova dessa conjectura foi anunciada em 2001 por Robertson, Sanders, Seymour e Thomas.

Hermann Gruber
fonte
O teorema de Snark não parece implicar 4CT, certo?
Hsien-Chih Chang張顯之
De fato, implica o 4CT: Toda subdivisão do gráfico de Petersen é claramente não-plana, de modo que a conjectura de snark implica a seguinte reformulação do 4CT (devido a Tait): Todo snark é não-plano.
Hermann Gruber
1
Ah, agora eu vejo onde está o meu problema. A prova do teorema de Snark é novamente uma prova auxiliada por computador. Tenho a impressão de que não há provas verificáveis ​​humanas para o 4CT e não entendi sua resposta. Obrigado!!
Hsien-Chih Chang,
3

"A rotulagem de face de gráficos planares máximos" é o título do meu artigo antigo, publicado recentemente, no qual eu transformei 4 cores de gráficos planares máximos em consistência na rotulagem de face. O link para o artigo é http://www.math.nsysu.edu.tw/~amen/2011/091021-3.pdf

Cahit
fonte
3

Como

LH Kauffman, Reformulando o teorema da cor do mapa , Discrete Mathematics 302 (2005) 145–172

salienta que o princípio da primazia devido a G. Spencer-Brown e a conjectura de Eliahou-Kryuchkov são reformulações equivalentes da FCT.

  • S. Eliahou, flips diagonais assinados e o teorema das quatro cores, European J. Combin. 20 (1999) 641-646.
  • SI Kryuchkov, Teorema das quatro cores e árvores, IV Kruchatov, Instituto de Energia Atômica, Moscou, 1992, IAE-5537/1.
  • G. Spencer-Brown, Leis de Forma, Gesetze der Form, Bohmeier Verlag, 1997.
Hermann Gruber
fonte
3

Artigo de Garry Bowlin e Matthew G. Brin, "Colorir gráficos planares por caminhos coloridos na Associahedra", revisado pela última vez em 12 de maio de 2013, arXiv: 1301.3984 math.CO contém a seguinte conjectura na página 26:

Conjectura 6.4. Para cada par de árvores finas e binárias (D, R) com o mesmo número de folhas, existe uma atribuição de sinal de D e uma palavra w de símbolos de rotação válidos para D, de modo que Dw = R.

Afirma-se que a conjectura 6.4, seguida de proposições e teoremas anteriores, é equivalente a 4CT.

David Clark
fonte
1

Um fluxo k em um gráfico não direcionado G é um gráfico direcionado derivado substituindo cada aresta em G por um arco e atribuindo-lhe um número inteiro entre -k e k , exclusivo, de modo que, para cada vértice em G, a soma dos números inteiros atribuído a arcos apontando para esse vértice é igual à soma dos números inteiros atribuídos a arcos apontando. Um fluxo k NWZ (zero lugar nenhum) é um fluxo k no qual nenhum arco foi atribuído ao número 0.

Para qualquer gráfico planar G , o dual de G é o gráfico que contém um vértice para cada face em uma incorporação plana de G e dois vértices em um compartilhamento compartilhado de uma aresta conectando-os a cada aresta que as faces correspondentes em G compartilham entre si em seus limites. De acordo com o Teorema da Dualidade da Coloração por Fluxo de Tutte, um gráfico planar sem istmo (ou seja, aresta cuja exclusão aumentaria o número de componentes) tem um fluxo NWZ k se e somente se o seu dual for k- colorido. Em outras palavras, um gráfico plano é de 4 cores se e somente se o seu dual tiver um fluxo NWZ 4.

Observe que 4CT exige que o gráfico planar em questão não possua loops (arestas conectando qualquer vértice a si mesmo) porque qualquer gráfico com um loop não pode ser colorido com um conjunto de cores, pois qualquer vértice com um loop ficaria adjacente a um vértice da mesma cor, independentemente de sua cor.

Jordan Longstaff
fonte
0

Eu estou trabalhando nisso:

Se você pode provar o teorema de mapas retangulares, que são mapas feitos de folhas de papel sobrepostas, você também provou o 4ct. Além disso, apenas mapas com faces com todas as 5 arestas ou mais podem ser considerados na pesquisa.

Consulte http://4coloring.wordpress.com/ para obter detalhes.

Mario Stefanutti
fonte