Versões Probabilísticas de Resultados da Teoria Combinatória dos Números

Bruno Fernandes Cerqueira Leite

Dissertação apresentada

ao

Instituto de Matemática e Estatística

da

Universidade de São Paulo

para obtenção do grau

de

Mestre em Matemática

Área de Concentração: Matemática Orientador: Prof. Dr. Yoshiharu Kokayakawa

Durante a elaboração deste trabalho, o autor recebeu apoio financeiro da FAPESP (processo 02/10983-7).

São Paulo, dezembro de 2004

Versões Probabilísticas de Resultados da Teoria Combinatória dos Números

Este exemplar corresponde à redação final da dissertação de mestrado devidamente corrigida e defendida por Bruno F. C. Leite

e aprovada pela comissão julgadora.

São Paulo, dezembro de 2004.

Banca examinadora:

• Prof. Dr. Yoshiharu Kohayakawa — IME-USP

• Prof. Dr. Carlos Gustavo Tamm de Araújo Moreira — IMPA

• Prof. Dr. Jozef Skokan — IME-USP

Para a Luciana

(seu apoio foi tão grande que eu poderia citá-la como co-autora...)

Agradecimentos

Agradeço aos meus familiares, pela ajuda que me deram.

Agradeço aos professores Edson de Faria e Yoshiharu Kohayakawa, pela fantástica orientação que tive nestes últimos cinco anos.

Agradeço a todos os meus amigos (em particular, Mac e Roberta), pelo companheirismo e pelas alegrias que me proporcionaram.

Agradeço em especial à Luciana, pela imensa compreensão e paciência, e por ter estado sempre ao meu lado, mesmo nos momentos mais difíceis (que não foram poucos). Sem ela, a conclusão deste trabalho teria sido praticamente impossível.

Agradeço, por fim, à FAPESP, pelo apoio financeiro dado durante o mestrado e ao longo de dois projetos de Iniciação Científica.

∑_{j=1}^{∞} \frac{1}{j^{2}} = \frac{1}{1^{2}} + \frac{1}{2^{2}} + \frac{1}{3^{2}} + ⋯ = \frac{π^{2}}{6} (!)

(Euler, 1736)

Resumo

Neste trabalho, provamos versões probabilísticas de dois teoremas clássicos da Teoria Combinatória dos Números: os Teoremas de Schur e de Sárközy.

Em 1916, Schur provou que se ℕ é finitamente colorido, uma das cores contém uma solução da equação x + y = z. Nossa versão probabilística do Teorema de Schur é, na verdade, uma versão probabilística “de densidade” do Teorema de Schur. Ela afirma, grosso modo, que fixando-se 0 < η ≤ 1/2, um subconjunto “típico” X de ℤ_{n} = ℤ/nℤ tem a seguinte propriedade: para todo subconjunto D ⊂ X com |D| ≥ (1/2 + η)|X|, existem x, y, z ∈ D satisfazendo x + y = z.

Em 1978, Sárközy mostrou que se A ⊂ ℕ é um subconjunto com densidade superior positiva, então A−A contém um quadrado diferente de zero. Em nossa versão probabilística do Teorema de Sárközy, provamos que, fixado 0 < η ≤ 1, um subconjunto “típico” X de ℤ_{n} tem a seguinte propriedade: para todo subconjunto D ⊂ X com |D| ≥ η|X|, existem x, y ∈ D tais que x − y é um quadrado diferente de zero.

Observamos que os dois teoremas acima são especialmente interessantes quando consideramos subconjuntos esparsos de ℤ_{n}, isto é, quando temos |X| = o(n).

Os enunciados precisos destas versões são os teoremas 13 e 14 do presente trabalho. A noção formal do que é um subconjunto “típico” pode ser vista na definição 11. Generalizações dos resultados acima são discutidas nos capítulos 4 e 5.

Abstract

In this work, we prove probabilistic versions of two classical theorems from Combinatorial Number Theory: Schur’s theorem and Sárközy’s theorem.

In 1916, Schur proved that if ℕ is finitely colored, then one of its colors contains a solution to the equation x + y = z. Our probabilistic version of Schur’s theorem is actually a “density” probabilistic version of Schur’s theorem. It states, roughly, that for a fixed 0 < η ≤ 1/2, a “typical” subset X of ℤ_{n} = ℤ/nℤ has the following property: for every subset D ⊂ X with |D| ≥ (1/2 + η)|X|, there are x, y, z ∈ D such that x + y = z.

In 1978, Sárközy showed that if A ⊂ ℕ is a subset with positive upper density, then A − A contains a square different from zero. In our probabilistic version of Sárközy’s theorem, we prove that, given 0 < η ≤ 1, a “typical” subset X ⊂ ℤ_{n} has the following property: for every subset D ⊂ X with |D| ≥ η|X|, there are x, y ∈ D such that x − y is a square different from zero.

We observe that both theorems above are particularly interesting when we consider sparse subsets of ℤ_{n}, that is, when we have |X| = o(n).

The precise statements of these results are the theorems 13 and 14 of this work. The formal notion of what is a “typical” subset can be found in definition 11. Generalizations of the results above are discussed in chapters 4 and 5.

Conteúdo

1 Introdução 2 1.1 Exemplos de versões probabilísticas . . . . . . . . . . . . . . . 2 1.2 Os Teoremas de Schur e Sárközy . . . . . . . . . . . . . . . . 4 1.3 Por que o interesse nas equações x + y = z e x − y = z^{2}? … 8

1.3.1 Resultados determinísticos: os Teoremas de Rado e de

Frankl–Graham–Rödl . . . . . . . . . . . . . . . . . . 8 1.3.2 Versões probabilísticas: resultados de Graham, Rödl

e Ruciński . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Quasi-aleatoriedade em ℤ_{n} e em grafos 12

3 Regularidade em grafos 16 3.1 η-Regularidade . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Transformada de Fourier e regularidade . . . . . . . . . . . . 20 3.3 O Lema de Regularidade de Szemerédi . . . . . . . . . . . . . 23 3.4 Aplicando o Lema de Regularidade . . . . . . . . . . . . . . . 26 3.5 A versão esparsa do Lema de Regularidade . . . . . . . . . . 29

4 Uma versão probabilística do Teorema de Schur 31 4.1 O lema dos pares proibidos . . . . . . . . . . . . . . . . . . . 31 4.2 O teorema Schur(η) . . . . . . . . . . . . . . . . . . . . . . . 38 4.3 O problema Schur(η) . . . . . . . . . . . . . . . . . . . . . . . 49

5 Herança de regularidade 51 5.1 Versão interna de herança de regularidade . . . . . . . . . . . 52 5.2 Uma versão probabilística do Teorema de

Sárközy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 5.3 Outras aplicações dos teoremas 67 e 68 . . . . . . . . . . . . . 59

6 Conclusão 64

Capítulo 1

Introdução

Neste trabalho, estamos interessados em investigar versões probabilísticas de teoremas clássicos da Teoria Combinatória dos Números. Dedicaremos especial atenção a dois problemas que resolvemos: provamos versões probabilísticas de densidade do Teorema de Schur e do Teorema de Sárközy.

1.1 Exemplos de versões probabilísticas

Como veremos a seguir, versões probabilísticas de muitos teoremas clássicos já foram estudadas. Como exemplo, examinaremos inicialmente os Teoremas de van der Waerden e Szemerédi.

Em 1927, van der Waerden provou o famoso teorema abaixo ([37]).

Teorema 1 (van der Waerden, 1927). Qualquer partição de ℕ em um número finito de partes é tal que alguma parte contém progressões aritméticas arbitrariamente longas.

Erdős e Turán [9] conjecturaram uma versão mais forte que o Teorema de van der Waerden, a saber, eles conjecturam a “versão de densidade” do teorema 1: se uma parte dos inteiros é “grande”, então ela contém progressões aritméticas arbitrariamente longas. Esta conjectura foi confirmada nesta generalidade apenas em 1975, por Szemerédi, através de seu célebre resultado:

Teorema 2 (Szemerédi, 1975). Todo conjunto A ⊂ ℕ com densidade superior positiva, isto é, com

d̄(A) = lim sup_{n→∞} n^{−1}|A ∩ {1, …, n}| > 0,  (1.1)

contém progressões aritméticas arbitrariamente longas.

No que se segue, será mais conveniente considerar as seguintes versões “finitas” dos teoremas 1 e 2.

Teorema 3 (van der Waerden, versão finita). Para quaisquer inteiros positivos r e k, existe um inteiro n_{0} = n_{0}(r, k) com a seguinte propriedade: para todo n ≥ n_{0}, toda partição de [n] = {1, …, n} em r partes é tal que alguma parte contém uma progressão aritmética com k elementos.

Teorema 4 (Szemerédi, versão finita). Para todo real η > 0 e inteiro positivo k, existe um inteiro n_{0} = n_{0}(η, k) com a seguinte propriedade: para todo n ≥ n_{0}, todo conjunto A ⊂ [n] com densidade pelo menos η, isto é,

n^{−1}|A ∩ [n]| ≥ η,  (1.2)

contém uma progressão aritmética com k elementos.

Usando um resultado conhecido em combinatória como “princípio da compacidade” (veja o capítulo 1 de [15]), não é difícil estabelecer a equivalência entre as diferentes versões dos teoremas.

Será conveniente escrever

Γ → (PA_{k})_{r}  (1.3)

se Γ ⊂ ℕ satisfaz a propriedade descrita no teorema 3, isto é, se toda partição Γ = U_{1}∪⋯∪U_{r} é tal que algum U_{i} contém uma progressão aritmética com k elementos. Em outras palavras: escrevemos (1.3) se para toda coloração de Γ com r cores (ou ‘toda r-coloração de Γ’), existe uma progressão aritmética de tamanho k monocromática. Definimos de forma análoga a notação

Γ →_{η} PA_{k}  (1.4)

para todo conjunto Γ ⊂ ℕ finito. Escrevemos (1.4) se todo U ⊂ Γ com |U| ≥ η|Γ| contém uma progressão aritmética com k elementos.

Os teoremas 3 e 4 dizem que segmentos iniciais Γ = [n] de ℕ suficientemente grandes satisfazem as relações (1.3) e (1.4). Ao passarmos tais teoremas para o contexto de resultados probabilísticos, a pergunta essencial é a seguinte:

(*) O que podemos dizer sobre conjuntos típicos Γ ⊂ [n]?

Para podermos falar sobre “conjuntos típicos”, definimos inicialmente uma distribuição de probabilidade sobre os subconjuntos de [n]. A distribuição mais simples que podemos considerar é a distribuição uniforme; na realidade, fixamos um inteiro N ≤ n e consideramos o conjunto \binom{[n]}{N} de todos os subconjuntos Γ ⊂ [n] de cardinalidade N e o munimos com a medida de probabilidade uniforme. Escreveremos [n]_{N} para um conjunto aleatório sorteado uniformemente ao acaso dentre todos os membros de \binom{[n]}{N}. Assim, para todo conjunto fixo X ⊂ [n] com |X| = N, temos

ℙ([n]_{N} = X) = \binom{n}{N}^{−1}.  (1.5)

Os dois próximos resultados que enunciamos fornecem uma resposta a nossa pergunta acima (*). Observamos que o primeiro resultado, devido a Rödl e Ruciński [31], é um resultado que pode se considerar completo, pois trata da propriedade (1.3) para todo k e r.

Teorema 5 (Rödl e Ruciński, 1995). Para todos inteiros k ≥ 3 e r ≥ 2, existem constantes positivas c e C tais que

lim_{n→∞} ℙ([n]_{N} → (PA_{k})_{r}) = \begin{cases}0 & se N ≤ cn^{1−1/(k−1)}, \\ 1 & se N ≥ Cn^{1−1/(k−1)}. \end{cases}  (1.6)

O teorema 5 afirma que ocorre uma transição quando a ordem de grandeza de N passa por n^{1−1/(k−1)}. Este fenômeno se repetirá em muitos outros teoremas deste tipo.

O segundo resultado probabilístico que enunciamos, provado em [24], é ainda parcial, pois trata da relação (1.4) apenas para k = 3.

Teorema 6 (Kohayakawa, Łuczak e Rödl, 1996). Para todo real η > 0, existem constantes positivas c e C tais que

lim_{n→∞} ℙ([n]_{N} →_{η} PA_{3}) = \begin{cases}0 & se N ≤ cn^{1/2}, \\ 1 & se N ≥ Cn^{1/2}. \end{cases}  (1.7)

A demonstração do teorema 6 é, infelizmente, bastante sutil e não parece admitir uma generalização simples para k > 3. O fato de se conhecer uma versão probabilística ‘completa’ do teorema 3, mas ter-se apenas uma tal versão para k = 3 do teorema 4 é razoável, pois, ao que tudo indica, o teorema 4 é substancialmente mais profundo que o teorema 3.

1.2 Os Teoremas de Schur e Sárközy

Em 1916, I. Schur provou o teorema a seguir:

Teorema 7 (Schur, 1916). Para todo inteiro positivo r, vale o seguinte. Se ℕ é colorido com r cores, então uma das cores contém uma solução da equação x + y = z.

Diremos que x + y = z é a equação de Schur, e uma tripla que satisfaz a equação de Schur será dita uma tripla de Schur. Usando o princípio da compacidade, pode-se obter a versão equivalente e “finita” do teorema acima:

Teorema 8 (Schur, versão finita). Para todo inteiro positivo r, existe um inteiro n_{0} tal que se n ≥ n_{0} e [n] = {1, 2, …, n} é colorido com r cores, então uma das cores contém uma tripla de Schur.

De modo análogo às definições dadas em (1.3) e (1.4), definimos as notações

Γ → (Schur)_{r}  (1.8)

e

Γ →_{η} (Schur)  (1.9)

para todo conjunto Γ ⊂ ℕ finito (ou ainda Γ ⊂ G, com G grupo abeliano e Γ finito). Escrevemos (1.8) se toda partição Γ = U_{1} ∪ ⋯ ∪ U_{r} é tal que algum U_{i} contém uma tripla de Schur, e escrevemos (1.9) se todo D ⊂ Γ com |D| ≥ η|Γ| contém uma tripla de Schur. O Teorema de Schur diz que para todo r, existe n_{0} = n_{0}(r) tal que, se n ≥ n_{0}, [n] → (Schur)_{r}.

Assim como o Teorema de van der Waerden tem sua versão de densidade (o Teorema de Szemerédi), podemos também provar uma versão de densidade para o Teorema de Schur:

Teorema 9 (Schur, versão densidade). Para todo 0 < η ≤ 1/2, existe n_{0} ∈ ℕ tal que, se n ≥ n_{0}, então [n] →_{1/2+η} (Schur).

Prova. A densidade não pode ser qualquer; de fato, se trocarmos ‘1/2+η’ por alguma constante entre 0 e 1/2, o teorema é falso. Para ver isso, considere o conjunto dos ímpares em [2n], que tem densidade 1/2 mas não tem triplas de Schur.

Tome n_{0} = n_{0}(η) = 1/η e fixe n ≥ n_{0}. Suponha que D ⊂ [n], |D| ≥ (1/2 + η)n e D não contém triplas de Schur. Seja (D − D)^{+} = {d_{1} − d_{2} : d_{1}, d_{2} ∈ D e d_{1} > d_{2}}. Note que (D − D)^{+} ⊂ [n] e

|(D − D)^{+}| ≥ |D| − 1 ≥ (1/2 + η − 1/n)n ≥ n/2.

Como |D| ≥ (1/2 + η)n, segue que existe x ∈ D ∩ (D − D)^{+}, e portanto x escreve-se como x = z − y onde x, y, z ∈ D. Mas então x + y = z, contradizendo o fato de D não ter triplas de Schur.

No capítulo 4, iremos provar uma versão probabilística do teorema de Schur. Antes de chegarmos lá, temos um pequeno capítulo sobre quasialeatoriedade e um capítulo com resultados sobre regularidade.

Na seção inicial do capítulo 4, falaremos brevemente sobre o teorema principal do artigo [19]. Usaremos o mais importante resultado auxiliar da prova deste teorema (o lema dos pares proibidos) na seção 4.2, para provar a versão probabilística do Teorema de Schur de que já falamos. Antes de enunciarmos esta versão, veremos duas definições simples.

Definição 10. Seja η real com 0 < η ≤ 1/2. Dizemos que D ⊂ ℤ_{n} = ℤ/nℤ tem a propriedade Schur(η) se D →_{1/2+η} (Schur).

Ou seja, D tem a propriedade Schur(η) se qualquer subconjunto de D com densidade 1/2 + η tem uma solução da equação de Schur. Note que a soma é considerada módulo n.

Definimos abaixo o conceito de conjunto aleatório que usaremos ao longo de todo nosso trabalho.

Definição 11. Dados n ∈ ℕ e 0 ≤ p ≤ 1, obtemos o subconjunto aleatório ℤ_{n,p} ⊂ ℤ_{n} da seguinte forma: para cada j ∈ ℤ_{n}, colocamos j em ℤ_{n,p} com probabilidade p e de modo independente. Ou seja, realizamos n sorteios independentes.

Podemos agora enunciar o problema abaixo, que é bastante natural, tendo em vista as versões probabilísticas dos Teoremas de van der Waerden e Szemerédi:

Problema 12 (Problema Schur(η)). Para todo 0 < η ≤ 1/2, existe uma constante C = C(η) tal que, se p = p(n) ≥ Cn^{−1/2}, então, com probabilidade tendendo a 1 quando n → ∞, ℤ_{n,p} tem a propriedade Schur(η).

No capítulo 4, iremos discutir os parâmetros do enunciado, esclarecendo perguntas razoáveis como “Por que, ao tratarmos da propriedade PA_{3}, a densidade pode ser qualquer 0 < η < 1, enquanto que, neste problema, exige-se que a densidade seja maior que 1/2?” ou “O que acontece se p for muito menor que n^{−1/2}?”, etc.

Infelizmente, só conseguimos resolver uma versão um pouco mais fraca do problema 12, que enunciamos abaixo.

Teorema 13 (Teorema Schur(η)). Para todo 0 < η ≤ 1/2, existe uma constante C = C(η) tal que, se p = p(n) ≥ C log n/\sqrt{n}, então, com probabilidade tendendo a 1 quando n → ∞, ℤ_{n,p} tem a propriedade Schur(η).

Na seção 4.2, é dada uma prova do teorema 13. Se conseguíssemos provar a conjectura 55 (enunciada na seção 4.3), teríamos então uma prova para o enunciado original (problema 12).

Na prova do teorema 13, mostramos que se S é um subconjunto de um conjunto aleatório de ℤ_{n}, então S − S = {s_{1} − s_{2} : s_{1}, s_{2} ∈ S} tem uma certa propriedade interessante. Note que a estrutura de S − S está claramente relacionada ao problema de Schur, pois se (S −S)∩S ≠ ∅, segue imediatamente que há uma solução da equação de Schur (x+y = z ou z−y = x) em S. Conhecendo tal propriedade interessante, era natural investigarmos o mesmo tipo de problema mudando apenas a equação envolvida.

Seria interessante, por exemplo, provar algum teorema envolvendo a equação x+y = 3z, ou a equação x−y = 3z. Infelizmente, aqui nossas tentativas foram infrutíferas. No entanto, ao pensar na equação x−y = z^{2} mod n (n primo), obtivemos algum sucesso. Antes de detalhar isto, iremos definir as notações

Γ →_{η} Diferença(S)  (1.10)

e

Γ →_{η} Soma(S)  (1.11)

para todo conjunto Γ ⊂ ℕ finito e todo S ⊂ ℕ (ou ainda Γ ⊂ G, onde Γ é finito, G é um grupo abeliano ou um corpo e S ⊂ G). Escrevemos (1.10) se todo D ⊂ Γ com |D| ≥ η|Γ| contém x, y com x − y ∈ S, e escrevemos (1.11) se todo D ⊂ Γ com |D| ≥ η|Γ| contém x, y com x + y ∈ S.

No teorema abaixo, n percorrerá somente os primos de ℕ. Definimos Quad(n) ⊂ ℤ_{n} como o conjunto dos quadrados não-nulos módulo n, ou seja, Quad(n) = {1^{2} mod n, 2^{2} mod n, …, (n − 1)^{2} mod n}. Usaremos no capítulo 5 o fato (simples) que | Quad(n)| = (n − 1)/2, quando n é primo ímpar.

Teorema 14 (Sárközy probabilístico). Para todos 0 < η, γ < 1 , existem constantes C = C(η, γ) e n_{0} = n_{0}(η, γ) tais que, se p = p(n) ≥ C/n e se n é um primo com n ≥ n_{0}, então, com probabilidade pelo menos 1 − γ, temos que

ℤ_{n,p} →_{η} Diferença(Quad(n))

(as operações são feitas módulo n).

Conseguimos provar o teorema 14 usando um resultado muito recente e ainda não publicado de Gerke, Kohayakawa, Rödl e Steger ([12]) que trata de herança de regularidade (tudo isto será esclarecido mais adiante). No capítulo 5, enunciaremos este resultado sobre herança de regularidade, e veremos como empregá-lo para demonstrar o teorema 14.

Uma outra versão do teorema acima, aparentemente bem mais difícil, seria exigir que o z ou o z^{2} (da equação x − y = z^{2} mod n) esteja também contido na η-fração de ℤ_{n,p}, assim como x e y. Chamaremos esta versão de “versão difícil do problema de Sárközy”.

O nome “Sárközy” está sendo citado em menção ao seguinte teorema ([33], veja também [11]):

Teorema 15 (Sárközy, 1978). Se A ⊂ ℕ é um conjunto com densidade superior positiva, então A − A contém um quadrado diferente de 0.

Lembramos que a densidade superior de um conjunto A ⊂ ℕ foi definida pela equação 1.1.

Ainda com relação ao teorema 14, veremos que ele seguirá imediatamente de um teorema mais geral, e veremos que este teorema mais geral nos renderá outros resultados interessantes. Detalharemos tudo isso no capítulo 5. Por fim, no capítulo 6 fazemos algumas últimas considerações e enunciamos alguns problemas correlatos que não soubemos resolver.

Para fechar a introdução, desejamos justificar o motivo do interesse nas equações que estudamos.

1.3 Por que o interesse nas equações x + y = z e x − y = z^{2}?

Nesta seção, damos um breve panorama do que já foi feito na área de versões probabilísticas de resultados da Teoria Combinatória dos Números, e aproveitamos para dar uma breve justificativa sobre o interesse nas equações x + y = z e x − y = z^{2}. Como o leitor poderá conferir nesta seção, muita coisa já foi feita na área de sistemas lineares, e, por isso, ao estudarmos a equação x − y = z^{2}, tentamos estudar algo aparentemente novo, e não excessivamente difícil. Já o estudo da equação de Schur justifica-se pelo fato de ela ser a mais simples equação que é P-regular mas não D-regular (estas definições encontram-se logo adiante), e pelo fato de já existirem teoremas probabilísticos que versam sobre equações (ou sistemas lineares de equações) D-regulares, ao passo que o problema análogo para equações (ou sistemas) P-regulares está em aberto.

Vamos começar a esclarecer isto citando dois resultados determinísticos: o Teorema de Rado e o Teorema de Frankl, Rödl e Graham.

1.3.1 Resultados determinísticos: os Teoremas de Rado e de Frankl–Graham–Rödl

O teorema 5 não é a versão mais geral do que se conhece nesta direção. De fato, pelo menos em certos casos, é conhecida uma versão probabilística do célebre Teorema de Rado [30], que generaliza o Teorema de van der Waerden.

Seja A = (a_{ij}) uma matriz k × l com entradas inteiras, e seja L(A) o sistema de equações

Ax = 0.  (1.12)

Dizemos que A é regular em relação a partições de ℕ, ou P-regular para ℕ, se para todo natural r e toda partição ℕ = U_{1} ∪ ⋯ ∪ U_{r}, existe x ∈ ℕ^{l} com todas as suas entradas em algum U_{i} tal que Ax = 0. Isto é, A é P-regular para ℕ se qualquer partição finita de ℕ é tal que o sistema L(A) admite uma solução inteiramente contida em uma das partes.

Rado [30] caracterizou as matrizes P-regulares, generalizando amplamente o resultado de van der Waerden. Para formularmos o resultado de Rado, precisamos introduzir uma nova definição.

