Get best of the week

A prova de arco-íris demonstra a presença de componentes padrão em gráficos

Os matemáticos provaram que cópias de gráficos menores sempre podem cobrir idealmente gráficos maiores.



Em 8 de janeiro, três matemáticos publicaram uma prova de um teorema da combinatória formulado há quase 60 anos, conhecido como hipótese de Ringel. Grosso modo, ela prevê que gráficos - construções que consistem em pontos e linhas - podem ser idealmente dobrados a partir de peças idênticas de tamanho menor.

Os matemáticos aceitaram com entusiasmo a confirmação dessa hipótese.

"A boa sorte é que este trabalho resolva uma hipótese muito antiga que não poderia ser verificada por outros métodos", disse Gil Kalai , matemático da Universidade Hebraica de Jerusalém, não relacionado a este trabalho.

A hipótese de Ringel prevê que tipos especiais de gráficos complexos - com trilhões de vértices e arestas - podem ser "lado a lado", ou seja, cobrir completamente, com cópias separadas de gráficos menores de um determinado tipo. Do ponto de vista conceitual, essa pergunta é semelhante à seguinte: posso ladrilhar completamente o chão da cozinha com as mesmas cópias de qualquer ladrilho da loja? Na vida real, a maioria dos tipos de ladrilhos não é adequada para a sua cozinha - para cobrir completamente o chão, você precisa combinar suas diferentes formas. Mas no mundo da teoria dos grafos, a hipótese prediz que você sempre pode colocar um gráfico em mosaico.

E na cozinha e nos gráficos, é importante onde exatamente você coloca o primeiro ladrilho. O novo trabalho destaca essa questão crucial - e de maneira que seja surpreendente e surpreendentemente intuitiva.

Floresta com árvores


Na combinatória, os matemáticos estudam como os vértices (pontos) e as arestas (linhas) se combinam para formar objetos mais complexos chamados gráficos. Você pode fazer muitas perguntas sobre gráficos. Um dos mais básicos: em que casos os gráficos menores e mais simples são idealmente incorporados nos maiores e mais complexos?

"Você tem um conjunto de peças de quebra-cabeça e não sabe se pode montá-las a partir dessas peças", disse Jacob Fox, da Universidade de Stanford.

Em 1963, o matemático alemão Gerhard RingelEle fez uma pergunta simples, mas mais ampla, desse tipo. Vamos começar, ele disse, com qualquer número ímpar de vértices maior que 3 (para a plausibilidade da hipótese, o número de vértices deve ser ímpar, como veremos mais adiante). Conecte-os com arestas para que cada vértice se conecte a todos os outros. Então obtemos um objeto chamado gráfico completo .



Imagine um gráfico de um tipo diferente. Pode ser uma maneira simples - várias arestas conectadas em uma linha. Ou um caminho com costelas ramificadas. Ramos podem ser adicionados a outros ramos. Você pode criar um gráfico arbitrariamente complexo, evitando apenas loops fechados. Esses gráficos são chamados de árvores.



A pergunta de Ringel refere-se à relação de gráficos e árvores completos. Ele disse: primeiro, imagine um gráfico completo de 2n + 1 vértices (um número ímpar). Imagine qualquer árvore que consiste em n + 1 vértices - e essas árvores podem ser muito diferentes.

Agora pegue uma dessas árvores e coloque-a de forma que cada borda da árvore coincida com a borda do gráfico completo. Em seguida, colocamos outra cópia da mesma árvore em outra parte do gráfico completo.

Ringel previu que, agindo dessa maneira, e começando no lugar certo, você poderia idealmente unir todo o gráfico completo. Isso significa que cada borda do gráfico completo será coberta pela borda da árvore e as cópias das árvores não se sobreporão.



“Eu posso tirar cópias da árvore. Coloquei uma cópia no gráfico completo. Ela cobre algumas costelas. Então repito o processo. A hipótese sugere que isso pode cobrir tudo ”, disse Benny Sudakov, do Instituto Federal Suíço de Tecnologia, co-autor da nova evidência, junto com Richard Montgomery, da Universidade de Birmingham, e Alexei Pokrovsky, do Birkbeck College da Universidade de Londres.

