11. Grafos aleatórios

Probabilidade discreta

• Digamos que nosso espaço amostral é um conjunto finito U.  Um evento é um subconjunto de U.  Um evento elementar é um elemento de U.
• Uma distribuição de probabilidades discreta é uma função P que associa a cada evento elementar u um número no intervalo [0,1] e satisfaz  ∑_u P(u) = 1,  onde ∑_u denota o somatório sobre todos os u em U.
• Dada uma distribuição de probabilidades P, a probabilidade de um evento A é o número P(A) := ∑_a P(a), onde a soma ∑_a se estende a todos os a em A.  Consequências simples: para quaisquer A e B,
  1. se A ⊆ B então P(A) ≤ P(B);
  2. P(A ∪ B) = P(A) + P(B) − P(A ∩ B).
• Dois eventos A e B são independentes se P(A ∩ B) = P(A) · P(B).
• Uma variável aleatória é uma função, digamos X, de U em R⁺ (ou seja, todos os números reais não negativos).  O valor esperado de uma variável aleatória X é  E(X) := ∑_u P(u) X(u),  com a soma se estendendo a todos os elementos u de U.
• Lema 11.1.4 (Desigualde de Markov):  Se X é uma variável aleatória não negativa e a um número estritamente positivo então   P [X ≥ a]  ≤  E(X) / a.

• Corolário 11.4.1 (Desigualde de Chebyshev):  Para qualquer variável aleatória X e qualquer lambda > 0, temos   P [|X − mü| ≥ lambda]  ≤  sigma² / lambda²,   onde mü := E(X) e sigma² := E((X − mü)²) = E(X²) − mü².

11.1  O conceito de grafo aleatório (= random graph)

• Espaço amostral G(n) :  todos os grafos sobre o conjunto de vértices V = {0, … , n−1}.  Cada elemento de G(n) pode ser entendido como um vetor de 0s e 1s indexado pelo conjunto [V]² de todos os pares não ordenados de elementos de V.  É claro que G(n) tem 2^N grafos, onde N := (ⁿ₂).
• Para qualquer p no intervalo [0,1], seja P a distribuição de probabilidades definida assim: para cada grafo G,   P(G) = p^‖G‖q^N−‖G‖,   onde q := 1 − p  e  N := (ⁿ₂). 

  Observe que a soma das probabilidades sobre todos os grafos vale 1:  ∑_G P(G) = ∑ p^‖G‖q^N−‖G‖ = ∑ (^N_m) p^mq^N−m = (p+q)^N = 1.

  Exemplo: Quando p = ½, temos P(G) = 2^–N, ou seja, todos os 2^N grafos têm a mesma probabilidade.

• O espaço amostral G(n) com essa distribuição P de probabilidades é denotado por G(n, p).
• Para cada e em [V]², seja A_e o evento formado por todos os grafos em G(n, p) em que e é uma aresta.  Proposição: P(A_e) = p.

  Prova:  P(A_e) = ∑_G p^‖G‖q^N–‖G‖.  Como A_e tem exatamente (^N−1_m−1) grafos com m arestas, temos  P(A_e) = ∑_m (^N−1_m−1) p^mq^N−m = p ∑_k (^N−1_k) p^kq^N−1−k = p (p+q)^N−1  = p,  onde a primeira soma tem m variando de 1 a N e a segunda tem k variando de 0 a N − 1. 

• Analogamente, se B_e é o evento formado por todos os grafos em G(n, p) que não têm a aresta e então P(B_e) = q.
• Suponha que e e f são elementos distintos de [V]².  Um cálculo análogo ao que fizemos acima mostra que  P(A_e ∩ A_f) = p² = P(A_e) P(A_f).  Portanto, os eventos A_e e A_f são independentes. 

  Analogamente, A_e e B_f são independentes,  B_e e B_f são independentes,  B_e e A_f são independentes.

• Lema 11.1.2:  Para n ≥ k ≥ 2,  a probabilidade de que um grafo G em G(n, p) tenha k vértices dois a dois independentes é  P [alpha(G) ≥ k] ≤ (ⁿ_k) q^K,  onde K := (^k₂).
• Teorema 11.1.3 (Erdös):  Para todo k ≥ 3, existe um grafo G com |G| ≤ 2^k/2 tal que omega(G) < k e alpha(G) < k.  (Em outras palavras, o número de Ramsey R(k) é maior que 2^k/2.)

  Aqui, omega(G) é o maior r tal que K^r é subgrafo de G.

  Prova:  Se n ≤ 2^k/2 e G está em G(n, ½) então P [omega(G)≥k e alpha(G)≥k] ≤ P [omega(G) ≥ k] + P [alpha(G) ≥ k] < ½ + ½ = 1.

11.2  O método probabilístico