Sejam a_{j} (1 ≤ j ≤ l) as colunas de A. Dizemos que A satisfaz a propriedade das colunas se podemos reordenar as colunas de A de forma que, para algum s, existam 0 = l_{0} < ⋯ < l_{s} = l tais que se

b_{j} = ∑{a_{j′}: l_{j−1} < j′ ≤ l_{j}} (1 ≤ j ≤ s),

então

(i) b_{1} = 0

e

(ii) para todo 1 < j ≤ s, o vetor b_{j} é uma combinação linear sobre ℚ dos vetores a_{j′} (j′ ≤ l_{j−1}).

O célebre resultado de Rado é o seguinte.

Teorema 16 (Rado, 1937). A matriz A é P-regular para ℕ se e só se A satisfaz a propriedade das colunas.

É fácil verificar que o teorema 16 generaliza o Teorema de van der Waerden. De fato, para se obter o Teorema de van der Waerden a partir do Teorema de Rado, basta considerar a matriz correspondente ao sistema

x_{1} − 2x_{2} + x_{3} = ⋯ = x_{k−2} − 2x_{k−1} + x_{k} = 0.  (1.13)

Uma generalização análoga para o Teorema de Szemerédi, que examinaremos a seguir, foi obtida por Frankl, Graham, e Rödl [10].

Uma matriz A é dita regular em relação a densidade para ℕ, ou D-regular para ℕ, se todo conjunto S ⊂ ℕ com densidade superior positiva, isto é, com

d̄(S) = lim sup_{n→∞} n^{−1}|S ∩ [n]| > 0,  (1.14)

é tal que (1.12) admite uma solução x com todas as suas entradas em S. Segue que uma matriz D-regular é P-regular.

Diremos que uma matriz A é irredundante se (1.12) não implicar que x tem duas entradas x_{i} e x_{j} (com i ≠ j) tais que x_{i} = x_{j}. Diremos que uma solução x = (x_{1}, …, x_{l}) é própria se todos os x_{i} forem distintos.

No que segue, o caso das matrizes redundantes não nos interessará. Frankl, Graham, e Rödl [10] provaram o seguinte resultado.

Teorema 17 (Frankl, Graham e Rödl, 1988). Uma matriz irredundante tem uma solução própria em cada conjunto S ⊂ ℕ com densidade superior positiva se e só se a soma de suas colunas é nula.

O teorema 17 generaliza o Teorema de Szemerédi (veja (1.13)); entretanto, observamos que a prova do teorema 17 usa o Teorema de Szemerédi.

1.3.2 Versões probabilísticas: resultados de Graham, Rödl e Ruciński

Uma generalização impressionante do teorema 5 é o teorema 18, devido a Rödl e Ruciński [32]. Se Γ ⊂ ℕ e A é uma matriz inteira, generalizando (1.3), escrevemos

Γ → (A)_{r}  (1.15)

se toda partição Γ = U_{1} ∪ ⋯ ∪ U_{r} de Γ em r partes é tal que (1.12) admite uma solução x com todas as suas entradas em algum U_{i}.

Precisamos ainda definir um parâmetro m(A) para matrizes A; este parâmetro mede, de certa forma, o grau de liberdade que temos para obter soluções de (1.12). Observamos que a definição exata deste parâmetro não é muito importante, pelo menos em uma primeira leitura; é suficiente observar que m(A) é um real satisfazendo 0 < m(A) ≤ 1, que depende apenas de A.

Se Q é um subconjunto de colunas de A, escrevemos h(Q) para o posto da matriz que obtemos ao eliminar as colunas em Q de A. Pomos

m(A) = max_{q} max_{Q} \frac{q − 1}{q − 1 + h(Q) − k} ,  (1.16)

onde o primeiro máximo é tomado sobre todos os inteiros 1 ≤ q ≤ l e o segundo máximo é tomado sobre todos os conjuntos de colunas Q com |Q| = q. No caso da matriz A do sistema (1.13), um argumento simples, mas que omitimos, mostra que m(A) = k − 1.

Teorema 18 (Rödl e Ruciński, 1997). Sejam A uma matriz D-regular para ℕ e r um inteiro positivo. Existem constantes positivas c e C tais que

lim_{n→∞} ℙ([n]_{N} → (A)_{r}) = \begin{cases}0 & se N ≤ cn^{1−1/m(A)}, \\ 1 & se N ≥ Cn^{1−1/m(A)}. \end{cases}  (1.17)

No teorema 18, o caso em que a matriz A é apenas regular em relação a partições de ℕ encontra-se em aberto.

Conjectura 19 (Rödl e Ruciński, 1997). O Teorema 18 é também válido para matrizes A regulares em relação a partições de ℕ.

A matriz mais simples que é P-regular mas não é D-regular é a matriz correspondente à equação x + y − z = 0. O fato dessa matriz ser P-regular é exatamente o conteúdo do Teorema de Schur (teorema 7).

Um passo na direção da conjectura 19 é o seguinte resultado, devido a Graham, Rödl, e Ruciński [14]. Abaixo, escrevemos

Γ → (Schur)_{r}  (1.18)

se toda partição de Γ em r partes é tal que a equação x + y = z é solúvel em alguma das partes.

Teorema 20 (Graham, Rödl e Ruciński, 1996). Temos

lim_{n→∞} ℙ([n]_{N} → (Schur)_{2}) = \begin{cases}0 & se N/n^{1/2} → 0, \\ 1 & se N/n^{1/2} → ∞. \end{cases}  (1.19)

Finalmente, observamos que no caso de matrizes D-regulares, um resultado mais forte que aquele do Teorema 18 pode ser verdade. De fato, podemos levantar o seguinte problema. Generalizando (1.4), dados uma matriz A, um real η > 0, e Γ ⊂ ℕ, escrevemos

Γ →_{η} A  (1.20)

se todo conjunto U ⊂ Γ com |U| ≥ η|Γ| contém uma solução de (1.12).

Problema 21. Sejam A uma matriz D-regular para ℕ e η um real positivo. Prove que existem constantes positivas c e C tais que

lim_{n→∞} ℙ([n]_{N} →_{η} A) = \begin{cases}0 & se N ≤ cn^{1−1/m(A)}, \\ 1 & se N ≥ Cn^{1−1/m(A)}. \end{cases}  (1.21)

Dado o grau de dificuldade das conjecturas acima enunciadas, resolvemos atacar problemas mais simples. Mesmo com essa opção, o material novo que obtivemos (o conteúdo das seções 4.2, 4.3, 5.1, 5.2 e 5.3) já é um pouco complicado tecnicamente.

Quasi-aleatoriedade em ℤ_{n} e em grafos

O objetivo deste capítulo é definir quasi-aleatoriedade e enunciar o teorema principal de [5]. Vamos começar com uma discussão bastante simplificada e informal.

Digamos que em algum concurso da loto (onde os números vão de 1 a 50 e cada apostador escolhe 6 números) o resultado do sorteio seja {1, 2, 3, 4, 5, 6}. Qualquer pessoa diria que tal evento “nunca ocorre” ou “é impossível”. De fato, apesar de sabermos que {1, 2, 3, 4, 5, 6} tem a mesma probabilidade que {4, 9, 17, 26, 32, 49}, temos alguma “sensação” de que o último evento é “mais razoável” que o primeiro.

Intuitivamente, um conjunto “com cara de aleatório” deve “ser aprovado” em alguns testes de aleatoriedade. Por exemplo, um conjunto S “com cara de aleatório” em {1, 2 …, 50} deve ter a propriedade que ∑_{s∈S} e^{2πis/50} é “pequeno”, ou seja, os vetores (e^{2πis/50})_{s∈S} devem estar bem distribuídos em S^{1} = {x ∈ ℂ: |x| = 1}, e não todos concentrados em alguma direção. Note que (sempre intuitivamente!) esse critério já exclui a possibilidade de que {1, 2, 3, 4, 5, 6} tenha “cara de aleatório”, uma vez que os vetores (e^{2πis/50})_{s∈{1,2,3,4,5,6}} estão todos apontando em direções próximas.

Vamos olhar agora para subconjuntos de ℤ_{n}. Dado S ⊂ ℤ_{n}, gostaríamos de poder dizer objetivamente se S “se parece” com um subconjunto aleatório ℤ_{n,p} ⊂ ℤ_{n}. Isto é, seria interessante conhecer algumas propriedades de conjuntos aleatórios que, de certa forma, os caracterizam. Dito de outra maneira, queremos propriedades que “captem” a aleatoriedade de um conjunto aleatório.

Vamos dar um exemplo. É fácil ver que o tamanho esperado de ℤ_{n,p} é np, e que o tamanho esperado da interseção de dois conjuntos ℤ_{n,p} sorteados independentemente é np^{2}. Dados S ⊂ ℤ_{n} e x ∈ ℤ_{n}, defina S+x = {s+x: s ∈ S}. Para p fixo, uma propriedade que “quase todos” os conjuntos ℤ_{n,p} possuem é a seguinte: para “quase todo” x ∈ ℤ_{n}, ||ℤ_{n,p} ∩ (ℤ_{n,p} + x)| − np^{2}| é “pequeno”.

Podemos assim enunciar um outro critério de quasi-aleatoriedade: para que um conjunto S ⊂ ℤ_{n} com |S| = pn seja considerado “com cara de aleatório”, ||S ∩ (S + x)| − np^{2}| deve ser “pequeno” para “quase todo” x.

Naturalmente, os exemplos acima são bastante simplificados e servem apenas para introduzir o conceito de quasi-aleatoriedade. Veremos logo abaixo que um conjunto será dito quasi-aleatório quando ele satisfaz uma série de critérios (como os acima) para ter “cara de aleatório”. Naturalmente, os critérios devem ser satisfeitos por quase todo conjunto aleatório. Assim, apesar de não ser aleatório, um conjunto quasi-aleatório “comportase” como se o fosse, já que tem muitas propriedades de conjuntos aleatórios.

O que Chung e Graham fizeram em [5] foi, basicamente, listar alguns critérios de quasi-aleatoriedade e provar o seguinte teorema: se um conjunto satisfaz um desses critérios, então ele satisfaz todos os outros. Ou seja, são todos critérios equivalentes. O teorema é extremamente surpreendente, pois a primeira impressão que se tem é que não há relação clara entre os critérios propostos.

Dizendo deste modo, pode parecer que o artigo de Chung e Graham é extremamente simples, o que é falso. A prova da equivalência dos critérios não é trivial, e, mais ainda, a grande dificuldade está em achar critérios que não sejam nem fracos nem fortes demais. Por exemplo, considere o critério C definido da seguinte forma: S ⊂ ℤ_{n} satisfaz C se e só se |S ∩ {1, 2, …, ⌊n/2⌋}| = |S|/2 + o(n) (onde pensamos em {1, 2, …, ⌊n/2⌋} como subconjunto de ℤ_{n} e não de ℤ). É fácil provar que quase todo conjunto aleatório ℤ_{n,1/2} satisfaz C, mas é claro (intuitivamente) que C é uma propriedade fraca demais para “captar” o “grau de aleatoriedade” de um conjunto.

Enunciaremos o teorema principal de [5] formalmente. Para S ⊂ ℤ_{n}, seja χ_{S} a função indicadora de S (χ_{S} vale 1 em S e 0 fora de S). Definimos o grafo de Chung-Graham de S, CG(S) = CG_{n}^{+}(S), como o grafo que tem ℤ_{n} como conjunto de vértices e {{i, j}: i+j ∈ S} como conjunto de arestas. Lembramos que as somas são sempre consideradas módulo n. Dados S, T ⊂ ℤ_{n}, denotamos s = |S| e t = |T |.

Listamos abaixo propriedades que um certo conjunto S ⊂ ℤ_{n} poderia possuir. Para este S, escreveremos simplesmente χ em vez de χ_{S}. Por “quase todo x ∈ X”, deve-se entender “para todos os elementos de X, exceto no máximo o(|X|)”. Como dissemos, Chung e Graham provaram que estas propriedades são todas equivalentes. Dado que todas as propriedades envolvem a notação assintótica “o pequeno”, o(.), é conveniente explicarmos melhor o que queremos dizer com “a propriedade P implica a propriedade P′”. Cada uma das ocorrências de o(1) (digamos) pode ser substituída por alguma função f(n) apropriada, e que vai a 0 quando n → ∞. Nesse sentido, escrever P ⇒ P′ significa que se S ⊂ ℤ_{n} satisfaz P = P (f(n)), então também deve satisfazer P′ = P′(f′(n)).

Para compreender melhor as três últimas propriedades é necessário saber o que é um grafo quasi-aleatório. Veremos isto logo a seguir.

Vamos às propriedades.

1. (WT) — Weak translation. Para quase todo x ∈ ℤ_{n},

|S ∩ (S + x)| = s^{2}/n + o(n).

2. (ST) — Strong translation. Para todo T ⊂ ℤ_{n} e quase todo x ∈ ℤ_{n},

|S ∩ (T + x)| = st/n + o(n).

3. (P (k)) — k-pattern. Para todo k fixo e para quase todos u_{1}, …, u_{k} ∈ ℤ_{n},

∑_{x} ∏_{j=1}^{k} χ(x + u_{j}) = s^{k}/n^{k−1} + o(n).

4. (R(k)) — k-representation. Para todo k fixo e para quase todo x ∈ ℤ_{n},

∑_{u_{1}+···+u_{k}=x} ∏_{j=1}^{k} χ(u_{j}) = s^{k}/n + o(n^{k−1}).

5. (EXP) — Exponential sum. Para todo j ≠ 0 em ℤ_{n},

∑_{x∈ℤ_{n}} χ(x) exp (\frac{2πijx}{n}) = o(n).

6. (GRAPH) — Quasi-random graph. O grafo CG(S) é quasi-aleatório.

7. (C(2t)) — 2t-cycle.

∑_{x_{1},...,x_{2t}} χ(x_{1} +x_{2})χ(x_{2} +x_{3}) … χ(x_{2t−1} +x_{2t})χ(x_{2t} +x_{1}) = s^{2t} +o(n^{2t}).

8. (DENSITY) — Relative Density. Para todo T ⊂ ℤ_{n},

∑_{x,y} χ_{T} (x)χ_{T} (y)χ_{S}(x + y) = st^{2}/n + o(n^{2}).

Não daremos aqui a prova da equivalência entre todas estas propriedades. A demonstração pode ser encontrada em [5].

Vamos agora definir informalmente quasi-aleatoriedade em grafos. Estaremos interessados em critérios satisfeitos por grafos aleatórios. O modelo de grafo aleatório que usaremos neste trabalho será sempre o modelo binomial, que definimos a seguir. Um grafo aleatório G_{n,p} é um grafo com n vértices em que cada uma das \binom{n}{2} arestas entra no grafo com probabilidade p, de modo independente das demais. Denotamos por G(n, p) o espaço de probabilidade resultante. Para mais informações sobre grafos aleatórios, damos duas referências: [4] e [22].

A idéia geral para se definir quasi-aleatoriedade em grafos é a mesma do caso em ℤ_{n}: lista-se um série de propriedades que se espera de um grafo aleatório, prova-se que são todas equivalentes (no sentido explicado acima), e define-se um grafo como sendo quasi-aleatório se e só se ele satisfaz uma das propriedades (e portanto, satisfaz todas). Em 1989, este roteiro foi seguido por Chung, Graham e Wilson [6] e sete critérios foram propostos para dizer se um grafo G com n vértices tem “cara” de G_{n,1/2} (só foi tratado o caso p = 1/2). Enunciamos dois dos critérios de [6], apenas a título de exemplo.

As propriedades abaixo se referem a um grafo G = (V, E) com n vértices. Para U ⊂ V (G), G[U] é o grafo induzido por U, isto é, o grafo com V (G[U]) = U e E(G[U]) = E(G) ∩ \binom{U}{2} (\binom{U}{2} é o conjunto de todos os subconjuntos de U com 2 elementos).

1. Para todo S ⊂ V (G), o grafo induzido por S tem |S|^{2}/4+o(n^{2}) arestas.

2. Para v ∈ V (G), seja Γ(v) o conjunto dos vizinhos de v em G. Então

∑_{v_{1},v_{2}∈V (G)} ||Γ(v_{1}) ∩ Γ(v_{2})| − n/4| = o(n^{3}).

Para encerrar, desejamos dizer que de especial interesse para nós é a equivalência entre os critérios (EXP) e (GRAPH) para quasi-aleatoriedade em ℤ_{n}. Grosso modo, temos que se S tem seus coeficientes de Fourier pequenos (isto é, satisfaz (EXP)), então CG(S) tem certas propriedades especiais, que não detalharemos agora. A relação entre estes dois critérios será vista com mais atenção na seção 3.2.

Regularidade em grafos

A noção de regularidade é central em nosso trabalho. Abstratamente falando, um grafo G tem propriedades de regularidade quando para todos U, W ⊂ V (G) com |U| e |W | “grandes”, temos algum tipo de informação sobre o número de arestas em G entre U e W.

Vamos fixar a notação para o capítulo. Seja G = G^{n} um grafo com n vértices. Para U, W ⊂ V (G) com U ∩ W = ∅, escrevemos E(U, W) = E_{G}(U, W) para denotar o conjunto das arestas de G que ligam U a W. Colocamos e(U, W) = e_{G}(U, W) = |E_{G}(U, W)|.

Começamos definindo o conceito de η-regularidade.

3.1 η-Regularidade

Definição 22. Suponha que 0 < η ≤ 1 e 0 < p ≤ 1. Dizemos que um grafo G com n vértices é η-regular com densidade p se para todos U, W ⊂ V (G) com U ∩ W = ∅ e |U|, |W | ≥ ηn temos

|e_{G}(U, W) − p|U||W || ≤ ηp|U||W |.

O lema 24 mostra que grafos aleatórios G_{n,p} são muito provavelmente η-regulares, desde que d = np seja suficientemente grande. Lembramos que G_{n,p} é o grafo aleatório em n vértices em que cada uma das \binom{n}{2} arestas entra no grafo com probabilidade p e de modo independente das demais arestas.

Antes de enunciar e provar o lema 24, vamos deixar registrado um resultado que usaremos frequentemente neste trabalho. Trata-se de uma forma da desigualdade de Hoeffding (veja as desigualdades 5.5 e 5.6 de [28]), que estima a probabilidade de uma certa soma de variáveis aleatórias desviar-se muito de sua média:

Lema 23 (Desigualdade de Hoeffding). Sejam X_{1}, X_{2}, …, X_{n} variáveis aleatórias independentes com 0 ≤ X_{j} ≤ 1 para todo j, e sejam Y = ∑_{j=1}^{n} X_{j} e y = E[Y]. Então, para todo 0 < t < 1 temos

ℙ(Y − y ≥ ty) ≤ exp (\frac{−t^{2}y}{3} ),

ℙ(Y − y ≤ −ty) ≤ exp (\frac{−t^{2}y}{2} )

e, finalmente,

ℙ(|Y − y| ≥ ty) ≤ 2 exp (\frac{−t^{2}y}{3} ).

Aplicaremos a desigualdade de Hoeffding na demonstração do lema a seguir.

Lema 24. Fixe 0 < η ≤ 1 e considere o grafo aleatório G_{p} = G_{n,p} ∈ G(n, p) com 0 < p = p(n) < 1. Seja d = d(n) = np(n). Então, existe uma constante d_{0} = d_{0}(η) tal que, se d > d_{0}, quase todo G_{p} é η-regular com densidade p.

Prova. Veremos que podemos escolher d_{0}(η) = 6/η^{4}. Fixe um grafo G e fixe também U, W ⊂ V (G) com U ∩ W = ∅ e |U|, |W | ≥ ηn. Por Hoeffding, a probabilidade de que tenhamos |e_{G}(U, W) − p|U||W || ≥ ηp|U||W | é no máximo 2 exp(−η^{2}p|U||W |/3) ≤ 2 exp(−η^{4}pn^{2}/3) = 2 exp(−η^{4}dn/3). Com isso, a probabilidade de haver um par (U, W) que viole a condição de ηregularidade é no máximo

2^{n}2^{n} 2 exp(−η^{4}dn/3) ≤ 2 exp(2n − η^{4}dn/3).

Esta última exponencial vai a zero quando n → ∞, se d > d_{0}(η) = 6/η^{4}.

Agora, definiremos uma outra condição de regularidade para grafos, mais forte que a η-regularidade. Novamente, seja d = np.

Definição 25. Seja G = G^{n} um grafo com n vértices, e suponha A > 0, p > 0. Seja d = pn. Dizemos que G é (p, A)-uniforme se, para todos os conjuntos U, W ⊂ V (G) com U ∩ W = ∅, temos

|e_{G}(U, W) − p|U||W || ≤ A\sqrt{d|U||W |}.

Dentro do espírito desta seção, observamos que um nome mais adequado para a propriedade acima seria (p, A)-regularidade, mas nos decidimos por “uniformidade” simplesmente para manter o termo que já está em uso na literatura. O próximo lema é uma observação trivial, mas que desejamos deixar registrada.

Lema 26. Se p ≥ A^{2}/(η^{4}n) e G = G^{n} é um grafo (p, A)-uniforme com n vértices, então G é η-regular com densidade p.

Prova. Sejam U, W ⊂ V (G) com |U|, |W | ≥ ηn = η|V (G)|. Temos que

A\sqrt{pn|U||W |} ≤ ηp|U||W | ⇔ A^{2}n ≤ η^{2}p|U||W |.

Mas, de fato, temos η^{2}p|U||W | ≥ η^{2}(ηn)^{2}A^{2}/(η^{4}n) = A^{2}n, como queríamos.

Nos próximos lemas, estimaremos e(G[U]) (número de arestas do grafo induzido por U) quando U é um subconjunto de vértices de um grafo com propriedades de regularidade. Escrevemos O_{1}(x) para denotar um termo y que satisfaz |y| ≤ x.

Lema 27. Seja G um grafo. Para todo U ⊂ V (G), temos

e(G[U]) = \frac{\binom{u}{2}}{⌊u/2⌋⌈u/2⌉} Med_{S} e_{G}(S, U \ S),  (3.1)

onde u = |U| e Med_{S} e_{G}(S, U \ S) é a média de e_{G}(S, U \ S) quando S percorre todos os subconjuntos S ⊂ U de tamanho |S| = ⌊u/2⌋.

Prova. Fixe U ⊂ V (G) e note que

\begin{matrix}∑ & ∗ \\ S \end{matrix} e_{G}(S, U \ S) = me(G[U]),  (3.2)

onde a soma com estrela é sobre todos os subconjuntos S ⊂ U de tamanho |S| = ⌊u/2⌋, e m é o número de vezes que uma certa aresta pré-fixada ab de G[U] é contada na soma (é claro que cada aresta é contada o mesmo número de vezes). Ou seja, m é o número de subconjuntos S ⊂ U de tamanho |S| = ⌊u/2⌋ que “separam” a aresta ab, isto é, o número de subconjuntos S ⊂ U de tamanho |S| = ⌊u/2⌋ tais que exatamente uma das extremidades de ab está em S.

Dada uma aresta ab, existem \binom{u−2}{⌊u/2⌋−1} subconjuntos S que separam ab com a ∈ S (|S| = ⌊u/2⌋), e \binom{u−2}{⌊u/2⌋−1} que separam ab com b ∈ S. Logo m = 2\binom{u−2}{⌊u/2⌋−1}. Agora, usaremos duas identidades de fácil verificação: para u ≥ 2 e k ≥ 1, temos que

\binom{u − 2}{k} = \frac{u − k − 1}{u − 1}\binom{u − 1}{k} e \binom{u − 1}{k − 1} = \frac{k}{u}\binom{u}{k}.

Com o auxílio delas, vemos que

m = 2\binom{u − 2}{⌊u/2⌋ − 1} = \frac{2⌈u/2⌉}{u − 1}\binom{u − 1}{⌊u/2⌋ − 1}

= \frac{2⌈u/2⌉⌊u/2⌋}{u(u − 1)}\binom{u}{⌊u/2⌋} = \begin{matrix}( & {u \atop ⌊u/2⌋} & ) \\ ( & {u \atop 2} & ) \end{matrix}⌈u/2⌉⌊u/2⌋,

e pela equação 3.2, temos que

