É possível decompor um grafo qualquer em subgrafos aresta-disjuntos com uma requerida pro-
priedade? E, se for possível, qual é o menor limitante superior que garante que esse conjunto de
subgrafos aresta-disjuntos exista para todo grafo? Muitos problemas clássicos em combinatória ex-
tremal seguem este formato de questão, dentre os quais estudaremos o seguinte: É possível decompor
um grafo em circuitos aresta-disjuntos?
O caso particular em que buscamos decompor um grafo em circuitos tem uma longa história,
remontando ao século XVIII e ao resultado de Euler sobre a existência de circuitos eulerianos. O
resultado de Euler implica imediatamente que qualquer grafo cujos vértices tem grau par (ou seja,
qualquer grafo euleriano) tem uma decomposição em O(n) circuitos aresta-disjuntos.
Outro resultado de decomposição em circuitos muito clássico é devido a Walecki [3] de 1892,
que mostrou ser possível decompor qualquer grafo completo com um número ímpar de vértices
em (n − 1)/2 circuitos Hamiltonianos. Essa decomposição utiliza a menor quantidade de circuitos
possível.
Isso levanta a seguinte questão levantada por Erdős-Gallai [5] nos anos 1960, que é um dos
principais problemas em aberto sobre decomposições de grafos:
Conjectura 1. Todo grafo de n vértices pode ser decomposto em O(n) circuitos e arestas
Por quase 50 anos, o limite mais conhecido no caso geral da conjectura de Erdős-Gallai (como
observado por Erdős e Gallai) veio de um argumento simples envolvendo a remoção iterativa de
um ciclo mais longo, o que mostra que um grafo de n vértices sempre pode ser decomposto em
O(n log n) ciclos e arestas. Em 2014, Fox, Conlon e Sudakov [2] fizeram um grande avanço nesse
problema, mostrando que tal decomposição com apenas O(n log log n) ciclos e arestas sempre existe.
O resultado mais recente, de Bucić e Montgomery [4], mostra que é possível fazer essa decomposição
em O(n log∗ n) circuitos e arestas disjuntos, em que log∗ é a função logaritmo iterado.
Inicialmente, o trabalho se propõe a ser uma resenha do resultado mais recente em cima do problema da decomposição das arestas de um grafo em circuitos e arestas disjuntos. Por meio deste, o aluno que o aluno aprenda técnicas clássicas e recentes de combinatória extremal e probabilística. Em segunda instância, conforme o andamento do projeto, o trabalho poderá ser uma resenha do progresso em direção à prova da Conjectura de Erdős-Gallai. Com isso, o trabalho abordaria desde os argumentos mais elementares em relação à conjectura quanto os mais recentes. Podendo, ainda, complementar com indícios e intuições do porquê se acredita que tal conjectura é verdadeira.
Cronograma
1. R. Aharoni and P. Haxell, Hall’s theorem for hypergraphs, J. Graph Theory, 35(2):83–88 (2000).
2. J. Fox, D. Conlon and B. Sudakov, Cycle packing, Random Struct. Algorithms, 45(4):608–626 (2014).
3. É. Lucas, Récréations mathématiques, vol. 2, Gauthier-Villars, 1883.
4. R. Montgomery, M. Bucić, Towards the Erdős-Gallai cycle decomposition conjecture, 2023.
5. A. W. Goodman, P. Erdős and L. Pósa, The representation of a graph by set intersections, (1966)