Finalmente, Ringel previu que o gráfico pode ser lado a lado, independentemente de qual das muitas opções de árvore você usará. Tal afirmação pode parecer muito geral. A conjectura de Ringel se aplica a gráficos completos com 11 vértices e gráficos completos com 11 trilhões + 1 vértices. E quanto maior o gráfico completo, maior será o número de árvores possíveis que podem ser desenhadas para n + 1 vértices. Como cada um deles pode criar uma ponte ideal para o gráfico completo correspondente?

No entanto, havia razões para acreditar que a hipótese de Ringel poderia ser verdadeira. A primeira confirmação foi de que a aritmética combinatória mais simples não excluiu essa opção: o número de arestas em um gráfico completo com 2n + 1 vértices sempre pode ser completamente dividido pelo número de arestas em uma árvore com n + 1 vértices.

"O fato de o número de arestas de um gráfico completo ser dividido pelo número de arestas de uma árvore é muito importante", disse Montgomery.

Os matemáticos rapidamente encontraram mais evidências da plausibilidade da hipótese, o que desencadeou uma cadeia de descobertas que eventualmente levaram à prova.

Coloque e vire


Uma das árvores mais simples é uma estrela: um pico central com bordas emanando dele. Mas difere da imagem típica de uma estrela, porque as bordas não precisam ser distribuídas uniformemente pelo topo. Todos eles só precisam vir de um lugar e não devem se cruzar em lugar algum, exceto no pico central. Se você quiser provar a exatidão da hipótese de Ringel, uma árvore em forma de estrela será um ponto de partida natural.



E, é claro, os matemáticos descobriram rapidamente que uma estrela de n + 1 vértices sempre abre perfeitamente um gráfico completo com 2n + 1 vértices. Esse fato é interessante por si só, mas sua prova fez os matemáticos pensarem mais.

Veja um exemplo simples. Vamos começar com 11 picos. Nós os colocamos em um círculo e conectamos cada vértice a todos os outros, obtendo um gráfico completo.



Agora considere a estrela correspondente a ela: o ponto central com cinco arestas emanando dela.



Agora colocamos a estrela de modo que o vértice central coincida com um dos vértices do gráfico completo. Abordaremos várias arestas, mas não todas. Agora mova a estrela um vértice, como se estivesse girando o botão da bússola. Obtemos uma nova cópia da estrela sobreposta a um conjunto completamente diferente de arestas do gráfico completo.

Giraremos a estrela ainda mais. Quando voltarmos ao ponto de partida, pavimentaremos todo o gráfico completo sem sobrepor estrelas - exatamente como previu Ringel.



"Sabemos que uma hipótese não pode ser descartada imediatamente, pelo menos se pegarmos uma árvore na forma de uma estrela", disse Sudakov. "Além disso, podemos até demonstrar isso de maneira muito bonita: desenhe um gráfico em um círculo, troque uma estrela, obtenha novas cópias e substitua o gráfico inteiro".

Logo depois que Ringel apresentou sua hipótese, o matemático eslovaco-canadense Anton Kotzig usou esse exemplo para uma previsão ainda mais ousada do que a de Ringel. Ringel disse que todo gráfico completo com um vértice 2n + 1 pode ser lado a lado com qualquer árvore com um vértice n + 1, Kotzig sugeriu que ele pode ser lado a lado exatamente da mesma maneira que com uma estrela: colocando a árvore em um gráfico completo e simplesmente girando-o.

A ideia parecia irrealista. A estrela é simétrica, portanto, não importa como colocá-la. A maioria das árvores está torta. Eles precisam ser colocados de uma maneira muito específica para que o método de rotação funcione.

"A estrela era uma estrutura simples que pode ser colocada manualmente, mas se você tem uma árvore que se espalha em suas mãos com vários ramos de diferentes comprimentos, é difícil imaginar como ela pode ser cuidadosamente colocada", disse Pokrovsky.

Para resolver a hipótese de Ringel usando o método rotativo de Kotsig, os matemáticos precisavam descobrir como colocar a primeira cópia da árvore para que os matagais intransitáveis ​​não saíssem. Felizmente, eles encontraram uma solução colorida.