e(G[U]) = \frac{1}{m} \begin{matrix}∑ & ∗ \\ S \end{matrix} e_{G}(S, U \ S) = \frac{1}{m}\binom{u}{⌊u/2⌋} Med_{S} e_{G}(S, U \ S)

= \frac{Med_{S} e_{G}(S, U \ S)\binom{u}{2}}{⌈u/2⌉⌊u/2⌋},

como queríamos.

Lema 28. Fixe A > 0, C ≥ 1 e 0 ≤ p ≤ 1. Sejam G = G^{n} um grafo com n vértices e U ⊂ V (G).

• Se G é (p, A)-uniforme, temos

e(G[U]) = p\binom{|U|}{2} + O_{1}(Ad^{1/2}|U|),

onde d = np.

• Se G é η-regular com densidade p e ⌊|U|/2⌋ ≥ ηn, temos

e(G[U]) = p\binom{|U|}{2} + O_{1} (ηp\binom{|U|}{2}) .

• Se G é um grafo tal que, para todo U ⊂ V (G) com |U| = ⌊n/2⌋, temos e_{G}(U, V \ U) ≥ p⌊n/2⌋⌈n/2⌉, então

e(G) ≥ p\binom{n}{2}.

Prova. Todas as asserções seguem imediatamente do lema 27. Mostraremos apenas a terceira, para exemplificar. Fixe U ⊂ V (G) com |U| = ⌊n/2⌋. Pelo lema 27, temos que

e(G) = e(G[V (G)]) = \frac{\binom{n}{2}}{⌊n/2⌋⌈n/2⌉} Med_{S} e_{G}(U, V \ U)

≥ \frac{\binom{n}{2}}{⌊n/2⌋⌈n/2⌉}p⌊n/2⌋⌈n/2⌉ = p\binom{n}{2}.

3.2 Transformada de Fourier e regularidade

O objetivo desta seção é usar a transformada de Fourier discreta para mostrar que certos grafos são bastante regulares. Começamos relembrando as propriedades da transformada que nos serão úteis.

Dada uma função f: ℤ_{n} → ℂ, definimos T (f): ℤ_{n} → ℂ, a transformada de Fourier de f, por

T (f)(x) = ∑_{y∈ℤ_{n}} f(y)e^{−2πiyx/n}.

Note que há uma associação óbvia entre o conjunto das funções de ℤ_{n} em ℂ e o espaço vetorial ℂ^{n}: a cada função f: ℤ_{n} → ℂ, associamos o vetor (f(0), f(1), …, f(n − 1)) ∈ ℂ^{n}. Assim, podemos ver a transformada de Fourier como uma aplicação de ℂ^{n} em si mesmo, e é fácil ver que tal aplicação é linear. Além disso, sabe-se que a transformada de Fourier é uma transformação linear que leva bases ortogonais em bases ortogonais e que “estica” cada vetor por um fator \sqrt{n}: para todo x ∈ ℂ^{n}, temos ||T (x)|| = \sqrt{n}||x||, onde a norma considerada é a usual em ℂ^{n}.

Dadas funções f e g, ambas de ℤ_{n} em ℂ, definimos a convolução f ∗ g : ℤ_{n} → ℂ por

(f ∗ g)(x) = ∑_{y∈ℤ_{n}} f(y)g(x − y).

Uma propriedade importante da convolução é que a transformada de Fourier da convolução é o produto das transformadas, isto é, T (f ∗ g)(x) = T (f)(x)T (g)(x). A prova é simples, mas não a daremos aqui.

No que segue, usaremos os grafos definidos abaixo. O grafo de Chung-Graham com adição já foi definido anteriormente, mas julgamos conveniente repetir sua definição aqui.

Definição 29. Dado S ⊂ ℤ_{n}, definimos o “grafo de Chung-Graham com adição”, ou simplesmente “grafo de Chung-Graham”, CG_{n}(S) = CG_{n}^{+}(S), por V (CG_{n}^{+}(S)) = ℤ_{n}, e ab ∈ E(CG_{n}^{+}(S)) se e só se a + b ∈ S. Definimos também o “grafo de Chung-Graham com subtração”, CG_{n}^{−}(S) por V (CG_{n}^{−}(S)) = ℤ_{n}, e ab ∈ E(CG_{n}^{−}(S)) se e só se a − b ∈ S ∪ (−S). Todas as operações são feitas módulo n.

A razão de exigirmos que a − b ∈ S ∪ (−S), em vez de simplesmente a − b ∈ S, é que desejamos obter um grafo comum, e não um grafo dirigido.

Nos lemas a seguir, provaremos algo sobre o número de arestas entre U e W no grafo CG_{n}(R) = CG_{n}^{+}(R), e isto será útil para estabelecer uma conexão entre os coeficientes de Fourier de R e a η-regularidade do grafo CG_{n}^{+}(R).

O produto interno nos lemas a seguir é o usual em ℂ^{n}: se W = (w_{i})_{i=1}^{n} e Z = (z_{i})_{i=1}^{n} são vetores de ℂ^{n}, ⟨W, Z⟩ = ∑_{i=1}^{n} w_{i}z̄_{i}. Não faremos distinção entre um subconjunto de ℤ_{n} e sua função indicadora.

Lema 30. Sejam R, U, W ⊂ ℤ_{n} com U ∩ W = ∅. Então

e_{CG_{n}^{+}(R)}[U, W] = ⟨R, U ∗ W ⟩.

Prova. Basta notar que

⟨R, U ∗ W ⟩ = ∑_{r} R(r) ∑_{u} U(u)W (r − u)

= ∑_{r} R(r) ∑_{u, w: u+w=r} U(u)W (w)

= |{u ∈ U, w ∈ W: u + w ∈ R}| = e_{CG_{n}^{+}(R)}[U, W]. (3.3)

Lema 31. Sejam R, U, W ⊂ ℤ_{n} com U ∩ W = ∅. Então

|e_{CG_{n}^{+}(R)}[U, W] − \frac{1}{n}|R||U||W || ≤ ( max_{j≠0} |T (R)(j)|)\sqrt{|U||W |}.  (3.4)

Prova. Temos

e_{CG_{n}^{+}(R)}[U, W] = ⟨R, U ∗ W ⟩ = \frac{1}{n}⟨T (R), T (U ∗ W)⟩

= \frac{1}{n} ∑_{j} T (R)(j)T (U ∗ W)(j) = \frac{1}{n} ∑_{j} T (R)(j)T (U)(j)T (W)(j)

= \frac{1}{n}|R||U||W | + \frac{1}{n} ∑_{j≠0} T (R)(j)T (U)(j)T (W)(j), (3.5)

e, por Cauchy-Schwarz,

|\frac{1}{n} ∑_{j≠0} T (R)(j)T (U)(j)T (W)(j)| ≤ \frac{1}{n}( max_{j≠0} |T (R)(j)|)||T (U)||_{2}||T (W)||_{2},

de onde segue o resultado, pois o lado direito da expressão acima é igual a max_{j≠0} |T (R)(j)|\sqrt{|U||W |}.

Agora iremos tratar do grafo de Chung-Graham com subtração.

Lema 32. Sejam R, U, W ⊂ ℤ_{n} com U ∩ W = ∅. Então

|e_{CG_{n}^{−}(R)}[U, W] − \frac{1}{n}|R ∪ (−R)||U||W || ≤ ( max_{j≠0} |T (R ∪ (−R))(j)|)\sqrt{|U||W |}.

(3.6)

Prova. Da equação 3.3 segue que

⟨R ∪ (−R), U ∗ (−W)⟩ = |{u ∈ U, w ∈ W: u − w ∈ R ∪ (−R)}|.

Portanto, e_{CG_{n}^{−}(R)}[U, W] = ⟨R∪(−R), U ∗(−W)⟩. Daqui em diante, a prova é análoga à do lema 31.

O próximo lema é o resultado principal desta seção. Ele mostra que a η-regularidade dos grafos de Chung-Graham está ligada aos coeficientes de Fourier de um conjunto apropriado.

Lema 33. Seja R ⊂ ℤ_{n}. Se max_{j≠0} |T (R)(j)| ≤ η^{2}|R|, o grafo CG_{n}^{+}(R) é η-regular com densidade |R|/n. Se max_{j≠0} |T (R∪(−R))(j)| ≤ η^{2}|R∪(−R)|, o grafo CG_{n}^{−}(R) é η-regular com densidade |R ∪ (−R)|/n.

Prova. Provaremos apenas a primeira asserção. Sejam U, W ⊂ ℤ_{n} com |U|, |W | ≥ ηn. Observe primeiramente que

max_{j≠0} |T (R)(j)| ≤ η^{2}|R| ≤ η \frac{|R|}{n}\sqrt{|U||W |}.

Logo,

max_{j≠0} |T (R)(j)|\sqrt{|U||W |} ≤ η \frac{|R|}{n}|U||W |,

e o resultado segue, pelo lema 31.

Para terminar, observe que, se d = pn e ( max_{j≠0} |T (R)(j)|)\sqrt{|U||W |} ≤

A\sqrt{d|U||W |}, então o grafo CG_{n}^{+}(R) é (p, A)-uniforme para p = |R|/n (veja a definição 25). Veja também que a condição acima equivale a termos

( max_{j≠0} |T (R)(j)|) ≤ A\sqrt{pn}.

3.3 O Lema de Regularidade de Szemerédi

Nesta seção, falaremos um pouco sobre o Lema de Regularidade de Szemerédi [35], comentaremos brevemente sua demonstração e daremos um exemplo de como o lema pode ser aplicado. Também enunciaremos uma extensão do lema, observada independentemente por Kohayakawa e Rödl (veja [23] ou [26]), apropriada para se lidar com grafos esparsos (isto é, grafos com quantidade subquadrática de arestas). É interessante notar que a primeira aparição do Lema de Regularidade na literatura foi em [34] (ainda em uma forma um pouco diferente de sua “forma final” de [35]), como ferramenta para a prova do Teorema de Szemerédi sobre inteiros em progressões aritméticas, que é o teorema 2 do capítulo 1.

Vamos relembrar a notação que usaremos. Ao longo da seção, G = G^{n} será um grafo com n vértices. Para U, W ⊂ V (G) com U ∩ W = ∅, escrevemos E(U, W) = E_{G}(U, W) para denotar o conjunto das arestas de G que ligam U a W. Colocamos e(U, W) = e_{G}(U, W) = |E_{G}(U, W)| e definimos a densidade do par (U, W), d(U, W), por d(U, W) = e_{G}(U, W)/(|U||W |). Note que 0 ≤ d(U, W) ≤ 1.

Na definição a seguir, vemos que um par (U, W) é Szemerédi-regular quando todo subgrafo “grande” (X, Y) de (U, W) tem quase a mesma densidade do par (U, W). Precisamente, temos:

Definição 34 (ε-Szemerédi-regularidade). Dados ε > 0, um grafo G e U, W ⊂ V (G) disjuntos, dizemos que o par (U, W) é ε-Szemerédi-regular se para todos X ⊂ U e Y ⊂ W com |X| ≥ ε|U| e |Y | ≥ ε|W |, temos

|d(X, Y) − d(U, W)| ≤ ε.

No que vem a seguir, trabalharemos sempre com um certo tipo especial de partições do conjunto de vértices de um grafo G.

Definição 35 (Partições equitáveis). Dizemos que uma partição P = (V_{i})_{i=0}^{k} de V = V (G) é (ε, k)-equitável se |V_{0}| ≤ εn e |V_{1}| = … = |V_{k}|. Dizemos que V_{0} é a classe excepcional de P.

Quando o valor de ε não for relevante, diremos simplesmente que P é k-equitável. Diremos também que P é equitável quando for k-equitável para algum k.

O Lema de Regularidade nos diz que para todo grafo G com n = |V (G)| grande, existe uma partição equitável de V (G) em um número “apropriado” de partes, V (G) = ∪_{j=0}^{k}V_{j}, tal que quase todos os pares (V_{i}, V_{j}) com 1 ≤ i < j ≤ k são Szemerédi-regulares.

Teorema 36 (Lema de Regularidade de Szemerédi). Para todos ε > 0 e m > 0, existem inteiros M = M(ε, m) e N = N(ε, m) tais que para todo grafo G com n ≥ N(ε, m) vértices, existe uma partição (ε, k)-equitável de V (G), V (G) = ∪_{j=0}^{k}V_{j}, com m ≤ k ≤ M(ε, m), e tal que no máximo εk^{2} dos pares (V_{i}, V_{j}) (1 ≤ i < j ≤ k) não são ε-Szemerédi-regulares.

Vamos explicar o papel de m e M no lema. Note que o resultado afirma algo sobre a distribuição das arestas entre os pares (V_{i}, V_{j}) com 1 ≤ i < j ≤ k, e não diz nada sobre as arestas que estão contidas em cada classe V_{i}. Assim, seria interessante se o número de arestas “internas” (ou seja, contidas em alguma classe) fosse (em proporção) muito pequeno. Isto é conseguido escolhendo-se um m suficientemente grande, pois o número de arestas “internas” é limitado por k\binom{n/k}{2} ∼ \binom{n}{2}/k ≤ \binom{n}{2}/m. Por outro lado, é essencial que o número de classes da partição seja limitado (k ≤ M) pois, por exemplo, a partição de V (G) em n classes com um único vértice em cada é trivialmente 0-Szemerédi-regular. De fato, a característica fundamental do Lema de Szemerédi é que o número de classes da partição é limitado e o limitante M não depende do grafo G.

Iremos agora rascunhar a demonstração do Lema de Regularidade. Embora a demonstração em [35] tenha apenas duas páginas, a prova do lema não pode ser considerada fácil; de fato, os argumentos em [35] estão extremamente condensados. Recomendamos fortemente a leitura das seções IV.5 e IV.6 de [3], onde são dadas uma prova menos concisa e mais “didática” do Lema de Regularidade, bem como algumas aplicações simples. A referência já clássica para quem deseja estudar com mais detalhes o Lema de Regularidade e suas consequências em teoria dos grafos é o survey de Komlós e Simonovits [27].

Vamos à “prova”. Para cada partição P de V (G), P = (V_{j})_{j=0}^{k}, definimos o índice de P, ind(P), por

ind(P) = \frac{1}{k^{2}} ∑_{1≤i<j≤k} (d(V_{i}, V_{j}))^{2} .

Como a soma contém \binom{k}{2} parcelas e cada uma delas está entre 0 e 1, é claro que sempre temos 0 ≤ ind(P) ≤ 1/2.

Se P e P̃ são partições equitáveis de V (G), diremos que P̃ refina P se toda classe não-excepcional de P̃ está inteiramente contida em uma classe não-excepcional de P. Dito isto, a idéia fundamental para provar o teorema 36 está contida no lema abaixo.

Lema 37. Seja G um grafo com n vértices, e seja P = (V_{j})_{j=0}^{k} uma partição (ε, k)-equitável de V (G). Se ε é tal que 4^{k} > 600ε^{−5} e mais de εk^{2} pares (V_{i}, V_{j}) (1 ≤ i < j ≤ k) não são ε-Szemerédi-regulares, então existe um refinamento P̃ = (Ṽ_{j})_{j=0}^{1+k4^{k}} de P tal que ind(P̃) ≥ ind(P) + ε^{5}/20, V_{0} ⊂ Ṽ_{0} e |Ṽ_{0} \ V_{0}| ≤ n/4^{k}.

Com este resultado, é fácil provar o teorema 36. Seja m_{0} o menor inteiro que satisfaz m_{0} ≥ m e 4^{m_{0}} > 600ε^{−5}. Começamos com uma partição (ε/2, m_{0})-equitável qualquer de V (G). Se esta partição tem no máximo εm_{0}^{2} pares Szemerédi-regulares, fim de prova; caso contrário, usando o lema acima, refinamos a partição inicial. Iteramos este processo até chegarmos à partição desejada. Isto ocorrerá em no máximo 10ε^{−5} iterações, pois cada iteração aumenta o índice em pelo menos ε^{5}/20, e por outro lado sabemos que o índice de uma partição é sempre menor ou igual a 1/2. Defina f : ℕ → ℕ por f(0) = m_{0} e f(t + 1) = 1 + f(t)4^{f(t)}. Então a partição final terá no máximo f(10ε^{−5}) classes (e portanto colocamos M = f(10ε^{−5})). É importante notar que o fato de a classe excepcional aumentar muito pouco a cada iteração também é crucial, pois a classe excepcional da partição final deve ter no máximo εn elementos (por definição de equitabilidade). Do lema acima segue que, se a classe excepcional inicial tem no máximo εn/2 elementos, então a classe excepcional da partição final tem no máximo

\frac{εn}{2} + \frac{n}{4^{m_{0}}} + \frac{n}{4^{f(m_{0})}} + \frac{n}{4^{f(f(m_{0}))}} + ⋯ ≤ \frac{εn}{2} + \frac{2n}{4^{m_{0}}} ,

e pela escolha de m_{0}, isto é no máximo \frac{ε}{2}n + \frac{ε^{5}}{300}n ≤ εn.

Na seção 3.4, veremos o Lema de Regularidade em ação, e com isso o leitor poderá sentir a grande força do resultado. No entanto, apesar de sua força, o Lema de Regularidade tem uma limitação importante: para grafos com quantidade subquadrática de arestas (e(G) = o(n^{2})) todo par (U, W) é Szemerédi-regular, e portanto o Lema de Szemerédi não nos dá nenhuma informação.

De fato, para todo X ⊂ U e Y ⊂ W com |X| ≥ ε|U| e |Y | ≥ ε|W |, temos

|d(X, Y) − d(U, W)| = |\frac{e(X, Y)}{|X||Y |} − \frac{e(U, W)}{|U||W |}| = |o(1) − o(1)| = o(1),

já que e(X, Y) e e(U, W) são o(n^{2}) enquanto que tanto |X||Y | como |U||W | são Ω(n^{2}). Lembramos que escrevemos f(n) = Ω(g(n)) se existir uma constante C > 0 tal que para todo n suficientemente grande, |f(n)| ≥ C|g(n)|. Em outras palavras, f(n) = Ω(g(n)) se e só se g(n) = O(f(n)).

Na seção 3.5, veremos uma variante “esparsa” do Lema de Szemerédi, que contorna parcialmente esta dificuldade.

3.4 Aplicando o Lema de Regularidade

Nesta seção, daremos uma aplicação do Lema de Regularidade de Szemerédi, para ilustrar seu mecanismo básico de uso.

Em muitas aplicações do Lema de Regularidade, começamos com um grafo qualquer G e a partir dele, construímos dois grafos especiais: o grafo reduzido de G e o grafo limpo de G. Vamos defini-los a seguir. Dados um grafo G, uma partição k-equitável P de V (G) e dois parâmetros ε > 0 e 0 ≤ d < 1, definimos o grafo reduzido de G (que denotaremos por R = R(G, P, ε, d)) por V (R) = [k] = {1, 2, …, k} e ij é aresta de R se e só se o par (V_{i}, V_{j}) é ε-Szemerédi-regular com densidade d(V_{i}, V_{j}) ≥ d. Definimos também o grafo limpo de G (que denotaremos por L(G, P, ε, d)) por V (L) = V (G) e e ∈ E(L) se e só se e ∈ E(G) e existem 1 ≤ i ≠ j ≤ k tais que e liga V_{i} a V_{j} e ij é aresta do grafo reduzido. Isto é, obtemos L a partir de G apagando arestas até restarem apenas as arestas que ligam pares ε-Szemerédi-regulares com densidade pelo menos d.

O grafo limpo de G é mais fácil de se lidar do que o grafo original G, e ele ainda contém a maior parte das arestas de G, se ε e d forem pequenos, e se k for grande. De fato, suponha que temos uma partição k-equitável P = (V_{j})_{j=0}^{k} dada pelo Lema de Regularidade aplicado com parâmetros ε e m = ⌈1/ε⌉, por exemplo. Seja n′ o tamanho de cada classe não-excepcional. Se e ∈ E(G)\E(L), há quatro casos: e está contida em algum V_{j} (j ≠ 0), e é incidente a V_{0}, e liga duas classes que formam um par ε-Szemerédi-irregular ou e liga duas classes que formam um par com densidade inferior a d. Assim, |E(G)\E(L)| ≤ k\binom{n′}{2}+εn^{2}+ε\binom{k}{2}n^{′2}+dn^{′2}\binom{k}{2}, e como temos n′ ≤ n/k segue que |E(G)\E(L)| ≤ \frac{1}{k} \binom{n}{2}+εn^{2} +εn^{2}/2+dn^{2}/2 ≤ \frac{1}{k} \binom{n}{2}+(2ε+ε+d)n^{2}/2 ≤ (\frac{1}{k} +4ε+d)\binom{n}{2}. Como escolhemos m = ⌈1/ε⌉, temos 1/k ≤ 1/m = 1/⌈1/ε⌉ ≤ ε. Assim, |E(G)\E(L)| é uma fração pequena de \binom{n}{2} (e, portanto, de e(G), já que assumimos implicitamente que e(G) = Ω(n^{2})), se ε e d forem pequenos e se m for grande.

A importância do grafo reduzido de G segue do fato que todo subgrafo de R com grau máximo “pequeno” é também subgrafo de G. Para formular isto mais precisamente, definiremos o grafo R(t) obtido a partir de R trocando-se cada vértice de R por t vértices independentes, e trocando cada aresta de R pelo grafo bipartido completo K_{t,t}. Com isso, enunciamos uma consequência muito interessante do Lema de Regularidade (para uma demonstração, veja [27]).

Teorema 38 (“Key Lemma”). Dados d > ε > 0, um grafo R e um inteiro positivo n′, construa um grafo G trocando cada vértice de R por n′ vértices, e trocando as arestas de R por pares ε-Szemerédi-regulares com densidade maior ou igual a d. Seja H um subgrafo de R(t) com h vértices e grau máximo Δ > 0, e seja ε_{0} = (d − ε)^{Δ}/(2 + Δ). Se ε ≤ ε_{0} e se t − 1 ≤ ε_{0}n′, então H ⊂ G.

Agora, usaremos o Lema de Szemerédi para dar uma prova bem curta (mas não muito detalhada) do famoso Teorema de Erdős, Stone e Simonovits.

Começaremos contextualizando o problema. Lembramos que o tamanho de um grafo G é seu número de arestas, e a ordem de G é o número de vértices de G. Dados grafos G e H, definimos ex(G, H) como o máximo tamanho de um subgrafo de G que não contém cópias de H. O problema é determinar ou estimar ex(G, H). Em 1941, Turán inaugurou a Teoria Extremal dos Grafos com seu histórico artigo [36] em que é determinado com exatidão o valor de ex(K_{n}, K_{p}), onde K_{t} é o grafo completo com t vértices. Abaixo, enunciamos uma versão levemente mais fraca do Teorema de Turán, mas que será mais adequada aos nossos propósitos.

Teorema 39 (Turán, 1941). Se G é um grafo com n vértices e mais de (1 − \frac{1}{p−1})n^{2}/2 arestas, então G contém uma cópia de K_{p}. Ou seja, ex(K_{n}, K_{p}) ≤ (1 − \frac{1}{p−1})n^{2}/2.

Mencionamos que no capítulo 29 de [1] são dadas 5 provas extremamente elegantes do Teorema de Turán.

Um passo natural então é trocar os grafos completos K_{p} por grafos gerais H e investigar ex(K_{n}, H), onde H é um certo grafo fixo. Em 1946, Erdős e Stone [8] realizaram um importante avanço nesta questão, ao provar o teorema abaixo. Definamos K_{p}(t, …, t) como o grafo p-partido completo em que cada classe tem t vértices.

Teorema 40 (Erdős e Stone, 1946). Se p ≥ 2 e t ≥ 1,

ex(K_{n}, K_{p}(t, …, t)) = (1 − \frac{1}{p − 1} + o(1)) \binom{n}{2}.

Em [7], Erdős e Simonovits observaram que o resultado acima implicava o teorema a seguir. Este resultado, que hoje é conhecido como o Teorema de Erdős, Stone e Simonovits, determina o comportamento assintótico de ex(K_{n}, H) para todo H.

Teorema 41 (Erdős, Stone e Simonovits, 1966). Seja χ(H) o número cromático de H. Então

ex(K_{n}, H) = (1 − \frac{1}{χ(H) − 1} + o(1)) \binom{n}{2}.

