Conjecturas implicando teorema de quatro cores

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 ) $G$$C$$f : C \rightarrow C$$L = (L_v : v \in V(G))$

• v ∈ $|L_v| \geq 4$ para todos e$v \in V$
• se então para todos , para todos . f ( α ) ∈ L v v ∈ V α ∈ $\alpha \in L_v$$f(\alpha) \in L_v$$v \in V$$\alpha \in C$

Em seguida, existe um -coloring do gráfico .$L$$G$

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

4CT é equivalente a:

• Colorir um hipergrafo induzido por uma família finita de discos (não necessariamente disjuntos no interior, mas também discos que possam ter sobreposições arbitrárias) com no máximo quatro cores$[1]$ .
• A proposição de que toda triangulação planar com mais de três vértices é a união de dois gráficos bipartidos conectados, cada um sem istmo .$[2]$
• Um problema combinatório sobre a álgebra de produtos cruzados com vetor tridimensional .$[3]$
• A proposição de que a gramática G é totalmente ambígua .$[4]$
• Para qualquer número inteiro positivo , existe pelo menos um caminho assinável que une duas permutações de .S $n$$S_n$

• Um equivalente algébrico do teorema das quatro cores é apresentado. O equivalente é a afirmação de não pertencer a uma família de polinômios em uma família de ideais polinomiais sobre um campo finito específico .$[6]$

  1. Smorodinsky S. Sobre o número cromático de hipergrafos geométricos .
  2. Mabry R. Gráficos bipartidos e o teorema das quatro cores .
  3. A coloração Kauffman LH Map e o vetor cruzam o produto .
  4. Cooper BJ et al. Rumo a uma prova teórica da linguagem do teorema das quatro cores .
  5. Eliahou S. et al. Permutações assinadas e o teorema das quatro cores .
  6. Howard L. Uma reformulação algébrica do teorema das quatro cores .

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.

Eu falei sobre isso no meu blog e nossa percepção é: por exemplo, a condição de Tait pode ser enfraquecida, pois há uma coloração que possui no máximo 0 (n) erros. Veja aqui: http://rjlipton.wordpress.com/2009/04/24/the-four-color-theorem/

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.

A conjectura de Hadwiger .

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.

$H$$G$$G$$r: V(G)\to V(H)$$r(v)=v$$v\in V(H)$

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

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.

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

$G$$\Delta(G)$$G$$G$$\Delta(G)$$G$$G$$\Delta(G)$$\Delta(G)$

$G$$K(G)$$G$$K(G)$$G$
$G$$K(G)$

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.

• Georges Gonthier, Prova Formal - O Teorema das Quatro Cores , Avisos da Sociedade Americana de Matemática 55 (11) 1382–1393, 2008.
• Yuri Matiyasevich, um equivalente probabilístico da conjectura de quatro cores , tradução de papel em Teoriya Veroyatnostei i ee Primeneniya 48 411–416, 2003.
• Yuri Matiyasevich, Algumas reformulações probabilísticas das conjecturas de quatro cores , Journal of Graph Theory 46 167-179, 2004. ( pré-impressão )

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.

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.

"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

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.

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.

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.

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.