A coloração do arco-íris geralmente facilita a vida. Ajuda a organizar um calendário ou a distinguir rapidamente um recipiente de alimento de outro em uma família numerosa. Acontece que essa também pode ser uma maneira eficaz de descobrir como colocar corretamente a primeira árvore dentro de um gráfico completo.

Imagine novamente um gráfico completo com 11 vértices dispostos em círculo. Marque suas bordas com códigos de cores de acordo com uma regra simples que leva em consideração a distância entre dois vértices.

Essa distância é determinada pelo número de etapas que devem ser executadas para ir de um vértice para outro em um círculo (sem cortar o caminho dentro do círculo). Obviamente, em um círculo, você sempre pode seguir duas direções, portanto definiremos a distância como o caminho mais curto entre dois picos. Se estes são vértices vizinhos, a distância entre eles será 1, e não 10. Se forem separados por um vértice, a distância será 2.



Agora, colorimos as bordas do gráfico de acordo com a distância. Pintamos todas as arestas que conectam os picos localizados a uma distância de 1 em uma cor - por exemplo, azul. Pintamos todas as arestas que conectam os picos localizados a uma distância de duas unidades na outra - por exemplo, amarelo.

Continuamos a colorir o gráfico para que todas as arestas que conectam os vértices que estão na mesma distância tenham a mesma cor. Distâncias diferentes serão codificadas em cores diferentes. Para um gráfico completo com vértices 2n + 1, você precisa de n cores para isso. O resultado é uma imagem bonita e útil.



Logo após Ringel e Kotzig apresentarem suas hipóteses, Kotzig percebeu que colorir seu gráfico completo poderia ser um guia para colocar uma árvore nele.

A idéia é organizar a árvore para que cubra uma borda de cada cor e não cubra nenhuma cor duas vezes. Os matemáticos chamam esse arranjo de réplica do arco-íris de uma árvore. Como a coloração requer n cores e uma árvore de n + 1 vértices terá n arestas, sabemos imediatamente que, com alta probabilidade, uma cópia do arco-íris pode ser encontrada.



No final da década de 1960, os matemáticos entendiam que uma cópia do arco-íris de uma árvore tinha uma propriedade especial: denota apenas a posição a partir da qual você pode conectar o gráfico inteiro girando a árvore.

"Se você fizer uma cópia do arco-íris, tudo funcionará", disse Pokrovsky.

Depois disso, os matemáticos já sabiam que podiam provar a hipótese de Ringel, provando que todo gráfico completo com vértices 2n + 1 continha uma cópia do arco-íris de qualquer árvore com vértices n + 1. E se uma cópia do arco-íris sempre existir, você poderá sempre conectar o gráfico.

No entanto, provar que algo sempre existe é difícil. Para isso, os matemáticos teriam que mostrar que gráficos completos simplesmente não podem deixar de conter cópias de árvores em arco-íris. Demorou mais de 40 anos, mas é exatamente isso que Sudakov e seus co-autores alcançaram em um novo trabalho.

Embalagem perfeita


Suponha que você tenha recebido um gráfico completo com 11 vértices e uma árvore com seis. O gráfico completo é pintado em cinco cores diferentes. A árvore tem cinco arestas. Sua tarefa é encontrar uma cópia em arco-íris da árvore dentro do gráfico completo.

Você pode simplesmente colocar as bordas da árvore no gráfico, por sua vez. O primeiro é fácil de colocar: você pode escolher qualquer borda de qualquer cor para ele. O segundo será um pouco mais difícil. Ele pode estar em quase qualquer lugar, exceto pela nervura da mesma cor que a recém-coberta. E quanto mais você coloca as bordas da árvore, mais difícil a tarefa se torna. Tendo atingido a última nervura, você perderá completamente a escolha da cor - haverá apenas uma. Resta esperar que você tenha planejado tudo com bastante antecedência.

