===Relembrando algumas definições=== Grafo simples: não há duas arestas diferentes entre dois vértices e nenhuma aresta tem as suas extremidades no mesmo vértice. Grafo $n$-regular: todos os vértices tem grau $n$. Subgrafo gerador: $H$ é grafo gerador de $G$ se $V(H) = V(G)$. $n$-fator: um subgrafo gerador $n$-regular. ===Seria legal se fosse verdade=== Imagina se para $k$ inteiro positivo existisse um $r$ suficientemente grande tal que todo grafo $r$-regular possui um subgrafo gerador $k$-regular. Seria legal, né? Será que conseguimos mostrar isso? \\ \\ \\ Não. ===Motivação=== Teorema de Petersen: Para todo $n$ inteiro positivo par, temos que todo grafo $n$-regular possui $\frac{n}{2}$ $2$-fatores sem arestas em comum. Pelo Teorema de Petersen, conseguimos mostrar que para todo $r, k$ inteiros positivos pares tal que $r > k$, todo grafo $r$-regular tem um subgrafo gerador $k$-regular: Como $r > k$, $\frac{r}{2} > \frac{k}{2}$, logo, se temos $\frac{n}{2}$ $2$-fatores, em particular temos $\frac{k}{2}$ $2$-fatores. Como esses $2$-fatores não tem arestas em comum, se unirmos $\frac{k}{2}$ deles teremos um subgrafo gerador $k$-regular! Mas isso vale somente para $r, k$ pares, não conseguimos mostrar para o caso em que um dos dois (ou ambos) são ímpares. Também conseguimos mostrar que para todo $k$ inteiro positivo e para todo $r$ inteiro positivo suficientemente grande, todo grafo $G$ $r$-regular contém um subgrafo $H$ $k$-regular. Mas não conseguimos pedir que $H$ seja gerador. ===A ideia=== Dado um grafo $G$, diremos que um subgrafo $H$ é $\epsilon$-gerador se $V(H) \geq (1 - \epsilon)V(G)$. Diremos que $H$ é "quase gerador" se para todo $\epsilon > 0$ tivermos que $V(H) \geq (1 - \epsilon)V(G)$. A ideia é mostrar que para todo $k$ inteiro positivo, existe um $r$ suficientemente grande tal que todo grafo $G$ $r$-regular contém um subgrafo $k$-regular "quase gerador", ou seja, que contém quase todos os vértices de $G$. ===Conjectura=== Para todo $\epsilon > 0$ todo $k$ inteiro positivo existe $r_{0} = r_{0} (\epsilon, k)$ tal que todo grafo $G$ simples $r$-regular com $r \geq r_{0}$ tem um subgrafo $H$ $k$-regular com $|V(H)| \geq (1 - \epsilon)|V(G)|$. ===O que já temos=== O resultado foi provado para $k=1$ e $k=2$, mas permanece aberto para $k \geq 3$. Iremos demonstrar os casos $k = 1$ e $k = 2$, abordando algumas definições e teoremas necessários para essas demonstrações. ===Coloração de arestas=== Uma coloroção sobre as arestas é uma forma de colorir as arestas de um grafo de forma que duas arestas com mesma extremidade não tem mesma cor. ===Teorema de Vizing=== Para todo grafo simples não direcionado existe uma coloração de arestas com no máximo $\Delta + 1$ cores. Note também que são necessárias pelo menos $\Delta$ cores. ===Caso $k = 1$=== Queremos mostrar que, para todo $\epsilon > 0$ existe $r_{0} = r_{0} (\epsilon)$ tal que todo grafo $G$ simples $r$-regular com $r \geq r_{0}$ tem um subgrafo $H$ $1$-regular com $|V(H)| \geq (1 - \epsilon)|V(G)|$. Como o grafo $G$ é $r$-regular, $\Delta = r$. Logo, podemos particionar $G$ em $r + 1$ subgrafos (nos baseando na coloração das arestas). Vamos olhar para o maior desses subgrafos (com relação ao número de arestas). Primeiro, note que ele é $1$-regular: como duas arestas adjacentes não podem ter mesma coloração, quando consideramos o subgrafo apenas das arestas de uma certa cor, temos apenas arestas isoladas (ou seja, grafos $1$-regulares). Já temos nosso subgrafo $1$-regular, falta mostrar que ele cobre quase todos os vértices. A soma dos graus de todos os vértices de $G$ é $r|V(G)| = 2E(g)$. Temos então que $r|V(G)|/2 = E(G)$. Como dividimos essas arestas em $r + 1$ partições, a maior delas tem, pelo menos, $r|V(G)|/2(r+1)$ arestas, tendo, então, pelo menos $r|V(G)|/(r+1)$ vértices. Como $r/(r+1)$ tende a $1$ quando $r$ tende a infinito, para todo $\epsilon$ positivo existe um $r$ suficientemente grande tal que esse subgrafo cobre quase todos os vértice de $V(G)$. ===Permanente=== Dada uma matriz $n * n$, o permanente dessa matriz é $\sum_{\sigma \in S_{n}} \prod_{i=1}^{n} a_{i, \sigma(i)}$. Na prática, o permanente de uma matriz é seu determinante com todos os sinais positivos. Essa ferramenta tem algumas aplicações em grafos. Em coberturas por ciclos, podemos olhar para uma matriz quadrada como a matriz de adjacências de um grafo direcionado com peso. Definindo o peso de uma cobertura por ciclos como o produto dos pesos dos arcos de cada ciclo, o permanente de $A$ é a soma dos pesos de todas as coberturas por ciclos do grafo. Algo semelhante pode ser feito com pareamentos perfeitos: uma matriz $n * n$ pode ser vista como um grafo bipartido com $n$ vértices de cada lado, onde cada entrada da matriz representa o peso da aresta correspondente. Definindo o peso do pareamento como o produto dos pesos de suas arestas, $perm(A)$ é a soma dos pesos de todos os pareamentos perfeitos dos grafos. ===As conjecturas que utilizaremos=== Conjectura de Minc: $perm(A) \leq \prod_{i=1}^{n} (r_{i}!)^{1/r_{i}}$, onde $r_{i}$ é a soma das entradas da $i$-ésima linha. Conjectura de van der Waerden: dada uma matriz $n * n$ onde a soma de cada linha e cada coluna é $r$, o permanente desse matriz é, pelo menos, $(r/n)^{n}n!$. Além disso, se todas as entradas são inteiras, o permanente é pelo menos $((r-1)^{r-1}/r^{r-2})^{n}$. ===Caso $k = 2$=== Queremos mostrar que, para todo $\epsilon > 0$ \pause existe $r_{0} = r_{0} (\epsilon)$ \pause tal que todo grafo $G$ simples $r$-regular com $r \geq r_{0}$ \pause tem um subgrafo $H$ $2$-regular com $|V(H)| \geq (1 - \epsilon)|V(G)|$. Como é possível imaginar pelas conjecturas que utilizaremos, o caso $k = 2$ envolve algumas contas extensas, além de utilizar ferramentas que não são abordadas no curso e com as quais não estamos habituados. Por isso, não seria proveitoso estudá-la à fundo. Mas ela pode ser encontrada em Problems and results in Extremal Combinatorics, Part I - Noga Alon (páginas 4--5). ===Curiosidades: mais algumas coisas nessa linha=== Teorema: Para todo inteiro $g \geq 3$ e todo real $\epsilon > 0$ existe $r_{0} = (\epsilon, g)$ tal que para todo $r > r_{0}$ todo grafo $G$ $r$-regular contém um subgrafo $H$ $2$-regular tal que $|V(H)| \geq (1 - \epsilon)|V(G)|$ tal que o número de vértices em cada componente conexa de $H$ é maior ou igual a $g$. Conjectura: Para todo grafo $H$ e todo real $\epsilon > 0$, existe $r_{0} = r_{0}(H, \epsilon)$ tal que, dado $r > r_{0}$, todo grafo $G$ $r$-regular tem um subgrafo com pelo menos $(1 - \epsilon)|V(G)|$ vértices que é uma coleção de grafos dois a dois vértice disjuntos tal que cada um desses grafos é uma cópia topológica de $H$. Já foi mostrado para grafos acíclicos, para ciclos (pelo teorema anterior) e para grafos com somente um ciclo. Ainda está em aberto para grafos mais complicados.