grafos aleatorios

REGULARIDADE - COMO USAR

GUILHERME MOTA (IME/USP)

Sumário
1. Introdução

1

2. Regularidade - Caso denso

1

2.1. Aplicações

3

2.1.1. Preliminares

3

2.1.2. Lemas auxiliares

3

2.1.3. Aplicação geral

4

3. Regularidade - Caso esparso

9

3.1. Aplicações

10

Referências

19

1. Introdução
Muitas vezes em combinatória extremal é necessário fazer uso de ferramentas avançadas para se chegar à solução de um determinado problema. Um resultado muito importante nesta área é o famoso Lema da Regularidade de Szemerédi, que trata da questão de aproximar um grafo qualquer por um grafo formado pela união de uma quantidade constante de grafos bipartidos aleatórios. De forma vaga, Szemerédi mostrou que, dado um grafo, é possível particionar seu conjuntos de vértices em um número limitado de partes (que não depende da quantidade de vértices do grafo) de modo que “quase todo” par destas partes se assemelha a um grafo bipartido aleatório. Desta maneira, é possível, através do estudo de grafos aleatórios, obter resultados sobre grafos quaisquer.

2. Regularidade - Caso denso
Para definir precisamente o que significa um par de conjuntos de vértices ser semelhante a um grafo aleatório, precisamos definir o conceito de par regular.

Seja G um grafo. Dados ε > 0 e A, B ⊂ V (G) subconjuntos disjuntos de vértices, dizemos que o par (A, B) é ε-regular se, para todo X ⊂ A e Y ⊂ B, tais que |X| ≥ ε|A| e |Y | ≥ εB, temos e(A, B) e(X, Y )
−
≤ ε.
|A||B|
|X||Y |
Ou seja, um par (A, B) é regular se, para todos subconjuntos suficientemente grandes de A e B, a densidade e(X, Y )/(|X||Y |) entre tais conjuntos é muito próxima à densidade entre A e B.
É fácil ver que qualquer par suficientemente grande de vértices de Gn,p é ε-regular com alta probabilidade. Portanto, faz sentido que um par (A, B) de um grafo G seja considerado “parecido” com um grafo aleatório quando tal par é ε-regular. Existem diversas outras propriedades,