• Idéia do método: Queremos mostrar que existe um grafo com certa propriedade. Digamos que X(G) vale 1 se G tem a propriedade e 0 em caso contrário. Escolha p no intervalo (0,1) de modo que E(X) > 0 em G(n, p). Então também P [X > 0] é positiva e portanto existe um grafo com a propriedade.
• Teorema 11.2.2 (Erdös):  Para todo k, existe um grafo H com cintura g(H) > k e número cromático chi(H) > k.

  (Apesar do valor elevado de chi, o grafo é localmente acíclico e portanto admite uma 2-coloração.)

• Corolário 11.2.3:  Existem grafos com cintura grande e valores arbitrariamente grandes de kappa, d e delta.

11.3  Propriedades de quase todos os grafos

• Uma propriedade gráfica é um subconjunto de G(n, p) fechado sob isomorfismo (ou seja, para quaisquer dois grafos isomorfos em G(n, p), ambos estão no subconjunto ou nenhum dos dois está no subconjunto).
• Para qualquer propriedade gráfica P, se a probabilidade P [G ∈ P] tende a 1 quando n tende a infinito, dizemos que quase todos os grafos em G(n, p) pertencem a P.

  Analogamente, se a probabilidade P [G ∈ P] tende a 0 quando n tende a infinito, dizemos que quase nenhum grafo em G(n, p) pertence a P.

• Lema 11.3.2:  Um grafo G tem a propriedade P_i,j se, para quaisquer conjuntos mutuamente disjuntos U e W com não mais que i e j vértices respectivamente, existe um vértice v fora de U ∪ W que é adjacente a todos os elementos de U e a nenhum dos elementos de W.  Para qualquer número p no intervalo (0,1) e quaisquer números naturais i e j,  quase todo grafo em G(n, p) tem a propriedade P_i,j.
• Corolário 11.3.3:  Para qualquer número p no intervalo (0,1) e qualquer número natural k,  quase todo grafo em G(n, p) é k-conexo.
• Corolário 11.3.1:  Para qualquer número p no intervalo (0,1) e qualquer grafo H com n ou menos vértices,  quase todo grafo em G(n, p) tem um subgrafo induzido isomorfo a H.
• Proposição 11.3.4:  Para qualquer número p no intervalo (0,1) e qualquer ε > 0,  quase todo grafo G em G(n, p) tem  chi(G) > c(ε) n / log n,  sendo c(ε) = −log (1−p) / (2 + ε).

11.4  Limiares de propriedades

• A seção anterior sugere que o espaço G(n, p) com p constante (ou seja, independente de n) não é muito interessante. É mais interessante estudar o espaço G(n, p) em que p é uma função de n (com p(n) ≥ 0 para todo n). Especialmente interessante é o caso em que p(n) tende a zero quando n tende a infinito.
• Idéia informal do conceito de limiar:  Suponha que P é uma propriedade gráfica e t uma função de n (por exemplo, t(n) = 1 / n).  Dizemos que t(n) é limiar para P se quase nenhum grafo em G(n, p(n)) está em P quando p(n) cresce mais devagar que t(n) e quase todos os grafos em G(n, p(n)) estão em P quando p é cresce mais rápido que t(n).
• Um limiar (= threshold function) para uma propriedade gráfica P é uma função t(n) tal que t(n) ≠ 0 para todo n e, para toda função p(n),
  1. se lim p(n) / t(n) = 0 quando n tende a infinito então quase nenhum grafo de G(n, p(n)) pertence a P e
  2. se lim p(n) / t(n) = ∞ quando n tende a infinito então quase todo grafo de G(n, p(n)) pertence a P.
• Teorema 11.4.3 (Erdös & Rényi):  Para qualquer grafo equilibrado H com uma ou mais arestas, a função  n^{−|H| / ‖H‖}  é um limiar para a existência de um subgrafo induzido isomorfo a H.

  Aqui, um grafo H é equilibrado se d(H') ≤ d(H) para todo subgrafo H' de H. 

  Resumo da primeira parte da prova:  Seja t(n) = n^{|H| / ‖H‖} e X(G) o número de subgrafos de G isomorfos a H.  Então P [X ≥ 1] ≤ E(X) ≤ p(n)^‖H‖ / n^|H| = (p(n)/t(n))^‖H‖. Se esse quociente tende a 0 então a probabilidade tende a 0.

  Resumo da segunda parte da prova:  Seja mü := E(X) e sigma² := E((X−mü)²).  Então P [X = 0] ≤ P [|X−mü| ≥ mü] ≤ sigma²/mü² = E(X²)/mü² − 1 ≤ c n p(n)^{−‖H‖/|H|} = c (p(n)/t(n))^{−‖H‖/|H|}, onde c não depende de n. Se p/t tende a infinito, essa última expressão tende a 0.

• Corolário 11.4.4:  A função n⁻¹ é um limiar para a existência de um subgrafo isomorfo a um ciclo
• Corolário 11.4.5:  Para qualquer árvore T com k ≥ 2 vértices, a função n^{−k / (k – 1)} é um limiar para a existência de um subgrafo isomorfo a T.
• Corolário 11.4.6:  Para todo k ≥ 2, a função n^{−2 / (k – 1)} é limiar para a existência de um subgrafo isomorfo a K^k.