Matemático russo refuta a hipótese de 53 anos sobre a coloração de redes

Apenas três páginas foram necessárias para o matemático russo descrever um método de colorir redes de um determinado tipo que excedia as expectativas dos especialistas

Uma hipótese de 53 anos sobre a melhor maneira de atribuir cores aos nós da rede é refutada em um artigo online. O trabalho em apenas três páginas mostra a existência de métodos para colorir certas cores que excederam todas as expectativas dos especialistas.

Tarefas para colorir redes [ ver número cromático / aprox. perev. ], inspirado na questão dessa coloração de mapas, em que os países vizinhos têm cores diferentes, estão no foco de pesquisas de matemáticos há quase 200 anos. A tarefa é entender como colorir os nós de uma determinada rede (ou gráfico , como os matemáticos os chamam) para que quaisquer dois nós conectados tenham cores diferentes. Dependendo do contexto, essa coloração pode fornecer uma maneira eficaz de acomodar os convidados em um casamento, organizar tarefas de produção por intervalos de tempo livres ou até mesmo resolver o sudoku .

As tarefas de colorir gráficos geralmente são fáceis de formular, mas incrivelmente difíceis de resolver. Mesmo em busca de uma resposta para a pergunta com a qual todo esse campo de pesquisa começou, quatro cores são suficientes para colorir qualquer mapa ? - Demorou mais de cem anos (se você estiver interessado, a resposta é sim).

A tarefa considerada no novo trabalho, até agora, não era considerada uma exceção. Ele não pôde ser resolvido por mais de 50 anos e diz respeito a produtos tensores - gráficos compostos de uma combinação especial de dois gráficos diferentes (vamos chamá-los de G e H). O produto tensorial dos gráficos G e H é um gráfico novo e maior, cada um dos vértices que denota um par de vértices dos gráficos originais - um de G e um de H - enquanto dois vértices do produto tensorial são conectados se ambos os vértices correspondentes em G e seus vértices correspondentes em H.

Suponha que você seja um professor de música e precise encontrar bons duetos para um concerto do quinto ano. Você pode fazer um gráfico, cujos vértices serão alunos, e os laços entre os pares indicarão a presença de boas relações entre eles. Em seguida, você pode fazer um segundo gráfico no qual cada nó indicará diferentes instrumentos musicais, e a conexão entre eles é a presença de partituras para um dueto desses dois instrumentos. No produto tensorial desses dois gráficos, haverá um vértice para cada união possível do aluno e do instrumento (digamos, Alice e trombone), e os dois vértices serão conectados se dois alunos trabalharem bem juntos e os dois instrumentos forem compatíveis.

Em 1966, Stephen Hedetniemi , agora professor da Universidade Clemson na Carolina do Sul, sugeriu em sua dissertação de doutorado que o número mínimo de cores necessárias para colorir um produto tensorial é a menor das duas cores necessárias para colorir qualquer um dos dois gráficos. . "Esta é uma das principais hipóteses na teoria dos grafos", disse Gil Kalai, da Universidade Hebraica de Jerusalém. "Muitas pessoas tentaram ponderá-la."

Nas últimas décadas, os matemáticos reuniram uma montanha de evidências, algumas das quais falaram sobre a verdade da hipótese e outras - sobre sua falsidade. Diferentes matemáticos tinham suposições diferentes sobre qual opção acabaria vencendo. Mas todos concordaram que pelo menos era uma tarefa difícil.

"Pessoalmente, pensei que essa hipótese era verdadeira, já que um grande número de pessoas inteligentes a estudava e teria que criar um contra-exemplo", se isso existisse, disse Anthony Bonato, da Universidade Ryerson, em Toronto.

Assim, o matemático russo Yaroslav Nikolaevich Shitov criou uma maneira simples de criar contra-exemplos, trabalhos de tensores que exigem menos cores do que qualquer um dos dois gráficos que os compõem. A evidência saiu "elementar, mas brilhante", disse Pavol Hell, da Universidade Simon Fraser, em Burnaby, Canadá.

Os gráficos de tensores estão intimamente relacionados a perguntas sobre mapeamentos de diferentes gráficos, e nessa área da matemática, a hipótese de Hedetniemi foi provavelmente o maior problema em aberto, disse Hell. "Este é um grande avanço."

Hangouts coloridos

