Teorema de Turán.

Paul Turán (foto abaixo) foi um matemático húngaro especialista em teoria dos números e combinatória. Neste post, veremos um dos resultados que iniciou a teoria extremal dos grafos: o Teorema de Turán.

Seja $G$ um grafo simples com $n$ vértices. Qual é o maior números de aresta que $G$ pode ter de modo que não tenhamos em $G$ uma $p$-clique?

Relação de Euler (prova com grafos).

Num post anterior, Sólidos Platônicos, usamos a famosa relação de Euler para poliedros, que é dada por:

$$ V - E + F = 2, $$

onde $V$ é o número de vértices de um poliedro convexo, $E$ é o número de arestas e $F$ é o número de faces.

A relação de Euler para poliedros é equivalente a relação de Euler para grafos planares conexos. Afinal, existe uma maneira natural de levar uma instância do primeiro problema para uma instância do segundo: sobre uma face do poliedro, "abra" o poliedro de modo que todas as faces esteja sobre um plano.  Iremos prová-la para grafos planares conexos.

Dado um grafo planar, isto é, um grafo desenhado sobre o plano e sem interseções entre arestas, chamamos de faces internas aquelas regiões internas limitadas pelas arestas do grafo que formam um ciclo. A face externa é a (única) região ilimitada. No que segue, consideramos como face tanto a interna quanto a externa.

Teorema (da relação de Euler). Se $G$ é um grafo planar conexo com $n$ vértices, $m$ arestas e $f$ faces, então vale que $$n - m + f = 2.$$

Conjectura de Erdös-Faber-Lovász

Lendo o texto do Béla Bollobás (veja aqui) e parei para pensar em qual problema seria um "sonho" para mim, isto é, um grande problema que eu amaria resolver. Depois de um tempo de reflexão, cheguei a escolha de uma conjectura em Teoria dos Grafos:

Conjectura de Erdös-Faber-Lovász. Se $k$ grafos completos, cada um tendo exatamente $k$ vértices, têm a propriedade de que cada par de grafos compartilham no máximo um vértice, então a união desses grafos pode ser colorida com $k$ cores.

Esta conjectura é de 1972 e pode ser encontrada num artigo do Erdös onde ele fala quais são os problemas que ele gostaria de ver resolvido (veja aqui o artigo).

O seu enunciado não é difícil de entender e esta conjectura tem tentado muitos combinatoristas. E este foi um dos motivos pela qual me interessei por esta conjectura.

A primeira vez que a vi foi num seminário do grupo de pesquisa da qual faço parte, o ParGO (link). Lá, vi a conjectura sendo relacionada com algo sobre b-coloração (um tema para um futuro post), do qual não lembro muito bem como isto era feito.

Confesso que já tentei resolver a conjectura algumas vezes (mais precisamente, cinco vezes). Infelizmente, meus conhecimentos em teoria dos grafos é ainda muito elementar, e o que pude aplicar na conjectura não me retornou nada muito surpreendente (mas ainda sim obtive algumas conclusões).

Cada vez que tentei resolvê-la, esta conjectura me encantava ainda mais. Sim, pois quando eu aprendia algum método novo (como o método probabilístico e o Lema da Regularidade), logo tentava aplicar na conjectura. O interessante é que tais ferramentas eram aplicáveis, em sua maioria, mas o que eu conseguia concluir não era o suficiente para provar a conjectura. É como se a conjectura fosse a prova de métodos fodásticos. Ou até mesmo, eu ainda não sou capaz de aplicá-los de maneira eficiente. Mas também acredito que muitos já devem ter tentado aplicá-los a esta conjectura.

No fim, tentar resolver a conjectura foi um bom exercício para mim. Pretendo mantê-la como um "sonho", e seguindo os conselhos do Bollobás, estudando problemas mais ao meu nível atual.

Grafos: definições, nomenclaturas e notações

Neste texto, irei dar algumas noções elementares sobre grafos baseadas no livro Graph Theory [1].