Vamos mostrar que o teorema 40 implica o teorema 41. Seja K(p, n) o grafo p-partido com n vértices, em que as classes C_{1}, C_{2}, …, C_{p} da p-partição satisfazem |C_{1}| ≤ |C_{2}| ≤ … ≤ |C_{p}| ≤ |C_{1}| + 1, e tal que e ∈ E(K(p, n)) se e só se e liga C_{i} a C_{j} para algum par (i, j) com i ≠ j. Uma conta simples mostra que e(K(p, n)) = (1 − \frac{1}{p} + o(1))\binom{n}{2}, e como para todo H e todo n temos H ⊄ K(χ(H) − 1, n), segue que

ex(K_{n}, H) ≥ e(K(χ(H) − 1, n)) = (1 − \frac{1}{χ(H) − 1} + o(1)) \binom{n}{2}. (3.7)

Por outro lado, pelo teorema 40, temos

ex(K_{n}, H) ≤ ex(K_{n}, K_{χ(H)}(|V (H)|, …, |V (H)|))

= (1 − \frac{1}{χ(H) − 1} + o(1)) \binom{n}{2}.

Iremos agora dar uma prova curta do teorema 40, via Lema de Regularidade.

Prova do teorema 40. Pela equação 3.7, vemos que é suficiente provarmos apenas a cota superior para ex(K_{n}, K_{p}(t …, t)). Fixe β > 0 e suponha que G é um grafo com n vértices (n suficientemente grande) e mais de (1 − \frac{1}{p−1} + β)\binom{n}{2} arestas. Tome d = β/2 e ε = (β/10)^{pt} e considere o grafo reduzido de G, R(G, P, ε, d), onde P = (V_{j})_{j=1}^{k} é uma partição k-equitável dada pelo Lema de Regularidade de Szemerédi aplicado a G com parâmetros ε e m = ⌈1/ε⌉. Considere também o grafo limpo de G, L(G, P, ε, d). É fácil ver que

\frac{e(R)}{k^{2}/2} ≥ \frac{e(L)}{n^{2}/2} > 1 − \frac{1}{p − 1}.

Logo, pelo Teorema de Turán, R contém uma cópia de K_{p}, e, pelo teorema 38, temos que G contém uma cópia de K_{p}(t, …, t), que é o que queríamos mostrar.

Um problema muito interessante que está em aberto é o de provar uma versão probabilística do teorema 41. Por exemplo, o teorema 41 nos diz que, para n grande, se fixarmos l ≥ 1 e pegarmos um pouco mais da metade das arestas de K_{n}, teremos necessariamente uma cópia de um circuito de comprimento 2l + 1, C^{2l+1}. Uma pergunta natural é: “É verdade que, com probabilidade tendendo a 1 quando n → ∞, se pegarmos um pouco mais da metade das arestas do grafo aleatório G_{n,p}, teremos obrigatoriamente uma cópia de C^{2l+1}?” Veremos no próximo capítulo que isso vale, se p = p(n) ≥ Cn^{−1+1/2l}, onde C é uma constante grande.

De modo geral, a questão é investigar ex(G_{n,p}, H). Seria interessante se tivéssemos um teorema do tipo “se p = p(n) é suficientemente grande, então quase todo G_{n,p} satisfaz ex(G_{n,p}, H) ≤ (1 − \frac{1}{χ(H)−1} + o(1)) e(G_{n,p})”, mas até o momento, resultados deste tipo só foram provados para alguns grafos H. Este problema, intitulado “Problema de Turán para grafos aleatórios”, tem atraído considerável atenção nos últimos anos. Segundo Janson, Łuczak e Ruciński, “trata-se de um dos mais importantes problemas em aberto na área de grafos aleatórios” ([22], capítulo 8). O enunciado preciso do problema foi formulado por Kohayakawa, Łuczak e Rödl em [25].

Haxell, Kohayakawa e Łuczak resolveram o problema quando H é um circuito [18, 19] (No próximo capítulo, veremos detalhadamente alguns dos métodos usados em [19], pois eles serão empregados para provar uma versão probabilística do Teorema de Schur). Em [25], Kohayakawa, Łuczak e Rödl resolveram o caso H = K_{4}. Recentemente, Gerke, Schickinger e Steger [13] resolveram o caso H = K_{5}. Todos os artigos acima citados usaram alguma variante esparsa do Lema de Regularidade. Estas variantes são o assunto da próxima seção.

3.5 A versão esparsa do Lema de Regularidade

Em meados da década de 90, Y. Kohayakawa e V. Rödl descobriram independentemente versões esparsas do Lema de Regularidade [23, 26]. Enunciaremos aqui apenas uma dessas versões, e a empregaremos na seção 4.1.

Nas definições abaixo, G será um grafo e U e W serão sempre subconjuntos disjuntos de V (G) com u = |U| e w = |W |.

Definição 42 (Densidade relativa d_{H,G}(U, W)). Seja H um subgrafo de G com V (H) = V (G). Definimos d_{H,G}(U, W) por

d_{H,G}(U, W) = \begin{cases}e_{H}(U, W)/e_{G}(U, W) & se e_{G}(U, W) > 0, \\ 0 & se e_{G}(U, W) = 0. \end{cases}

Definição 43 (Pares (ε, H, G)-regulares). Fixe ε > 0. Dizemos que o par (U, W) é (ε, H, G)-regular se para todos U′ ⊂ U e W′ ⊂ W com |U′| ≥ ε|U| e |W′| ≥ ε|W | temos

|d_{H,G}(U′, W′) − d_{H,G}(U, W)| ≤ ε.

Definição 44 (Partições (ε, H, G)-regulares). Seja P = (V_{i})_{i=0}^{k} uma partição (ε, k)-equitável de V = V (G). Dizemos que P é (ε, H, G)-regular se no máximo ε\binom{k}{2} pares (V_{i}, V_{j}) (com 1 ≤ i < j ≤ n) não são (ε, H, G)- regulares.

Agora podemos enunciar o resultado de Kohayakawa e Rödl, que é uma extensão do Lema de Regularidade de Szemerédi.

Teorema 45 (Kohayakawa, Rödl). Dados ε > 0 e k_{0} ≥ 1, existem constantes η = η(ε, k_{0}) e K_{0} = K_{0}(ε, k_{0}) ≥ k_{0} que dependem somente de ε e k_{0} tais que, se G é um grafo η-regular e H é um subgrafo de G com V (H) = V (G), então existe uma partição de V = V (G) que é (ε, k)-equitável e (ε, H, G)-regular, com k_{0} ≤ k ≤ K_{0}.

A prova deste resultado segue bem de perto a prova do Lema de Regularidade original, e por isso não faremos maiores comentários sobre ela. Note também que se tomarmos G = K_{n}, o grafo completo com n vértices, recuperamos o Lema de Szemerédi original.

Recomendamos a leitura de [23] para os interessados em conhecer algumas aplicações da versão esparsa do Lema de Regularidade. Além de estar se mostrando uma ferramenta útil no ataque ao Problema de Turán para grafos esparsos (veja a seção anterior), mencionamos que a versão esparsa do Lema de Szemerédi foi empregada na prova do teorema 6, e também foi útil para se encontrar um novo critério de quasi-aleatoriedade para grafos [26]. Por sua vez, deste novo critério segue imediatamente o seguinte fato: existe um algoritmo que verifica se um grafo com n vértices é quasi-aleatório (no sentido de Chung, Graham e Wilson [6]) em tempo O(n^{2}). Isto é surpreendente, pois o tempo de leitura de grafo já é quadrático na entrada. O melhor algoritmo conhecido até então levava tempo O(n^{2,376}).

Uma versão probabilística do Teorema de Schur

Nosso principal objetivo neste capítulo é provar o teorema 13. Isto será feito na seção 4.2. Na seção 4.1, provaremos o lema dos pares proibidos, um resultado auxiliar muito importante na prova. A seção final, 4.3, é dedicada ao enunciado de uma conjectura que, se verdadeira, nos permitiria resolver o problema 12. Discutimos também uma variante do problema.

Ao longo de todo o capítulo, usaremos a seguinte definição. Uma função A : ℕ → ℝ^{+} é uma A-função se existe uma constante c > 0 tal que, para todo n, 1 ≤ A(n) ≤ c\sqrt{log n}.

4.1 O lema dos pares proibidos

Nesta seção, falaremos um pouco sobre o que é feito em [19], com forte ênfase no resultado que chamaremos de lema dos pares proibidos. Começamos com algumas definições. Escrevemos G = G^{n} para dizer que G é um grafo com n vértices, e denotaremos o circuito de comprimento l por C^{l}. Mais precisamente, um circuito de comprimento l em G é um conjunto de l vértices de G distintos, {v_{1}, …, v_{l}}, tais que para todo i ∈ ℤ_{l}, v_{i}v_{i+1} ∈ E(G).

Para 0 < γ < 1 e grafos G, H, escrevemos G →_{γ} H se em qualquer subconjunto de arestas de G com cardinalidade maior que γe(G) há uma cópia de H. O principal resultado de [19] é o seguinte.

Teorema 46 (Haxell, Kohayakawa e Łuczak, 1996). Para todo 0 < η < 1/2 e todo inteiro positivo l, existe uma constante C = C(η, l) > 0 tal que quase todo grafo G_{n,p} com p = p(n) ≥ Cn^{−1+1/2l} satisfaz G_{n,p} →_{1/2+η} C^{2l+1}.

