Get best of the week

Rainbow Coloring são os melhores amigos dos matemáticos

Recentemente, as cores do arco-íris ajudaram a realizar uma nova prova. E eles não são a primeira vez que são úteis.



O código de cores do quadrado latino e seu gráfico podem dizer muito sobre eles:

recentemente conversamos sobre uma nova prova da hipótese de Ringel . Parte da evidência estava relacionada ao uso de cores do arco-íris, uma maneira especial de codificar cores para visualizar informações. No entanto, esses livros para colorir têm sido usados ​​por matemáticos há muito tempo para facilitar a solução de quebra-cabeças, e agora eles estão tentando aplicar essa técnica ao problema associado ao anterior.

A hipótese de Ringel é um problema do campo da combinatória relacionado à construção de gráficos - pontos (vértices) conectados por linhas (arestas). Ele prevê uma relação especial entre gráficos grandes de um determinado tipo com 2n + 1 vértices e gráficos proporcionalmente menores com n + 1 vértices.

Vamos começar, por exemplo, com 11 picos. Conecte cada vértice a todos os outros para obter o chamado gráfico completo. Em seguida, pegue seis dos vértices disponíveis e conecte-os, como quisermos, apenas para não obter loops fechados. Assim, temos o chamado "madeira".


Exemplos de gráficos e árvores completos

A hipótese de Ringel diz que cópias de qualquer árvore podem cobrir ou ladrilhar idealmente todas as bordas do gráfico completo correspondente - assim como você pode ladrilhar o chão da cozinha com os mesmos ladrilhos.



Como no chão da cozinha, para o sucesso é necessário escolher o local correto do primeiro ladrilho. Os três matemáticos que criaram a cor de prova codificaram as bordas do gráfico completo com base na distância entre os vértices para encontrar esse local.



Depois, tentaram organizar a árvore dentro do gráfico completo, de modo a cobrir uma borda de cada cor. Tendo mostrado que tal arranjo de "arco-íris" é possível em qualquer caso, eles provaram que o ladrilho ideal previsto por Ringel sempre funciona.

No entanto, essa técnica de coloração do arco-íris não foi resgatada pela primeira vez.

No século 18, Leonard Euler ficou interessado em algo como o Sudoku para crianças. Pegue um quadrado de células 3x3. Euler o preencheu para que em cada linha e cada coluna houvesse números de 1 a 3, nunca se repetindo. Este quebra-cabeça é chamado de quadrado latino . Padrões e técnicas descobertos por Euler e outros matemáticos no estudo de quadrados latinos têm uma conexão com muitas áreas diferentes da matemática.



Então Euler se perguntou: é possível escolher três células, uma de cada coluna e cada linha, para que os números nelas não se repitam? Suponha que você possa selecionar uma célula da primeira coluna da primeira linha que contém 1, uma célula da segunda linha da segunda coluna que contém 3 e da terceira linha da terceira coluna que contém 2. Portanto, selecionamos três células, cada uma das quais pertencendo a diferentes linhas e colunas, e contém seu número - 1, 3, 2. Esse conjunto de células é chamado transversal.



Euler queria saber se é possível dividir toda a grade 3x3 (ou uma grade quadrada de qualquer tamanho) inteiramente em conjuntos transversais, para que cada conjunto tenha um número de cada linha e cada coluna. Ou seja, no caso de um quadrado 3x3, eu gostaria de encontrar três conjuntos transversais diferentes cobrindo todas as células do quadrado.

Como resultado, matemáticos descobriram que uma maneira de explorar esse problema é transformar um quadrado em um gráfico. Para fazer isso, desenhe três vértices à esquerda, indicando três colunas. Em seguida, desenhamos três vértices à direita, representando as linhas. Desenhe as arestas conectando cada vértice à direita com cada vértice à esquerda. Cada aresta, sendo uma combinação de uma linha e coluna específica, representa uma das nove células. Por exemplo, a aresta entre o vértice superior direito e o vértice superior esquerdo corresponde à célula da primeira linha da primeira coluna (célula superior esquerda do quadrado latino).



Agora pegamos os lápis de cor e codificamos as cores das costelas de acordo com o número do quadrado que eles indicam. Suponha que pintemos as linhas que indicam 1 com azul, vermelho com 2 e amarelo com 3. Se 1 estiver na célula superior esquerda, a borda entre os vértices superiores será azul.



Vamos olhar para as cores das bordas. É possível escolher três arestas de cada uma das três cores para que elas comecem e terminem em vértices diferentes? Esse conjunto é chamado de correspondência de arco-íris. Se você o encontrar, fica claro que no quadrado latino correspondente há uma transversal. Além disso, se você encontrar três correspondências diferentes do arco-íris, fica claro que todo o quadrado latino consiste em transversais.



A coloração do arco-íris ajudou os pesquisadores a estudar problemas no passado e também se tornou um elemento-chave na nova prova da hipótese de Ringel. Eles também desempenham um papel em uma tarefa ainda mais complexa, a hipótese de marcação graciosa .

Para entender a essência do problema, primeiro desenhe seis vértices e conecte-os para formar uma árvore. Atribua a cada vértice um número de qualquer maneira. Em seguida, marque cada aresta com a diferença entre os números dos vértices que conectam. Ou seja, por exemplo, se uma aresta conecta os vértices 6 e 2, marcamos essa aresta com o número 4.

Seu objetivo é fazer com que os rótulos das arestas sigam em seqüência e seus números não se repitam. Nesse caso, 1, 2, 3, 4, 5. Se você puder fazer isso, haverá uma marcação graciosa para sua árvore.



Na década de 1960, Gerhard Ringel - aquele que apresentou a hipótese - e Anton Kotsig, juntos, sugeriram que qualquer árvore, independentemente do número de arestas ou forma, pode ser marcada com elegância.

A hipótese de marcação graciosa implica a hipótese de Ringel - ou seja, se a primeira hipótese for verdadeira, a hipótese de Ringel também será verdadeira. Para entender isso, voltemos a uma árvore de seis vértices, marcada com elegância, e a um gráfico completo de 11 vértices. Distribuímos esses 11 vértices em torno da circunferência e os numeramos de 1 a 11. Agora, colocaremos uma cópia da árvore no gráfico completo para que os rótulos dos vértices coincidam: o vértice 5 da árvore se sobrepõe ao vértice 5 do gráfico completo e assim por diante. Esta veiculação é uma cópia do arco-íris de uma árvore marcada com elegância.



Portanto, se você sabe que as árvores com o número de vértices n + 1 sempre podem ser marcadas com elegância, então você sabe que elas sempre podem ser colocadas dentro do gráfico completo correspondente com 2n + 1 vértices para obter uma cópia em arco-íris da árvore. E esse posicionamento será exatamente a posição com a qual iniciar o processo de colocação de Ringel.

"Se você encontrar uma marcação graciosa, posso lhe dizer como encontrar sua cópia do arco-íris", disse Benny Sudakov, do Instituto Federal Suíço de Tecnologia, um dos três autores da prova da hipótese de Ringel.

Obviamente, os matemáticos foram capazes de provar a verdade da hipótese de Ringel sem ter que provar a hipótese da marcação graciosa, deixando essa pergunta sem resposta.

"A marcação graciosa é uma questão atraente e bonita em si mesma, e ainda permanece em aberto", disse Sudakov.

No entanto, os métodos que levaram à prova da hipótese de Ringel provavelmente podem ser aplicados à marcação graciosa - e os matemáticos estão ansiosos para descobrir até que ponto esses métodos podem levá-los.

More articles:


All Articles