7. Subestruturas em grafos densos

• Este capítulo estuda algumas condições suficientes para que um grafo tenha um subgrafo completo ou um subgrafo multipartido completo. Essas condições exigem, em particular, que o grafo seja denso.

  Exemplo:  Se  ‖G‖ > ¼ |G|²  então  K³ é subgrafo de G.

• Um grafo é denso se seu número de arestas for da ordem de n².  (Na verdade, o conceito só faz sentido quando aplicado a uma família de grafos com número arbitrariamente grande de vértices. Grafos de uma tal família são densos se ‖G‖ = Ω(|G|²) para G na família.)

  Exemplos: Os grafos completos são densos. O conjunto de todos os grafos com n vértices e mais que (ⁿ₂) − 100n arestas são densos. As florestas não são densas.

7.1  Subgrafos

• Teorema 7.1.1 (Turán):  Para todo r > 1,  se  ‖G‖ > t_r–1(|G|)  então  G inclui um K^r.

  Aqui, t_k(n) é o número de arestas do grafo k-partido completo com n vértices cujas partes têm tamanhos entre ⌊n/k⌋ e ⌈n/k⌉.  Não tenho uma fórmula fechada para t_k,  mas não é difícil verificar que  n²(k−1) / 2k − k/8  ≤  t_k(n)  ≤  n²(k−1) / 2k.

• Generalização:  Dado um grafo H, todo grafo G com n vértices e mais que  ex(n, H)  arestas inclui uma cópia de H.  O número  ex(n, H)  é chamado número extremo para n e H.  Exemplo:  ex(n, K^r) = t_r–1(n).
• Surpreendente:  O quociente  ex(n, H) / (ⁿ₂)  tem limite quando n tende a infinito.  (O denominador é o número de arestas de um grafo completo com n vértices.)  Mais surpresa:  o limite vale  (chi(H) − 2) / (chi(H) − 1),  onde chi é o número cromático.   A prova depende da seguinte generalização do teorema 7.1.1:
• Teorema 7.1.2 (Erdös & Stone):  Para todo r ≥ 2, todo s ≥ 1, e todo ε > 0,  existe n tal que  se  |G| ≥ n  e  ‖G‖ ≥ t_r–1(|G|) + ε|G|²  então  G inclui K_s^r.

  Aqui, K_s^r é o grafo r-partido completo com partes de tamanho s,  ou seja, K_{s, .. , s} com r repetições de s  (esse grafo inclui um enorme número de cópias de K^r).  

  Boa maneira de provar 7.1.2:  use o lema da regularidade de Szemerédi.

7.2  Lema da regularidade

• Lema 7.2.1 (Szemerédi):  Para todo ε > 0 e todo m ≥ 1, existe M tal que  se  |G| ≥ m  então  G tem partição ε-regular  {V₀, V₁, … , V_k}  com m ≤ k ≤ M.
• Uma partição  {V₀,V₁, … ,V_k}  de V é ε-regular se
  1. |V₀| ≤ ε|V|
  2. |V₁| = … = |V_k|
  3. no máximo εk² dos pares (V_i, V_j) com i ≠ 0 e j ≠ 0 não são ε-regulares.

  Um par (A, B) de partes mutuamente disjuntas de V é ε-regular se  |d(X,Y) − d(A,B)| ≤ ε para toda parte X de A com pelo menos ε|A| elementos e toda parte Y de B com pelo menos ε|B| elementos.  Aqui, d(X,Y)  denota o quociente  |E(X, Y)| / (|X|·|Y|).

• A propósito, Lema 7.3.1:  Suponha que (A,B) é ε-regular e Y é uma parte de B com pelo menos ε|B| elementos. Então mais que (1 − ε)|A| vértices de A têm  (d(A,B) − ε)|Y|  vizinhos em Y.

7.3  Aplicação do lema da regularidade

• Prova do Teorema 7.1.2 (de Erdös & Stone): . . .