Um grafo $G$ é um par ordenado $G = (V,E)$, onde $V$ é um conjunto qualquer e $E$ é uma coleção de pares de elementos de $V$, i.e., $E = \{\; \{x,y\} \; | \; x,y \in V, x\neq y\}$. Os elementos de $V$ são chamados de vértices do grafo e os elementos de $E$ são chamados de arestas. Uma aresta $e$, formalmente, é um par $e = \{x,y\}$, onde $x,y$ são vértices do grafo, mas por comodidade iremos representar a aresta $e$ apenas por $xy$, de modo que não haverá confusão ao identificarmos $e=xy=yx$.

Segundo a nossa definição de grafo, não há possibilidade de duas arestas distintas conectarem o mesmo par de vértice. Também não há chance alguma de existir uma aresta que conecte um vértice $x$ a ele mesmo (arestas deste tipo recebem o nome de laços ou loops). Assim, segundo a definição de alguns livros, o nosso grafo é um grafo simples. Mas como este é principal tipo de grafo que nos interessa por enquanto, não iremos nos preocupar em dizer que os nossos grafos são simples. Existem outros tipos de grafos tão interessante quanto os simples: grafos orientados, múltiplos, com fluxos, labelados, entre outros (ver [1]). Outra coisa, não esteremos, por enquanto, interessados em grafo cujo o conjunto dos vértices é infinito. Logo, assumiremos desde já que $|V| < \infty$. Consequentemente, o conjunto das arestas é finito também.

É muito comum e conveniente representar um grafo $G$ por um desenho sobre um plano onde os vértices são representados por pontos no plano e arestas que conectam dois vértices $x$ e $y$ são representados por linhas (retas ou curvilíneas) que contêm os pontos que representam os vértices $x$ e $y$ como extremidades. Claramente, um grafo pode ser desenhado de inúmeras maneiras distintas, logo não devemos nos apegar ao desenho do grafo, mas utilizá-lo para visualizar rapidamente algumas afirmações. Muitas vezes iremos verificar algo através de um desenho, mas isso deve ser feito de modo que fique claro que esta verificação é independente da maneira que desenhamos.

Primeira postagem e o primeiro teorema sobre grafos.

Esta é a primeira postagem do blog Tiorema! Pretendo, neste espaço, postar algumas coisitas matemáticas que acho interessante. Tem tanta coisa que nem sei bem por onde começar. Como gosto muito de combinatória, decidi começar por um dos primeiros teoremas em Teoria dos Grafos: o Teorema de Euler. O leitor que não conhece ainda a Teoria dos Grafos ou que não está muito familiarizado com as definições e notações poderá ler um post que preparei com as principais noções que usarei ao falar de grafos [link], apesar de que neste post a principal definição será feita logo no próximo parágrafo de modo que um conhecimento básico de grafos já é suficiente para uma boa leitura deste texto.

Dado um grafo $G=(V,E)$, um passeio (de tamanho $k$) em $G$ é uma sequência alternada de vértices e arestas

$$P = v_0 e_1 v_1 e_2 v_2 \ldots  v_{k-1} e_{k} v_k, $$

com $v_0, v_i\in V$ e $e_i = \{v_{i-1},v_{i}\} \in E$, pra todo $1 \leq i \leq n$. Os vértices $v_i$ não precisam todos serem distintos; quando são, $P$ é chamado de caminho. Quando as aresta $e_i$ são todas distintas, dizemos que $P$ é uma trilha. Quando $v_0 = v_k$, dizemos que $P$ é um passeio fechado; se $P$ for uma trilha, dizemos que ele é uma trilha fechada. Uma trilha fechada cujos os vértices $v_i$, para $i \geq 1$, são distintos é chamado de ciclo.

Uma trilha fechada $P$ é um circuito Euleriano do grafo $G$ se todas as arestas de $G$ estiverem em $P$. Em outras palavras, queremos percorrer todo o grafo através das arestas começando de um vértice e voltando, no fim, para o mesmo vértice, mas sem passar pela mesma aresta duas vezes. Um grafo que contém um circuito Euleriano é dito ser um grafo Euleriano.

Euler se interessou por esse tipo de passeio quando se questionou se era possível visitar todas as quatro regiões da cidade Königsberg (território da Prússia até 1945, atual Kaliningrado). Estas quatro regiões eram conectadas por sete pontes (ver figura abaixo). Mas Euler não queria visitá-las de qualquer maneira, ele queria passar por cada ponte exatamente um vez.