Essa ideia de que a tarefa de encontrar uma cópia do arco-íris de uma árvore se torna mais complicada à medida que você coloca mais e mais arestas da árvore no gráfico era uma parte necessária do método usado por três matemáticos para resolver esse problema. Eles procuraram maneiras de manter a maior flexibilidade possível no final do processo.

Desde o início, eles sabiam que seria fácil encontrar cópias em arco-íris de árvores muito simples - árvores que pareciam um caminho longo, sem galhos ou com um pequeno número delas. O mais difícil foi posicionar corretamente as árvores com muitas arestas convergindo em um ponto - como estrelas, apenas com uma forma mais desigual e irregular. Colocá-los é como empurrar o carrinho para dentro de um porta-malas meio cheio.

"A dificuldade começa quando você tenta preencher um gráfico completo com coisas estranhas que parecem estrelas", disse Pokrovsky.

Qualquer pessoa que enche o porta-malas sabe que você sempre precisa começar com os objetos mais complexos - malas grandes e coisas inflexíveis, como bicicletas. Jaquetas sempre podem ser empurradas. E os matemáticos adotaram essa filosofia.

Imagine uma árvore com 11 arestas. Seis deles convergem em um ponto central. Quase todos os outros formam uma única forma, distante da principal.



A parte mais difícil de colocar é a parte da árvore que consiste em um pico com seis arestas. Portanto, os matemáticos o separaram do resto da árvore e o colocaram primeiro para anexar esta parte mais tarde - como se você decidisse desmontar a cama antes de arrastá-la para o segundo andar e remontá-la na sala desejada. Eles nem sequer colocaram essa parte da estrela no gráfico uma vez - encontraram vários locais adequados para colocar suas cópias dentro do gráfico completo.

E então eles selecionaram aleatoriamente uma cópia. Ao fazer isso, eles garantiram que o espaço livre restante no gráfico também fosse aleatório - ou seja, com uma distribuição aproximadamente igual de arestas de cores diferentes. Foi nesse lugar que eles precisaram colocar o resto da árvore - o caminho que eles primeiro colocaram de lado.

Eles enfrentaram restrições ao escolher opções para sua veiculação. O caminho deve estar conectado à estrela - a parte da árvore que eles já colocaram e também teve que cobrir cores que não eram cobertas anteriormente pela estrela com a qual ela se conecta.

Mas os matemáticos deixaram opções para si. Eles poderiam conectar o caminho a quase todas as várias cópias da estrela. O que é ainda melhor, como o espaço ao redor da estrela era aleatório, eles tinham opções para escolher cores diferentes para cobrir com o resto da árvore.

"No final da construção de árvores, quando a situação se torna complicada, não tenho mais uma cor obrigatória, mas uma pequena escolha", disse Montgomery.

Três matemáticos completam sua prova com um argumento da teoria da probabilidade. Eles mostraram que depois de incorporar as partes mais complexas das árvores, desde que o espaço restante na coluna inteira fosse essencialmente aleatório, você sempre pode encontrar uma maneira de construir no restante das árvores para obter uma cópia do arco-íris.

"Agora você pode forçar o que adia desde o início, como se quisesse absorver o que restava da árvore e obter uma coloração completa do arco-íris", disse Noga Alon, da Universidade de Princeton.

Os matemáticos não descreveram a maneira exata de encontrar uma cópia do arco-íris para cada árvore com n + 1 vértices em cada gráfico completo com 2n + 1 vértices. No entanto, eles provaram que uma cópia do arco-íris deve estar nela.

E se uma cópia do arco-íris sempre existir, você poderá fazer a ponte do gráfico com o método previsto por Ringel. Assim, sua hipótese é verdadeira.

A prova também fornece novas ferramentas para resolver problemas semelhantes não resolvidos na combinatória - por exemplo, o problema da "marcação graciosa", que prevê que um gráfico completo pode ser lado a lado mesmo em condições mais rigorosas, segundo as quais as árvores precisam ser colocadas com mais precisão.

"Isso mostra que os métodos que as pessoas pensam há muito tempo realmente têm um grande potencial", afirmou Fox. "Se você aplicá-las corretamente, poderá resolver problemas que antes pareciam inexpugnáveis."

More articles:


All Articles