Para imaginar quais informações podem ser extraídas da coloração do gráfico de tensores, imagine que você convidará seus amigos para sua propriedade suburbana todo fim de semana. E, como um bom anfitrião, você deseja reunir pessoas que gostarão da companhia um do outro.

Você sabe que alguns de seus amigos poderão fazer amigos rapidamente com base no trabalho, enquanto outros não. Você também sabe que seus amigos têm um hobby - outra maneira pela qual os hóspedes podem encontrar interesses comuns. Você especula que um professor de dança de violino pode se divertir conversando com um instrutor de ioga jogando tênis ou discutindo música com um fazendeiro que produz xarope de bordo e toca piano, mas provavelmente não sobre ele do que ele falará com um cientista político colecionando selos. Você deseja que todos os convidados possam encontrar interesses comuns em qualquer fim de semana, seja um emprego ou um hobby, e está se perguntando quantas reuniões precisará organizar para classificar todos os convidados da lista.


Yaroslav Shitov descobriu um contra-exemplo da hipótese de Hedetniemi, de 53 anos, a partir da teoria dos grafos

Você pode imaginar a relação de vários tipos de trabalho na forma de gráfico, cujos nós serão o trabalho e quaisquer dois trabalhos serão conectados por arestas, entre as quais, muito provavelmente, não será possível encontrar tópicos comuns para conversação (essa abordagem pode parecer invertida, no entanto, no contexto da coloração gráficos, essa conexão de vértices faz sentido, pois usaremos cores para separar esses pares problemáticos). Você também pode fazer um gráfico, cujos vértices são hobbies diferentes e interconectar todos os incompatíveis.

O produto tensorial desses dois gráficos terá nós para cada par trabalho-hobby e os dois vértices serão combinados se o trabalho e os dois hobbies forem incompatíveis - essa é exatamente a situação que você deseja evitar no fim de semana. Se você pode colorir os vértices do produto tensorial para que os vértices conectados pelas nervuras tenham cores diferentes, isso permitirá criar listas de convidados para diferentes fins de semana: você pode convidar pessoas correspondentes a vértices verdes para o fim de semana "verde", vértices vermelhos para "vermelho" ", E assim por diante, e certifique-se de que convidados incompatíveis estejam nas listas em diferentes fins de semana. O número de cores usadas indica quantos dias você precisará tirar no calendário.

A partir deste exemplo, segue-se que qualquer coloração válida do gráfico de trabalho pode ser transferida para o produto tensorial - você pode simplesmente colorir cada combinação de hobby e trabalho na mesma cor que você usou para o trabalho. Essa coloração levará ao fato de que, nas reuniões, cada casal de convidados será compatível exclusivamente de acordo com seus interesses profissionais, independentemente de seu hobby.

E vice-versa, qualquer coloração admissível do gráfico do hobby é transferida para o produto tensorial. Hedetniemi sugeriu que a melhor maneira de colorir um gráfico tensorial seria fazer com que um dos gráficos originais tivesse um número mínimo de cores.

À primeira vista, a hipótese de Hedetniemi parece improvável. Afinal, se você basear a coloração tensorial na coloração do gráfico de trabalho, ignora tudo o que sabe sobre os hobbies compatíveis de seus amigos e potencialmente compartilha os convidados que se dão bem. Se você combinar todas as informações sobre trabalho e hobbies, poderá usar menos flores e aproveitar um merecido fim de semana sem convidados.

E, no entanto, por mais de 50 anos, os matemáticos não conseguiram encontrar um único produto tensorial, para colorir, o que exigiria menos cores do que para qualquer um de seus gráficos constituintes. Eles conseguiram provar que a hipótese é verdadeira se não fossem necessárias mais de quatro cores para colorir um dos dois gráficos. Também é verdade no caso mais geral de cores "fracionárias", quando cada vértice pode ser atribuído a uma combinação de cores - por exemplo, 2/3 amarelo e 1/3 verde. (Em termos de reuniões de fim de semana, isso pode corresponder a uma situação em que há três jornalistas em sua lista de amigos, um deles joga tênis e você convidou dois deles para o fim de semana “amarelo” e o terceiro para o “verde”).