Ou seja, os autores resolveram o Problema de Turán para grafos aleatórios no caso em que H é um circuito ímpar. O teorema acima prova que, desde que p = p(n) seja suficientemente grande (ou “vá a zero suficientemente devagar”), então quase certamente ex(G_{n,p}, C^{2l+1}) ≤ (1/2+η)e(G_{n,p}). Como sempre, ao dizer que quase todo grafo G_{n,p} tem a propriedade Q, queremos dizer que lim_{n→∞} ℙ((G_{n,p} tem a propriedade Q) = 1.

Na demonstração do nosso teorema 13, usaremos não apenas o principal lema de [19] (o lema dos pares proibidos) como também as idéias da prova do teorema 46.

O lema dos pares proibidos é a principal ferramenta na demonstração do teorema 46. Nesta seção, nosso principal objetivo é provar este lema.

Começaremos definindo o grafo dos pares proibidos. Dado um grafo H e um inteiro l ≥ 1, vamos definir o grafo J = J(H) = J_{l}(H) em V (H) ligando dois vértices x, y ∈ V (H) em J se e só se existir um caminho entre x e y de comprimento 2l, em H. Mais precisamente, ligamos x a y em J_{l}(H) se e só se existirem vértices v_{1}, v_{2}, …, v_{2l−1} distintos tais que as arestas xv_{1}, v_{1}v_{2}, …, v_{2l−1}y estão todas em H. Esse grafo será extremamente importante, e será chamado de grafo dos pares proibidos. Suponha que estamos interessados em grafos H que não possuem circuitos C^{2l+1}, e suponha que xy é um par proibido por H. Então, não pode haver aresta em H ligando x a y, ou então fecharíamos um circuito de comprimento 2l + 1 em H. Daí vem o nome “pares proibidos”.

Podemos agora enunciar o lema dos pares proibidos. Fixe constantes reais C > 0 e 0 < γ_{0} ≤ 1. Fixe uma A-função A = A(n) e suponha que G = G^{n} é um grafo (p, A)-uniforme, onde p = p(n) ≥ CA^{2}n^{−1+1/2l}, e seja H um subgrafo de G com pelo menos γ_{0}e(G) arestas. O lema abaixo diz que e(J_{l}(H)) é quase tão grande quanto (e(H)/e(G))\binom{n}{2}, se C e n forem suficientemente grandes.

Lema 47 (Lema dos pares proibidos). São dados um inteiro l ≥ 1, reais 0 < δ ≤ 1, 0 < γ_{0} ≤ 1, e uma A-função A = A(n). Existe uma constante C_{0} = C_{0}(l, δ, γ_{0}) > 0 tal que vale o seguinte. Seja G = G^{n} um grafo (p, A)-uniforme com p = p(n) ≥ C_{0}A^{2}n^{−1+1/2l}, e seja H ⊂ G um subgrafo de G com e(H) ≥ γ_{0}e(G). Então, se n for suficientemente grande, temos e(J_{l}(H)) ≥ (1 − δ)(e(H)/e(G))\binom{n}{2}.

Há dois ingredientes importantes na prova do lema 47: a versão esparsa para o lema de regularidade de Szemerédi (teorema 45) e o lema 48 que veremos a seguir. Seja H = H^{k} um grafo com k vértices, e suponha que γ̄ = (γ_{e})_{e∈H} é uma família de pesos 0 ≤ γ_{e} ≤ 1 nas arestas e ∈ E(H) de H. Para x ∈ V (H), seja Γ(x) o conjunto dos vértices vizinhos de x em H. Dados vértices x, y ∈ V (H), não necessariamente distintos, seja Z_{x,y} = Γ_{H}(x) ∩ Γ_{H}(y) o conjunto dos vizinhos comuns de x e y, e defina

w(x, y) = w_{H,γ̄}(x, y) = \begin{cases}0 & se Z_{x,y} = ∅, \\ max\{γ_{zy}: z ∈ Z_{x,y}\} & se Z_{x,y} ≠ ∅. \end{cases}

Para x ∈ V (H), defina o γ̄-grau de x, dγ̄(x), por dγ̄(x) = d^{H,γ̄}(x) = ∑_{y∈Γ_{H}(x)} γ_{xy}. Seja γ̄(H) = ∑_{e∈E(H)} γ_{e}. Fixada uma ordenação χ = (x_{1}, …, x_{k}) dos vértices de H, definimos w(H, γ̄, χ) = ∑_{1≤i≤j≤k} w(x_{i}, x_{j}). Dizemos que uma ordenação χ = (x_{1}, …, x_{k}) dos vértices de H respeita γ̄ se, para todo 1 ≤ i ≤ k, o vértice x_{i} é um vértice de γ̄_{i}-grau mínimo em H_{i} = H[x_{i}, …, x_{k}], o subgrafo de H induzido por x_{i}, …, x_{k}, onde γ̄_{i} = (γ_{e})_{e∈E(H_{i})}. Note que uma tal ordenação sempre existe: ache primeiro x_{1}, depois x_{2}, etc. Agora podemos enunciar um dos ingredientes para a prova do lema dos pares proibidos.

Lema 48. Seja H = H^{k} um grafo com k vértices e sem laços, e suponha que é dada uma família de pesos γ̄ = (γ_{e})_{e∈H} com 0 ≤ γ_{e} ≤ 1. Se χ = (x_{1}, …, x_{k}) é uma ordenação dos vértices de H que respeita γ̄, então w(H, γ̄, χ) ≥ γ̄(H).

Prova. Provaremos o resultado por indução em k. Se k = 1, não há nada para provar. Suponha agora k ≥ 2, e assuma que o lema já foi provado para valores menores de k. Considere H_{2} = H[x_{2}, …, x_{k}] e γ̄_{2} = (γ_{e})_{e∈E(H_{2})}. Obviamente, χ_{2} = (x_{2}, …, x_{k}) é uma ordenação dos vértices de H_{2} que respeita γ̄_{2}, e por indução segue que w(H_{2}, γ̄_{2}, χ_{2}) ≥ γ̄_{2}(H_{2}). Se Γ_{H}(x_{1}) = ∅, temos w(H, γ̄, χ) = w(H_{2}, γ̄_{2}, χ_{2}) ≥ γ̄_{2}(H_{2}) = γ̄(H). Por outro lado, se Γ_{H}(x_{1}) ≠ ∅, tomamos um elemento qualquer z ∈ Γ_{H}(x_{1}). Pela hipótese sobre a ordenação χ, temos d^{H,γ̄}(z) ≥ d^{H,γ̄}(x_{1}), e portanto

w(H, γ̄, χ) ≥ w(H_{2}, γ̄_{2}, χ_{2}) + ∑_{y∈Γ_{H}(z)} w(x_{1}, y)

≥ γ̄_{2}(H_{2}) + ∑_{y∈Γ_{H}(z)} γ_{zy} = γ̄_{2}(H_{2}) + d^{H,γ̄}(z) ≥ γ̄_{2}(H_{2}) + d^{H,γ̄}(x_{1})

= γ̄(H),

como queríamos.

O lema 50 é o ponto chave para provar o lema dos pares proibidos. Para descrevê-lo, sejam l ≥ 1 um inteiro e C, ε, μ > 0 reais positivos. Fixe uma A-função A = A(n), e fixe também reais 0 < ρ ≤ γ ≤ 1. Seja G = G^{n} um grafo (p, A)-uniforme com p = p(n) ≥ CA^{2}n^{−1+1/2l}, e seja H um subgrafo de G com V (H) = V (G). São dados três conjuntos dois a dois disjuntos V_{1}, V_{2}, V_{3} ⊂ V = V (G), com |V_{i}| = m ≥ μn (i = 1, 2, 3) e tais que os pares (V_{1}, V_{2}) e (V_{2}, V_{3}) são (ε, H, G)-regulares com d_{1,2} = d_{H,G}(V_{1}, V_{2}) ≥ ρ e d_{2,3} = d_{H,G}(V_{2}, V_{3}) ≥ γ. Basicamente, o lema 50 afirma que o grafo dos pares proibidos, J_{l}(H), é tal que e_{J_{l}}(V_{1}, V_{3}) é quase tão grande como γm^{2}, desde que C e n sejam grandes, e ε seja suficientemente pequeno.

Na prova do lema 50, usaremos as seguintes definições. Seja J um grafo bipartido com bipartição V (J) = X ˙∪Y. Dizemos que J é (b, f)-expansor se para todo U ⊂ V (J) com |U| ≤ b e tal que U ⊂ X ou U ⊂ Y, temos que |Γ_{J}(U)| ≥ f|U|, onde Γ_{J}(U) = ∪_{u∈U}Γ_{J}(u) e Γ_{J}(u) é o conjunto dos vizinhos de u no grafo J. Se G é um grafo e U, W ⊂ V (G), U ∩W = ∅, então G[U, W] será o grafo bipartido com vértices U ˙∪W e arestas E_{G}(U, W).

O seguinte lema será necessário para provar o lema 50. A versão esparsa do Lema de Regularidade é usada em sua demonstração.

Lema 49. Sejam 0 < ε ≤ 1/5 e 0 < ρ ≤ 1 reais dados, e suponha que 0 < η ≤ ε/8. Seja G = G^{n} um grafo com n vértices, η-uniforme com densidade 0 < p ≤ 1, e seja H um subgrafo de G com V (H) = V (G). Suponha que, para (i, j) = (1, 2) e (i, j) = (2, 3), temos que (V_{i}, V_{j}) é um par (ε, H, G)- regular com d_{i,j} = d_{H,G}(V_{i}, V_{j}) ≥ ρ. Suponha também que |V_{i}| ≥ (η/ε)n para i ∈ {1, 2, 3}. Então, existem conjuntos V′_{i} ⊂ V_{i} (i ∈ {1, 2, 3}) tais que

|Γ_{H}(x) ∩ V′_{j}| ≥ (1 − 5ε/ρ)d_{i,j}e_{G}(V_{i}, V_{j})/|V_{i}|

para todos (i, j) ∈ {(1, 2), (2, 1), (2, 3), (3, 2)} e todo x ∈ V′_{i}. Além disso, temos que |V′_{i}| ≥ (1 − 2ε)|V_{i}| para i ∈ {1, 2, 3}.

Prova. A prova é muito similar à prova do lema 3.2 de [17], e por isso não a daremos aqui.

Lema 50. São dados um inteiro l ≥ 1, reais C > 0, 0 < δ ≤ 1, 0 < μ ≤ 1 e 0 < ρ ≤ γ ≤ 1. Fixe uma A-função A = A(n), e sejam G, H e J_{l}(H) grafos como os descritos antes do lema 49. Então, se C ≥ C_{0} = 32/(δρμ)^{2} e 0 < ε ≤ ε_{0} = δρ/24, temos e(J_{l}[V_{1}, V_{3}]) ≥ (1 − δ)γm^{2}, desde que n seja suficientemente grande.

Prova. Assumimos que n é grande, e, em particular, temos que G é ηuniforme para η = εμ (veja o lema 26). Se G é um grafo, escrevemos δ(G) para denotar o grau mínimo entre os vértices de G. A prova do lema 50 segue de três fatos.

Fato 1 Existem conjuntos V′_{i} ⊂ V_{i} com |V′_{i}| ≥ (1 − 2ε)m (i = 1, 2, 3) tais que H_{1,2} = H[V′_{1}, V′_{2}] e H_{2,3} = H[V′_{2}, V′_{3}] têm grau mínimo δ(H_{1,2}) ≥ (1 − δ/4)d_{1,2}pm e δ(H_{2,3}) ≥ (1 − δ/4)d_{2,3}pm

Prova. Este fato segue do lema 49.

Fato 2 Para (i, j) = (1, 2) e (i, j) = (2, 3), o grafo bipartido H_{i,j} = H[V′_{i}, V′_{j}] é ((1 − δ/2)d_{i,j}m/f, f)-expansor para todo 0 < f ≤ (δρμ/4A)^{2}d.

Prova. Fixe (i, j) ∈ {(1, 2), (2, 3)} e σ ∈ {i, j}, e suponha que 0 < f ≤ (δρμ/4A)^{2}d. Tome U ⊂ V′_{σ} com u = |U| ≤ (1 − δ/2)d_{i,j}m/f e seja W = Γ_{H_{i,j}}(U). Suponha por absurdo que w = |W | < fu. Então, pelo fato 1 e pela (p, A)-uniformidade de G, temos

(1 − \frac{δ}{4}) d_{i,j}pmu ≤ e_{H_{i,j}}(U, W) ≤ e_{G}(U, W)

≤ puw + A(duw)^{1/2} ≤ (1 − \frac{δ}{2}) d_{i,j}pmu + A(duw)^{1/2}.

Logo (δ/4)d_{i,j}pmu ≤ A(duw)^{1/2}, e portanto w ≥ (δρμ/4A)^{2}du ≥ fu, o que é uma contradição. Logo |Γ_{H_{i,j}}(U)| ≥ f|U|, como queríamos.

Fato 3 Para todo x ∈ V′_{1}, temos |Γ_{J_{l}}(x) ∩ V′_{3}| ≥ (1 − 3δ/4)γm.

Prova. Note que d = pn = CA^{2}n^{1/2l}, e portanto H_{1,2} e H_{2,3} são ((1 − δ/2)d_{i,j}m/f, f)-expansores para 0 < f ≤ 2n^{1/2l}. Agora, fixe x ∈ V′_{1}, e seja X_{0} = {x}. Escolha conjuntos X_{1}, X_{2}, …, X_{2l−1} tais que n^{i/2l} ≤ |X_{i}| ≤ 2n^{i/2l} para 1 ≤ i ≤ 2l − 1, e X_{1} ⊂ Γ_{H_{1,2}}(X_{0}), X_{2} ⊂ Γ_{H_{1,2}}(X_{1}) \ X_{0},…, X_{2l−1} ⊂ Γ_{H_{1,2}}(X_{2l−2}) \ (X_{1} ∪ … ∪ X_{2l−3}). Finalmente, seja X_{2l} = Γ_{H_{2,3}}(X_{2l−1}). O resultado segue do fato 2.

O lema 50 segue dos fatos 1 e 3, pois e(J_{l}[V_{1}, V_{3}]) ≥ (1 − 3δ/4)γm|V′_{1}| ≥ (1 − δ)γm^{2}.

Agora podemos provar o lema 47, dos pares proibidos.

Demonstração do lema 47. Fixe um inteiro l ≥ 1, e fixe também reais 0 < δ ≤ 1, 0 < γ_{0} ≤ 1, além de uma A-função A = A(n). Pela natureza do parâmetro δ, podemos assumir que δ ≤ 15γ_{0}. Seja ε = γ_{0}δ^{2}/2160 e k_{0} = ⌈1/ε⌉, e sejam 0 < η = η(ε, k_{0}) ≤ 1 e K_{0} = K_{0}(ε, k_{0}) ≥ k_{0} valores encontrados via teorema 45 (versão esparsa do lema de Szemerédi). Note que podemos assumir que η ≤ ε/(2K_{0}). Seja ρ = γ_{0}δ/15 ≤ 1, e, finalmente, seja C_{0} = C_{0}(l, δ, γ_{0}) = 10^{7}(K_{0}/δ^{2}γ_{0})^{2}. Mostraremos que esta escolha de C_{0} é apropriada para o lema.

Sejam então H um subgrafo de um grafo (p, A)-uniforme G = G^{n} com γ = e(H)/e(G) ≥ γ_{0} e p = p(n) ≥ C_{0}A^{2}n^{−1+1/2l}. Podemos assumir que V (H) = V (G), e que n é maior que uma certa constante grande, adequadamente escolhida. Pelo lema 26, temos que G é η-regular com densidade p. Aplicamos agora o teorema 45 a H ⊂ G para obter uma partição P = (V_{i})_{i=0}^{k} de V = V (G) que é (ε, H, G)-regular e (ε, k)-equitável, com k_{0} ≤ k ≤ K_{0}. Seja m = |V_{i}| (1 ≤ i ≤ k). Note que m ≥ n(1 − ε)/k.

Usaremos agora as idéias de grafo reduzido e grafo limpo, adaptadas ao contexto da versão esparsa do Lema de Regularidade. Seguiremos a notação de [19], usando H^{∗} para o grafo reduzido, e H′ para o grafo limpo. Definimos o grafo reduzido H^{∗} por V (H^{∗}) = [k] e ij ∈ E(H^{∗}) (1 ≤ i < j ≤ k) se e só se (V_{i}, V_{j}) é um par (ε, H, G)-regular com d_{H,G}(V_{i}, V_{j}) ≥ ρ. Para e = ij ∈ E(H^{∗}), seja γ_{e} = d_{H,G}(V_{i}, V_{j}), e seja γ̄ = (γ_{e})_{e∈E(H^{∗})}. Podemos supor que χ = (1, 2, …, k) é uma ordenação que respeita γ̄. Por último, definimos um grafo H′ ⊂ H com V (H′) = V (H) e tal que xy ∈ E(H) é aresta de H′ se e só se x ∈ V_{i} e y ∈ V_{j} para algum par {i, j} com 1 ≤ i < j ≤ k e ij ∈ E(H^{∗}). Mostraremos que, a exemplo do que ocorre na versão original do Lema de Regularidade, o grafo limpo H′ ainda tem grande parte das arestas de H. Note que o número de arestas de H é e(H) = γe(G) ∼ γp\binom{n}{2}.

Fato 1 Temos e(H′) ≥ (1 − δ/6)γp\binom{n}{2}.

Prova. Estimaremos |E(H) \ E(H′)|. Da (p, A)-uniformidade de G e dos lemas 26 e 28, segue que, para todo W ⊂ V (G) com |W | ≥ 3ηn, temos e(G[W]) ≤ (1 + η)p\binom{|W |}{2}, se n é suficientemente grande. Logo e(H[V_{0}]) ≤ ε^{2}pn^{2}.

Além disso, escrevendo como sempre d = pn, temos

e_{G}(V_{0}, V \ V_{0}) ≤ p|V_{0}||V \ V_{0}| + A\sqrt{d|V_{0}||V \ V_{0}|} ≤ εpn^{2} + An\sqrt{d} ≤ 2εpn^{2}

para n suficientemente grande. Note que ∑ e_{G}(V_{i}, V_{j}) com a soma sobre todos os 1 ≤ i < j ≤ k tais que (V_{i}, V_{j}) não é (ε, H, G)-regular é no máximo ε\binom{k}{2}(1 + η)pm^{2} ≤ εpn^{2}. Já a soma ∑ e_{H}(V_{i}, V_{j}) sobre todos os 1 ≤ i < j ≤ k tais que d_{H,G}(V_{i}, V_{j}) ≤ ρ é no máximo ρ\binom{k}{2}(1 + η)pm^{2} ≤ ρpn^{2}. Para n suficientemente grande, temos que ∑_{1≤i≤k} e(G[V_{i}]) ≤ k(1 + η)p\binom{m}{2} ≤ pn^{2}/k. Portanto |E(H) \ E(H′)| ≤ (4ε + ρ + 1/k)pn^{2} ≤ (5ε + ρ)pn^{2} se n é suficientemente grande. Por outro lado, temos e(H) = γe(G) ≥ γ(1−η)p\binom{n}{2}, e então segue que

e(H′) ≥ γ(1 − η)p\binom{n}{2} − 2(6ε + ρ)p\binom{n}{2} = (1 − η − 12\frac{ε}{γ} − 2\frac{ρ}{γ} ) γp\binom{n}{2}

≥ (1 − \frac{δ}{6}) γp\binom{n}{2}.

Aplicaremos agora o lema 48 a (H^{∗}, γ̄). Como no lema 48, seja γ̄(H^{∗}) = ∑_{e∈E(H^{∗})} γ_{e}.

Fato 2 Temos γ̄(H^{∗}) ≥ (1 − δ/2)γk^{2}/2.

Prova. Esta afirmação segue facilmente do fato 1. Note que

(1 − \frac{δ}{6}) γp\binom{n}{2} ≤ e(H′) = ∑_{e=ij∈E(H^{∗})} e_{H}(V_{i}, V_{j})

= ∑_{e=ij∈E(H^{∗})} γ_{e}e_{G}(V_{i}, V_{j}) ≤ (1 + η)pm^{2}γ̄(H^{∗}) ≤ (1 + η)p\frac{n^{2}}{k^{2}} γ̄(H^{∗}).

Logo

γ̄(H^{∗}) ≥ \frac{1 − δ/6}{1 + η} (1 − \frac{1}{n}) γ \frac{k^{2}}{2} ≥ (1 − \frac{δ}{2}) γ \frac{k^{2}}{2} .

Finalmente, mostraremos que e(J_{l}(H)) ≥ (1 − δ)γ\binom{n}{2}. Fixe 1 ≤ i < j ≤ k. Pelo lema 50, aplicado com δ/6, temos que e(J_{l}[V_{i}, V_{j}]) ≥ (1 − δ/6)w(i, j)m^{2}, onde w(i, j) = w_{H^{∗},γ̄}(i, j) foi definido antes do lema 48. Segue do fato 2 e do lema 48 que

e(J_{l}(H)) ≥ ∑_{1≤i<j≤k} e(J_{l}[V_{i}, V_{j}])

≥ (1 − \frac{δ}{6}) m^{2} (w(H^{∗}, γ̄, x) − ∑_{1≤i≤k} w(i, i))

≥ (1 − \frac{δ}{6}) m^{2}γ̄(H^{∗}) − km^{2} ≥ \frac{1}{2} (1 − \frac{2δ}{3} ) γk^{2}m^{2} − \frac{n^{2}}{k}

≥ \frac{1}{2}(1 − ε)^{2} (1 − \frac{2δ}{3} ) γn^{2} − εn^{2} ≥ (1 − δ)γ\binom{n}{2},

como queríamos.

4.2 O teorema Schur(η)

Nosso objetivo nesta seção é provar o teorema 13. Vamos lembrar algumas definições dadas na seção 1. Dizemos que S ⊂ ℤ_{n} tem a propriedade Schur(η) se todo D ⊂ S com |D| ≥ (1/2+η)|S| contém uma tripla de Schur. Lembramos que ℤ_{n,p} é um subconjunto aleatório de ℤ_{n} obtido por n sorteios independentes com probabilidade p.

Vamos agora discutir os parâmetros do enunciado do problema 12. Em primeiro lugar, observa-se que ao tratarmos da propriedade PA_{3} (teorema 6), a densidade pode ser qualquer η > 0, enquanto que no problema 12 impomos a condição de que a densidade deve ser maior que 1/2. O motivo disso é o seguinte. Fixe n par. Para pelo menos metade dos conjuntos ℤ_{n,p}, vale que a quantidade de elementos ímpares é maior ou igual à quantidade de elementos pares (note que como n é par, podemos de fato falar em paridade em ℤ_{n}). Se exigirmos apenas que |D| = (1/2)|ℤ_{n,p}|, o enunciado do teorema tornase falso, pois para cada um dos ℤ_{n,p} com mais ímpares que pares descritos acima, podemos tomar D como sendo os elementos ímpares de ℤ_{n,p} (logo |D| ≥ (1/2)|ℤ_{n,p}|), e não haverá solução em D da equação de Schur pois a soma de dois ímpares em ℤ_{n} (n par) dá sempre par. Assim, a probabilidade de ℤ_{n,p} ter a propriedade Schur(η) para η = 0 é no máximo 1/2. Mesmo quando n é ímpar, não podemos permitir que a densidade seja qualquer real positivo; de fato, como ficará claro quando falarmos sobre a generalização deste problema para grupos abelianos finitos, a densidade sempre deverá ser um pouco maior que 2/7.

Agora falemos sobre a probabilidade p = p(n). Vamos mostrar que se p(n)/n^{−1/2} → 0 quando n → ∞, então quase certamente ℤ_{n,p} não tem a propriedade Schur(η). De fato, existem n^{2} triplas (x, y, z) de ℤ_{n} que satisfazem x + y = z (uma tripla assim é dita uma tripla de Schur), e, em média, p^{3}n^{2} delas são tais que x, y, z ∈ ℤ_{n,p}. Devido à hipótese imposta sobre p, temos que o número esperado de triplas de Schur em ℤ_{n,p}, n^{2}p^{3}, é muito menor que np, o tamanho esperado de ℤ_{n,p}. Assim, para quase todo ℤ_{n,p}, podemos apagar no máximo o(|ℤ_{n,p}|) pontos de ℤ_{n,p} destruindo todas as triplas de Schur contidas em ℤ_{n,p}. Daí segue que, com probabilidade tendendo a 1 quando n → ∞, ℤ_{n,p} não tem a propriedade Schur(η).

Usaremos a seguir os conceitos de par proibido e elemento proibido. Vimos na seção anterior que um par proibido por H, ou, mais precisamente, um par l-proibido por H, é simplesmente um par {x, y} tal que xy ∈ E(J_{l}(H)). Ao longo desta seção, por “par proibido” entenda-se sempre “par 1-proibido”. Ou seja, {x, y} é um par proibido por H se existe z ∉ {x, y} tal que xz, zy ∈ E(H).

Se D ⊂ ℤ_{n}, dizemos que x ∈ ℤ_{n} é um elemento proibido por D, e que D proíbe x, se x ∈ (D − D) = {d_{1} − d_{2} : d_{1}, d_{2} ∈ D}. O nome “elemento proibido” vem da seguinte observação. Se D não contém triplas de Schur, então D ∩ (D − D) = ∅. De fato, se temos x ∈ D ∩ (D − D), então x ∈ D escreve-se como z − y com y, z ∈ D, e portanto x + y = z, absurdo. Logo, um elemento proibido por D não pode estar em D, se D não tem triplas de Schur.

Vamos agora dar algumas palavras sobre os próximos lemas. O lema 51 serve para mostrar que o grafo CG(ℤ_{n,p}) = CG_{n}^{+}(ℤ_{n,p}) é quase certamente (p, A)-uniforme (neste capítulo, estaremos sempre nos referindo ao grafo de Chung-Graham com adição). Isso será importante para podermos usar o lema dos pares proibidos na nossa demonstração. O lema 52 afirma, grosso modo, que se D ⊂ R ⊂ ℤ_{n}, então e(CG_{n}(D))/e(CG_{n}(R)) ≥ |D|/|R|. O lema 53 servirá para converter pares proibidos pelo grafo CG(D) em elementos proibidos por D. Finalmente, todos esses lemas serão usados para provar o principal resultado auxiliar da seção, o lema dos elementos proibidos (lema 54). Grosso modo, este lema nos diz que se B ⊂ ℤ_{n,p} e |B|/|ℤ_{n,p}| = γ_{0}, então quase certamente B proíbe pelo menos γ_{0}n elementos de ℤ_{n}. Vamos agora aos lemas.

O lema a seguir é o “ponto fraco” da nossa demonstração. É por causa dele que só conseguimos provar o teorema 13, em vez de resolver o problema 12. Nós só conseguimos mostrar que CG(ℤ_{n,p}) é (p, A)-uniforme para A = \sqrt{24 log n}. O ideal (veja a próxima seção) seria provar isto para A igual a uma constante.

Lema 51. Para todo p = p(n), temos quase certamente que CG(ℤ_{n,p}) = CG_{n}(ℤ_{n,p}) é (p, A)-uniforme para A = \sqrt{24 log n}.

Prova. Daqui em diante, usaremos as letras especiais ℙ e 𝔼 para denotar probabilidade e esperança, respectivamente. Lembrando que o grafo CG_{n}^{+}(R) é (p, A)-uniforme se max_{j≠0} |T (R)(j)| ≤ A\sqrt{pn}, o lema seguirá facilmente do fato abaixo.

Fato Para todo j ≠ 0 e 0 < t ≤ pn\sqrt{2}/2, temos ℙ(|T (ℤ_{n,p})(j)| ≥ t) ≤ 8e^{−t^{2}/12np}.

Prova. Fixe j ≠ 0. Se z ∈ ℂ, usaremos as notações Re(z) e Im(z) para denotar as partes real e imaginária de z. Note que se |z| ≥ t, então ou | Re(z)| ≥ t/\sqrt{2} ou | Im(z)| ≥ t/\sqrt{2}. Logo

ℙ(|T (ℤ_{n,p})(j)| ≥ t)

≤ ℙ(| Re T (ℤ_{n,p})(j)| ≥ \frac{t}{\sqrt{2}}) + ℙ(| Im T (ℤ_{n,p})(j)| ≥ \frac{t}{\sqrt{2}}). (4.1)

Sejam (X_{r})_{r∈ℤ_{n}} variáveis aleatórias dadas por

X_{r} = \begin{cases}Re e^{−2πijr/n} = cos(−2πjr/n) & com probabilidade p, \\ 0 & com probabilidade 1 − p, \end{cases}

e, além disso, sejam (X_{r}^{+})_{r∈ℤ_{n}} e (X_{r}^{−})_{r∈ℤ_{n}} variáveis aleatórias dadas por X_{r}^{+} = max{X_{r}, 0} e X_{r}^{−} = − min{X_{r}, 0}. Segue que 0 ≤ X_{r}^{+} ≤ 1, 0 ≤ X_{r}^{−} ≤ 1 e X_{r} = X_{r}^{+} − X_{r}^{−}. Além disso, temos

X_{r}^{+} = \frac{X_{r} + |X_{r}|}{2} e X_{r}^{−} = \frac{|X_{r}| − X_{r}}{2} .

Sejam também X = ∑_{r∈ℤ_{n}} X_{r}, X^{+} = ∑_{r∈ℤ_{n}} X_{r}^{+} e X^{−} = ∑_{r∈ℤ_{n}} X_{r}^{−}. Temos

𝔼(X) = ∑_{r∈ℤ_{n}} 𝔼(X_{r}) = ∑_{r∈ℤ_{n}} p Re(e^{−2πijr/n}) = p Re( ∑_{r∈ℤ_{n}} e^{−2πijr/n}) = 0,

e

𝔼(X^{+}) = ∑_{r∈ℤ_{n}} 𝔼(X_{r}^{+}) = \frac{∑_{r∈ℤ_{n}} 𝔼(X_{r}) + ∑_{r∈ℤ_{n}} 𝔼(|X_{r}|)}{2} = \frac{∑_{r∈ℤ_{n}} 𝔼(|X_{r}|)}{2}.

Seja α = 𝔼(X^{+}) = ∑_{r∈ℤ_{n}} 𝔼(|X_{r}|)/2. É fácil ver que α = 𝔼(X^{−}) e que α ≤ pn/2. Note também que

2α = ∑_{r∈ℤ_{n}} 𝔼(|X_{r}|) = p ∑_{r∈ℤ_{n}} | cos(−2πjr/n)|

≥ p ∑_{r∈ℤ_{n}} cos(−2πjr/n)^{2} = \frac{p}{2} ∑_{r∈ℤ_{n}}(1 + cos(−4πjr/n)) = pn/2,

de onde segue que α ≥ pn/4. Pela desigualdade de Hoeffding (lema 23), para todo 0 < v < 1, temos ℙ(|X^{+} − α| ≥ vα) ≤ 2 exp ( − v^{2}α/3) e ℙ(|X^{−} − α| ≥ vα) ≤ 2 exp ( − v^{2}α/3), logo temos ℙ(|X| ≥ 2vα) ≤ 4 exp ( − v^{2}α/3). Equivalentemente, para todo 0 < t ≤ 2\sqrt{2}α, temos ℙ(|X| ≥ t/\sqrt{2}) ≤ 4 exp ( − t^{2}/(24α)). Como α ≤ pn/2, temos ℙ(|X| ≥ t/\sqrt{2}) ≤ 4 exp ( − t^{2}/(12pn)). Mas isto equivale a dizer que

ℙ(| Re T (ℤ_{n,p})(j)| ≥ \frac{t}{\sqrt{2}}) ≤ 4 exp ( − t^{2}/(12pn)).

Analogamente, provamos que

ℙ(| Im T (ℤ_{n,p})(j)| ≥ \frac{t}{\sqrt{2}}) ≤ 4 exp ( − t^{2}/(12pn)),

e a prova do fato está concluída, pela equação 4.1.

Com isso, é fácil provar o lema 51, pois ℙ(|T (ℤ_{n,p})(j)| ≥ \sqrt{24pn log n}) ≤ 8e^{−2 log n} = 8/n^{2}, e portanto

ℙ( max_{j≠0} |T (ℤ_{n,p})(j)| ≥ \sqrt{24pn log n}) ≤ 8/n,

o que conclui a prova.

Lema 52. Sejam D e R tais que D ⊂ R ⊂ ℤ_{n} e |D| = c|R|. Então e(CG_{n}(D)) ≥ c(1 − 2/n)e(CG_{n}(R)).

Prova. Vamos mostrar inicialmente que, para todo D ⊂ ℤ_{n}, temos |D|n/2 ≤ e(CG_{n}(D)) ≤ (1 + 2/n)|D|n/2. Dados B ⊂ ℤ_{n} e x ∈ ℤ_{n} \ B, examinaremos as arestas que estão em CG_{n}(B ∪ {x}) e que não estão em CG_{n}(B) (note que CG_{n}(B) é subgrafo de CG_{n}(B ∪ {x})). Ao acrescentar x a B, incluímos as arestas {i, j} com i + j = x. Suponha primeiramente que n é ímpar, n = 2m + 1. É fácil ver que incluiremos m + 1 novas arestas. Se n for par (n = 2m), incluiremos m arestas se x for ímpar, e m + 1 arestas se x for par. Note que, em todos os casos, o número de arestas que foram incluídas está entre n/2 e n/2 + 1.

Acrescentando um a um os |D| elementos de D, teremos que o número total de arestas incluídas, e(CG_{n}(D)), satisfaz

|D|\frac{n}{2} ≤ e(CG_{n}(D)) ≤ |D|\frac{n}{2} + |D| = (1 + \frac{2}{n})|D|\frac{n}{2},  (4.2)

que é o que queríamos. Com isso, temos

\frac{e(CG_{n}(D))}{e(CG_{n}(R))} ≥ \frac{|D|n/2}{(1 + 2/n)|R|n/2} = \frac{c}{(1 + 2/n)} ≥ c (1 − \frac{2}{n}) .

Lema 53 (Lema de conversão). Se a quantidade de pares proibidos por CG_{n}(D), e(J_{1}(CG_{n}(D)), é maior ou igual a c\binom{n}{2}, para alguma constante 0 < c ≤ 1, então

D − D = {x − y ∈ ℤ_{n}: x, y ∈ D}

tem pelo menos cn − 2 elementos.

Prova. Há uma associação clara entre pares proibidos por CG_{n}(D) e elementos de D − D. Se {x, z} é par proibido, existe y ∈ ℤ_{n} tal que x + y ∈ D e y + z ∈ D. Mas então x − z = (x + y) − (y + z) ∈ D − D. O problema é que essa associação não é bijetora.

Para cada m ∈ ℤ_{n}, definimos rep_{n}(m) como sendo o menor representante positivo da classe de m em ℤ_{n}, isto é, o único elemento do conjunto {x ∈ ℤ: x ≡ m (mod n)} ∩ {0, 1, 2, …, n − 1}. Dado um par proibido {x, z}, definimos d(x, z) = min{rep_{n}(x − z), rep_{n}(z − x)} (é a menor distância entre as classes de x e z em ℤ_{n}).

A função d acima descrita leva um par proibido {x, z} em um elemento d(x, z) de (D − D) ∩ {1, 2, …, ⌊n/2⌋} (observe que estamos olhando para {1, 2, …, ⌊n/2⌋} = {¯1, ¯2, …, ¯ ⌊n/2⌋} como subconjunto de ℤ_{n} e não de ℤ). Note que {x, z} é par proibido em CG_{n}(D) se e só se existe y ∈ ℤ_{n} tal que x+y ∈ D e y +z ∈ D. Mas isso equivale a dizer que para todo t ∈ ℤ_{n} temos (x + t) + (y − t) ∈ D e (y − t) + (z + t) ∈ D. Com isso provamos que {x, z} é par proibido se e só se {x + t, z + t} é par proibido para todo t. Assim, para todo k pertencente à imagem de d, temos |d^{−1}(k)| = n, e segue que

|(D − D) ∩ \{1, 2, …, ⌊n/2⌋\}| ≥ \frac{c\binom{n}{2}}{n} = \frac{c(n − 1)}{2},

e analogamente temos |(D − D) ∩ {⌈n/2⌉, …, n − 1}| ≥ c(n − 1)/2. Finalmente, somamos as duas últimas equações, obtendo

|D − D| ≥ c(n − 1) − 1 ≥ cn − 2,

onde o “−1” certifica que, no caso em que n é par (e portanto ⌊n/2⌋ = ⌈n/2⌉ = n/2), não contamos duas vezes |(D − D) ∩ {n/2}|.

O grafo J = J_{1} que aparece na demonstração do lema abaixo é o grafo dos pares 1-proibidos.

Lema 54 (Lema dos elementos proibidos). Dados reais 0 < δ ≤ 1 e 0 < γ_{0} ≤ 1, existe uma constante C_{0} = C_{0}(δ, γ_{0}) > 0 tal que, se p = p(n) ≥ C_{0} log n/\sqrt{n}, então, para n suficientemente grande, vale o seguinte.

Se CG_{n}(ℤ_{n,p}) é (p, \sqrt{24 log n})-uniforme e se B ⊂ ℤ_{n,p} é tal que |B| ≥ γ_{0}|ℤ_{n,p}|, o número de elementos proibidos por B é pelo menos (1 − δ)(|B|/|ℤ_{n,p}|)n.

Prova. Seja C^{∗} = C^{∗}(l, δ, γ_{0}) a constante determinada pelo lema 47. Para provar o presente lema, escolha C_{0} = 24C^{∗}(1, δ/2, γ_{0}/2). Pelo lema 52, temos que

e(CG_{n}(B))/e(CG_{n}(ℤ_{n,p})) ≥ (1 − 2/n)|B|/|ℤ_{n,p}|.

Pelo lema 47, e pela escolha de C_{0}, vemos que

e(J_{1}(CG_{n}(B)) ≥ (1 − δ/2)\frac{e(CG_{n}(B))}{e(CG_{n}(ℤ_{n,p}))}\binom{n}{2}

≥ (1 − δ/2)\frac{|B|}{|ℤ_{n,p}|} (1 − \frac{2}{n}) \binom{n}{2}. (4.3)

Finalmente, segue do lema de conversão (lema 53) que

|B − B| ≥ (1 − δ/2)\frac{|B|}{|ℤ_{n,p}|} (1 − \frac{2}{n}) n − 2 ≥ (1 − δ)\frac{|B|}{|ℤ_{n,p}|}n

para n suficientemente grande.

Vamos agora falar sobre as linhas gerais da prova do teorema 13. Queremos mostrar que quase certamente ℤ_{n,p} tem a propriedade Schur(η). Fixe uma realização ℤ_{n,p} e seja D ⊂ ℤ_{n,p} tal que |D| = (1/2 + η)|ℤ_{n,p}| e tal que D não contém triplas de Schur. Quebraremos ℤ_{n,p} em k + 1 partes (Z_{i})_{i=1}^{k+1}, sendo as k primeiras partes bem pequenas, e a última de tamanho aproximadamente |ℤ_{n,p}|/2. Mostraremos que uma das partes menores é tal que D∩Z_{i} proíbe muitos elementos, o que implica que |D − D| ≥ |(D ∩ Z_{i}) − (D ∩ Z_{i})| é grande. Olharemos em seguida para Z_{k+1} e concluiremos que, com alta probabilidade, há muitos elementos proibidos por D dentro de Z_{k+1}, e, como devemos ter (D−D)∩D = ∅, não haverá “espaço” suficiente dentro de Z_{k+1} para os elementos de D ∩ Z_{k+1}, o que é um absurdo. Vamos detalhar um pouco mais estas idéias, antes de demonstrar formalmente o teorema.

Prova do teorema 13 (esboço). Podemos imaginar que jogamos o seguinte jogo: nós sorteamos ℤ_{n,p}, um adversário escolhe um subconjunto D ⊂ ℤ_{n,p} com densidade 1/2 + η e aí nós temos que achar uma tripla de Schur em D para vencer o jogo. O que queremos provar é que para a enorme maioria dos ℤ_{n,p} sorteados, nós venceremos, por melhor que jogue nosso adversário.

Em primeiro lugar, observamos que basta nos concentrarmos no caso p = o(1). Daremos uma prova “rascunhada” desta observação. Suponha que provamos o teorema para alguma função p = p(n), e agora queremos prová-lo para uma função p′ = p′(n) ≥ p(n). Fixe D ⊂ ℤ_{n,p′} com |D| ≥ (1/2 + η)|ℤ_{n,p′}|. Agora, sorteie um subconjunto ℤ_{n,p′}^{∗} ⊂ ℤ_{n,p′}, colocando cada elemento de ℤ_{n,p′} em ℤ_{n,p′}^{∗} com probabilidade p/p′.

Seja Z(n, p) o espaço de probabilidade formado pelos subconjuntos aleatórios de ℤ_{n} em que cada elemento x ∈ ℤ_{n} entra no subconjunto com probabilidade p (isto é, Z(n, p) é o espaço dos ℤ_{n,p}). Então é claro que ℤ_{n,p′}^{∗} ∈ Z(n, p). Com alta probabilidade, temos que D^{∗} = D ∩ ℤ_{n,p′}^{∗} tem cardinalidade aproximadamente (p/p′)|D|, logo com alta probabilidade vale que |D^{∗}| ≥ (1/2 + η/2)|ℤ_{n,p′}^{∗}|, e, por hipótese, já sabemos que quase certamente D^{∗} tem uma tripla de Schur. Mas isto implica que D contém uma tripla de Schur, que é o que queríamos.

Fixe então p = p(n) = o(1). Escrevemos ℤ_{n,p} ∈ Z(n, p) como uma união de dois subconjuntos aleatórios de Z(n, p_{1}), onde (1 − p) = (1 − p_{1})^{2}:

ℤ_{n,p} = ℤ_{n,p_{1}}^{(1)} ∪ ℤ_{n,p_{1}}^{(2)},

e agora escrevemos ℤ_{n,p_{1}}^{(1)} como uma união de k elementos de Z(n, p_{2}), onde k é uma constante grande que será escolhida depois, e p_{2} é tal que (1−p_{1}) = (1 − p_{2})^{k}. Temos

ℤ_{n,p_{1}}^{(1)} = ⋃_{i=1}^{k} Z_{i} = ⋃_{i=1}^{k} ℤ_{n,p_{2}}^{(i)},

onde Z_{i} = ℤ_{n,p_{2}}^{(i)}. Como p = o(1), temos p_{1} ∼ p/2 e p_{2} ∼ p_{1}/k ∼ p/2k.

Basicamente, o que fizemos até aqui foi dizer ao nosso adversário: “Em vez de sortearmos ℤ_{n,p} de uma vez, iremos fazer isto em k + 1 etapas, sendo que os k primeiros ‘pedaços’ serão pequenos e o último terá aproximadamente metade de ℤ_{n,p}”. Dado que o último pedaço sorteado tem só metade de ℤ_{n,p} e como o adversário deve escolher uma fração 1/2 + η de ℤ_{n,p}, ele é obrigado a pegar alguns elementos entre os k primeiros pedaços. Iremos nos concentrar no pedaço j (1 ≤ j ≤ k) com maior densidade. Vamos agora tornar isto mais preciso.

Suponha que D ⊂ ℤ_{n,p} é tal que |D| = (1/2+η)|ℤ_{n,p}| mas D não contém soluções da equação de Schur. Sejam γ_{1} e γ_{2} as densidades de D ∩ ℤ_{n,p_{1}}^{(1)} em ℤ_{n,p_{1}}^{(1)} e de D ∩ ℤ_{n,p_{1}}^{(2)} em ℤ_{n,p_{1}}^{(2)}, respectivamente. Ou seja, temos

|D ∩ ℤ_{n,p_{1}}^{(1)}| = γ_{1}|ℤ_{n,p_{1}}^{(1)}| e |D ∩ ℤ_{n,p_{1}}^{(2)}| = γ_{2}|ℤ_{n,p_{1}}^{(2)}|.

Com alta probabilidade, temos γ_{1} + γ_{2} ∼ 1 + 2η.

Para 1 ≤ i ≤ k, definimos os conjuntos D_{i} por D_{i} = D ∩ Z_{i} e as densidades γ_{i}^{(2)} por |D_{i}| = γ_{i}^{(2)}|Z_{i}|. Seja j (1 ≤ j ≤ k) tal que γ_{j}^{(2)} =

max_{1≤i≤k} γ_{i}^{(2)} e seja γ^{∗} = γ_{j}^{(2)}. Observe que temos γ^{∗} ≥ γ_{1} > 2η. Aplicando

o lema 54 (juntamente com o lema 51) a D_{j} ⊂ ℤ_{n,p_{2}}^{(j)}, temos quase certamente que

|D − D| ≥ |D_{j} − D_{j}| ≥ (1 − δ)γ^{∗}n.

Vamos lembrar que δ é tão pequeno quanto desejarmos, de modo que o resultado acima diz, grosso modo, que |D − D| ≥ γ^{∗}n. Já vimos que os elementos de D − D são chamados de elementos proibidos justamente porque se x ∈ D − D, x não pode estar em D. Usaremos este fato ((D − D) ∩ D = ∅) agora. Sabe-se que a distribuição binomial com parâmetros n e p vai ficando muito concentrada na média conforme n cresce. O número de elementos de ℤ_{n,p_{1}}^{(2)} que são elementos proibidos por D é uma variável aleatória com distribuição binomial. Os parâmetros desta binomial são |D− D| ≥ γ^{∗}n (número de ensaios de Bernoulli) e p_{1} (probabilidade), e portanto é extremamente improvável que tal número de elementos seja muito menor que p_{1}γ^{∗}n ∼ γ^{∗}|ℤ_{n,p_{1}}^{(2)}|. Como já observamos, D ∩ ℤ_{n,p_{1}}^{(2)} não pode conter nenhum elemento proibido. Como, aproximadamente, uma proporção γ^{∗} dos elementos de ℤ_{n,p_{1}}^{(2)} são proibidos, D ∩ ℤ_{n,p_{1}}^{(2)} deve estar contido entre os (1 − γ^{∗})|ℤ_{n,p_{1}}^{(2)}| elementos restantes de ℤ_{n,p_{1}}^{(2)}. Mas isto é muito improvável, já que |D ∩ ℤ_{n,p_{1}}^{(2)}| = γ_{2}|ℤ_{n,p_{1}}^{(2)}| e

γ_{2}|ℤ_{n,p_{1}}^{(2)}| ∼ (1 + 2η − γ_{1})|ℤ_{n,p_{1}}^{(2)}| ≥ (1 + 2η − γ^{∗})|ℤ_{n,p_{1}}^{(2)}| > (1 − γ^{∗})|ℤ_{n,p_{1}}^{(2)}|,

e portanto “falta espaço” em ℤ_{n,p_{1}}^{(2)}.

Com isso, mostramos que, dado um sorteio de ℤ_{n,p}, e fixadas escolhas do adversário para uma etapa j (com 1 ≤ j ≤ k) e para um subconjunto D_{j} ⊂ ℤ_{n,p_{2}}^{(j)}, iremos perder com baixíssima probabilidade. Agora, se escolhemos k suficientemente grande, esta “baixíssima probabilidade” é tão pequena que, mesmo multiplicada pelo número de escolhas do adversário para a etapa j (com 1 ≤ j ≤ k) e para um subconjunto D_{j} ⊂ ℤ_{n,p_{2}}^{(j)}, ela ainda continua bastante pequena. De fato, o número de escolhas a que nos referimos acima é limitado por k2^{|ℤ_{n,p_{2}}^{(j)}|} ∼ k2^{np_{2}} ∼ k2^{np/(2k)} e o fato de aparecer um 1/k no expoente é crucial para nós. De fato, é exatamente por esta razão que fizemos o sorteio em k + 1 etapas: sem isso, teríamos um problema neste ponto.

Assim, com a escolha certa de k, esta “demonstração” está completa.

Daremos agora a demonstração formal do teorema 13.

Prova do teorema 13. Seja k = ⌈54η^{−3}⌉, ε = η/12, δ = η/4, γ_{0} = η e seja C = C(η) = 2kC_{0} > 0, onde C_{0} = C_{0}(δ, γ_{0}) > 0 é dado pelo lema dos elementos proibidos. Mostraremos que esta escolha de C servirá no teorema 13. Fixemos p = p(n) ≥ C log n/\sqrt{n}. Iremos assumir que n é muito grande, e, como já foi observado, podemos nos deter no caso em que p = p(n) = o(1).

Seja Z(n, p) o espaço de probabilidade formado pelos subconjuntos de ℤ_{n} em que cada elemento está no subconjunto com probabilidade p, e cada sorteio é independente dos demais.

Iremos gerar ℤ_{n,p} ∈ Z(n, p) em k+1 rodadas. Sejam 0 < p_{1} = p_{1}(n) < 1, 0 < p_{2} = p_{2}(n) < 1 tais que 1 − p = (1 − p_{1})^{2} e 1 − p_{1} = (1 − p_{2})^{k}. Considere agora k + 1 conjuntos aleatórios Z_{i} = ℤ_{n,p_{2}}^{(i)} ∈ Z(n, p_{2}) (1 ≤ i ≤ k) e Z_{k+1} = ℤ_{n,p_{1}}^{(2)} ∈ Z(n, p_{1}). Note que o conjunto ∪_{i=1}^{k+1}Z_{i} = (∪_{i=1}^{k}ℤ_{n,p_{2}}^{(i)}) ∪ ℤ_{n,p_{1}}^{(2)} é um elemento de Z(n, p).

Formalmente, trabalharemos com

Z = (Z_{1}, …, Z_{k}; Z_{k+1})

= (ℤ_{n,p_{2}}^{(1)}, …, ℤ_{n,p_{2}}^{(k)}; ℤ_{n,p_{1}}^{(2)}) ∈ Ω = (∏_{i=1}^{k} Z(n, p_{2})) × Z(n, p_{1}). (4.4)

Definimos ainda ℤ_{n,p_{1}}^{(1)} = ∪_{i=1}^{k}Z_{i} e ℤ_{n,p} = ℤ_{n,p_{1}}^{(1)} ∪ ℤ_{n,p_{1}}^{(2)} = ℤ_{n,p_{1}}^{(1)} ∪ Z_{k+1}.

O evento que queremos evitar, B, é “existe D ⊂ ℤ_{n,p} com |D| ≥ (1/2 + η)|ℤ_{n,p}| tal que D não contém triplas de Schur”. Mostraremos que a probabilidade de B vai a zero quando n → ∞.

Lembramos que escrevemos O_{1}(x) para denotar um termo y tal que |y| ≤ x. Seja Ω′ ⊂ Ω o conjunto dos Z = (Z_{1}, …, Z_{k}; Z_{k+1}) ∈ Ω tais que: para todo 1 ≤ i ≤ k, CG_{n}(Z_{i}) é (p_{2}, \sqrt{24 log n})-uniforme e |Z_{i}| = (1 + O_{1}(ε))np/2k; para i = 1, 2, |ℤ_{p_{1}}^{(i)}| = (1 + O_{1}(ε))np/2; e finalmente, |ℤ_{n,p}| = (1 + O_{1}(ε))np. Pela desigualdade de Hoeffding (lema 23) e pelo lema 51, ℙ(Ω′) = 1 − o(1) quando n → ∞, e portanto podemos assumir que nosso Z está em Ω′. Por essa razão, vamos nos concentrar em calcular ℙ(B′), onde B′ = B ∩ Ω′.

Antes disso, fixemos mais algumas notações. Para cada Z ∈ B′, fixe D = D(Z) ⊂ ℤ_{n,p} com |D| ≥ (1/2+η)|ℤ_{n,p}| e tal que D não tem triplas de Schur. Para i = 1, 2, sejam D_{i}^{(1)} = D_{i}^{(1)}(Z) = D ∩ ℤ_{n,p_{1}}^{(i)}, d_{i}^{(1)} = d_{i}^{(1)}(Z) = |D_{i}^{(1)}| e γ_{i}^{(1)} = γ_{i}^{(1)}(Z) = d_{i}^{(1)}/|ℤ_{n,p_{1}}^{(i)}|. Para 1 ≤ i ≤ k, sejam D_{i}^{(2)} = D_{i}^{(2)}(Z) = D ∩ Z_{i}, d_{i}^{(2)} = d_{i}^{(2)}(Z) = |D_{i}^{(2)}| e γ_{i}^{(2)} = γ_{i}^{(2)}(Z) = d_{i}^{(2)}/|Z_{i}|.

Agora fixe Z ∈ B′. Note que |D| = |D(Z)| ≤ d_{1}^{(1)} + d_{2}^{(1)}, e portanto

\frac{1}{2} + η ≤ \frac{|D|}{|ℤ_{n,p}|} ≤ γ_{1}^{(1)} \frac{|ℤ_{n,p_{1}}^{(1)}|}{|ℤ_{n,p}|} + γ_{2}^{(1)} \frac{|ℤ_{n,p_{1}}^{(2)}|}{|ℤ_{n,p}|}

≤ γ_{1}^{(1)} \frac{(1 + ε)np_{1}}{(1 − ε)np} + γ_{2}^{(1)} \frac{(1 + ε)np_{1}}{(1 − ε)np} ≤ (γ_{1}^{(1)} + γ_{2}^{(1)})\frac{(1 + 3ε)}{2},

donde concluímos que γ_{1}^{(1)} + γ_{2}^{(1)} ≥ (1 + 2η)/(1 + 3ε).

Note que d_{1}^{(1)} ≤ d_{1}^{(2)} + d_{2}^{(2)} + ⋯ + d_{k}^{(2)}, e portanto temos que γ_{1}^{(1)} ≤ ((1 + 3ε)/k) ∑_{1≤i≤k} γ_{i}^{(2)}. Logo, se γ^{∗} = γ^{∗}(Z): = max_{1≤i≤k} γ_{i}^{(2)}, temos (1 + 3ε)γ^{∗} ≥ (1 + 3ε)((∑_{1≤i≤k} γ_{i}^{(2)})/k) ≥ γ_{1}^{(1)}. Com isso, vemos que γ^{∗} + γ_{2}^{(1)} ≥ (γ_{1}^{(1)} + γ_{2}^{(1)})/(1 + 3ε) ≥ (1 + 2η)/(1 + 3ε)^{2} ≥ 1 + η. Em particular, γ^{∗} ≥ η.

Para 1 ≤ j ≤ k, seja B′_{j} = {Z ∈ B′: γ_{j}^{(2)} = γ^{∗}}. Como B′ = ∪_{j=1}^{k}B′_{j}, é suficiente mostrarmos que ℙ(B′_{j}) = o(1) quando n → ∞, para todo 1 ≤ j ≤ k. Fixemos a partir de agora algum j com 1 ≤ j ≤ k, e consideremos Z ∈ B′_{j}. Temos

ℙ(B′_{j}) = ∑_{Z_{0}} ℙ(B′_{j} ∩ {Z: Z_{j} = Z_{0}})

= ∑_{Z_{0}} ℙ(B′_{j} | Z_{j} = Z_{0})ℙ(Z_{j} = Z_{0}) ≤ max_{Z_{0}} ℙ(B′_{j} | Z_{j} = Z_{0}), (4.5)

onde Z_{0} varre todos os elementos de Z(n, p_{2}) de tamanho (1 + O_{1}(ε))np/2k e tais que CG_{n}(Z_{j}) é (p_{2}, A)-uniforme. Iremos agora fixar um certo Z_{0} e mostrar que ℙ(B′_{j} | Z_{j} = Z_{0}) é pequeno.

Para D_{0} ⊂ Z_{0}, seja P (j, Z_{0}, D_{0}) = ℙ(Z ∈ B′_{j} e D_{j}^{(2)}(Z) = D_{0} | Z_{j} = Z_{0}). Então,

ℙ(B′_{j} | Z_{j} = Z_{0}) = ∑_{D_{0}⊂Z_{0}} P (j, Z_{0}, D_{0})

≤ 2^{(1+ε)(p/2k)n} max_{D_{0}⊂Z_{0}} P (j, Z_{0}, D_{0}). (4.6)

Vamos fixar D_{0} ⊂ Z_{0} com P (j, Z_{0}, D_{0}) > 0. Note que γ^{∗} = |D_{0}|/|Z_{0}| ≥ η = γ_{0}. Segue do lema dos elementos proibidos (lema 54) que |D_{0} − D_{0}| ≥ (1 − δ)γ^{∗}n.

Agora, para cada Z ∈ Ω, definimos D′ = D′(Z) = Z_{k+1} ∩ (D_{0} − D_{0}) = ℤ_{n,p_{1}}^{(2)} ∩ (D_{0} − D_{0}), e d′ = d′(Z) = |D′|. Observe que d′ = d′(Z) (Z ∈ Ω) tem distribuição binomial Bi(|D_{0} − D_{0}|, p_{1}) com parâmetros |D_{0} − D_{0}| e p_{1}. Suponha que Z ∈ B′_{j}, Z_{j} = Z_{0} e D_{j}^{(2)}(Z) = D_{0}. Como D não contém triplas de Schur, temos D′(Z) ∩ D_{2}^{(1)}(Z) = ∅. Como (D′(Z) ∪ D_{2}^{(1)}(Z)) ⊂ Z_{k+1}, temos d′(Z)+γ_{2}^{(1)}|Z_{k+1}| ≤ |Z_{k+1}|, e portanto d′(Z) ≤ (1−γ_{2}^{(1)})|Z_{k+1}|. Com isso,

P (j, Z_{0}, D_{0}) ≤ ℙ (Z ∈ Ω′ e d′(Z) ≤ (1 − γ_{2}^{(1)})|Z_{k+1}|)

≤ ℙ (d′(Z) ≤ (1 − γ_{2}^{(1)})(1 + ε)\frac{pn}{2}) (4.7)

Estimaremos esta probabilidade usando o fato que d′ = d′(Z) ∼ Bi(|D_{0}− D_{0}|, p_{1}) e mostrando que (1 − γ_{2}^{(1)})(1 + ε)\frac{pn}{2} é significantemente menor que a esperança de d′, 𝔼(d′). Claramente, 𝔼(d′) ≤ p_{1}n ≤ pn. Além disso, lembrando que γ^{∗} + γ_{2}^{(1)} ≥ 1 + η, temos

𝔼(d′) − (1 − γ_{2}^{(1)})(1 + ε)\frac{pn}{2} ≥ ((1 − δ)γ^{∗} − (1 + ε)(1 − γ_{2}^{(1)}))\frac{pn}{2} ≥

(η − δ − ε)\frac{pn}{2} ≥ \frac{η}{3}pn ≥ \frac{η}{3}𝔼(d′), (4.8)

e é fácil ver que 𝔼(d′) ≥ (ηp/3)n. Pela desigualdade de Hoeffding (lema 23), d′(Z) ≤ (1 − γ_{2}^{(1)})(1 + ε)\frac{pn}{2} ocorre com probabilidade no máximo

ℙ(d′(Z) ≤ (1 − \frac{η}{3})𝔼(d′)) ≤ exp ( − \frac{η^{3}}{54}pn).

Da equação acima, e das equações 4.6 e 4.7, vemos que

ℙ(B′_{j} | Z_{j} = Z_{0}) ≤ 2^{(1+ε)(p/2k)n} exp ( − \frac{η^{3}}{54}pn)

= exp \{ log 2(1 + ε)(p/2k)n − \frac{η^{3}}{54}pn\},

e isso vai a zero quando n → ∞, pois

log 2(1 + ε)(p/2k)n − \frac{η^{3}}{54}pn ≤ pn(\frac{1}{2k} − \frac{η^{3}}{54}) ≤

pn(\frac{η^{3}}{108} − \frac{η^{3}}{54}) = −pn\frac{η^{3}}{108} ≤ −C log n\sqrt{n}\frac{η^{3}}{108} (4.9)

e −C log n\sqrt{n}η^{3}/108 → −∞ quando n → ∞.

4.3 O problema Schur(η)

É fácil ver que toda a demonstração do teorema 13 pode ser usada para resolver o problema 12, caso um resultado mais forte que o lema 51 seja provado. Conforme vimos, seria suficiente provar a seguinte conjectura.

Conjectura 55. Existe A > 0 tal que para todo p = p(n), com probabilidade tendendo a 1 quando n → ∞, temos

( max_{j≠0} T (ℤ_{n,p})(j)) ≤ A\sqrt{pn}.

Há uma última observação que gostaríamos de fazer sobre o Teorema de Schur. Para provar algo sobre a equação x + y = z, usamos o lema dos pares proibidos com l = 1. Usando o lema com l ≥ 1, obtemos uma generalização do resultado. Seja ∑_{j=1}^{l} a_{j} = ∑_{j=1}^{l+1} b_{j} a equação de Schur l-generalizada. Note que obtemos a equação de Schur original fazendo l = 1. Então, podemos provar uma generalização do teorema 13:

Teorema 56 (Teorema Schur(η) generalizado). Para todos l ∈ ℕ^{∗} e 0 < η ≤ 1/2, existe uma constante C = C(η, l) tal que, se p = p(n) ≥ C log n n^{−1+1/(2l)}, então, com probabilidade tendendo a 1 quando n → ∞, qualquer subconjunto de ℤ_{n,p} com densidade 1/2 + η tem uma solução da equação de Schur l-generalizada.

Toda a prova do teorema original pode ser facilmente adaptada ao teorema referente à equação de Schur generalizada. O único ponto da prova que poderia apresentar algum problema é o lema de conversão (lema 53). No entanto, sua adaptação também é fácil, como esboçaremos a seguir. Falaremos somente sobre o caso l = 2 unicamente para não carregar a notação.

Lema 57 (Lema de conversão generalizado). Se o número de pares 2proibidos por CG_{n}(D), e(J_{2}(CG_{n}(D)), é maior ou igual a c\binom{n}{2}, para alguma constante 0 < c ≤ 1, então

D − D + D − D = {x − y + z − w ∈ ℤ_{n}: x, y, z, w ∈ D}

tem pelo menos cn − 2 elementos.

Prova. Construiremos uma associação entre pares 2-proibidos por CG_{n}(D) e elementos de D −D +D −D. Se {x, y} é par 2-proibido, existem a, b, c ∈ ℤ_{n} tais que x + a ∈ D, a + b ∈ D, b + c ∈ D e c + y ∈ D. Mas então x − y = (x + a) − (a + b) + (b + c) − (c + y) ∈ D − D + D − D. Além disso, é fácil ver que {x, y} é um par 2-proibido se e só se {x + t, y + t} é um par 2-proibido para todo t.

Para m ∈ ℤ_{n}, lembramos que rep_{n}(m) é o único inteiro contido em {x ∈ ℤ: x ≡ m (mod n)} ∩ {0, 1, 2, …, n − 1}. Dado um par 2-proibido {x, z}, definimos d(x, z) = min{rep_{n}(x−z), rep_{n}(z −x)}. Note que a função d leva pares 2-proibidos em elementos de (D−D+D−D)∩{1, 2, …, ⌊n/2⌋}, e, além disso, para todo k pertencente à imagem de d, temos d^{−1}(k) = n.

Logo,

|(D − D + D − D) ∩ \{1, 2, …, ⌊n/2⌋\}| ≥ \frac{c\binom{n}{2}}{n} = \frac{c(n − 1)}{2},

e analogamente temos |(D − D + D − D) ∩ {⌈n/2⌉, …, n − 1}| ≥ c(n − 1)/2. Segue daí que

|D − D| ≥ c(n − 1) − 1 ≥ cn − 2,

como queríamos.

Naturalmente, a veracidade da conjectura 55 nos levaria a uma demonstração do seguinte:

Problema 58 (Problema Schur(η) generalizado). Para todos l ∈ ℕ^{∗} e 0 < η ≤ 1/2, existe uma constante C = C(η, l) tal que, se p = p(n) ≥ Cn^{−1+1/(2l)}, então, com probabilidade tendendo a 1 quando n → ∞, qualquer subconjunto de ℤ_{n,p} com densidade 1/2+η tem uma solução da equação de Schur l-generalizada.

O mesmo tipo de argumento dado para o problema Schur(η) original nos mostra que o enunciado acima é “ótimo”: ele é falso se p = o(n^{−1+1/(2l)}), ou se trocarmos “1/2 + η” por “1/2”.

Herança de regularidade

Neste capítulo, enunciaremos um resultado recente de Gerke, Kohayakawa, Rödl e Steger, ainda não publicado [12]. A partir deste resultado (teorema 60), desenvolvemos uma versão mais conveniente para nossos propósitos (teorema 64) e depois provaremos o teorema 14.

Começamos relembrando algumas definições. Dado um certo grafo G = (V, E), e dois subconjuntos disjuntos U, W ⊂ V, definimos E(U, W) como o conjunto das arestas entre U e W no grafo G, e colocamos e(U, W) = e_{G}(U, W) = |E(U, W)|. Denotamos ainda por G[U, W] o grafo bipartido com vértices U ˙∪W e arestas E(U, W).

Definição 59. Sejam 0 < ε, d ≤ 1. Um grafo bipartido B = (V_{1} ˙∪V_{2}, E) é (ε, d)-bipartido-regular se para todos V′_{1} ⊂ V_{1}, V′_{2} ⊂ V_{2} com |V′_{1}| ≥ ε|V_{1}| e |V′_{2}| ≥ ε|V_{2}|, temos

|E(V′_{1}, V′_{2})| ≥ (1 − ε)d|V′_{1}||V′_{2}|.

Com isso, podemos enunciar o resultado principal de [12]. Basicamente, o teorema abaixo afirma que, dado um grafo bipartido B = (V_{1} ˙∪V_{2}, E) que é (ε, d)-bipartido-regular, e dado um certo inteiro apropriado q, então quase todos os subconjuntos de tamanho q de V_{1} induzem um grafo (ε′, d)- bipartido-regular com V_{2}, desde que ε seja suficientemente pequeno. Ou seja, estes subconjuntos de tamanho q “herdam” a propriedade de regularidade de V_{1}.

Teorema 60 (Herança de regularidade). Para todos 0 < β, ε′ < 1, existem ε_{0} = ε_{0}(β, ε′) > 0 e C = C(ε′) tais que para todo 0 < ε ≤ ε_{0} e todo 0 < d < 1, qualquer grafo G = (V_{1} ˙∪V_{2}, E) bipartido e (ε, d)-bipartido-regular tem a seguinte propriedade. O número de subconjuntos Q ⊂ V_{1} com q = |Q| ≥ C/d que formam um grafo (ε′, d)-bipartido-regular com V_{2} é pelo menos

(1 − β^{q})\binom{|V_{1}|}{q}.

5.1 Versão interna de herança de regularidade

Usaremos agora o teorema 60 para deduzir uma outra versão de herança de regularidade. Começamos com uma observação simples: aplicando o teorema 60 duas vezes, obtemos o corolário abaixo. Note que, ao contrário do que ocorre no teorema anterior, aqui a constante C depende de β.

Corolário 61 (Herança de regularidade, versão 2). Para todos 0 < β, ε′ < 1, existem ε_{0} = ε_{0}(β, ε′) > 0 e C = C(β, ε′) tais que para todo 0 < ε ≤ ε_{0} e todo 0 < d < 1, qualquer grafo G = (V_{1} ˙∪V_{2}, E) bipartido e (ε, d)-bipartido-regular tem a seguinte propriedade. O número de pares (X, Y) com X ⊂ V_{1}, Y ⊂ V_{2} e q = min{x, y} ≥ C/d (onde x = |X| e y = |Y |) tais que o grafo G[X, Y] é (ε′, d)-bipartido-regular é pelo menos

(1 − β^{q})\binom{|V_{1}|}{x}\binom{|V_{2}|}{y}.

Note que quando dizemos que G[X, Y] é (ε′, d)-bipartido-regular, estamos afirmando algo sobre as arestas entre X e Y, mas não dizemos nada sobre as arestas contidas em X ou Y. Para nossos interesses, é necessária uma versão que afirme algo sobre as arestas internas. Veremos agora uma versão “interna” dos teoremas anteriores, e que é aplicável a grafos não necessariamente bipartidos. Antes disso, precisamos de um lema simples.

Lema 62. Sejam n e q = q(n) inteiros positivos com 3 ≤ q ≤ n/2. Existe uma constante absoluta n_{0} tal que, para n ≥ n_{0}, temos

2\begin{matrix}( & {n \atop ⌊n/2⌋} & ) \\ ( & {n−q \atop ⌊(n−q)/2⌋} & ) \end{matrix} ≤ 3^{q}.

Prova. Vamos usar uma estimativa padrão para \binom{k}{⌊k/2⌋}, que segue facilmente da fórmula de Stirling. A estimativa é a seguinte (veja o lema 95 de [29]):

\binom{k}{⌊k/2⌋} = (1 + o(1))\sqrt{\frac{2}{πk}} 2^{k}.

Com isso, para n suficientemente grande, temos

2\begin{matrix}( & {n \atop ⌊n/2⌋} & ) \\ ( & {n−q \atop ⌊(n−q)/2⌋} & ) \end{matrix} = (2 + o(1))\sqrt{\frac{2}{πn}}2^{n}\sqrt{\frac{π(n − q)}{2}} \frac{1}{2^{n−q}}

= (2 + o(1))\sqrt{\frac{n − q}{n}} 2^{q} ≤ 3^{q}.

Definimos abaixo um conceito parecido com a (ε, d)-bipartido-regulari-dade, mas que se aplica a grafos gerais (não só aos bipartidos):

Definição 63. Sejam 0 < ε, d ≤ 1. Um grafo G = (V, E) é (ε, d)-inf-regular se para todos U, W ⊂ V com U ∩ W = ∅, |U| ≥ ε|V | e |W | ≥ ε|V |, temos

|E(U, W)| ≥ (1 − ε)d|U||W |.

Agora podemos enunciar e provar a “versão interna de herança de regularidade”. Lembramos apenas que G[Q] é o subgrafo de G induzido pelo subconjunto de vértices Q ⊂ V (G). Estará implícito o tempo todo que n = |V | = |V (G)|.

Teorema 64 (Versão interna de herança de regularidade). Para todos 0 < α, ε̃ < 1, existem ε̃_{0} = ε̃_{0}(α, ε̃) > 0 e C̃ = C̃(α, ε̃) tais que para todo 0 < ε ≤ ε̃_{0} e todo 0 < d < 1, qualquer grafo G = (V, E) (ε, d)-inf-regular com n = |V (G)| suficientemente grande (isto é, maior que uma certa constante absoluta) tem a seguinte propriedade. Seja q um inteiro maior ou igual a C̃/d. Então, o número de subconjuntos Q ⊂ V com |Q| = q e tais que e(G[Q]) ≥ (1 − ε̃)d\binom{q}{2} é pelo menos

(1 − α^{q})\binom{|V |}{q}.

Prova. Dados α e ε̃, escolhemos β = (α/3)^{3} e usamos o corolário 61 com esta escolha de β e com ε′ = ε̃ para obter ε_{0} e C. Por fim, escolhemos ε̃_{0}(α, ε̃) = ε_{0}/3 e C̃(α, ε̃) = 3C, e agora mostraremos que o teorema é verdadeiro com esta escolha de ε̃_{0} e de C̃. Suponha agora que 0 < ε ≤ ε̃_{0} = ε_{0}/3, 0 < d < 1 e seja G um grafo (ε, d)-inf-regular. Se q > n/2, o teorema segue do lema 28. Assim, fixe um inteiro C̃/d ≤ q ≤ n/2 e observe que ⌊q/2⌋ ≥ C̃/3d = C/d.

Dizemos que {U, W } é uma bipartição equilibrada de V = V (G) se U ˙∪W = V e ||U| − |W || ≤ 1. Seja A = \binom{V}{q} o conjunto dos subconjuntos de V de tamanho q, e seja B o conjunto das bipartições equilibradas de V. Note que

|B| = \binom{n}{⌊n/2⌋}.

Montaremos agora um grafo bipartido H com vértices A ˙∪B. Se Q ∈ A e {U, W } ∈ B, (Q, {U, W }) será uma aresta de H se e só se {U ∩ Q, W ∩ Q} for uma bipartição equilibrada de Q (isto é, se e só se (U ∩Q) ˙∪(W ∩Q) = Q e ||U ∩ Q| − |W ∩ Q|| ≤ 1).

Diremos que uma aresta (Q, {U, W }) ∈ E(H) é especial se

e_{G}(U ∩ Q, W ∩ Q) < (1 − ε̃)d⌊q/2⌋⌈q/2⌉.

Por fim, diremos que Q ⊂ A é um conjunto ruim se

e(G[Q]) < (1 − ε̃)d\binom{q}{2}.

Mostraremos que conjuntos ruins são muito raros. A estratégia da prova é contar o número de arestas especiais do grafo H de duas formas diferentes. Primeiro estimaremos quantas destas arestas saem de A, e depois, quantas saem de B. Da comparação destas estimativas seguirá o resultado.

Fixe Q ∈ A. Se e_{G}(U ∩ Q, W ∩ Q) ≥ (1 − ε̃)d⌊q/2⌋⌈q/2⌉ para todo {U, W } ∈ Γ_{H}(Q), segue do lema 28 que Q não é um conjunto ruim. Logo, se Q é ruim, existe {U, W } ∈ Γ_{H}(Q) tal que e_{G}(U ∩ Q, W ∩ Q) < (1 − ε̃)d⌊q/2⌋⌈q/2⌉, ou seja, tal que a aresta (Q, {U, W }) é especial. Note que se (Q, {U, W }) é uma aresta especial e se {U′, W′} ∈ B é tal que {U′ ∩ Q, W′ ∩ Q} = {U ∩ Q, W ∩ Q}, então a aresta (Q, {U′, W′}) também é especial. Como existem pelo menos \binom{n−q}{⌈n/2⌉−⌈q/2⌉} modos de estender uma bipartição equilibrada de Q para uma bipartição equilibrada de V, temos que

(Número de arestas especiais) ≥

\binom{n − q}{⌈n/2⌉ − ⌈q/2⌉} × (Número de conjuntos ruins). (5.1)

Fixe agora {U, W } ∈ B e considere o grafo bipartido G[U, W]. Como G é (ε, d)-inf-regular, segue que G[U, W] é (3ε, d)-bipartido-regular. Como 3ε ≤ 3ε̃_{0} = ε_{0}, temos pelo corolário 61 que o número de pares (X, Y) com X ⊂ U, Y ⊂ W, x = |X| = ⌊q/2⌋ e y = |Y | = ⌈q/2⌉ tais que o grafo G[X, Y] não é (ε̃, d)-bipartido-regular é no máximo

β^{q/3}\binom{|U|}{x}\binom{|W |}{y} ≤ β^{q/3}\binom{⌈n/2⌉}{⌈q/2⌉}^{2}.

Analogamente, o número de pares (X, Y) com X ⊂ U, Y ⊂ W, x = |X| = ⌈q/2⌉ e y = |Y | = ⌊q/2⌋ tais que o grafo G[X, Y] não é (ε̃, d)-bipartido-regular é no máximo

β^{q/3}\binom{|U|}{x}\binom{|W |}{y} ≤ β^{q/3}\binom{⌈n/2⌉}{⌈q/2⌉}^{2}.

Logo, o número de conjuntos Q ∈ Γ_{H}({U, W }) tais que e_{G}(U ∩ Q, W ∩ Q) < (1 − ε̃)d⌊q/2⌋⌈q/2⌉ é no máximo 2β^{q/3}\binom{⌈n/2⌉}{⌈q/2⌉}^{2}, e portanto, o número

de arestas especiais que saem de \{U, W \} é no máximo 2β^{q/3}\binom{⌈n/2⌉}{⌈q/2⌉}^{2}. Com isso, temos que

(Número de arestas especiais) ≤ 2β^{q/3}\binom{⌈n/2⌉}{⌈q/2⌉}^{2}|B|

= 2β^{q/3}\binom{⌈n/2⌉}{⌈q/2⌉}^{2}\binom{n}{⌊n/2⌋}. (5.2)

Daqui em diante, ignoraremos pisos e tetos (⌊x⌋, ⌈x⌉). Das desigualdades 5.1 e 5.2, temos que

\binom{n − q}{(n − q)/2} × (Número de conjuntos ruins) ≤ 2β^{q/3}\binom{n/2}{q/2}^{2}\binom{n}{n/2},

ou seja,

(Número de conjuntos ruins) ≤ 2β^{q/3} \begin{matrix}\binom{n/2}{q/2} & 2 & \binom{n}{n/2} \\ ( & {n−q \atop (n−q)/2} & ) \end{matrix} ≤ 2β^{q/3}\binom{n}{q}\begin{matrix}( & {n \atop n/2} & ) \\ ( & {n−q \atop (n−q)/2} & ) \end{matrix}.

Por fim, segue do lema 62 que, para n suficientemente grande, o número de conjuntos ruins é no máximo

3^{q}β^{q/3}\binom{n}{q} = (3β^{1/3})^{q}\binom{n}{q} = α^{q}\binom{n}{q}.

5.2 Uma versão probabilística do Teorema de Sárközy

Iremos agora aplicar o teorema anterior dando uma prova do teorema 14. Na verdade, provaremos resultados mais gerais, a saber, os teoremas 67 e 68. Vamos começar estabelecendo algumas notações.

Convencionemos que ℕ = {1, 2, 3 …}. Seja M = {m_{1}, m_{2}, …} um subconjunto infinito de ℕ com 1 ≤ m_{1} < m_{2} < . . ..

Definição 65. Dizemos que S_{M} é uma M-sequência se S_{M} for uma sequência de conjuntos indexada por M, S_{M} = (S_{m_{i}})_{i∈ℕ}, tal que, para todo i, S_{m_{i}} ⊂ ℤ_{m_{i}}.

Denotaremos a densidade de um grafo G por d(G) = e(G)/\binom{n}{2}, onde n = |V (G)|.

Definição 66. Seja S_{M} uma M-sequência. Dizemos que S_{M} é adiçãoregular se para todo ε > 0 existe i_{0} ∈ ℕ tal que, se i ≥ i_{0}, o grafo CG_{m_{i}}^{+}(S_{m_{i}}) é (ε, d(CG_{m_{i}}^{+}(S_{m_{i}})))-inf-regular. Analogamente, dizemos que S_{M} é subtração-regular se para todo ε > 0 existe i_{0} ∈ ℕ tal que, se i ≥ i_{0}, o grafo CG_{m_{i}}^{−}(S_{m_{i}}) é (ε, d(CG_{m_{i}}^{−}(S_{m_{i}})))-inf-regular.

Usaremos a seguir as notações definidas pelas equações 1.10 e 1.11. Os teoremas principais desta seção são os seguintes:

Teorema 67. Suponha que S_{M} = (S_{m_{i}})_{i∈ℕ} é uma M-sequência adiçãoregular. Para todos 0 < η, γ < 1, existem constantes C = C(η, γ) e i_{0} = i_{0}(η, γ) tais que, se i ≥ i_{0} e se p: M → [0, 1] satisfaz p = p(m_{i}) ≥ C/|S_{m_{i}}|, então, com probabilidade pelo menos 1 − γ, temos que

ℤ_{m_{i},p} →_{η} Soma(S_{m_{i}}).

Teorema 68. Suponha que S_{M} = (S_{m_{i}})_{i∈ℕ} é uma M-sequência subtraçãoregular. Para todos 0 < η, γ < 1, existem constantes C = C(η, γ) e i_{0} = i_{0}(η, γ) tais que, se i ≥ i_{0} e se p: M → [0, 1] satisfaz p = p(m_{i}) ≥ C/|S_{m_{i}}|, então, com probabilidade pelo menos 1 − γ, temos que

ℤ_{m_{i},p} →_{η} Diferença(S_{m_{i}}).

Dado que as demonstrações dos teoremas acima são extremamente parecidas, provaremos apenas o primeiro deles.

Prova do teorema 67. Fixe reais 0 < η, γ < 1. Sejam e = exp(1) e α = γη/(2e(2 + γ)). Note que 0 < α < 1 e que ∑_{t=1}^{∞}(2αe/η)^{t} = 2αe/(η − 2αe) = γ/2. Seja ε̃ = 10^{−2} e use o teorema 64 para achar C̃ = C̃(α, ε̃) e ε̃_{0} = ε̃_{0}(α, ε̃) = ε̃_{0}(α, 10^{−2}) > 0. Tome C = C(η, γ) = 4C̃(α, ε̃)/η. Podemos supor sem perda que C é tal que 2 exp(−C/12) ≤ γ/2. Como S_{M} é adição-regular, existe i_{0} = i_{0}(ε̃_{0}) = i_{0}(γ, η) tal que, se i ≥ i_{0}, o grafo G = CG_{m_{i}}^{+}(S_{m_{i}}) é (ε̃_{0}/2, d(CG_{m_{i}}^{+}(S_{m_{i}})))-inf-regular.

Veremos que, com esta escolha de C e de i_{0}, o teorema 67 é verdadeiro. Fixe i ≥ i_{0}. Vamos provar que

ℙ(ℤ_{m_{i},p} →_{η} Soma(S_{m_{i}})) ≥ 1 − γ.

Lembramos que Z(n, p) é o espaço de probabilidade dos subconjuntos de ℤ_{n} em que cada elemento está no subconjunto com probabilidade p. Seja Z(n, p)′ o subconjunto de Z(n, p) formado pelos conjuntos ℤ_{n,p} que satisfazem np/2 ≤ |ℤ_{n,p}| ≤ 3np/2. Pela desigualdade de Hoeffding (lema 23),

ℙ(Z(m_{i}, p)′) ≥ 1 − 2 exp(−m_{i}p/12) ≥ 1 − 2 exp(−C/12) ≥ 1 − γ/2

Vamos supor daqui em diante que ℤ_{m_{i},p} ∈ Z(m_{i}, p)′. Note que isto implica que, ao escolhermos D ⊂ ℤ_{m_{i},p} com |D| = η|ℤ_{m_{i},p}|, teremos ηm_{i}p/2 ≤ |D| ≤ 3ηm_{i}p/2.

Seja G o grafo CG_{m_{i}}^{+}(S_{m_{i}}). Diremos que um conjunto Q ⊂ ℤ_{m_{i}} com |Q| = q é indesejável se

e(G[Q]) = e(CG_{m_{i}}^{+}(S_{m_{i}})[Q]) < (1 − ε̃)d(CG_{m_{i}}^{+}(S_{m_{i}}))\binom{q}{2}.

Vamos mostrar que a probabilidade de ℤ_{m_{i},p} ∈ Z(m_{i}, p)′ conter um subconjunto de densidade η e indesejável é no máximo γ/2.

Seja q um inteiro positivo com ηm_{i}p/2 ≤ q ≤ 3ηm_{i}p/2. Note que, da equação 4.2 (na demonstração do lema 52), segue que

q ≥ \frac{ηm_{i}p}{2} ≥ \frac{4ηC̃(α, ε̃)m_{i}}{2η|S_{m_{i}}|} ≥ \frac{C̃(α, ε̃)}{d(CG_{m_{i}}^{+}(S_{m_{i}}))}.

Com isso, podemos aplicar o teorema 64 ao grafo CG_{m_{i}}^{+}(S_{m_{i}}) e ao inteiro q para concluir que o número de conjuntos Q ⊂ ℤ_{m_{i}} de tamanho exatamente q com e(G[Q]) < (1 − ε̃)d(CG_{m_{i}}^{+}(S_{m_{i}}))\binom{q}{2} é no máximo α^{q}\binom{m_{i}}{q}.

O número esperado de conjuntos indesejáveis de tamanho exatamente q e contidos em ℤ_{m_{i},p} ∈ Z(m_{i}, p)′ é no máximo o número de conjuntos indesejáveis de tamanho q vezes a probabilidade de um destes conjuntos indesejáveis estar contido em ℤ_{m_{i},p}, e isto é limitado por

α^{q}\binom{m_{i}}{q}p^{q} ≤ (α\frac{m_{i}e}{q}p)^{q} ≤ (\frac{2αe}{η})^{q} ,

onde usamos o fato que \binom{m_{i}}{q} ≤ (m_{i}e/q)^{q} (para uma prova disto, veja o lema 94 de [29]). Portanto, o número esperado de conjuntos indesejáveis em ℤ_{m_{i},p} ∈ Z(m_{i}, p)′ com tamanho entre ηm_{i}p/2 e 3ηm_{i}p/2 é no máximo

∑_{q=ηm_{i}p/2}^{3ηm_{i}p/2} (\frac{2αe}{η})^{q} ≤ ∑_{q=1}^{∞} (\frac{2αe}{η})^{q} = γ/2.

Com isso, segue da desigualdade de Markov que a probabilidade de ℤ_{m_{i},p} ∈ Z(m_{i}, p)′ não conter nenhum conjunto indesejável com cardinalidade entre ηm_{i}p/2 e 3ηm_{i}p/2 é pelo menos 1 − γ/2.

Voltemos a Z(m_{i}, p). Vimos que, com probabilidade pelo menos 1 − γ, nenhum conjunto D com densidade η em ℤ_{m_{i},p} ∈ Z(m_{i}, p) é indesejável. Isto implica que, com probabilidade pelo menos 1−γ, ℤ_{m_{i},p} ∈ Z(m_{i}, p) é tal que, se D é uma η-fração de ℤ_{m_{i},p}, temos e(G[D]) ≥ (1 − ε̃)d(CG_{m_{i}}^{+}(S_{m_{i}}))\binom{|D|}{2} ≥ 1. Finalmente, observe que cada uma destas arestas representa uma solução de x + y ∈ S_{m_{i}} com x, y ∈ D.

O teorema 14 segue imediatamente do teorema 68, bastando tomar M igual ao conjunto dos primos e S_{M} = (S_{m_{i}})_{i∈ℕ} com S_{m_{i}} = Quad(m_{i}), onde Quad(n) ⊂ ℤ_{n} é o conjunto dos quadrados não-nulos módulo n. É fácil ver que, se n é primo, | Quad(n)| = n(1 + o(1))/2. A última coisa que falta verificar é que S_{M} é subtração-regular. Veremos que isto é bem simples. Usaremos o fato abaixo, que é um resultado clássico da teoria dos números, provado por Gauss.

Fato 69. Seja m um primo e seja j ∈ ℤ_{m}, j ≠ 0. Então

S(m) = ∑_{x=1}^{m−1} e^{−2πijx^{2}/m} = O(\sqrt{m}).

Prova. A demonstração pode ser encontrada em vários textos de teoria dos números. Por exemplo, veja [2].

Corolário 70. Seja m um primo. Então, temos para todo j ≠ 0 que

T (Quad(m))(j) = ∑_{x∈Quad(m)} e^{−2πijx/m} = O(\sqrt{m}).  (5.3)

Prova. Seja ℤ_{m}^{∗} = ℤ_{m} \ {0} e considere f: ℤ_{m}^{∗} → ℤ_{m}^{∗} dada por f(x) = x^{2} e m é primo. É fácil ver que para cada y na imagem de f, |f^{−1}(y)| = 2. Desta observação, segue que

∑_{x∈Quad(m)} e^{−2πijx/m} = \frac{1}{2} ∑_{x=1}^{m−1} e^{−2πijx^{2}/m},

e o resultado segue do fato 69.

Pelo lema 33, segue que S_{M} = (Quad(m_{i}))_{i∈ℕ} é adição-regular, onde M é a subsequência dos primos. É fácil ver agora que S_{M} também é subtraçãoregular, e com isso provamos o teorema 14.

Observe que, “no meio do caminho”, provamos também o seguinte teorema:

Teorema 71. Para todos 0 < η, γ < 1 , existem constantes C = C(η, γ) e n_{0} = n_{0}(η, γ) tais que, se p = p(n) ≥ C/n e se n é um primo com n ≥ n_{0}, então, com probabilidade pelo menos 1 − γ, temos que

ℤ_{n,p} →_{η} Soma(Quad(n)).

Como observação final, note que a propriedade essencial de Quad(n) que utilizamos foi a adição-regularidade (e a subtração-regularidade). Por sua vez, isto seguiu do fato que para j ≠ 0, o j-ésimo coeficiente de Fourier de Quad(n) é o(| Quad(n)|). Na próxima seção, veremos mais alguns exemplos de M-sequências com esta propriedade, e, com isso, daremos novas aplicações dos teoremas 67 e 68.

5.3 Outras aplicações dos teoremas 67 e 68

Nesta seção, mostraremos que os teoremas 67 e 68 têm algumas outras aplicações, além dos teoremas 14 e 71.

Vimos que os quadrados módulo n (n primo) formam uma M-sequência adição-regular. Fixe f(z), um polinômio com coeficientes inteiros não constante. Provaremos que a imagem de f(z) módulo n (n primo) é adiçãoregular. Com isso, obteremos um teorema para a equação x + y = f(z).

Começamos observando que existem extensões do fato 69 para polinômios gerais. Enunciamos uma destas extensões, que é um resultado devido a Hua [20, 21].

Teorema 72 (L. K. Hua). Sejam m um inteiro positivo e f(x) = a_{k}x^{k} + …+a_{1}x+a_{0} um polinômio com coeficientes inteiros. Se mdc(a_{k}, …, a_{1}, m) = 1, então para todo θ > 0, existe uma constante c_{1}(k, θ) que só depende de k e de θ tal que

| ∑_{x∈ℤ_{m}} e^{−2πif(x)/m}| ≤ c_{1}(k, θ)m^{1− \frac{1}{k} +θ}.

Note que foi fácil passar do fato 69 ao corolário 70 porque, se m é primo e f: ℤ_{m}^{∗} → ℤ_{m}^{∗} é dada por f(x) = x^{2}, cada elemento da imagem de f tem o mesmo número de pré-imagens (a saber, 2). Isto é, para todo k na imagem de f, |f^{−1}(k)| é constante. Isto não vale para polinômios quaisquer, e, portanto, será necessário desenvolver outro método para aplicar o teorema 72.

No que segue, usaremos grafos de Chung-Graham com pesos. Vamos definir este conceito. Seja R um multiconjunto finito contido em ℤ_{n}, isto é, um conjunto com elementos de ℤ_{n} em que permitimos elementos repetidos (finitas vezes). Por exemplo, S = {1, 1, 1, 1, 3, 5, 5, 6, 6, 6} é um multiconjunto contido em ℤ_{7}. A função característica de um multiconjunto R contido em ℤ_{n}, que também denotaremos por R, é a função R: ℤ_{n} → ℕ tal que R(j) é a multiplicidade do elemento j em R. Assim, a função característica do multiconjunto S = {1, 1, 1, 1, 3, 5, 5, 6, 6, 6} contido em ℤ_{7} é o vetor (S(j))_{j=0}^{6} tal que (S(j)) = (0, 4, 0, 1, 0, 2, 3).

Com isso, podemos falar de grafos de Chung-Graham com pesos. No grafo de Chung-Graham “tradicional”, CG_{n}^{+}(R), vale que {i, j} é aresta se e só se existe r ∈ R tal que i + j ≡ r (mod n). No grafo de Chung-Graham com pesos, R deve ser um multiconjunto, e para cada r ∈ R e para cada i, j ∈ ℤ_{n} com i+j = r, colocaremos R(r) arestas ligando i a j (ou uma aresta com peso R(r), equivalentemente). Denotaremos este grafo por PCG_{n}^{+}(R). Três últimas convenções que faremos são: (1) se U, W ⊂ V (PCG_{n}^{+}(R)) = ℤ_{n} e U ∩ W = ∅, cada aresta {i, j} entre U e W entrará k vezes no cômputo de e(U, W), onde k = R(i + j) é o peso da aresta {i, j}; (2) as multiplicidades das arestas são levadas em conta no cálculo de e(PCG_{n}^{+}(R)); e (3) por “|R|”, deve-se entender “∑_{r} R(r)”.

Dito isto, é fácil verificar que os lemas da seção 3.2 ainda valem neste contexto com pesos. As provas podem ser adaptadas de maneira evidente. Em particular, o lema 33 é válido, e ele será usado na prova do teorema 73.

Faremos agora uma observação simples, mas importante: suponha que o grafo PCG_{n}^{+}(R) é (ε, d)-inf-regular (podemos ter d ≥ 1 neste contexto!) e max_{r∈ℤ_{n}} R(r) = L > 0. Então o grafo de Chung-Graham “tradicional”, CG_{n}^{+}(R), que é obtido de modo trivial a partir de PCG_{n}^{+}(R) (apagando arestas múltiplas ou transformando todos os pesos R(r) > 1 em R(r) = 1), é (ε, d/L)-inf-regular.

Vamos fixar algumas notações. Começamos definindo a função aritmética Δ: ℕ → ℕ, do seguinte modo: para n > 1, Δ(n) é o menor primo que divide n, e Δ(1) = 1. Além disso, se f: ℤ_{m} → ℤ_{m} é um polinômio, denotaremos a imagem de f por Im_{m} f(x). Observe que Im_{m} f(x) é um subconjunto ordinário de ℤ_{m}. Definimos Im_{m}^{∗} f(x) como o multiconjunto {f(0), f(1), …, f(m − 1)} contido em ℤ_{m}. Finalmente, definimos ϕ_{m}(f) = max_{j∈ℤ_{m}} |f^{−1}(j)|. O teorema abaixo é o resultado mais importante desta seção.

Teorema 73. Seja f(x) um polinômio com coeficientes inteiros, não constante. Seja M = {m_{1}, m_{2}, …} um subconjunto infinito de ℕ com 1 ≤ m_{1} < m_{2} < … e lim_{i∈ℕ} Δ(m_{i}) = ∞. Suponha ainda que existe L > 0 tal que ϕ_{m_{i}}(f) ≤ L para todo m_{i} ∈ M. Então, para todo ε > 0, existe i_{0} > 0 tal que, se i ≥ i_{0}, o grafo de Chung-Graham ordinário CG_{m_{i}}^{+}(Im_{m_{i}} f(x)) é (ε, 1/L)-inf-regular.

Prova. Com o auxílio do teorema 72, mostraremos que os grafos de Chung-Graham com pesos PCG_{m_{i}}^{+}(Im_{m_{i}}^{∗} f(x)) têm propriedades de regularidade.

Fixe m_{i} ∈ M, j ∈ ℤ_{m_{i}}^{∗}. Seja t = mdc(j, m_{i}) e sejam j′ = j/t e m′_{i} = m_{i}/t. Seja k o grau de f e defina θ = 1/(2k). Pelo teorema da divisão euclideana, para cada 0 ≤ x < m_{i}, existem 0 ≤ y < t e 0 ≤ r < m′_{i} com x = ym′_{i} + r. Logo,

∑_{x∈ℤ_{m_{i}}} e^{−2πijf(x)/m_{i}} = ∑_{x∈ℤ_{m_{i}}} e^{−2πij′f(x)/m′_{i}}

= ∑_{y∈ℤ_{t}} ∑_{r∈ℤ_{m′_{i}}} e^{−2πij′f(ym′_{i}+r)/m′_{i}} = t ∑_{r∈ℤ_{m′_{i}}} e^{−2πij′f(r)/m′_{i}}, (5.4)

e, pelo teorema 72, isto é limitado, em módulo, por

tc_{2}(k, θ)(m′_{i})^{1− \frac{1}{k} +θ} = tc_{2}(k, θ)(m′_{i})^{1− \frac{1}{2k}}

= t^{1/(2k)}c_{2}(k, θ)(m′_{i}t)^{1− \frac{1}{2k}} = t^{1/(2k)}c_{2}(k, θ)(m_{i})^{1− \frac{1}{2k}} .

Como t ≤ m_{i}/Δ(m_{i}), temos que

| ∑_{x∈ℤ_{m_{i}}} e^{−2πijf(x)/m_{i}} | ≤ \frac{c_{2}(k, θ)m_{i}}{\sqrt[2k]{Δ(m_{i})}} ,

e isto é o(m_{i}), pois, por hipótese, Δ(m_{i}) → ∞.

Segue do lema 33 (adaptado a grafos com pesos) que, para todo ε > 0, existe i_{0} > 0 tal que, se i ≥ i_{0}, o grafo com pesos PCG_{m_{i}}^{+}(Im_{m_{i}}^{∗} f(x)) é εregular com densidade 1, e em particular, é (ε, 1)-inf-regular. Como vimos, isto implica que o grafo de Chung-Graham ordinário CG_{m_{i}}^{+}(Im_{m_{i}} f(x)) é (ε, 1/L)-inf-regular, para todo i ≥ i_{0}, como queríamos.

Seja M a subsequência dos primos. O teorema 73 mostra que a Msequência S_{M} = (F_{m_{i}})_{i∈ℕ} dada por F_{m_{i}} = Im_{m_{i}} f(x) ⊂ ℤ_{m_{i}} é “praticamente” adição-regular. O único problema é que a densidade não está correta.

Apesar deste pequeno problema, a prova do teorema 67 pode ser facilmente adaptada para provar o seguinte teorema:

Teorema 74. Seja f um polinômio de coeficientes inteiros, não constante. Para todos 0 < η, γ < 1 , existem constantes C = C(η, γ) e n_{0} = n_{0}(η, γ) tais que, se p = p(n) ≥ C/n e se n é um primo com n ≥ n_{0}, então, com probabilidade pelo menos 1−γ, temos que qualquer η-fração de ℤ_{n,p} contém x, y tais que existe z ∈ ℤ_{n} com x − y = f(z).

Para a próxima aplicação, usaremos um outro teorema de Hua, que trata de somas trigonométricas parciais. A prova deste resultado pode ser vista no capítulo 1 de [20].

Teorema 75 (L. K. Hua). Sejam m um inteiro positivo e f(x) = a_{k}x^{k} + …+a_{1}x+a_{0} um polinômio com coeficientes inteiros. Se mdc(a_{k}, …, a_{1}, m) = 1, então para todo θ > 0, existe uma constante c_{3}(k, θ) que só depende de k e de θ tal que para todo t com 1 ≤ t ≤ m, temos

| ∑_{x=1}^{t} e^{−2πif(x)/m}| ≤ c_{2}(k, θ)m^{1− \frac{1}{k} +θ}.

Com isto, poderemos exibir um exemplo de uma M-sequência S_{M} = (S_{m_{i}})_{i∈ℕ} esparsa (isto é, |S_{m_{i}}|/m_{i} → 0), adição-regular e subtração-regular. Seja M o conjunto dos primos, e para todos m_{i} ∈ M, μ > 0, seja Q(m_{i}, μ) o subconjunto de ℤ_{m_{i}} dado por

Q(m_{i}, μ) = {x^{2} mod m_{i}: 1 ≤ x ≤ m_{i}^{1/2+μ}}.

O corolário abaixo segue imediatamente do teorema 75 e do lema 33.

Corolário 76. Fixe 0 < μ < 1/2 e considere a M-sequência S_{M} = (S_{m_{i}})_{i∈ℕ}, onde M é o conjunto dos primos e para todo i ∈ ℕ, S_{m_{i}} = Q(m_{i}, μ). Então S_{M} é adição-regular e subtração-regular.

Nossos dois últimos teoremas seguem do corolário acima, e dos teoremas 67 e 68.

Teorema 77. Para todos 0 < μ < 1/2, 0 < η, γ < 1, existem constantes C = C(μ, η, γ) e n_{0} = n_{0}(μ, η, γ) tais que, se p = p(n) ≥ C/n^{1/2+μ} e se n é um primo com n ≥ n_{0}, então, com probabilidade pelo menos 1 − γ, temos que

ℤ_{m_{i},p} →_{η} Soma(Q(m_{i}, μ)).

Teorema 78. Para todos 0 < μ < 1/2, 0 < η, γ < 1, existem constantes C = C(μ, η, γ) e n_{0} = n_{0}(μ, η, γ) tais que, se p = p(n) ≥ C/n^{1/2+μ} e se n é um primo com n ≥ n_{0}, então, com probabilidade pelo menos 1 − γ, temos que

ℤ_{m_{i},p} →_{η} Diferença(Q(m_{i}, μ)).

O teorema 75 pode ser usado para achar outros exemplos de M-sequên-cias esparsas, adição-regulares e subtração-regulares, mas não prosseguiremos nesta direção.

Conclusão

Para encerrar o presente trabalho, desejamos mencionar alguns problemas relacionados às versões probabilísticas dos teoremas de Schur e Särkozy.

Começamos falando sobre problemas relacionados à versão probabilística do Teorema de Schur. Em primeiro lugar, seria interessante verificar a validade da conjectura 55. Mesmo que ela seja falsa, seria interessante provar isto.

Outro problema, muito mais interessante, seria fazer uma versão probabilística para o Teorema de Schur para grupos abelianos. O enunciado abaixo, por exemplo, é uma generalização natural do Problema de Schur em ℤ_{n}.

Problema 79 (Schur probabilístico em grupos abelianos). O teorema Schur(η) é verdadeiro se trocarmos ℤ_{n} por uma classe qualquer de grupos abelianos finitos G = (G_{j})_{j=1}^{∞} com |G_{j}| → ∞.

A demonstração do teorema 13 pode ser adaptada para o problema acima. É claro que, no caso de a conjectura 55 ser verdadeira, poderíamos trocar a hipótese p > C log n/\sqrt{n} (que é o que sabemos fazer) por p > C/\sqrt{n} (que é o valor “certo”).

O problema acima fica mais difícil se quisermos considerar a “densidade correta”. Vamos explicar isto. Recordemos que, em ℤ_{n}, o motivo pelo qual exigimos inicialmente no enunciado do problema que a densidade seja maior que 1/2 é a existência, para n par, de conjuntos livres de somas (ou seja, sem soluções de x + y = z) com densidade 1/2. Quando consideramos um grupo abeliano em geral, nem sempre haverá um subconjunto livre de somas com metade dos elementos do grupo. Por exemplo, em ℤ_{7}, pode-se verificar que a cardinalidade do maior subconjunto livre de somas é 2.

Seja G um grupo abeliano e seja μ(G) a densidade do maior subconjunto livre de somas de G. Sabe-se, por exemplo, que μ(ℤ_{2n}) = 1/2 e que μ(ℤ_{7}) = 2/7. Recentemente, Green e Rusza [16] determinaram o valor de μ(G) para todo G finito. Enunciaremos o resultado deles abaixo.

Teorema 80 (Green, Rusza, 2004). Seja G um grupo abeliano de ordem n.

• Se n é divisível por algum primo congruente a 2 mod 3, então μ(G) = \frac{1}{3} + \frac{1}{3p}, onde p é o menor primo congruente a 2 mod 3 que divide n;

• Se n não é divisível por nenhum primo congruente a 2 mod 3, mas 3 | n, então μ(G) = \frac{1}{3};

• Se n só tem fatores primos congruentes a 1 mod 3, então μ(G) = \frac{1}{3} − \frac{1}{3m}, onde m é o expoente de G (a máxima ordem de um elemento do grupo).

Em particular, para todo G abeliano finito, 2/7 ≤ μ(G) ≤ 1/2.

É natural tentar resolver o problema 79 trocando a densidade 1/2 + η pela densidade “correta”, μ(G) + η. Daremos um exemplo. Sabemos, pelo teorema acima, que μ(ℤ_{3}^{n}) = μ(ℤ_{3} × … × ℤ_{3}) = 1/3. Seja (ℤ_{3}^{n})_{p} um subconjunto aleatório de ℤ_{3}^{n} obtido por 3^{n} sorteios independentes, cada um com probabilidade p. Seria interessante resolver o seguinte problema:

Problema 81 (Schur para grupos com densidade corrigida). Para todo η > 0, existe uma constante C = C(η) tal que, se p = p(m) é tal que p(3^{n}) > C3^{−n/2}, então, com probabilidade tendendo a 1 quando n → ∞, qualquer subconjunto de (ℤ_{3}^{n})_{p} com densidade pelo menos 1/3+η tem triplas de Schur.

Naturalmente, pode-se formular uma versão com outra classe de grupos, no lugar de (ℤ_{3^{n}})_{n}.

Uma outra área de problemas é a de versões probabilísticas do Teorema de Schur com coloração (e não mais densidade). Por exemplo, vimos no capítulo introdutório (teorema 20, referência [14]) que Graham, Rödl e Ruciński provaram que se N = N(n) satisfaz N/n^{1/2} → ∞, então [n]_{N} → (Schur)_{2} com probabilidade tendendo a 1 quando n → ∞ (estas notações foram definidas pelas equações 1.5 e 1.8). No entanto, a generalização disto para m > 2 está em aberto.

Sobre a versão probabilística do Teorema de Sárközy, um desafio interessante seria investigar a versão difícil do problema de Sárközy. Lembramos que tratamos da equação x − y = z^{2} no nosso resultado (teorema 14), e a exigência sobre os termos da equação é que x e y estejam no subconjunto de densidade η de ℤ_{n,p}, enquanto que z pode ser qualquer elemento de ℤ_{n}. A proposta é investigar o que acontece se exigirmos que z (ou z^{2}) também esteja no subconjunto de densidade η de ℤ_{n,p}.

Outro problema, mais humilde, é achar outras M-sequências interessantes (não muito artificiais) que sejam adição-regulares ou subtração-regulares. Evidentemente, para cada nova M-sequência adição- ou subtração-regular, teremos um novo corolário do teorema 67 ou do teorema 68.

Bibliografia

[1] M. Aigner and G. Ziegler, Proofs from The Book, second ed., Springer-Verlag, Berlin, 2001, Including illustrations by Karl H. Hofmann. MR MR1801937 (2001j:00001)

[2] T. M. Apostol, Introduction to analytic number theory, Springer-Verlag, New York, 1976, Undergraduate Texts in Mathematics. MR 55 #7892

[3] B. Bollobás, Modern graph theory, Springer-Verlag, New York, 1998. MR 99h:05001

[4] , Random graphs, second ed., Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge University Press, Cambridge, 2001. MR 2002j:05132

[5] F. R. K. Chung and R. L. Graham, Quasi-random subsets of Z_{n}, J. Combin. Theory Ser. A 61 (1992), no. 1, 64–86. MR 94b:05168

[6] F. R. K. Chung, R. L. Graham, and R. M. Wilson, Quasi-random graphs, Combinatorica 9 (1989), no. 4, 345–362. MR 91e:05074

[7] P. Erdős and M. Simonovits, A limit theorem in graph theory, Studia Scientiarum Mathematicarum Hungarica 1 (1966), 51–57.

[8] P. Erdős and A. H. Stone, On the structure of linear graphs, Bulletin of the American Mathematical Society 52 (1946), 1087–1091.

[9] P. Erdős and P. Turán, On some sequences of integers, Journal of the London Mathematical Society 11 (1936), no. 2, 261–264.

[10] P. Frankl, R. L. Graham, and V. Rödl, Quantitative theorems for regular systems of equations, J. Combin. Theory Ser. A 47 (1988), no. 2, 246– 261. MR 89d:05020 [11] H. Furstenberg, Ergodic behavior of diagonal measures and a theorem

of Szemerédi on arithmetic progressions, J. Analyse Math. 31 (1977), 204–256. MR 58 #16583

[12] S. Gerke, Y. Kohayakawa, V. Rödl, and A. Steger, Small subsets inherit sparse ε-regularity, in preparation, 2004.

[13] S. Gerke, T. Schickinger, and A. Steger, K^{5}-free subgraphs of random graphs, Random Structures and Algorithms 24 (2004), no. 2, 194–232.

[14] R. L. Graham, V. Rödl, and A. Ruciński, On Schur properties of random subsets of integers, J. Number Theory 61 (1996), no. 2, 388–408. MR 98c:05013

[15] R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey theory, second ed., John Wiley & Sons Inc., New York, 1990, A Wiley-Interscience Publication. MR 90m:05003

[16] B. Green and I. Z. Ruzsa, Sum-free sets in abelian groups.

[17] P. E. Haxell, Y. Kohayakawa, and T. Łuczak, The induced size-Ramsey number of cycles, Combin. Probab. Comput. 4 (1995), no. 3, 217–239. MR 96h:05140

[18] , Turán’s extremal problem in random graphs: forbidding even cycles, J. Combin. Theory Ser. B 64 (1995), no. 2, 273–287. MR 96e:05151

[19] , Turán’s extremal problem in random graphs: forbidding odd cycles, Combinatorica 16 (1996), no. 1, 107–122. MR 97k:05180

[20] L. K. Hua, Additive theory of prime numbers, Translations of Mathematical Monographs, Vol. 13, American Mathematical Society, Providence, R.I., 1965. MR MR0194404 (33 #2614)

[21] , Introduction to number theory, Springer-Verlag, Berlin, 1982. MR MR665428 (83f:10001)

[22] S. Janson, T. Łuczak, and A. Ruciński, Random graphs, Wiley-Interscience, New York, 2000. MR 2001k:05180

[23] Y. Kohayakawa, Szemerédi’s regularity lemma for sparse graphs, Foundations of computational mathematics (Rio de Janeiro, 1997), Springer, Berlin, 1997, pp. 216–230. MR 99g:05145 [24] Y. Kohayakawa, T. Łuczak, and V. Rödl, Arithmetic progressions of

length three in subsets of a random set, Acta Arith. 75 (1996), no. 2, 133–163. MR 97b:11011

[25] , On K^{4}-free subgraphs of random graphs, Combinatorica 17 (1997), no. 2, 173–213. MR 98h:05166

[26] Y. Kohayakawa and V. Rödl, Szemerédi’s regularity lemma and quasirandomness, Recent advances in algorithms and combinatorics, CMS Books Math./Ouvrages Math. SMC, vol. 11, Springer, New York, 2003, pp. 289–351. MR MR1952989 (2003j:05065)

[27] J. Komlós and M. Simonovits, Szemerédi’s regularity lemma and its applications in graph theory, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), János Bolyai Math. Soc., Budapest, 1996, pp. 295– 352. MR 97d:05172

[28] C. McDiarmid, On the method of bounded differences, Surveys in combinatorics, 1989 (Norwich, 1989), London Math. Soc. Lecture Note Ser., vol. 141, Cambridge Univ. Press, Cambridge, 1989, pp. 148–188. MR 91e:05077

[29] C. G. Moreira and Y. Kohayakawa, Tópicos em combinatória contemporânea, Publicações Matemáticas do IMPA. [IMPA Mathematical Publications], Instituto de Matemática Pura e Aplicada (IMPA), Rio de Janeiro, 2001, 23^{o} Colóquio Brasileiro de Matemática. [23rd Brazilian Mathematics Colloquium]. MR MR1846391 (2002e:05003)

[30] R. Rado, Studien zur Kombinatorik., Math. Z. 36 (1933), 424–480 (German).

[31] V. Rödl and A. Ruciński, Threshold functions for Ramsey properties, J. Amer. Math. Soc. 8 (1995), no. 4, 917–942. MR 96h:05141

[32] , Rado partition theorem for random subsets of integers, Proc. London Math. Soc. (3) 74 (1997), no. 3, 481–502. MR 98d:05147

[33] A. Sárkőzy, On difference sets of sequences of integers. I, Acta Math. Acad. Sci. Hungar. 31 (1978), no. 1–2, 125–149. MR 57 #5942

[34] E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975), 199–245, Collection of articles in memory of Juriĭ Vladimirovič Linnik. MR 51 #5547 [35] , Regular partitions of graphs, Problèmes combinatoires et

théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), CNRS, Paris, 1978, pp. 399–401. MR 81i:05095

[36] P. Turán, Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok 48 (1941), 436–452, in Hungarian, with German summary.

[37] B. L. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw Archief voor Wiskunde 15 (1927), 212–216.