Esses achados sugeriram que a hipótese poderia ser verdadeira, mas outros disseram o contrário. Por exemplo, matemáticos mostraram que a hipótese de Hedetniemi se desintegra em gráficos que requerem um número infinito de cores para colorir ou em gráficos direcionados cujas bordas têm direções preferidas. Mas, apesar de os matemáticos terem provado a hipótese de Hedetniemi para alguns casos e refutados para outros, eles não conseguiram resolver o problema no campo que o próprio Hedetniemi originalmente considerava: gráficos finitos não direcionados com cores inteiras.

"Todos geralmente pensavam que era verdade, mas era difícil provar ou refutar", disse Noga Elon, da Universidade de Princeton.

Desenhos para colorir

Shitov esmagou todas essas incertezas com uma demonstração clara e simples da falsidade da hipótese de Hedetniemi. No trabalho, cuja prova principal cabe em uma página, recheada de matemática, ele mostra como criar um tipo especial de produto tensorial, que requer menos cor para pintar do que qualquer um de seus componentes.

Shitov começa seu trabalho observando o que acontecerá se combinarmos o gráfico G com um de seus gráficos exponenciais e obtermos seu produto tensorial. O gráfico exponencial possui um nó para cada uma das cores possíveis G com um determinado número fixo de cores (todas as cores possíveis são permitidas, não apenas aquelas cujos vértices conectados possuem cores diferentes). Se o gráfico G, por exemplo, tiver 7 vértices e houver 5 cores em nossa paleta, o gráfico exponencial terá 5 ⁷ vértices - e é por isso que é chamado exponencial.


A hipótese de Stephen Hedetniemi sobre o número mínimo de cores para colorir o produto tensorial dos gráficos permanece não confirmada há mais de 50 anos

Se retornarmos à opção de coloração, na qual os vértices conectados devem ter cores diferentes, não podemos garantir que as cinco cores da nossa paleta sejam suficientes para colorir o gráfico G e, da mesma forma, podem não ser suficientes para colorir o gráfico exponencial com 5 ⁷ vértices . No entanto, os matemáticos sabem há muito tempo que existe um gráfico para o qual cinco cores são suficientes: é um produto tensorial que consiste em G e seu gráfico exponencial.

De fato, todos os gráficos exponenciais têm essa propriedade: um produto tensorial que combina um gráfico exponencial com o gráfico a partir do qual ele foi criado pode ser colorido exatamente com o mesmo número de cores que o gráfico original. Shitov refutou a hipótese de Hedetniemi, mostrando como é possível criar um gráfico G para que sejam necessárias mais cores para colorir tanto ele quanto seu gráfico exponencial.

Hedetniemi afirmou que estava "completamente encantado" com a resolução da situação com sua hipótese depois de tantas décadas. A evidência de Shitov "tem certa elegância, simplicidade e pura qualidade", ele escreveu em um email.

O novo contra-exemplo acabou por ser astuto e inventivo, dizem os matemáticos, e não precisa de ferramentas matemáticas avançadas e complexas. "Para um especialista em teoria dos grafos, esse design pode ser explicado em duas frases", disse Kalai.

Por que ninguém percebe esse argumento há mais de 50 anos é um mistério para os matemáticos. "Às vezes, uma pequena jóia se esconde sob uma pilha de folhagem", disse Hell. "Shitov simplesmente conseguiu entender essa questão mais profundamente do que todos os outros."

Os gráficos de Shitov são gigantescos: ele não calculou seu tamanho exato, mas estima que o gráfico G provavelmente terá cerca de ^4.100 vértices e os gráficos exponenciais terão pelo menos ^4.000 vértices, ou seja, muito mais do que o número aproximado de partículas elementares em universo observável [ cerca de 10 ⁸⁰ / aprox. perev. ]

Mas, é claro, tudo depende do observador. Shitov acredita que seu contra-exemplo “não é tão grande. Em matemática, você pode encontrar contra-exemplos, em comparação com os quais isso será muito pequeno ".

E embora você não consiga convidar ^4.000 para sua casa de campo, o trabalho de Shitov não rejeita a existência de contra-exemplos de tamanho muito menor. Mas agora que os matemáticos sabem que a hipótese de Hedetniemi é falsa, a questão natural será exatamente como ela é falsa: como menos cores podem ser necessárias para colorir um produto tensorial em comparação com seus gráficos constituintes e qual é o número mínimo de nós e arestas que esses contra-exemplos podem ter?

Enquanto isso, Elon disse que o novo trabalho contém uma lição importante para todos os matemáticos: "Às vezes, a razão pela qual uma hipótese é tão difícil de provar é que ela é falsa".