Um M6todo Probabilistico em Combinat6ria

C4sar Alberto Bravo Pariente

DISSERTACAO APRESENTADA

A 0

INSTITUTO D E MATEMATICA E ESTAT~STICA

DA

UNIVERSIDADE DE SAO PAUL0

PARA

OBTENCAO DO GRAU DE MESTRE

EM

MATEMATICA APLICADA

Area de Concentraggo: Ci6ncia da Computac;iio

Orientador : Prof. Dr. Yoshiharu Kohayakawa

-S5o Paulo, Outubro de 1996-

Urn M6todo Probabilistico em Combinatbria

Este exemplar corresponde a reda~iio final da dissertaqao devidamente corrigida

e defendida por Cksar Alberto Bravo Pariente e aprovada pela comissiio julgadora.

Siio Paulo, 4 de Dezembro de 1996.

Banca examinadora:

Prof. Dr. Yoshiharu Kohayakawa (orientador) - IME-USP

Prof. Dr. Vladimir Belit'sky - IME-USP

Prof. Dr. David Grable - Humbolt Universitat zu Berlin, Alemanha

Agradecimentos Sem dJvidas, o presente trabalho niio tivesse podido ser realizado sem a direqgo do

meu orientador. Professor Doutor Yoshiharu Iiohayakawa. Sua pacibcia e apoio constante sempre foram alkm das minhas maiores expectativas. SLo para ele os protestos de meu maior respeito e agradecimento. E oportuno agradecer aqui tambkm aos profesores Doutor \--ladimir Belitskj e Doutor David Grable clue fizeram parte de banca na defesa de minha dissertaqgo.

Desejo agradecer tambkm aos colegas que tiveram o trabalho de revisar tanto meu projeto de dissertaqiio quanto as vers6es prkvias deste trabalho, por ter me dedicado parte de seu tempo no meio de suas pr6prias atividades academicas; notadamente Claus -4kira Matsushigue, Flavio Keidi Miyazawa, Jair Donadelli Junior, Orlando Lee e Patricia Cristina Gimenez.

Quero ainda lembrar dos grandes amigos que fiz no Brasil, com quens compartilhe momentos bons e ruins, e que sempre me ajudaram a enfrentar os problemas que se apresentaram na minha estadia em Sampa: Flavio Leidi Miyazawa, Marcelo Esteban Coniglio, Simone, Sergio e Gabriel Borger, Sonia Elizabeth Trepode, os amigos do CRUSP e, ultimamente, a muito amigiivel turma '96 da Oficina de Teatro do TUSP.

Finalmente queria agradecer a todos meus professores, tanto da graduas50 na Uni- versidad Nacional Mayor de San Marcos no Perh, quanto da p6s gradua~iio na Universidade de Siio Paulo no Brasil. Quero dedicar a eles (e elas) este trabalho, com a esperanqa de que nosso amor pela matemiitica seja tgo duradouro (jii que n5o tiio frutifero), quanto o seu.

Durante a fase de crkditos de matkrias do mestrado o autor usufruiu de uma bolsa da CAPES.

Abstract The following work is an effort to present, in survey form, a collection of results that

illustrate the application of a certain probabilistic method in cornbinatorics. We do not present new results in the area: however, we do believe that the systematic presentation of these results can help those who use probabilistic methods comprehend this useful technique.

The results we refer to have appeared over the last decade in the research literature and were used in the investigation of problems which have resisted other, more classical, approaches. Instead of theorizing about the method, we adopted the strategy of presenting three problems, using them as practical examples of the application of the method in question. Surprisingly, despite the difficulty of the solutions to these problems, they share the characteristic of being able to be formulated very intuitively, as we will see in Chapter One.

We should warn the reader that despite the fact that the problems which drive our discussion belong to such different fields as number theory, geometry, and combinatorics, our goal is to place emphasis on what their solutions have in common and not on the subsequent implications that these problems have in their respective fields. Occasionally, we will comment on other potential applications of the tools utilized to solve these problems.

The problems which we are discussing can be characterized by the decades-long wait for their solution: the first, from number theory, arose from the research in Fourier series conducted by Sidon at the beginning of the century and was proposed by him to Erdos in 1932. Since 1950, there have been diverse advances in the understanding of this problem, but the result we talk of comes from 1981. The second problem, from geometry, is a conjecture formulated in 1951 by Heilbronn and finally refuted in 1982. The last problem, from combinatorics, is a conjecture formulated by Erdos and Hanani in 1963 that was treated in several particular cases but was only solved in its entirety in 1985.

PrefacioO presente trabalho �e um esfor�co de apresentar, organizado em forma de survey, umconjunto de resultados que ilustram a aplica�c~ao de um certo m�etodo probabil��stico. Embo-ra n~ao apresentemos resultados novos na �area, acreditamos que a apresenta�c~ao sistem�aticadestes resultados pode servir para a compreens~ao de uma ferramenta �util para quem usados m�etodos probabil��sticos na sua pesquisa em combinat�oria.Os resultados de que falaremos tem aparecido na �ultima d�ecada na literatura especia-lizada e foram usados na investiga�c~ao de problemas que resistiram a outras aproxima�c~oesmais cl�assicas. Em vez de teorizar sobre o m�etodo a apresentar, n�os adotaremos a es-trat�egia de apresentar tres problemas, usando-os como exemplos pr�aticos da aplica�c~ao dom�etodo em quest~ao. Surpreendentemente, apesar da di�culdade que apresentaram pa-ra ser resolvidos, estes problemas compartilham a caracter��stica de poder ser formuladosmuito intuitivamente, como veremos no Cap��tulo 1.Devemos advertir que embora os problemas que conduzem nossa exposi�c~ao perten�cama �areas t~ao diferentes quanto teoria de n�umeros, geometria e combinat�oria, nosso intuito�e fazer enfase no que de comum tem as suas solu�c~oes e n~ao das posteriores implica�c~oesque estes problemas tenham nas suas respectivas �areas. Ocasionalmente comentaremossim, outras poss��veis aplica�c~oes das ferramentas usadas para solucionar estes problemasde motiva�c~ao.Os problemas de que tratamos tem-se caracterizado por aguardar v�arias d�ecadas emespera de solu�c~ao: O primeiro, da teoria de n�umeros, surgiu na pesquisa de s�eries de fourierque Sidon realizava a princ��pios do s�eculo e foi proposto por ele a Erd}os em 1932. Emboratenham havido, desde 1950, diversos avan�cos na pesquisa deste problema, o resultado deque falaremos data de 1981. J�a o segundo problema, da geometria, �e uma conjecturaformulada em 1951 por Heilbronn e refutada �nalmente em 1982. O �ultimo problema, decombinat�oria, �e uma conjectura de Erd}os e Hanani de 1963, que foi tratada em diversoscasos particulares at�e ser �nalmente resolvida em toda sua generalidade em 1985.

1

Sum�ario1 Visita guiada �a motiva�c~ao e nota�c~oes 21.1 Uma seq�uencia de Sidon densa . . . . . . . . . . . . . . . . . . . . . . . . . 41.1.1 O n�umero de independencia dos grafos sem triangulos . . . . . . . . 81.2 Um limitante inferior para o problema de Heilbronn . . . . . . . . . . . . . 101.2.1 O n�umero de independencia dos hipergrafos sem 2-circuitos . . . . . 111.3 A conjectura de Erd}os e Hanani . . . . . . . . . . . . . . . . . . . . . . . . 131.3.1 A vers~ao restrita de Pippenger do teorema de Frankl e R�odl . . . . 142 Conjuntos Independentes 182.1 Grafos sem triangulos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.1.1 A transforma�c~ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.1.2 O algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302.2 Hipergrafos de cintura maior que 4 . . . . . . . . . . . . . . . . . . . . . . 332.2.1 A transforma�c~ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372.2.2 O algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412.3 Conseq�uencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432.3.1 Uma seq�uencia de Sidon densa . . . . . . . . . . . . . . . . . . . . . 432.3.2 Um limitante inferior para o problema de Heilbronn . . . . . . . . . 493 Uma T�ecnica de R�odl 523.1 A vers~ao restrita de Pippenger do teorema de Frankl e R�odl . . . . . . . . 533.1.1 A transforma�c~ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533.1.2 O algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593.2 Conseq�uencias: a conjectura de Erd}os e Hanani . . . . . . . . . . . . . . . 613.3 Apendice: Desenvolvimento hist�orico da t�ecnica de R�odl . . . . . . . . . . . 633.3.1 O trabalho seminal de R�odl e os coment�arios de Spencer . . . . . . 633.3.2 O teorema de Frankl e R�odl . . . . . . . . . . . . . . . . . . . . . . 673.3.3 A extens~ao de Pippenger e Spencer . . . . . . . . . . . . . . . . . . 69

1

Cap��tulo 1Visita guiada �a motiva�c~ao e nota�c~oesEsta introdu�c~ao pretende ser um roteiro para a leitura de nossa disserta�c~ao. Vamosapresentar aqui os problemas que motivaram os resultados expostos em nosso trabalho epretendemos que esta apresenta�c~ao seja o mais \reader-friendly" poss��vel para que o leitorpossa us�a-la mesmo para se informar rapidamente de nossa discuss~ao, usando os cap��tulosseguintes para conhecer os detalhes das demonstra�c~oes.Adotamos esta estrat�egia mesmo porque o discurso nos cap��tulos seguintes n~ao �e con-vidativo o su�ciente para permitir uma r�apida revis~ao do material apresentado.Este �e o momento para explicitar o que s~ao os tres problemas \leit-motiv" de quefalaremos: o primeiro, da teoria de n�umeros, consiste na constru�c~ao de uma seq�uenciapertencente a uma certa classe. O segundo, da geometria, limita inferiormente a �aream��nima num certo tipo de con�gura�c~ao de triangulos no plano. O terceiro �e um problemade \combinat�oria pura", por assim dizer, e preferimos adiar um pouco sua descri�c~ao.Para ilustrar o uso do m�etodo probabil��stico nestes problemas de motiva�c~ao, n�os nosconcentraremos na discuss~ao de dois objetos combinat�orios, n�umero de independencia emgrafos e hipergrafos, e coberturas m��nimas, discutidos cada um deles nos Cap��tulos 2 e 3respectivamente.Em cada caso, apresentaremos o problema de motiva�c~ao de forma intuitiva e assina-laremos as distintas etapas que se deram na sua pesquisa, remetendo o leitor �a se�c~aocorrespondente da disserta�c~ao para os detalhes t�ecnicos das provas.Vamos esbo�car agora o m�etodo probabil��stico que est�a por tr�as dos avan�cos na pesquisados problemas mencionados.Em geral, o uso de t�ecnicas probabil��sticas em combinat�oria permite mostrar a existenciade um certo objeto combinat�orio. A id�eia geral �e mostrar que a probabilidade de que existaum objeto como desejado �e positiva. Por exemplo, num grafo, podemos estar interessadosem mostrar a existencia de um conjunto \grande" de v�ertices entre os quais n~ao h�a arestas.A estrat�egia trivial para uma tal demonstra�c~ao existencial consiste em sortear indepen-dentemente, com alguma probabilidade, os elementos do conjunto envolvido (no exemplo,os v�ertices) e calcular depois a probabilidade de que os elementos escolhidos formem o ob-2

jeto combinat�orio desejado. Se essa probabilidade for positiva, podemos �car satisfeitose aceitar esta estrat�egia como razo�avel para a constru�c~ao do objeto desejado. Mas, emgeral, essa pode ser uma vis~ao otimista demais.Em vez disso, a estrat�egia do m�etodo probabil��stico que visamos ilustrar neste traba-lho consiste em construir aos poucos o objeto combinat�orio no qual estamos interessados:ou seja, escolhe-se uma quantidade pequena dos elementos do conjunto de interesse demodo a formar um objeto como o desejado, mas de tamanho menor. Depois repete-seesta constru�c~ao um n�umero su�ciente de vezes de modo que a uni~ao dos objetos \peque-nos" constru��dos a cada passo formem o objeto combinat�orio do tamanho desejado. Adesvantagem desta aproxima�c~ao de \sorteios sucessivos" �e a varia�c~ao indesejada de algunsparametros de interesse. Por exemplo, se num grafo todos os v�ertices incidem em tresarestas podemos perder essa propriedade ao apagar alguns v�ertices.Tencionamos ressaltar que as provas dos resultados principais esbo�cadas neste trabalhocompartilham de caracter��sticas semelhantes: em linhas gerais, essas provas dividem-seem duas etapas, a que n�os nos referiremos como \A transforma�c~ao" e \O algoritmo". Naprimeira etapa, estuda-se uma transforma�c~ao do objeto em considera�c~ao, transforma�c~aoesta que altera os parametros do objeto de forma controlada; tipicamente, a transforma�c~aoenvolve escolher e remover um conjunto (de v�ertices ou arestas) ao acaso. Na segundaetapa, mostra-se que iterando-se a transforma�c~ao em quest~ao um n�umero adequado devezes, pode-se fazer com que os parametros de interesse atinjam um determinado valor.A seguir vamos expor o funcionamento deste processo em cada um dos problemas quetrataremos.

3

1.1 Uma seq�uencia de Sidon densaNesta se�c~ao vamos discorrer sobre um certo problema da teoria de n�umeros que Sidonpropos em 1932 a Erd}os. Trataremos sempre de seq�uencias formadas por n�umeros naturais.Em geral, pode se dizer que neste contexto �e interessante conhecer a rapidez de crescimentodas seq�uencias em estudo. Sendo pouco relevante estudar essa rapidez para seq�uenciasparticulares, vamos nos concentrar em seq�uencias pertencentes a uma certa \classe". Paradar um pouco de contexto ao t��tulo desta se�c~ao vamos de�nir o conceito de densidadede uma seq�uencia, embora ele esteja presente s�o implicitamente nos resultados que vamosdescrever.De�ni�c~ao 1.1.1 Seja S uma seq�uencia de n�umeros inteiros positivos estritamente mo-n�otona crescente, digamos S = fa1 < a2 < : : : < ak < : : :g, �nita ou in�nita. Para cadan de�nimos o n�umero de contagem fS(n) de S at�e n (tamb�em conhecido por fun�c~aode contagem) como o n�umero de elementos de S menores ou iguais a n.A densidade de Schnirelmann �S de S �e�S = infn fS(n)n :A densidade assint�otica inferior d de S e a densidade assint�otica superior dde S s~ao de�nidas por dS = lim infn!1 fS(n)n ;dS = lim supn!1 fS(n)n :Se dS = dS dizemos que S possui densidade assint�otica dS, dada pelo valor comum.Segundo Erd}os (cf. [7]), Sidon colocou tres problemas:(1) Seja S = fa1 < a2 < : : : < ak < : : :g uma seq�uencia in�nita de inteiros e, paratodod n inteiro positivo, BS(n) o n�umero de solu�c~oes de n = ai + aj. Existe umaseq�uencia S para a qual BS(n) > 0, por�em para todo � > 0 temos BS(n)=n� ! 0,conforme n!1?(2) Seja S = f1 � a1 < a2 < : : : < ak � ng e suponha que todos os ai+aj s~ao diferentespara todo i; j 2 f1; : : : ; kg. Determine fS(n) = max k.(3) Seja S = fa1 < a2 < : : : < ak : : :g e suponha que todos os ai+aj s~ao diferentes paratodo i; j 2 f1; : : : ; k; : : :g. Determine fS(n).4

Observe que uma seq�uencia satisfazendo (1) �e uma base dos naturais no sentido que todonatural pode-se escrever como soma de seus elementos. Por outro lado, as seq�uenciassatisfazendo (2) e (3) n~ao precisam ter esta propriedade e, mais ainda, a proibi�c~ao derepetir somas impede obter alguns dos inteiros como soma de elementos de seq�uenciasdestes tipos. N�os nos concentraremos em seq�uencias de tipo (2) e (3).A pesquisa desenvolvida em torno destes problemas tem dado origem a uma �areaconhecida como teoria aditiva de n�umeros. Em homenagem a Sidon, as seq�uenciascomo as descritas por (2) e (3) formam uma classe que leva seu nome.De�ni�c~ao 1.1.2 Uma seq�uencia de Sidon �e uma seq�uencia de n�umeros inteiros posi-tivos S = fa1 < a2 < ::: < ak < :::g, �nita ou in�nita, tal que todo inteiro m tem, nom�aximo, uma representa�c~ao da formam = ai + aj; com ai; aj 2 S; i < j:Por abuso de nota�c~ao, vamos �as vezes chamar as seq�uencias de Sidon de conjuntos deSidon.Vamos considerar primeiro o caso �nito.Denotamos com s(n) o n�umero m�aximo de elementos de [n] = f1; 2; : : : ; ng que formamuma seq�uencia de Sidon. Os primeiros limites triviais para s(n) s~ao os seguintes:(2n)1=3 < s(n) < (2n)1=2 + 1;sendo que o limite inferior �e fornecido pelo algoritmo guloso e o superior �e devido aofato de que para toda seq�uencia de Sidon S contida em [n], as diferen�cas positivas doselementos de S s~ao n�umeros distintos menores que n.O problema de determinar s(n) foi investigado por Erd}os, Tur�an e Chowla com osseguintes resultados.Teorema 1.1.3 (Erd}os e Tur�an, '41; [9])1p2 � lim inf s(n)pn � lim sup s(n)pn � 1:Teorema 1.1.4 (Erd}os, '44; Chowla, '44; [6] e [4])lim inf s(n)pn � 1:Ou seja, o crescimento de s(n) �e aproximadamente o crescimento da raiz quadrada den, conforme n cresce inde�nidamente. 5

No caso in�nito n~ao se tem resultados t~ao precisos. Seja S uma seq�uencia de Sidonin�nita, denotamos por fS(n) o n�umero de elementos de S n~ao maiores que n. Em [9],Erd}os e Tur�an comentam que para toda seq�uencia in�nita de Sidon S temoslim inf fS(n)pn = 0;mas que existe uma seq�uencia de Sidon S tal quelim sup fS(n)pn � 12 :De fato, para a primeira a�rmativa, Erd}os provou muito mais:Teorema 1.1.5 (Erd}os, '55; [12]) Para toda seq�uencia in�nita de Sidon S temoslim inf fS(n)s lognn <1:Temos ainda uma melhora para o limite superior.Teorema 1.1.6 (Kr�uckenberg, '61; [15]) Existe uma seq�uencia in�nita de Sidon S talque lim sup fS(n)pn � 1p2 :J�a que tanto limite inferior quanto limite superior caracterizam subseq�uencias convergentesaos pontos de acumula�c~ao m��nimo e m�aximo da seq�uencia original, esses resultados n~aodizem muito sobre a rapidez de crescimento de fS(n).Passaram-se vinte anos at�e se conseguir construir uma seq�uencia de Sidon de cresci-mento mais r�apido: em 1981, Ajtai, Koml�os e Szemer�edi [2] apresentaram uma constru�c~aoprobabil��stica de uma seq�uencia de Sidon mais densa que as anteriores. Eis o enunciado.Teorema 1.1.7 (Ajtai, Koml�os e Szemer�edi, '81; [2]) Existe uma seq�uencia de Si-don S tal que fS(n) > c(n logn)1=3;para todo n 2 N, onde c > 0 �e uma constante universal.A estrat�egia geral na prova dos resultados anteriores ao Teorema 1.1.7 esteve baseada emdois fatos:(a) Associar a cada n�umero primo p um conjunto �nito de Sidon, normalmente baseadoem congruencias m�odulo p. 6

(b) Escolher uma seq�uencia de n�umeros primos tal que os conjuntos associados a primosdiferentes n~ao compartilhem somas.Desse modo a uni~ao dos conjuntos associados aos n�umeros primos da seq�uencia formavaa seq�uencia in�nita de Sidon procurada.Existia neste enfoque um compromisso na constru�c~ao da seq�uencia de primos. Por umlado, era necess�ario que termos consecutivos desta seq�uencia estivessem longe o bastantepara evitar que seus conjuntos associados compartilhassem somas. Por outro lado, ostais termos consecutivos n~ao deviam estar longe demais para evitar que a densidade daseq�uencia fosse \baixa". Manter esse compromisso foi a preocupa�c~ao principal de Erd}os,Tur�an e Kr�uckenberg.No novo resultado, Ajtai, Koml�os e Szemer�edi, atacam este problema construindo a talseq�uencia de primos baseando-se num resultado de grafos sem triangulos (3-circuitos; vejaa pr�oxima subse�c~ao, Teorema 1.1.9). A id�eia b�asica �e usar a proibi�c~ao de existir triangulospara evitar repetir somas de termos da seq�uencia em constru�c~ao. Os conjuntos associadosaos n�umeros primos tamb�em s~ao melhorados.Antes de abandonar a discuss~ao do Teorema 1.1.7 vamos mencionar uma outra apli-ca�c~ao sua que tem recuperado importancia devido a um resultado recente na investiga�c~aodos n�umeros de Ramsey R(3; t).O grafo completoKn �e o grafo sobre n v�ertices tal que entre quaisquer par de v�erticesexiste uma aresta. Se s, t s~ao inteiros positivos, de�nimos o n�umero de Ramsey R(s; t)como o m��nimo n tal que toda 2-colora�c~ao das arestas de Kn induz um Ks monocrom�aticoou um Kt monocrom�atico. Um subgrafo completo �e tamb�em chamado de clique. Equi-valentemente ent~ao, R(s; t) �e o menor inteiro tal que todo grafo sobre n v�ertices tem umclique de s v�ertices ou um conjunto independente de t v�ertices. Usamos G(3)n para denotarum grafo livre de K3, ou seja, tal que nenhum tres de seus v�ertices induz um K3. Emparticular temos R(3; t) = minfn : �(G(3)n ) � t para todo G(3)n g:Considerando os grafos G(3)n com grau m�aximo t temos que o Teorema 1.1.7 implica tri-vialmente que vale n = R(3; t) � c1t2= log t:Recentemente Kim [13], tem mostrado quec2(1� o(1))t2= log t � R(3; t);provando assim que o ordem de magnitude de R(3; t) �e justamente t2= log t. A prova doresultado de Kim est�a baseada no \m�etodo da semialeatoridade" desenvolvido a partir dotrabalho de R�odl que comentamos na Se�c~ao 3.3.17

1.1.1 O n�umero de independencia dos grafos sem triangulosDe�ni�c~ao 1.1.8 Um grafo G = (VG;EG) �e formado por um conjunto VG de v�erticese um conjunto EG de arestas.Cada aresta une um par de v�ertices.Dado um v�ertice x o n�umero de v�ertices aos quais x est�a unido �e o grau d(x) de x.O conjunto dos v�ertices aos quais x est�a unido �e chamado vizinhan�ca de x e denotadopor �(x).O grau m�edio t = t(G) do grafo G �e de�nido por t = Px2VG d(x)=n.Um conjunto independente (de v�ertices) de G �e um subconjunto de VG entre osquais n~ao h�a arestas.O n�umero de independencia �(G) do grafo G �e o tamanho de um conjunto inde-pendente m�aximo, i.e., tal que n~ao existe outro conjunto independente de cardinalidademaior.Se S � V de�nimos o subgrafo induzido por S, denotado G[S], como o grafo comconjunto de v�ertices S e conjunto de arestasEG[S] = fxy 2 EG : x; y 2 Sg:No Cap��tulo 2 estuda-se o n�umero de independencia (isto �e, o tamanho de um conjuntom�aximo de v�ertices que n~ao induz arestas) no contexto de grafos e hipergrafos; o resultadocentral para grafos �e o seguinte.Teorema 1.1.9 (Ajtai, Koml�os e Szemer�edi, '81; [2]) Se um grafo G livre de trian-gulos com n v�ertices tem grau m�edio t > c1, ent~ao G tem n�umero de independencia�(G) > c2n(log t)=t;onde c1 > 0 e c2 > 0 s~ao constantes absolutas.Para de�nir a transforma�c~ao neste caso, mostra-se que se pode tomar um conjunto dev�ertices K de G ao acaso que induz um subgrafo com n�umero de independencia grande ede�ne-se o grafo transformado G� como o grafo induzido pelos v�ertices que n~ao induzemarestas com v�ertices de K. O conjunto K deve ser tal que o quociente n0=t0 entre o n�umerode v�ertices n0 do grafo transformado e seu grau m�edio t0 = Px2VG� d(x)=n0 n~ao decrescemuito em rela�c~ao ao quociente do grafo original. Note que este quociente �e essencialmenteo limite inferior para �(G) do Teorema 1.1.9. Para completar a prova deste resultado,iteramos a transforma�c~ao descrita at�e obtermos um grafo transformado com um n�umerodesprez��vel de v�ertices em rela�c~ao ao grafo original. Demonstra-se a seguir que a uni~aodos conjuntos independentes m�aximos dos subgrafos induzidos pelos conjuntos K geradosdurante as itera�c~oes formam um conjunto independente de tamanho su�cientemente grandeem G. 8

Tamb�em no Cap��tulo 2, apresentamos um resultado an�alogo ao Teorema 1.1.9 parahipergrafos. Este resultado �e, entretanto, mais t�ecnico e assim n~ao o discutiremos aqui.Os resultados acima foram concebidos como instrumentos na investiga�c~ao de problemascombinat�orios em teoria de n�umeros e geometria (cf. Se�c~oes 2.3.1 e 2.3.2).

9

1.2 Um limitante inferior para o problema de Heil-bronnConsideremos o disco D de �area 1 no plano e um conjunto S = fp1; : : : ; png de n pontosde D. Seja �(S) a �area m��nima de um triangulo cujos v�ertices s~ao 3 pontos diferentes deD. Heilbronn (� 51) colocou o problema de calcular�(n) = max�(S);onde S toma valores sobre todos os conjuntos de n pontos em D. A primeira estimativapara �(n) �e �(n) = O(n�1);e Heilbronn conjecturou que o valor correto era �(n) = O(n�2).Conjectura 1.2.1 (Heilbronn, � '51) Para alguma constante absoluta c > 0, todacon�gura�c~ao de n pontos no disco unit�ario cont�em necessariamente um triangulo de �areamenor que c=n2.Erd}os mostrou [18] que se essa conjectura fosse v�alida ent~ao o resultado seria o \melhorposs��vel". Para tanto ele provou que �(n) 6= o(n�2)construindo um conjunto de n pontos em n�1([1; n]2 \ Z2) nenhum tres deles colineares; aa�rmativa decorre de que todo triangulo nesse reticulado tem �area � c=n2, para algumaconstante absoluta c.Vamos comentar como a vis~ao probabil��stica \cl�assica" fornece apenas�(n) � cn�2:Com efeito, dado � > 0, pode-se limitar por c� a probabilidade de que 3 pontos de Descolhidos uniforme e independentemente formem um triangulo de �area � �.Tomando � = c=n2 pode-se provar que 2n pontos escolhidos ao acaso uniforme eindependentemente de�nem em m�edia no m�aximo n triangulos de �area < c=n2. Retirandoum v�ertice de cada um desses triangulos, obtemos um conjunto S de pelo menos n pontosde D sem triangulos de �area menor que c=n2.Por�em a conjectura de Heilbronn �e falsa e foi refutada em 1982 por Koml�os, Pintz eSzemer�edi, [14], que provaram que �(n) n~ao s�o n~ao �e dominada por c=n2 (para algumaconstante c), como seu crescimento �e, pelos menos, mais veloz que esse limite vezes umfator logar��tmico. 10

Teorema 1.2.2 (Koml�os, Pintz e Szemer�edi, '82; [14]) Para todo inteiro n existeuma con�gura�c~ao de n pontos no disco unit�ario que n~ao cont�em triangulos de �area menorque c1(logn)=n2;onde c1 > 0 �e uma constante absoluta.A constru�c~ao probabil��stica que prova este teorema �e uma bela amostra da aplica�c~aode resultados combinat�orios em geometria. O cora�c~ao da prova consiste em de�nir um 3-grafo F sobre n1+� pontos escolhidos ao acaso no disco unit�ario, pondo tres de tais pontosnuma aresta de F se eles formam um triangulo de �area menor ou igual a c1(logn)=n2.Depois mostra-se que retirando-se um v�ertice de cada um dos circuitos de comprimentodois de F , o n�umero de v�ertices n~ao diminui sensivelmente. Da�� o Teorema 1.2.5 (veja apr�oxima subse�c~ao) com parametro k = 2 fornece um conjunto independente de tamanho nem F , i.e., n pontos que n~ao cont�em triangulos de �area menor que c1(logn)=n2, provandoassim o Teorema 1.2.2.1.2.1 O n�umero de independencia dos hipergrafos sem 2-circuitosDe�ni�c~ao 1.2.3 Um hipergrafo F = (X;F) sobre um conjunto n~ao vazio X �e umafam��lia de subconjuntos de X.Os elementos de X s~ao os v�ertices e os elementos de F s~ao as hiperarestas de F .O i-grau di(x) de um v�ertice x 2 X �e o n�umero de (i + 1)-hiperarestas contendo x,i.e. a quantidade de hiperarestas de tamanho i + 1 que cont�em x.A vizinhan�ca de x, denotada �(x), �e o conjunto dos v�ertices que pertencem a algumahiperaresta que cont�em o v�ertice x. De�nimos, ademais,�1(x) = �(x)�i(x) = [y2�i�1(x)�(y); :Se todas as hiperarestas tem o mesmo tamanho h, dizemos que F �e um h-grafo.Um conjunto independente (de v�ertices) de F �e um subconjunto de X que n~aocont�em nenhuma hiperaresta de F .O n�umero de independencia �(F) do hipergrafo F �e o tamanho de um conjun-to independente m�aximo de F , i.e., tal que n~ao existe outro conjunto independente decardinalidade maior.Se S � X de�nimos o subhipergrafo induzido por S, denotado F [S], como o grafocom conjunto de v�ertices S e conjunto de hiperarestasF [S] = fF 2 F : F � Sg:11

De�ni�c~ao 1.2.4 Dado um hipergrafo F = (V;F) e X � V , pomosF(X) = fF 2 F : X � Fg;e d(X) = jF(X)j:Quando X = fxg, escrevemos simplesmente F(x) e d(x) e se X = fx; yg escrevemosF(x; y) e d(x; y).Como acabamos de comentar, a prova do Teorema 1.2.2 est�a baseada no teoremaseguinte.Teorema 1.2.5 (Duke, Lefmann e R�odl, '95; [5]) Sejam dados um inteiro k � 2 eum (k + 1)-grafo F sobre n v�ertices tais que para algum t0 = t0(n) e algum n0 = n0(k; t)temos(i) duas hiperarestas quaisquer se intersectam no m�aximo num v�ertice,(ii) �(F) � tk, onde t � t0(k),(iii) n � n0(k; t).Ent~ao �(F) � cknt (log t)1=k;onde ck �e uma constante absoluta.Na verdade, este teorema �e um corol�ario de um teorema com hip�oteses mais restritivasdevido a Ajtai, Koml�os, Pintz, Spencer e Szemer�edi [1]. Essa vers~ao estabelece o limitanteinferior do Teorema 1.2.5 para hipergrafos sem circuitos de comprimento 2, 3 e 4. A suaprova foi tamb�em baseada no m�etodo probabil��stico que estamos apresentando. No brevepreambulo �a Subse�c~ao 2.2.1 apresentaremos a dedu�c~ao deste resultado mais geral a partirda vers~ao mais restrita. Na Se�c~ao 2.2 apresentaremos, com algum detalhe, o roteiro quesegue a demonstra�c~ao do resultado de Ajtai, Koml�os, Pintz, Spencer e Szemer�edi, emboran~ao apresentemos as provas em forma completa.

12

1.3 A conjectura de Erd}os e HananiO problema que motiva esta se�c~ao �e um pouco diferente dos anteriores no sentido que �eum problema abstrato de combinat�oria. Embora seu enunciado seja muito intuitivo, ossucessivos avan�cos na t�ecnica usada na prova original permitem hoje dizer que a provaoriginal foi desnecessariamente complicada. Eis o enunciado original.Dados inteiros r, k e n (r � k � n), de�nimos M(k; r; n) como a cardinalidade deum sistema m��nimo de k-conjuntos (subconjuntos de tamanho k) de [n] = f1; : : : ; ng talque todo r-conjunto de [n] est�a contido em, no m��nimo, um dos k-conjuntos do sistema.Analogamente denotamos por m(k; r; n) a cardinalidade de um sistema m�aximo de k-conjuntos de [n] tal que todo r-conjunto de [n] est�a contido, no m�aximo, num k-conjuntodo sistema.Conjectura 1.3.1 (Erd}os e Hanani, '63; [8]) Para todo r � k �xos, temoslimn!+1m(k; r; n) kr! nr!�1 = limn!+1M(k; r; n) kr! nr!�1 = 1Erd}os e outros (veja [11]) provaram diversos casos particulares desta conjectura.Por�em, foi s�o em 1985 que R�odl [17], forneceu uma prova desta conjectura em todasua generalidade. Ele provou a conjectura de Erd}os e Hanani usando r-grafos completospara empacotar os r-conjuntos. No mesmo ano, Spencer [19] aprimorou o resultado deR�odl relaxando um pouco as hipoteses e introduzindo o conceito de hipergrafo pseudoaleat�orio com densidade � e tolerancia �. A cobertura dos r-conjuntos ainda se faz comr-grafos completos. Ainda no mesmo ano, Frakl e R�odl [10], conseguem impor condi�c~oessu�cientes para a existencia de uma cobertura quase perfeita num r-grafo. Eles conseguemdeixar de usar r-grafos completos para cobrir os r-conjuntos, retirando apenas um con-junto de arestas e de�nindo como hipergrafo transformado aquele formado pelas arestasque n~ao se intersectam com as retiradas. As condic~oes de regularidade de Spencer s~aotrocadas por condi�c~oes sobre o grau dos v�ertices e sobre a quantidade de arestas contendodois v�ertices. Embora este novo resultado represente um avan�co importante na simpli�-ca�c~ao da t�ecnica desenvolvida para provar a conjectura de Erd}os e Hanani, ele ainda exigehip�oteses um pouco restritivas (a quantidade de hiperarestas que cont�em dois v�erticesdeve ser inversamente proporcional a uma potencia do logaritmo do n�umero de v�ertices).Finalmente, em '89 Pippenger e Spencer [16], apresentaram sua extens~ao do teoremade Frankl e R�odl, que j�a fora comentado em 1988 por F�uredi [11], quem, ademais, apre-sentou a vers~ao restrita de Pippenger no seu artigo. O resultado de Pippenger e Spencer[16] �e mais geral que o de Frankl e R�odl no sentido que suas hip�oteses s~ao menos restri-tivas (a quantidade de hiperarestas que cont�em dois v�ertices �e limitada linearmente pelograu m�aximo do hipergrafo). Este novo resultado mostra que as fam��lias de r-grafos comgrau m��nimo assint�otico ao grau m�aximo e tal que o n�umero de hiperarestas contendo doisvertices quaisquer �e desprezivel em rela�c~ao ao grau m�aximo, tem-se que o ��ndice crom�atico13

�e assint�otico ao grau m�aximo. Isto quer dizer que as hiperarestas podem ser particiona-das em coberturas ou emparelhamentos quase perfeitos. �E importante mencionar que otrabalho de Pippenger e Spencer tem dado origem a resultados de J. Kahn sobre outrasconjecturas de Erd}os. N�os mencionamos estes resultados no nosso projeto de disserta�c~aopor�em temos abandonado a pretens~ao de trat�a-los nesta vers~ao �nal.Na Se�c~ao 2:3 apresentamos o desenvolvimento hist�orico da t�ecnica originada na provadesta conjectura. Aqui comentamos como essa conjectura �e conseq�uencia do teorema deFrankl e R�odl na vers~ao de Pippenger.1.3.1 A vers~ao restrita de Pippenger do teorema de Frankl eR�odlDe�ni�c~ao 1.3.2 Seja F um hipergrafo. Uma cobertura (de v�ertices por arestas) K emF �e um conjunto de hiperarestas de F tal que cada v�ertice est�a, no m��nimo, numa hipe-raresta de K. Um empacotamento P em F �e um conjunto de hiperarestas de F tal quetodo v�ertice est�a, no m�aximo, numa hiperaresta de P. Uma cobertura ou um empacota-mento �e perfeito se cada v�ertice est�a em exatamente uma de suas hiperarestas. Nestecaso os conceitos coincidem. Denotamos por �(F) a cardinalidade de um empacotamentom�aximo e por Cob(F) a cardinalidade de uma cobertura m��nima de F .Dado um n�umero inteiro positivo n, usamos [n] para denotar o conjunto dos n primei-ros inteiros positivos, i.e., [n] = f1; : : : ; ng.Se n e r s~ao inteiros positivos tais que r � n, denotamos com [n](r) a cole�c~ao dossubconjuntos de [n] de tamanho r, i.e.,[n](r) = fF � [n] : jF j = rg:Dados A e B n�umeros reais e � > 0 usamos A �� B para denotar 1�� � A=B � 1+�.Vamos expressar agora a conjectura de Erd}os e Hanani como o problema de achar acobertura m��nima de um certo hipergrafo.Consideremos o �kr�-grafo F com conjunto de v�ertices V (F) = [n](r), e F 2 F se esomente se j [ F j = k e jF j = �kr�.Observamos agora que a cardinalidade de uma cobertura m��nima deste hipergrafo �eexatamente M(k; r; n). Para provar a segunda a�rmativa da conjectura de Erd}os e Hanani,bastaria ent~ao que consegu��ssemos provar que este n�umero �e assintoticamente igual aoquociente entre o n�umero de v�ertices do hipergrafo �nr� e o tamanho de suas arestas �kr�.Isto �e o que garante o seguinte teorema.Teorema 1.3.3 (Pippenger, cf. F�uredi, '88; [11]) Para todo inteiro r � 2 e n�umerosreais K � 1 e � > 0 existe um � > 0 para o qual vale o seguinte. Se, para algum d inteiropositivo, o r-grafo F = (V;F) sobre n v�ertices satisfaz14

(i) d(x) < Kd para todo x 2 V ,(ii) d(x) �� d vale para, no m��nimo, (1� �)n dos v�ertices,(iii) d(x; y) < �d para todo x 6= y,ent~ao Cob(F) < (n=r)(1 + �):Na Se�c~ao 3:2 mostraremos como ambas as a�rmativas da conjectura de Erd}os e Hanani,podem ser deduzidas deste resultado. Agora descreveremos como se aplica a estrat�egiageral do m�etodo probabil��stico na prova deste teorema.Come�camos descrevendo o que signi�ca a transforma�c~ao neste caso e na continua�c~aoesbo�camos a prova desta transforma�c~ao, o que �e equivalente a descrever uma itera�c~ao doalgoritmo que prova o Teorema 1.3.3. Terminaremos a discuss~ao deste teorema comentan-do como s~ao escolhidos os parametros e os limites do referido algoritmo.Lema 1.3.4 (A transforma�c~ao) Sejam �xos r, � > 0 e K. Ent~ao para todo �0 > 0,existe um � > 0 para o qual vale o seguinte. Se n > n0(r; �0; �; K) e D > D0(r; �0; �; K) e�e dado um r-grafo F = (V;F) sobre n v�ertices satisfazendo(i) d(x) < KD para todo x 2 V ,(ii) d(x) �� D vale para, no m��nimo, (1� �)n v�ertices,(iii) d(x; y) < �D para todo x 6= y,ent~ao existe R � F tal que pondo V � = V n SR, e F� = FjV �, temos(iv) jRj ��0 �n=r,(v) jSF�j ��0 ne��,(vi) d�(x) ��0 De��(r�1) vale para, no m��nimo, (1� �0)jSF�j dos v�ertices de F�.Passamos a esbo�car a prova deste lema.Escolhe-se um conjunto de hiperarestas pequeno e inversamente proporcional ao grau\predominante" D do hipergrafo F . Retira-se ent~ao do hipergrafo original todos osv�ertices pertencentes �as hiperarestas escolhidas, obtendo-se assim o hipergrafo transfor-mado F�.Se no hipergrafo original temos:Todos os v�ertices com grau limitado por um m�ultiplo de um certo D.15

Quase todos os v�ertices tem grau muito pr�oximo a D.A quantidade de arestas que cont�em dois v�ertices quaisquer �e desprez��vel com res-peito ao grau comum D.Ent~ao obtemosS~ao escolhidas aproximadamente �n=r hiperarestas. Estas arestas v~ao formar uma\cobertura parcial".O n�umero de v�ertices de F� sofre um pequeno decrescimento exponencial e�� comrespeito ao n�umero de v�ertices do hipergrafo original F .O grau dos v�ertices de F� decresce por um m�ultiplo deste fator linear no tamanhodas hiperarestas com respeito ao grau dos v�ertices de F .As condi�c~oes sobre o hipergrafo original F podem ser pensadas como condi�c~oes de \altaregularidade" ou \altamente quase regularidade".O problema �e que o hipergrafo transformadoF� n~ao precisa ser \t~ao regular quanto" F .Essa perda de regularidade �e indesej�avel pois no algoritmo que de�niremos na continua�c~aoprecisamos iterar essa transforma�c~ao. Para contornar esse problema, permite-se que tantoas condi�c~oes sobre F quanto aquelas sobre F� sejam satisfeitas com uma certa \tolerancia"a mais ou a menos. Essa tolerancia (� no Lema 1.3.4) servir�a como um parametro quenos permite \controlar" a perda de regularidade.Algoritmo 1.3.5 Para provar a a�rmativa do Teorema 1.3.3 itera-se a transforma�c~aodescrita, criando em cada itera�c~ao um conjunto de arestas cuja uni~ao, depois da itera�c~ao�nal, formar�a a cobertura que garante a tese do teorema.Por�em a necessidade de controlar a perda das \condi�c~oes de regularidade" requer tomaros seguintes cuidados com a tolerancia e o limite para o grau usados na transforma�c~ao.Para determinar quais s~ao os parametros �, d e n necess�arios para impor as condi�c~oes(i), (ii), (iii) do Teorema 1.3.3) ao hipergrafo original F procedemos como segue.Uma vez �xa a precis~ao com que pretendemos que M(k; r; n) se ajuste a �kr��nr��1,o controle que temos sobre a quantidade de hiperarestas escolhidas na transforma�c~aopermite limitar o tamanho das coberturas (parciais) pelos termos de uma s�erie geom�etricade raz~ao e�1. Isto nos permite determinar quantas itera�c~oes ser~ao necess�arias para cobriruma quantidade grande de v�ertices.Observe que em cada passo (itera�c~ao da transforma�c~ao) cada cobertura parcial con-tribui com um fator exponencial para o tamanho da cobertura total procurada e, comodevemos ajustar esse tamanho a (n=r)(1 + �), precisamos que a soma das parcelas sejacontrolada pelo �. Esse controle se executa usando as condi�c~oes (iv), (v), (vi) do Lema1.3.4. Note que para tanto, precisamos escolher um outro �0 pequeno o su�ciente que o16

hipergrafo transformado satisfa�ca nossos requerimentos, i.e., para controlar os aportes �asoma geom�etrica. Nessas condi�c~oes o Lema 1.3.4 nos devolve o � necess�ario para garantiras hip�oteses sobre o hipergrafo original e aplicar com sucesso o Lema 1.3.4.Esta estrat�egia de�ne um processo de indu�c~ao reversa �nita no qual, em cada passo,estaremos determinando as condi�c~oes precedentes que deve satisfazer o hipergrafo inicial.O processo termina quando atingimos o n�umero de passos (determinados previamente)necess�arios para cobrir e�cientemente as hiperarestas de F .Quando o processo termina, escolhemos � para as hip�oteses (i), (ii), (iii) do Teorema1.3.3 como o �ultimo � gerado nas sucessivas aplica�c~oes do Lema 1.3.4. O n�umero dev�ertices n e o limitante para o grau d ser~ao escohidos, respectivamente, como os m�aximosentre todos os n0 e D0 gerados nas sucessivas aplica�c~oes do Lema 1.3.4. Todos essoscuidados ser~ao descritos em mais detalhe na Se�c~ao 3.1 onde se exp~oe a prova do Teorema1.3.3.Antes de entrar em nossa mat�eria de estudo vamos �xar alguma nota�c~ao.Ao longo desta apresenta�c~ao usaremos P para denotar probabilidades e E para o valoresperado de uma vari�avel aleat�oria. Diz-se que uma vari�avel aleat�oria X tem distribui�c~aobinomial B(n; p) com parametros n e p se X conta o n�umero de sucessos numa seq�uenciade n experimentos independentes, onde cada sucesso tem a mesma probabilidade p deocorrencia.Vamos usar o s��mbolo � em tres contextos diferentes. Escrevemos A � B querendosigni�car que o quociente A=B tende a 1 quando n (tipicamente o n�umero de v�erticesde um hipergrafo) tende a in�nito. Com A �� B denotaremos 1 � � � A=B � 1 + �.Finalmente escrevemos \A � B quase sempre" para denotar que, para todo � > 0, aprobabilidade P(A �� B) tende a 1 quando n tende a in�nito; mais precisamente: Se Zn �euma vari�avel aleat�oria indexada por n e z(n) �e uma fun�c~ao de n escrevemos\Zn � z(n) quase sempre"se, para todo � > 0, temos limn!+1P(Zn �� z(n)) = 1:No decorrer do trabalho, c1; c2; : : : ; ck, �, �, , �i, �i, �, � denotam constantes apro-priadas ao contexto. Se X � V denotamos seu complemento por �X = V nX.

17

Cap��tulo 2Conjuntos Independentes2.1 Grafos sem triangulosConsideremos o problema de determinar o n�umero de independencia de um grafo G =(VG;EG), onde VG denota o conjunto de v�ertices do grafo e EG �e o conjunto de aretas.Em um grafo qualquer, podemos proceder gulosamente, pondo em nosso conjunto indepen-dente, um v�ertice x de grau m��nimo e iterando este processo no grafoG� = Gn(fxg[�(x)).Deste modo obtemos um conjunto independente que garante�(G) � nt+ 1 = �(nt );onde t �e o grau m�edio do grafo.Nessa se�c~ao vamos apresentar um resultado que melhora esse limite, para o caso degrafos sem triangulos, adicionando a ele um fator logar��tmico em t. No que resta da se�c~aoassumiremos que G �e um grafo livre de triangulos. Consideraremos que o conjunto dev�ertices de grafo �e [n] = f1; : : : ; ng e que se i 2 [n] �e um v�ertice, seu grau, denotado di,�e o n�umero de arestas incidentes ao v�ertice i. Ali�as, o grau medio do grafo G, denotadot = t(G), �e de�nido por t = Pni=1 di=n = 2jEGj=n.2.1.1 A transforma�c~aoNeste primeiro resultado a transforma�c~ao mencionada na introdu�c~ao vai signi�car o se-guinte.Achar um conjunto de v�ertices C que induz um subgrafo G[C] com n�umero deindependencia alto (pr�oximo �a cardinalidade de C).De�nindo V � = VG n (C [D), onde D �e o conjunto de v�ertices que s~ao adjacentesa algum v�ertice de C, temos que no grafo G� = (VG�; EG�), induzido por V �, oquociente entre o n�umero de v�ertices e o grau m�edio n~ao decresce demasiado emrela�c~ao ao grafo original. 18

Para provar estas a�rmativas vamos escolher os v�ertices de C ao acaso, pondo umv�ertice x de G em C com probabilidade p e deixando x fora de C com probabilidade1 � p. Em seguida, demonstra-se que podemos escolher p de modo que as condi�c~oesque procuramos s~ao satisfeitas com probabilidade n~ao nula. A parte t�ecnica da provadeste lema requer estimar jEG[C]j, jVG�j, jEG�j, usando a desigualdade de Chebyshev ea seguinte desigualdade exponencial an�aloga �a desigualdade de Schwarz.Lema 2.1.1 Seja G = (VG;EG) um grafo sobre n v�ertices e com grau m�aximo �. Ent~ao1jEGj Xij2EG e�x(di+dj) � 1n nXi=1 e�xdi!2para todo 0 � x � ln(1:25)=4�.Demonstra�c~ao. Embora comprida, a demostra�c~ao deste lema �e simples. A a�rmativaseguinte esbo�ca toda a estrategia da prova.A�rmativa 2.1.2 SejaF (x) = 1jEGj Xij2EG e�x(di+dj) � 1n2 nXi;j=1 e�x(di+dj):Ent~ao(i) F (0) = 0,(ii) F 0(0) � 0,(iii) F 0(x) � 0 para todo x 2 [0; ln(1:25)=4�].Estas tres condi�c~oes garantem queF (x) � 0; para 0 � x � 1=10�:�E imediato que (i) decorre da de�ni�c~ao de F (x); para veri�car (ii) e (iii) vamos fazeralguns c�alculos.A�rmativa 2.1.3 SejaHr = 1jEGj Xij2EG(di + dj � 2t)r � 1n2 nXi;j=1(di + dj � 2t)r:Ent~ao(iv) H0 = 0, 19

(v) H1 = 2�2=t, onde �2 �e a variancia de di,(vi) Hl � (2�)l�2 (4 + 4�=t) �2 para todo l � 2.Com efeito,(iv) H0 = 1jEGj Xij2EG 1� 1n2 nXi;j=1 1 = 1jEGj jEGj � 1n2n2 = 1� 1 = 0:(v) Vamos tratar em separado os termos de H1.Xij2EG(di + dj � 2t) = Xij2EG(di + dj)� 2tjEGj= nXi=1 d2i � t nXi=1 di = nXi=1 di(di � t):Para o segundo termo temosnXi;j=1(di + dj � 2t) = nXi;j=1(di + dj)� 2tn2= 2n nXi=1 di!� 2tn2 = 2n(2jEGj)� 2tn2 = 0:Portanto, H1 = 2nt nXi=1 di(di � t) = 2t ( 1n nXi=1 d2i )� t2! :Observemos que a �ultima express~ao entre parenteses �2 = ( 1n Pni=1 d2i ) � t2 �e a varianciado grau di de um v�ertice i.(vi) Desconsiderando o segundo termo de Hl temosHl � 2nt Xij2EG(di + dj � 2t)(2�)l�1= (2�)l�1 2nt nXi=1 di(di � t)= (2�)l�12�2t = (2�)l�24�t �2e isto basta para garantir (vi).20

A�rmativa 2.1.4 SejaGr = 1jEGj Xij2EG(di + dj)r � 1n2 nXi;j=1(di + dj)r:Ent~ao(vii) Gr = Prl=0 �rl�Hl(2t)r�l para r � 0.(viii) G0 = 0,(ix) G1 � 0,(x) Gr < (4�)r2�2=�t para todo r � 2.Com efeito,(vii) Gr = 1jEGj Xij2EG(di + dj � 2t+ 2t)r � 1n2 nXi;j=1(di + dj � 2t+ 2t)re pelo teorema do binomio= 1jEGj Xij2EG rXl=0 rl!(di + dj � 2t)l(2t)r�l � 1n2 nXi;j=1 rXl=0 rl!(di + dj � 2t)l(2t)r�l= rXl=0 rl!8<: 1jEGj Xij2EG(di + dj � 2t)l � 1n2 nXi;j=1(di + dj � 2t)l9=; (2t)r�l:(viii) Decorre imediatamente de (iv).(ix) De (vii), (iv) e (v) temosG1 = 1Xl=0 1l!Hl(2t)1�l = 10!H0(2t) + 11!H1 = H1 = 2�2=t:e portanto G1 > 0 pois �2 � 0 ao ser uma variancia, como j�a dizemos, no �nal da prova de(v). Outro jeito de ver isso �e usando a desigualdade de Schwarz. Consideremos os vetoresn-dimensionais x = (d1; : : : ; dn) e y = (1; : : : ; 1); pela desigualdade de Schwarz temos nXi=1 di!2 � n nXi=1 d2i ;ou seja nt2 � nXi=1 d2i :21

Observamos que G1 = 0 quando �2 = 0, isto �e, quando o grafo �e regular (pelo resultadoem IR : x = ty).(x) De (vii) e (vi) temosGr = rXl=0 rl!Hl(2t)r�l � rXl=0 rl!(2�)l�2 (4 + 4�=t)�2(2t)r�l= (4 + 4�=t) (2�)�2�2 rXl=0 rl!(2�)l(2t)r�l! = (4 + 4�=t) (2�)�2(2� + 2t)r�2e portanto Gr � �t +�� � 1�t(2� + 2t)r�2:Para provar (ii) e (iii) expressamos F (x) segundo a f�ormula de TaylorF (x) = 1Xr=0F (r)(0)xrr! :Segue-se por indu�c~ao queF (r)(x) = drdx(F (x)) = (�1)r 8<: 1jEGj Xij2EG(di + dj)re�x(di+dj) � 1n2 nXi;j=1(di + dj)re�x(di+dj)9=;e portanto F (r)(0) = (�1)rGr; para todo r � 0:Temos assim que (ix) implica F 0(0) � 0, garantindo (ii).Al�em disso F 0(x) = 1Xr=0F (r+1)(0)xrr! = F 0(0) + 1Xr=1F (r+1)(0)xrr! :De (x) temos jF (r+1)(0)jxr = Gr+1xr � (4�)r+12�2�t xr1Xr=1 jF (r+1)(0)jxrr! = 1Xr=1 jGr+1jxrr! � 1Xr=1(4�)r+12�2�t xrr!= 2�2t 4 1Xr=1 (4�x)rr! = 2�2t 4f 1Xr=0 (4�x)rr! � 1g = 2�2t 4(e4�x � 1)e portanto para satisfazer (iii) basta que4(e4�x � 1) < 1o qual �e v�alido para todo x 2 [0; ln(1:25)=4�]; observe que a s�erie converge nesse intervalo.22

2Lema 2.1.5 (A transforma�c~ao) Seja G = (VG;EG) um grafo sobre n v�ertices e consi-deremos um conjunto C � VG. De�nimosD = fx 2 VG : 9y 2 C tal que xy 2 EGg = �(C) = [x2C �(x);I = C \ �D = C nD = C n �(C);V � = �C \ �D = V n (C [D) = V n (C [ �(C)):Ent~ao o subgrafo G� = (VG�; EG�) de G, induzido por V �, satisfaz�(G) � �(G[C]) + �(G�) � jIj+ �(G�);ou seja, I �e um conjunto independente de G que n~ao cont�em v�ertices de G�.Com efeito, pela sua de�ni�c~ao, I n~ao induz arestas em G e ali�as V � \ I = ;. Notetamb�em que n~ao pode haver arestas ligando um v�ertice de I a um v�ertice de V �.2

23

Lema 2.1.6 (Ajtai, Koml�os e Szemer�edi, '81; [2]) Seja G = (VG;EG) um grafo so-bre n v�ertices, sem triangulos, com grau m�edio t e grau m�aximo �. Ent~ao existe umconjunto C � VG, satisfazendo(i) jCj > n=(100t),(ii) jEG[C]j < jCj=50e tal que o subgrafo G� = (VG�; EG�) de G, induzido por V � segundo o Lema 2.1.5, sobren0 v�ertices e com grau m�edio t0, satisfaz(iii) jVG�j > n=2,(iv) n0=t0 = jVG�j2=(2jEG�j) > #jVGj2=(2jEGj) = #n=t:onde # = 1� 1=t� c3qt=n.Demonstra�c~ao. Assumimos primeiro que 10t = � e escolhemos um conjunto C � V decardinalidade k = n=(100t). Dado C, consideramos G� = (VG�; EG�), o grafo induzidopela transforma�c~ao (2.1.5).Estima�c~ao de EG[C]. De�nimosXij(C) = ( 1 se i 2 C e j 2 C;0 se i 62 C ou j 62 C:Para ij 2 EG �xo e arbitr�ario temos,E(Xij(C)) = XP(Xij(C) = 1); onde a soma �e indizapa por C � VG : jCj = k= XP(i 2 C e j 2 C); onde a soma �e indizada por C � VG : jCj = k= n� 2k � 2!, nk!:Portanto E(jEG[C]j) = Xij2EGE(Xij(C)) = jEGj n� 2k � 2!, nk!E(jEG[C]j) = k(k � 1)t2(n� 1) � k2t2n : (2.1)Var(jEG[C]j) = Xij2EG;rs2EGE(Xij(C)Xrs(C))� E(Xij(C))E(Xrs(C))= Xij2EG;rs2EG( n� g(ij; rs)k � g(ij; rs)!, nk!� k2(k � 1)2n2(n� 1)2)24

onde g(ij; rs) �e o n�umero de v�ertices determinado pelas arestas ij e rs.= Xij2EGVar(Xij(C)) +X( n� 3k � 3!, nk!� k2(k � 1)2n2(n� 1)2)onde a segunda soma �e indizada por ij; rs 2 EG : g(ij; rs) = 3. Assim, o primeirosomando corresponde aos pares de arestas determinados por dois v�ertices e o segundosomando corresponde aos pares de arestas que s~ao de�nidas por tres v�ertices; observe quese g(ij; rs) = 4 ent~ao Cov(Xij(C); Xrs(C)) = 0.J�a que a variancia pode-se limitar pela esperan�ca e que a quantidade de pares dearestas (ij; rs) para as quais g(ij; rs) = 3 �e limitada superiormente por Pni=1 t2i < n�2temos Var(jEG[C]j) < k2 tn + n�2 k3n3 = k2 tn + k3 t2n2portanto Var(jEG[C]j) < 2k3 t2n2 :Assim qVar(jEG[C]j)=E(jEG[C]j) < 400qt=n: (2.2)Estima�c~ao de jVG�j. De�nimosX�i (C) = ( 1 se (�i [ fig) \ C = ;;0 caso contr�ario:Para i 2 VG �xo e arbitr�ario temos,E(X�i (C)) = XC�VG:jCj=kP(X�i (C) = 1)= XP((�i [ fig) \ C = ;) onde a soma �e indizada por C � VG : jCj = k= n� di � 1k !, nk!portanto E(jVG�j) = nXi=1 E(X�i (C)) = nXi=1 n� di � 1k !, nk!pela convexidade de f(x) = �xk� temosE(jVG�j) � n Pni=1 n�di�1nk !, nk! = n n� t� 1k !, nk!25

= n(n� t� 1)k(n)k > n(n� t� 1)knk 1� kn� t!k :Portanto E(jVG�j) > 0:9n:Agora limitamos superiormente a variancia.Var(jVG�j) = nXi;j=1nE(X�i (C)X�j (C))� E(X�i (C))E(X�j (C))o= nXi;j=18<: n�Nijk !, nk!� n�Nik ! n�Njk !, nk!29=;onde Ni = di + 1, Nj = dj + 1 e Nij = j�i [ fig [ �j [ fjgj. Para estimar a variancia,sustra��mos e adicionamos aos termos desta soma a quantidade n�Ni �Njk !, nk!e j�a que (n)k(n�N1�N2)k � (n�N1)k(n�N2)k podemos descartar as diferen�cas negativascriadas em cada termo, e temosVar(jVG�j) � nXi;j=1( n�Nijk !� n�Ni �Njk !), nk!� nXi;j=1 Ni+NjXh=Nij+1 n� hk � 1!, nk!= kn nXi;j=1 Ni+NjXh=Nij+1 n� hn� 1!k � kn nXi;j=1(Ni +Nj �Nij)= kn nXi=18<: nXj=1:j=i(Ni +Nj �Nij) + Xj2VG:ij2EG(Ni +Nj �Nij) + Xj2VG:ij =2EG(Ni +Nj �Nij)9=;= kn nXi=18<:(di + 1) + (2di) + nXj=1:ij =2EG j�i [ �jj9=; = kn nXi=1 f(di + 1) + (2di) + di(di � 1)g= kn nXi=1(di + 1)2 � kn nXi=1(di + 1)(� + 1) � knn(t+ 1)(� + 1)= n(t + 1)10 �10t+ 110t � < n(t + 1)5 < ntportanto Var(jVG�j) < nt26

e assim qVar(jVG�j)=E(jVG�j) < 2qt=n: (2.3)Estima�c~ao de jEG�j. De�nimos, para cada aresta ij 2 EG,X�ij(C) = ( 1 se (�i [ fig [ �j [ fjg) \ C = ;;0 caso contr�ario:Para ij 2 EG �xa e arbitr�aria temos,E(X�ij(C)) = XC�VG:jCj=kP(X�ij(C) = 1)= XC�VG:jCj=kP((�i [ fig [ �j [ fjg) \ C = ;) = n�Nijk !, nk!portanto E(jEG�j) = Xij2EGE(X�ij(C)) = Xij2EG n�Nijk !, nk!pela convexidade de f(x) = �xk� temos� nt2 Pij2EG(n�Nij)=jEGjk !, nk!j�a que o grafo n~ao tem triangulos= nt2 n�Pni=1 d2i =jEGjk !, nk!e como f(x) = �xk� �e uma fun�c~ao crescente, para todo x � k, temos� nt2 n� 2�� 1k !, nk! = nt2 (n� 2�� 1)k(n)k� nt2 (n� 2�)k(n)k 1� kn� 2�!k > nt2 1� kn� 2�!k > nt=10portanto E(jEG�j) > 0:1nt:Agora limitamos superiormente a variancia.Var(jEG�j) = Xij;rs2EG8<: n�Nij;rsk !, nk!� n�Nijk ! n�Nrsk !, nk!29=;27

onde Nij;rs = j�i [ fig [ �j [ fjg [ �r [ frg [ �s [ fsgj. Sustraindo e adicionando aostermos dessa soma a quantidade n�Nij �Nrsk !, nk!e depois de descartar as diferen�cas negativas criadas em cada termo, temosVar(jEG�j) � Xij;rs2EG( n�Nij;rsk !� n�Nij �Nrsk !), nk!� Xij;rs2EG Nij+NrsXh=Nij;rs+1 n� hk !, nk!� Xij;rs2EG Nij+NrsXh=Nij;rs+1 kn n� hn� 1!k� kn Xij;rs2EG (Nij +Nrs �Nij;rs) = kn Xij;rs2EG jNij \Nrsj= kn Xij;rs2EG Xx2jNij\Nrsj 1 = kn Xx2V Xij;rs2EG:x2jNij\Nrsj 1� kn Xx2V Xu;v2�x dudv � kn Xx2V �4 = knn�4portanto Var(jEG�j) < 100nt3e assim qVar(jEG�j)=E(jEG�j) < 100qt=n: (2.4)As desigualdades (2:2), (2:3), e (2:4), e a desigualdade de Chebyshev garantem que existeum conjunto C � V tal que para � su�cientemente pequeno valemjVG�j > E(jVG�j)(1� �); (2.5)jEG�j < E(jEG�j)(1 + �); (2.6)jEG[C]j < E(jEG[C]j)(1 + �): (2.7)28

Das contas anteriores, tomando � = O(qt=n), temos(EjVG�j)2=(2E(jEG�j)) = �Pni=1 �n�Nik �/�nk��22Pij2EG �n�Nijk �/�nk�� �Pni=1 (n)k(n)k e�(1+o(1)) dikn �(1+o(1)) kn�22Pij2EG (n)k(n�k+1)k e�(1+o(1))(di+dj) kn> n22jEGj � 1nPni=1 e�kdi=n�21jEGjPij2EG e�k(di+dj)=n e�1=100t> �1� 1t� ntsendo que a pen�ultima desigualdade �e devida ao Lema 2.1.1. Ent~ao (2:5) e (2:6) garantemque jVG�j2=(2jEG�j) > (1� �)2(1 + �) �1� 1t� nt > #nttamb�em jVG�j > (1� �)E(jVG�j) > #0:9n:A a�rmativa (ii) decorre de 2:1 e 2:7.No caso em que o grafo n~ao satisfaz max di � 10t, apagamos todos os v�ertices de grau� 10t e aplicamos a constru�c~ao descrita ao grafo sobre os n0 v�ertices restantes. Neste caso,a desigualdade de Markov mostra que P(di � 10t) � 0:1 e, portanto, temos n0 � 0:9n;segue-se que n0=t0 � 0:9n=t; o limite inferior para jVG�j muda parajVG�j > #(0:9)2n > n=2e os outros n~ao s~ao afetados.2

29

2.1.2 O algoritmoSempre temos que o n�umero de independencia de um grafo G sobre n v�ertices e grau m�ediot e maior o igual a n=t. Em nosso caso, para construir efetivamente um tal conjunto in-dependente, sorteamos um conjunto C como descrito no Lema 2.1.6, tantas vezes comoseja necess�ario at�e conseguirmos algum que satisfa�ca as a�rmativas deste lema. A a�rma-tiva (ii) garante que, no m�aximo, 2jCj=50 dos v�ertices s~ao cobertos por arestas do grafoinduzido por C; portanto, temos que C cont�em um conjunto independente de v�ertices detamanho, pelo menos, 0:01n=t.Vamos construir um conjunto independente \grande" emG iterando o processo descritono Lema 2.1.6 um n�umero �(log t) de vezes, escolhendo cada vez os grafos induzidos G[C]e G� no grafo transformado G da itera�c~ao anterior. Isso fornece em cada itera�c~ao umconjunto independente grande, a uni~ao dos quais vai garantir a a�rmativa do lema.Teorema 2.1.7 (Ajtai, Koml�os e Szemer�edi, '81; [2]) Se um grafo livre de triangulosG com n v�ertices tem grau m�edio t > c1, ent~ao�(G) > c4n(log t)=t:Demonstra�c~ao. J�a que G n~ao tem triangulos, segue que �(G) � t e, como sempre temosn > t, segue que se t � pn logn, teremosn > t > qn logn;implica pnt > 1pn > plognte portanto qn logn = n 1pnqlogn > n lognt > n log tte temos a tese.Para o caso t < pn logn, consideremos o seguinte algoritmo.230

Algoritmo 2.1.8 Entrada: Um grafo G = (VG;EG) sobre n v�ertices, sem triangulos ecom grau m�edio t.Sa��da: Um conjunto independente I de tamanho � c(n=t)(log t).1. Ponha G0 = G, t0 = t, #0 = 1, r = 1.2. Enquanto r < (log t)=2 e #r > 1� 1=(log t)Sorteie um conjunto C como descrito no Lema 2.1.6 e veri�que se esse conjuntosatisfaz as a�rmativas do lema; caso contr�ario, volte a sortear at�e conseguirum conjunto C adequado.PonhaGr = G�r�1,Ir o conjunto independente de VGr�1[C],nr = jVGrj,tr = t(Gr) e#r = 1� 1=tr � c3qtr=nr.3. Devolva I = Srs=0 Is.Lema 2.1.9 (Invariantes) Em cada passo \s" da execu�c~ao do algoritmo (2.1.8) valem(i) ns > n=2s,(ii) ns=ts > (1� 1=(log t))sn=t.Demonstra�c~ao. As a�rmativas provam-se por indu�c~ao matem�atica.(i) Caso base : (iii) do Lema 2.1.6 garante que n1 > n0=2.Passo indutivo : Seja s > 1 e suponhamos que (i) vale para s�1. Ent~ao, novamentepor (iii) do Lema 2.1.6, temos ns > ns�1=2 e, pela hip�otese indutiva, ns > n=2� 2s�1 =n=2s.(ii) Caso base : (iv) do Lema 2.1.6 e a de�ni�c~ao do la�co do Algoritmo 2.1.8 garantemque n1=t1 > (1� 1=(log t))n=tPasso indutivo : Seja s > 1 e suponhamos que (ii) vale para s� 1. Ent~ao por (iv)do Lema 2.1.6 temos ns=ts > #ns�1=ts�1, pela hip�otese indutiva temos ns=ts > #(1 �1=(log t))s�1n=t e a de�ni�c~ao do la�co do Algoritmo 2.1.8 garante a tese.231

Lema 2.1.10 (Certi�cado) O conjunto I devolvido pelo Algoritmo 2.1.8 �e um conjuntoindependente do grafo G e satisfaz jIj � c4n(log t)=t:Demonstra�c~ao. Pela de�ni�c~ao do Algoritmo 2.1.8, temos que considerar os seguintescasos.1. Suponhamos que a execu�c~ao do algoritmo termina e #r > 1 � 1=(log t). Portantor = (log t)=2; temos, jIj = rXi=0 jIsj > rXs=1 nsts :Ent~ao, usando o invariante (ii) do lema anterior, obtemosjIj > nt rXs=1(1� 1= log t)s= nt (log t)=2Xs=1 (1� 1= log t)s= nt (1� (1� 1= log t)(log t)=21� (1� 1= log t) )= nt (1� e�1=2)(1� 1 + 1= log t)= (1� e�1=2)nt (log t)2. Suponhamos agora que a execu�c~ao do algoritmo termina com #r < 1 � 1=(log t).Portanto r < (log t)=2. Temos ent~ao1� t�1=3 < # = 1� 1=t� cqtr=nr � 1� 1= log t�t�1=3r < �1= log tt�1=3r > 1= log t1=tr > 1=(log t)3portanto nr(tr + 1) > cnrtr> c nr(log t)3 > c n(log t)3 12r � c npt(log t)3 > cn log ttpara t su�cientemente grande.2Os resultados expostos acima resumem a estrat�egia b�asica do m�etodo probabil��sticoque seguiremos neste trabalho. Na pr�oxima se�c~ao vamos apresentar a vers~ao para o casode hipergrafos, enfatizando com um pouco mais de detalhe esta estrat�egia.32

2.2 Hipergrafos de cintura maior que 4Vamos detalhar um pouco mais a estrat�egia apresentada na se�c~ao anterior, desta vezna vers~ao para hipergrafos. Na primeira subse�c~ao descrevemos a transforma�c~ao usadaneste caso e na subse�c~ao seguinte as considera�c~oes necess�arias para a prova algor��tmica.Precisamos introduzir alguma nota�c~ao.De�ni�c~ao 2.2.1 Seja F = (V;F) um hipergrafo sobre n v�ertices. Dado x 2 V de�nimosFx = fF � V n fxg : F [ fxg 2 Fg. Dizemos que F �e regular se para 1 � i � k temosque di(x) = di(y) para todo x, y 2 V . Dizemos que a cintura g(F) de F �e pelo menos hse F n~ao tem circuitos de comprimento menor do que h.No que resta da se�c~ao assumimos que k �e um inteiro �xo arbitrario, F �e um (k + 1)-grafo sobre n v�ertices e que toda aresta F de F satisfaz 2 � jF j � k + 1. Enunciamosagora o resultado central desta se�c~ao.Teorema 2.2.2 (Ajtai, Koml�os, Pintz, Spencer e Szemer�edi, '82; [1]) Seja dado um(k+1)-grafo F sobre n v�ertices tal que para algum t0 = t0(k) e algum n0 = n0(k; t) valem(i) g(F) � 5,(ii) �(F) � tk, onde t � t0(k),(iii) n � n0(k; t).Ent~ao �(F) � cknt (log t)1=k:Veremos rapidamente que este teorema implica uma vers~ao menos restritiva comosegue.Corol�ario 2.2.3 (Alon, Lefmann e R�odl, '91; [3]) Seja dado um (k+1)-grafo H so-bre n v�ertices tal que(i) g(H) � 5,(ii) �(H) � tk, onde t � t0(k).Ent~ao �(H) � cknt (log t)1=k:33

Demonstra�c~ao. Seja H um (k + 1)-grafo sobre n v�ertices satisfazendo as hip�oteses docorol�ario e seja m um inteiro positivo tal quem > n0(k; t)n :Consideremos o hipergrafo Fm formado por m c�opias de H, disjuntas nos v�ertices. Ent~aoFm tem mn > n0(k; t)=n v�ertices e satisfaz as condi�c~oes (i), (ii) e (iii) do Teorema 2:2:2e portanto m�(H) = �(Fm) > cknmt (log t)1=k;assim, �(H) > cknt (log t)1=k:2 Recentemente este resultado foi melhorado no sentido de n~ao ser preciso desconsiderarcircuitos de comprimento 4. Eis a nova vers~ao.Teorema 2.2.4 (Duke, Lefmann e R}odl, '95; [5]) Sejam dados um inteiro k � 2 eum (k + 1)-grafo F sobre n v�ertices tais que(i) g(F) � 3,(ii) �(F) � tk, onde t � t0(k),(iii) n � n0(k; t).Ent~ao �(F) � cknt (log t)1=k:Demonstra�c~ao. Denotamos por �3 o n�umero de 3-circuitos de F e por �4 o n�umero de4-circuitos de F .Para limitar superiormente �3 consideremos um v�ertice qualquer x e vejamos quantostriangulos podem conte-lo. Duas arestas F1 e F2 incidentes a x podem ser escolhidas de,no m�aximo, �tk2 � formas. Para de�nir a terceira aresta do 3-circuito precisamos escolherum v�ertice y 2 F1 e outro z 2 F2. Portanto�3 � n tk2!k2 � c3nt2k:J�a que F n~ao tem 2-circuitos, escrevemos Fx;y = F1 e Fx;z = F2 para ressaltar que cadapar de v�ertices determina univocamente a aresta que os cont�em.Vamos agora limitar superiormente �4. Consideremos um v�ertice qualquer x e veja-mos quantos quadrados podem conte-lo. Pela observa�c~ao anterior, um tal quadrado �ca34

de�nido ao escolher tres outros v�ertices y, z e w. Estes v�ertices determinam as arestasFxy, Fxz, Fyw e Fzw do quadrado. Como antes, as arestas Fxy e Fxz podem ser escolhidasde, no m�aximo, �tk2 � formas. Nestas arestas, precisamos escolher y 2 F1 e z 2 F2. Temosainda, no m�aximo, tk escolhas para Fy;w e k escolhas para o w em Fy;w que vai determinarFx;w. Portanto �4 � n tk2!(k + 1)tk(k + 1)2 � c4nt3k:Seja Y � V tal queP(x 2 Y ) = p = t��1; para todo x 2 Vonde 0 < � < (k � 1)=(4k � 1). Ent~ao jY j � B(n; p) e portantojY j � pn; quase sempre. (2.8)Sejam agora �3(Y ) e �4(Y ) as v.a. que contam respectivamente o n�umero de 3-circuitose de 4-circuitos de F [Y ]. Ent~ao, para i = 3; 4, segue queE(�i(Y )) = �ipik� cint(i�1)kpik= cit�(k�1)+�ik��pn= o(pn)pela escolha de �.Denotando o n�umero esperado de arestas em Y por E(F [Y ]), temosE(F [Y ]) = pkjFj � 1kpktk�1ne pela desigualdade de Markov, P(X � ��) � 1� 1=�, com � = 2, obtemosP�jF [Y ]j � 2kpktk�1n� � 0:5 (2.9)J�a que dois eventos, cada um com probabilidade maior o igual que meio, devem ter in-terse�c~ao n~ao vazia, concluimos que existe um Y � V que satisfaz ambas a�rmativas (7) e(8).Agora, apagamos um v�ertice de cada 3-circuito e de cada 4-circuito em Y , e obtemosum subconjunto Y0 � Y , com Y0 � pn, tal que o subhipergrafo induzido F [Y0] de F temcintura g(F [Y0]) � 5.Observemos que o grau m�edio de F [Y0] satisfaz(k + 1)jF [Y0]jnp � 2(k + 1)(k + 1)pk+1tk+1npn = 2pktk;35

assim, os v�ertices de grau maior que 5pktk tem grau \grande" no seguinte sentido. Paracada v�ertice x 2 Y0, a desigualdade de Markov garanteP(dx � 5pktk = (5=2)2pktk) � 2=5e portanto a quantidade de v�ertices de Y0 que tem grau maior ou igual a 5pktk �e menorou igual a (2=5)jY0j � 0:5np e depois de apag�a-los, obtemos um conjunto Y1 � Y0, comjY1j � pn=2, que induz um subhipergrafo F [Y1] de F [Y0] que satisfaz�(F [Y1]) = tk � 5pktk = 5t�k:Ent~ao, pelo Corol�ario 2.2.3 obtemos�(F) � �(F [Y1]) � ckY1t1 (log t1)1=k � cknt (log t)1=k:2

36

2.2.1 A transforma�c~aoDescrevemos brevemente a transforma�c~ao que utilizaremos na prova do resultado centraldesta se�c~ao.Lema 2.2.5 (A transforma�c~ao; [1]) Seja dado um hipergrafo F = (V;F) e considere-mos um conjunto C � V . De�nimosD = fx 2 V : F � C para algum F 2 Fxg;I = C \ �D;V � = �C \ �D;F� = fF 0 = F \ V � : F 2 F ; F � C [ V �; F \ V � 6= ;g:Ent~ao o hipergrafo F� = (V �;F�) satisfaz(i) �(F) � �(F [C]) + �(F�) � jIj+ �(F�),(ii) (V �;F [V �]) � (V �;F�),(iii) (V �;F�) n~ao cont�em hiperarestas unit�arias e todas as (k + 1)-arestas de F� s~ao(k + 1)-arestas de F .Demonstra�c~ao. (i) Com efeito, claramente I �e um conjunto independente de F ; agorasuponhamos, para um absurdo, que existe um conjunto independente J de F� e uma arestaF 2 F tal que F � I [ J . Mas ent~ao F \ V � 2 F�, o qual contradiz o fato de ser Jindependente em F�.(ii) Decorre simplesmente do fato de I ser um conjunto independente.(iii) Pela de�ni�c~ao de F�, toda aresta contida em V � �e uma aresta de F�.(iv) Se fxg = F 0 = F \ V � �e uma aresta unit�aria de F� ent~ao x 2 V �, por�em tamb�emdeveria existir F 2 Fx contida totalmente em C ou seja x 2 D, o qual �e uma contradi�c~ao.A outra a�rmativa �e imediata.2Na constru�c~ao do algoritmo, os elementos do conjunto C da transforma�c~ao ser~ao es-colhidos ao acaso.De�ni�c~ao 2.2.6 Dizemos que um conjunto de v�ertices C � V tem distribui�c~ao V (p),com 0 < p < 1 se P(x 2 C) = pe esses eventos s~ao mutuamente independentes.37

Lema 2.2.7 Seja dado um (k + 1)-grafo regular F = (V;F) com n v�ertices, cinturag(F) � 5 e grau m�aximo � tk. Considere C � V com distribui�c~ao V (p) com p = 1=t esejam I e (V �;F�) como em (2.2.5). Ent~aojIj � nete jV �j � ne ;quase sempre.Da de�ni�c~ao do conjunto I em (2.2.5) segue que os eventos fx 2 Ig e fy 2 Ig s~aoindependentes se a distancia entre x e y �e maior do que 2 no hipergrafo F . Ademais, acondi�c~ao da cintura ser maior do que 4 implica que os v�ertices �a distancia menor ou igual a2 s~ao \poucos"; da�� temos que jIj tem distribui�c~ao \quase" binomial com n experimentose probabilidade de sucesso p � 1=et. A tese para jIj do Lema 1.2.7 segue da desigualdadede Chebyshev. O argumento para jV �j �e an�alogo.A primeira a�rmativa do Lema 1.2.7 e (i) do Lema 2.2.5 implicam o seguinte.Corol�ario 2.2.8 Seja dado um (k + 1)-grafo regular F = (V;F) com n v�ertices, cinturag(F) � 5 e grau m�aximo � tk. Ent~ao �(F) > net :Lema 2.2.9 Seja dado um (k + 1)-grafo regular F = (V;F) com n v�ertices, cinturag(F) � 5 e grau m�aximo � tk. Considere C � V com distribui�c~ao V (p) com p = 1=t esejam I e (V �;F�) como em (2.2.5). Ent~aod�i (x) � ki!� te�i ; 1 � i � k;quase sempre.Do esbo�co da prova do Lema 1.2.7 sabemos que jV �j segue basicamente uma distri-bui�c~ao binomial. Algo similar acontece com o i-grau d�i (x) de x em F�. Cada (k+1)-arestaincidente a x em F pode se transformar numa (i + 1)-aresta das �ki� poss��veis em F�, ea probabilidade da transforma�c~ao em cada caso �e aproximadamente pk�ie�i. Como nom�aximo s~ao tk experimentos, pois o grau m�aximo de F �e � tk, temos que d�i (x) temdistribui�c~ao dominada porB tk; ki!pk�ie�i! ; 1 � i � k;e a tese do Lema 1.2.9 segue da desigualdade de Chebyshev.38

Na constru�c~ao a seguir, vamos requerer que os hipergrafos transformados sejam regu-lares (ou melhor, \o mais regulares poss��veis" ou \quase-regulares"); o seguinte lema vaiser utilizado para manter essa propriedade entre um hipergrafo e seu transformado emcada passo da prova algor��tmica.Lema 2.2.10 (Quase-regularidade; [1]) Seja dado um hipergrafo F = (V;F) de jV j =n v�ertices com cintura g(F) � 5 tal que para todo x 2 Vdi(x) � ai; 1 � i � k:Ent~ao existe F+ � F tal que(i) g(F+) � 5,(ii) d+i (x) � ai para todo 1 � i � k e todo x, onde d+i (x) denota o i-grau de x em F+,(iii) o conjunto B = fx : d+i (x) 6= ai, algum ig tem cardinalidade jBj � k2b3, ondeb = 1 +Pki=1 iai.Demonstra�c~ao. Seja F+ o hipergrafo maximal tal que F+ � F e satisfaz (i) e (ii).De�nimos Bi = fx : d+i (x) � aigde modo que B = [ki=1Bi:Vamos ver que jBij � ib3:Com efeito, suponhamos que, para algum i, se satisfaz jBij � ib3.J�a que j�3(x)j � b3 podemos de�nir uma nova aresta fx1; :::; xi+1g, escolhendo induc-tivamente um elemento arbitr�ario xj de �3(xs) para s < j.Ent~ao F+[fx1; :::; xi+1g �e hipergrafo sem circuitos de comprimento 3 e 4 e satisfazendoa condi�c~ao (ii) o qual contradiz a escolha de F+.Portanto jBj � kXi=1 jBij = b3k(k + 1)=2e temos (iii).2Lema 2.2.11 Seja dado um hipergrafo regular F = (V;F) com n v�ertices, cintura g(F) �5, e com di(x) = �i ki!ti; 1 � i � k:39

Considere C � V com distribui�c~ao V (p) com p = w=t, onde w satisfaz w = O(log t), esejam I e (V �;F�) como em (2.2.5). Ent~ao existem n�umeros reais ��i (1 � i � k) e � > 0tais que (V �;F�) tem n� = n� v�ertices ed�i (x) � ��i ki!(t�)i; 1 � i � k;quase sempre.O tal � vai ser escolhido tal que � � e�1. Considera�c~oes an�alogas ao Lema 1.2.7permitem obter que, tamb�em neste caso, quase sempre,jIj � np� = nt �w;jV �j � n�;e como esbo�cado para o Corol�ario 1.2.8 pode-se provar que �(F) > (n=t)�w.Al�em disso, dado x 2 V , o n�umero d�ij(x) de (j+1)-arestas incidentes a x em F que s~aotransformadas em (i + 1)-arestas incidentes a x em F� segue uma distribui�c~ao binomialde dj(x) experimentos e probabilidade de sucesso �ji�pj�i�i, i.e. d�ij(x) tem distribui�c~aoB dj(x); ji!pj�i�i! :Da�� a tese do Lema 1.2.10 segue pela desigualdade de Chebyshev com t� = t� e�� = kXj=1�j k � ij � i!wj�i:

40

2.2.2 O algoritmoNesta subse�c~ao vamos apresentar resultados que garantem o funcionamento do algoritmoda prova do Teorema 1.2.2. Esta subse�c~ao �e uma revis~ao da discuss~ao do par�agrafo 2 de[1].Apresentamos a seguir a constru�c~ao algor��tmica do conjunto independente que garantea tese do Teorema 1.2.2.Algoritmo 2.2.12 Entrada: Um (k+1)-grafo regular F = (V;F) com n v�ertices, cinturag(F) � 5 e dk(x) � tk.Sa��da: Um conjunto independente I de tamanho � ck(n=t)(log t)1=k.1. Ponha (V0;F0) = (V;F).2. Para s = 0 at�e s = d0:01 log te fa�caw = ws = (s+ 1)1=k � s1=k.Seja C � Vs com distribui�c~ao V (p), onde p = ps = ws=ts.C de�ne I = Is e (Vs+1;Fs+1) = (V �s ;F�s ) como em (2.2.5).Substitua Fs+1 pela sua extens~ao F+s+1 segundo (2.2.10).3. Devolva I = Sd0:01 log tes=0 Is.A seguir argumentamos que o algoritmo acima calcula efetivamente o que precisamos.Lema 2.2.13 (Os invariantes) Em cada itera�c~ao s do Algoritmo 2.2.12 temos, quasesempre,(i) �s � e�1,(ii) jVsj = ns � ne�s, ts � te�s, vs � s1=2,(iii) di = �i�ki�tis, onde �i = vk�is para todo x 2 Vs,(iv) jIsj � (n=et)ws.Demonstra�c~ao. A prova deste lema �e indutiva.Caso base: Ao in��cio da execu�c~ao do algoritmo, j�a que o hipergrafo de entrada �e(k + 1)-uniforme e regular, os Lemas 1.2.7 e 1.2.9 e o Corol�ario 1.2.8 garantem que aexecu�c~ao da transforma�c~ao de (2.2.5) mant�em os invariantes.Passo indutivo: Nas seguintes itera�c~oes, o algoritmo usa (2.2.10) para preservar aregularidade, mas o hipergrafo transformado n~ao �e mais (k + 1)-uniforme; neste caso, oLema 1.2.10 garante que a transforma�c~ao (2.2.5) conserva os invariantes do Lema 1.1.12,completando a indu�c~ao.2 41

Corol�ario 2.2.14 (Certi�cado) O conjunto I devolvido pelo Algoritmo 2.2.12 �e umconjunto independente de (V;F) e satisfazjIj � ck(n=t)(log t)1=k:Demonstra�c~ao. A tese �e conseq�uencia de (iv) do Lema 1.2.12 e do fato de que jIj s�odepende da soma telesc�opicad0:01 log teXs=0 ws = d0:01 log teXs=0 (s+ 1)1=k � s1=k = d0:01 log te = c0k log t:Com efeito, jIj = d0:01 log teXs=0 jIsj � d0:01 log teXs=0 (n=et)ws = c0k(n=et) log t:2

42

2.3 Conseq�uencias2.3.1 Uma seq�uencia de Sidon densaDe�ni�c~ao 2.3.1 Uma seq�uencia de Sidon �e uma seq�uencia de n�umeros inteiros posi-tivos S = fa1 < a2 < ::: < ak < :::g (�nita ou in�nita) tal que todo inteiro m tem, nom�aximo, uma representa�c~ao da formam = ai + aj; com ai; aj 2 S; i < j:Denotamos com s(n) o n�umero m�aximo de elementos de f1; : : : ; ng que formam umaseq�uencia de Sidon. Se S �e uma seq�uencia in�nita de Sidon, denotamos com fS(n) on�umero de elementos de S n~ao maiores que n.Vimos no Cap��tulo 1 que o crescimento de s(n) �e aproximadamente o crescimento daraiz quadrada de n, conforme n cresce inde�nidamente. O resultado para grafos semtriangulos da Se�c~ao 2.1 foi desenvolvido como ferramenta para a investiga�c~ao de fS(n).Agora vamos apresentar essa aplica�c~ao.Remetemos o leitor ao Cap��tulo 1 para o hist�oricodos avan�cos na pesquisa deste problema.Precisamos de um lema t�ecnico antes de continuar. Dados dois inteiros x, y com x � ydizemos que a tripla (x; y; x+ y) �e um triangulo geral.Dizemos que um conjunto A gera um triangulo geral (x; y; x + y) se x 2 A � A =fa� a0 : a; a0 2 Ag, y 2 A� A e x+ y 2 A� A.Lema 2.3.2 Dados N triangulos gerais e um intervalo (a; a + n) existe um conjuntodiferen�ca D � (a; a + n) tal que(i) jDj � pn=3,(ii) no m�aximo 10N=pn dos triangulos gerais dados podem encontrar-se em D comodiferen�cas consecutivas (d; d+ x; d+ x+ y) para algum d.Demonstra�c~ao. Como a cada triangulo geral (x; y; x+ y) corresponde o triangulo geral(x� a; y � a; x + y � 2a) podemos assumir que a = 0.A estrat�egia para obter as a�rmativas �e construir m = pn=10 conjuntos diferen�caD1; : : : ; Dm de tamanho pn=3, todos eles contidos em (0; n) e tais que nenhum par delescompartilha um triangulo geral. Algum desses conjuntos Dj deve satisfazer (ii).Seja um n�umero primo p = 4k + 1 tal que0:8pn < p < 0:9pn:De�nimosDj = fpx + (jx2) : 1 � x < p tais que (jx2) < p=2g; j = 1; : : : ; m43

onde (t) �e o m��nimo res��duo positivo de tmod p.Dj �e um conjunto diferen�ca. Com efeito, sejamui = pxi + (jx2i ) 2 Dj; i = 1; 2; 3; 4:Assumindo que u1 6= u2 e u3 6= u4 supomos, por absurdo, queu1 � u2 = u3 � u4da�� temos x1 � x2 = x3 � x4;x21 � x22 = x23 � x24:Dessas equa�c~oes obtemos x1 + x2 = x3 + x4;e somando a esta equa�c~ao a primeira equa�c~ao temosx1 = x3 e x2 = x4:E, portanto, u1 = u3 e u2 = u4.Cada triangulo geral est�a contido num s�o Dj. Seja um triangulo geral T =(ap+ c; bp + d; (a+ b)p + (c+ d)), com 0 � c < p, 0 � d < p e suponhamos queT � Dj; para algum j 2 [m]Vamos mostrar que tal j �e �unico. Com efeito, sepxi + (jx2i ); j = 1; 2; 3;s~ao os elementos deD correspondentes a T , digamos (px1+(jx21); px2+(jx22); px3+(jx23)) =(d; d+ ap + c; d+ (a+ b)p + c+ d), para algum d. Nessas condi�c~oespx1 + (jx21) = d;px2 + (jx22) = d+ ap+ c;px3 + (jx23) = (a+ b)p + c+ d;px1 + (jx21)� px2 � (jx22) = ap + c;px3 + (jx23)� px2 � (jx22) = bp + de, portanto, x1 � x2 = amod p; (jx22)� (jx21) = cmod p;44

x2 � x3 = b mod p; (jx22)� (jx23) = d mod p:fx1 � x2g�1 = a�1 mod p;fx2 � x3g�1 = b�1 mod p;(jfx1 � x2gfx1 + x2g) = c mod p;(jfx2 � x3gfx2 + x3g) = d mod p;portanto, (jfx1 + x2g) = a�1c mod p;(jfx2 + x3g) = b�1d mod p:(jfx1 � x3g) = fa�1c� b�1dgmod px1 � x3 = fa� bgmod p;j = fa� bg�1fa�1c� b�1dgmod p:2Se passaram vinte anos at�e se conseguir construir uma seq�uencia de Sidon de cresci-mento mais r�apido: em 1981, Ajtai, Koml�os e Szemer�edi [2] apresentaram uma constru�c~aoprobabil��stica de uma seq�uencia de Sidon mais densa que as anteriores; seu resultado �ebaseado no Teorema 2.1.7. Eis o enunciado.

45

Teorema 2.3.3 (Ajtai, Koml�os e Szemer�edi, '81; [2]) Existe uma seq�uencia de Si-don S tal que fS(n) > 110500 (n logn)1=3;para todo n 2 N.Demonstra�c~ao. Por indu�c~ao matem�atica.Caso Base. Deve-se garantir a existencia de um conjunto Bi0 , para io su�cientementegrande, tal que(i) Bi0 � [2:10i0; 3:10i0],(ii) jBi0 j = b(i1=30 10i0=3)=10500c,(iii) Bi0 �e um conjunto diferen�ca,(iv) O conjunto Ai0 = Bi0 gera menos do que 101;26i0 triangulos gerais.Hip�otese indutiva. Seja i > i0 e suponhamos que existam Bi0 ; Bi0+1 ; : : : ; Bi�1 taisque para todo h tal que i0 � h < i se satisfaz(i) Bh � [2:10h; 3:10h],(ii) jBhj = b(h1=310h=3)=10500c,(iii) Bh �e um conjunto diferen�ca,(iv) O conjunto Ah = [j�hBj gera menos do que 101:26h triangulos gerais,(v) Para nenhum par b; b0 2 Bh acontece b� b0 2 Ah�1 � Ah�1.A id�eia �e mostrar que a seq�uencia de elementos dos Bi formam uma seq�uencia de Sidoncom a densidade desejada.Passo Indutivo. Pelo Lema 2.3.2 sabemos que existe um conjunto diferen�ca D �[2:10i; 3:10i], tal que(i) D = 10i=2=3,(ii) No m�aximo 10:101;26(i�1):10�0;5i = 100;76i+0;5 < 101;26i dos triangulos gerados porAi�1, podem ser encontrados em D como diferen�cas consecutivas (d; d+x; d+x+y).Escolhemos B � D pondoP(x 2 B) = p = 5:10�0;15i; 8x 2 D;46

sendo esses eventos independentes. Temos, portanto, que jBj segue uma distribui�c~aobinomial B((1=3)10i=2; 5:10�0;15i) e assimjBj � (5=3)100;35i; quase sempre:Pondo � = 2=5 na desigualdade de Chebyshev, P((1� �)� < X < (1+ �)�) > 1� (1=n�2p),obtemos P(100;35i < jBj < (7=3)100;35i) > 0; 9: (2.10)Seja agora GTRi o n�umero de triangulos gerais gerados por Ai�1 [B e GTRi�1 o n�umerode triangulos gerais gerados por Ai�1. Ent~ao, para i > 600,E(GTRi �GTRi�1) < (4:100;35i)3 + (4:100;35i)4p < (1=20)101;26i;j�a que pelo menos dois dos 6 inteiros que determinam cada triangulo geral devem estarem Bi. Portanto, pela desigualdade de Markov, P(X � ��) � 1� (1=�), tomando � = 10obtemos P(GTRi �GTRi�1 < (1=2)101;26i) � 0; 9 (2.11)e, portanto, P(GTRi < 101;26(i�1) + (1=2)101;26i < 101;26i) � 0; 9: (2.12)Seja agora Gi = (B;EGi) onde, dados b; b0 2 B temos que bb0 2 EGi se e somente seb � b0 2 Ai�1 � Ai�1. De�nimos TR como o n�umero de triangulos em Gi. Ent~ao, parai > 100, obtemos E(TR) < 100;77ip3 = 125:100;32i:Ent~ao pela desigualdade de Markov, tomando � = 10 e i > 300, temosP(TR < 100;33i) > 0; 9: (2.13)Como os eventos (1), (2), (3), (4) tem probabilidade � 0:9 ent~ao eles tem interse�c~ao n~aovazia e, portanto, existe um B satisfazendo (i), (iii), (iv) (por (3)).Podemos ent~ao retirar os triangulos de Gi sem diminuir demais a quantidade dev�ertices. Por abuso de nota�c~ao, chamamos tambem Gi esse grafo sem triangulos. Te-mos que o n�umero de arestas de EGi �e limitado por jAi�1 � Ai�1jp2 = O(jAi�1j2p2) ecomo jAi�1j2 � 0@ i�1Xk=i0 k1=310k=3100 1A2 � c((i� 1)10i�1)1=3100 !2 � c2100(i10i)1=3;E(EGi) < (1=5000)i2=3102i=3p2 < (1=100)i2=310(2=3�0;3)i47

e pela desigualdade de Markov, com � = 10, temosP(EGi < (1=10)i2=310(2=3�0:3)i) � 0; 9: (2.14)Seja t o grau m�edio de Gi. Ent~ao, por (5) e por (1)t = 2jEGijjVGij < 210 i2=310(2=3�0:3)i100:35i < 210 i2=310(2=3�0:65)ie pelo Teorema 2.1.7, Gi cont�em pelo menos2:100:35i log tt > 10(0:35+0:65)i 10 log ti2=3102i=3= 10i=310 log ti2=3 � ii2=3 10i=3v�ertices independentes. Tomando extremos temos2:100:35i log tt > i1=310i=3v�ertices independentes; desses v�ertices (1=10500)i1=310i=3 v~ao formar Bi satisfazendo (ii) e(v).2

48

2.3.2 Um limitante inferior para o problema de HeilbronnRecordemos do Cap��tulo 1 a conjectura de Heilbronn. Consideremos o disco D de �area1 no plano e um conjunto S = fp1; :::; png de n pontos de D. Seja �(S) a �area m��nimade um triangulo cujos v�ertices s~ao 3 pontos diferentes de D. Heilbronn (� 51) colocou oproblema de calcular �(n) = max�(S)onde S toma valores sobre todos os conjuntos de n pontos em D. A primeira estimativapara �(n) �e �(n) = O(n�1);e Heilbronn conjecturou que o valor correto era �(n) = O(n�2).Conjectura 2.3.4 (Heilbronn, � '51) Para alguma constante absoluta c > 0, todacon�gura�c~ao de n pontos no disco unit�ario cont�em necessariamente um triangulo de �areamenor que cn�2.Erd}os, em [18], mostrou que �(n) 6= o(n�2) provando assim que se essa conjecturafosse v�alida ent~ao o resultado seria o \melhor poss��vel".Por�em a conjectura de Heilbronn �e falsa e foi refutada em 1982 por Koml�os, Pintze Szemer�edi [14], que provaram que �(n) n~ao s�o n~ao �e limitada por cn�2 (para algumaconstante c), como seu crescimento �e, pelo menos, mais veloz que esse limite vezes un fatorlogar��tmico.Teorema 2.3.5 (Koml�os, Pintz e Szemer�edi, '82; [14]) Para todo inteiro n existeuma con�gura�c~ao de n pontos no disco unit�ario que n~ao cont�em triangulos de �area menorque c1(logn)=n2;onde c1 > 0 �e uma constante absoluta.Demonstra�c~ao. De�namos os n�umeros t, n1, � pondot = n1=1001 ;n = c2(n1=t)(log t)1=2;� = c3(logn)=n2:Escolhamos ao acaso n1 pontos no disco unit�ario, independentemente e uniformemente ede�namos o 3-grafo F pondo 3 destes pontos a, b, c numa aresta fa; b; cg de F se e somentese os pontos a, b, c formam um triangulo de �area menor do que �.Vamos limitar a probabilidade de que tres destes pontos, a; b; c formem um triangulode �area menor do que �. Para tanto, expressamos essa probabilidade em termos doTeorema de Probabilidade TotalP(Area(a; b; c) � �) = Z +1�1 P(Area(a; b; c) � � j jb� aj = r)fjb�aj(r)dr49

onde, P(Area(a; b; c) � � j jb� aj = r) = ZArea(a;b;c)�� fArea(a;b;c)jjb�aj(a j r)dapara limitar superiormente a probabilidade condicional consideramos que a base do triangulo�e formada pelos pontos a; b e que estes pontos se encontram a distancia r; a altura h doterceiro ponto c deve satisfazer hr=2 < �. Nestas condi�c~oes, a �area onde o ponto c podetomar valores �e limitada pela �area de um retangulo de base m�axima � 2=p� e altura2h < 4�=r, portanto,P(Area(a; b; c) � � j jb� aj = r) � 2hr < (4�=r)(2=p�):Por outro lado, a distribui�c~ao do comprimento da base do triangulo pode-se limitar comosegue P(r � jb� aj � r +�r) � �(r +�r)2 � �r2;portanto, F (r +�r)� F (r)�r � �(2r +�r)e tomando limite quando �r ! 0 obtemosF 0(r) = f(r) = 2�r:Portanto, P(Area(a; b; c) � �) � Z 2=p�0 8�rp�2�rdr = 32� < t2=n21:Sejam agora Xa;b;c = ( 1 se a; b; c 2 V e Area(a; b; c) � �;0 caso contr�arioe X igual ao n�umero de triangulos de �area menor ou igual que �. Ent~aoX = Xa;b;c2V e Area(a;b;c)��Xa;b;c;portanto, E(X) = Xa;b;c2V e Area(a;b;c)��E(Xa;b;c)= n3!P(a; b; c 2 V e Area(a; b; c) � �) < n36 t2n21 ;portanto, o valor esperado do n�umero de triangulos de �area menor que � �e menor quen1t2=6 e, assim, o valor esperado do grau m�edio t(3) satisfazt(3) = 1n Xx2V d(3)(x) = 3jFjn ;50

portanto, E(t(3)) = 3E(jFj)n < 3n nt26 = t22 :Agora vamos mostrar que podem-se descartar os circuitos de comprimento 2 do 3-grafoF , sem diminuir muito o n�umero de v�ertices.Com efeito, j�a queP(x; y 2 V tais que jy � xj < d) = ZD P(y 2 V : jy � xj < d j x 2 V )fX(x)dxonde P(y 2 V : jy � xj < d j x 2 V ) = Zy:jy�xj<d fjy�xjjx(s j x)ds:J�a que esta �ultima integral �e limitada superiormente por �d2 e como a �area D �e 1, temosP(x; y 2 V tais que jy � xj < d) � d2�ent~ao o n�umero de pares de v�ertices a distancia menor que d = n�0:6 em F �e, com altaprobabilidade, menor que n12 !d2� < 2n0:81descartemos estes v�ertices de F .Que duas arestas formem um 2-circuito signi�ca que foram escolhidos quatro v�erticesa; b; c; d tais que as arestas fa; b; cg e fa; b; dg formam triangulos de �area menor do que �.Sendo que a elei�c~ao dos v�ertices �e independente ent~ao as probabilidades de eleger c e d semultiplicam e, pela desigualdade de Markov, temos que o n�umero de 2-circuitos de F �e,com alta probabilidade, menor quec4n41 Z 2d �2r2 2�rdr < c5t4 logn1 < n0:11 :Apagando os v�ertices em cada um destes circuitos, obtemos um 3-grafo (que denotamostamb�em por F), com cintura maior ou igual do que 3. Portanto, pelo Teorema 2.2.4 este3-grafo cont�em pelo menos c2(n1=t)(log t)1=2 = nv�ertices independentes, ou seja, existem n pontos no disco unit�ario D que n~ao temtriangulos de �area menor do que c1(logn)=n2:251

Cap��tulo 3Uma T�ecnica de R�odlO ano 1985 foi prol���co em resultados sobre empacotamentos e coberturas de hipergrafos;Os resultados que comentaremos foram desenvolvidos a partir da prova original de R�odl deuma conjectura de Erd}os e Hanani. Na primeira se�c~ao deste cap��tulo vamos nos concentrarem expressar, na linguagem algor��tmica das Se�c~oes 2.1 e 2.2 do Capitulo 2, uma vers~aomuito elegante de Pippenger do resultado de Frankl e R�odl; o resultado de R�odl ser�aobtido como corol�ario desse teorema de Pippenger na segunda se�c~ao; a terceira se�c~aodeste cap��tulo �e incluida como um hist�orico geral dos sucessivos avan�cos desta t�ecnicadesenvolvidos a partir do resultado original de R�odl,De�ni�c~ao 3.0.6 Dado um hipergrafo F = (V;F) e X � V , de�nimosF(X) = fF 2 F : X � Fge d(X) = jF(X)j:No caso de ser X = fxg, escrevemos simplesmente F(x) e d(x) e se X = fx; yg escreve-mos F(x; y) e d(x; y).Uma cobertura (de v�ertices por arestas ) K em F �e um conjunto de hiperarestasde F tal que cada v�ertice est�a, no m��nimo, numa hiperaresta de K. Um empacotamen-to P em F �e um conjunto de hiperarestas tal que todo v�ertice est�a, no m�aximo, numahiperaresta de P. Uma cobertura ou um empacotamento �e perfeito se cada v�ertice est�aem exatamente uma de suas hiperarestas. Neste caso os conceitos coincidem. Denotamospor �(F) a cardinalidade de um empacotamento m�aximo e por Cob(F) a cardinalidade deuma cobertura m��nima de F .De�ni�c~ao 3.0.7 Dado um hipergrafo F = (V;F) o ��ndice crom�atico �0(F) �e o n�umerom��nimo de empacotamentos nos quais as hiperarestas de F podem ser particionadas. De-notamos com �(F) o tamanho m�aximo de uma cole�c~ao disjunta de coberturas de F .52

Os resultado de Pippenger que apresentaremos foi derivado do seguinte teorema deFrankl e R�odl.Teorema 3.0.8 (Frankl e R�odl, '85; [10]) Sejam dados � > 0 arbitr�ario, um r-grafoF = (V;F) sobre n v�ertices e a > 3 um n�umero real. Existe um n�umero real positivo� = �(�) tal que se para algum D temos(i) d(x) �� D para todo x 2 V ,(ii) d(x; y) < D=(logn)a para todo x, y, x 6= y,ent~ao, para todo n > n0(�), temos Cob(F) � nr (1 + �):3.1 A vers~ao restrita de Pippenger do teorema deFrankl e R�odl3.1.1 A transforma�c~aoAlguns anos depois, em 1989, Pippenger e Spencer [16] obtem um resultado bem maisforte que o de Frankl e R�odl, sob hip�oteses menos restritivas. Parafraseando o sum�ariodo artigo: Numa cole�c~ao de r-grafos com grau m��nimo assint�otico ao grau m�aximo � etal que o n�umero de hiperarestas contendo qualquer par de v�ertices �xos �e desprez��vel emrela�c~ao ao grau m�aximo, tem-se que o ��ndice crom�atico �e assint�otico ao grau m�aximo. Istoquer dizer que as hiperarestas podem ser particionadas em empacotamentos ou coberturasquase-perfeitos.A seguir apresentamos o novo resultado.Lema 3.1.1 (A transforma�c~ao) Sejam �xos r, � > 0 e K. Ent~ao para todo �0 > 0,existe um � > 0 para o qual vale o seguinte. Se n > n0(r; �0; �; K) e D > D0(r; �0; �; K) e�e dado um r-grafo F = (V;F) sobre n v�ertices satisfazendo(i) d(x) < KD para todo x 2 V ,(ii) d(x) �� D vale para, no m��nimo, (1� �)n v�ertices,(iii) d(x; y) < �D para todo x 6= y,ent~ao existe R � F tal que pondo V � = V n SR, e F� = FjV �, temos(iv) jRj ��0 �n=r,(v) jSF�j ��0 ne��, 53

(vi) d�(x) ��0 De��(r�1) vale para, no m��nimo, (1� �0)jSF�j dos v�ertices de F�.Demonstra�c~ao. De�ne-se o subhipergrafo R pondoP(F 2 R) = p = �=Dsendo estes eventos independentes. Da�� as provas de (iv), (v) e (vi) do Lema 2.3.4 seguemo seguinte roteiro: aproxima-se a esperan�ca da vari�avel de interesse at�e um erro pequeno�; depois estima-se a variancia da vari�avel para aplicar a desigualdade de Chebyshev emostrar que a vari�avel est�a pr�oxima do valor de sua esperan�ca com alta probabilidade.Sem entrar em todos os detalhes, vamos esbo�car as aproxima�c~oes das esperan�cas.Considere X = fx 2 V : d(x) = (1� �)Dgde (ii) sabemos jXj � (1� �)n e portanto(1� �)2Dr � Px2X d(x)r � (1 + �)DjXjrpara x 2 X. Por outro lado, de (i), temos0 � Px62X d(x)r � KDj �Xjrportanto (1� �)2Dnr � Px2V d(x)r = jFj � Dr f(1 + �)jXj+ j�XjgKconsiderando jXj � n e j �Xj � �n temos(1� (2� �)�)Dnr � jFj � Dnr f1 + (1 +K)�gtomando �1 = minf(2� �)�; (1 +K)�g obtemos(1� �1)Dnr � jFj � Dnr (1 + �1)i.e. jFj ��1 Dnr :(iv) Da a�rmativa anterior temos,j jFj � Dnr j p � �1Dnr p54

e j�a que jRj � B(jFj; p) segue quej E(jRj)� �nr j� �1 �nri.e. (1� �1)�nr � E(jRj) � (1 + �1)�nrE(jRj) ��1 �nrou E(jRj) = (1� �1)�nr :Para aproximar jRj por sua variancia temos que escolher um � tal quej jRj � E(jRj) j� �E(jRj)i.e. (1� �)E(jRj) � jRj � (1 + �)E(jRj)da aproxima�c~ao para E(jRj)(1� �1)(1� �)�nr � (1� �)E(jRj) � jRj � (1 + �)E(jRj) � (1 + �)(1 + �1)�nrportanto basta tomar �2 = �1 + �+ �1� e � � �1, temos(1� �2)�nr � jRj � (1 + �2)�nre assim jRj ��2 �nrou jRj = (1� �2)�nr :J�a que para a variancia temosVar(jRj) = jFjp(1� p) � 2n�r ;ent~ao, pela desigualdade de Chebyshev, obtemosP�jRj = (1� �2)�nr � = P (j jRj � E(jRj) j� �E(jRj))� 1� Var(jRj)(�E(jRj))2 = 1� 2r�2�n(1� �1) ! 1para algum �2, quando n! +1. Da�� (iv) vale quase sempre.55

(v) De�nimos, para cada x 2 V �, as vari�aveisYx = ( 1 se x 62 SR0 se x 2 SR:Portanto j[F�j = Xx2V � Yx:J�a que temos E(Yx) = (1� p)d(x)e e�2pd(x) � (1� p)d(x) � e�pd(x)ent~ao para os v�ertices x tais que d(x) = D(1� �)e�2p(1��)D � e�2pd(x) � (1� p)d(x) � e�pd(x) � e�p(1+�)De�2�(1��) � (1� p)d(x) � e��(1+�)Tomando �3 = maxfe��(1+�) � e��; e�� � e��(1��)g (e para isto � tem que ser pequeno obastante) obtemose�� � �3 � e�2�(1��) � (1� p)d(x) � e��(1+�)es � e�� + �3e�� � �3 � (1� p)d(x) � e�� + �3j E(Yx)� e�� j� �3;ou melhor, tomando �� = �3=e�� temosE(Yx) ���3 e��:Por outro lado, j�a que os outros v�ertices satisfa�cem 0 � E(Yx) � 1 obtemosn(1��)(e����3) � Xx:d(x)=D(1��) E(Yx) � E(j[F�j) = Xx:d(x)=D(1��) E(Yx)+ Xx:d(x)6=D(1��) E(Yx)� Xx:d(x)=D(1��)(e�� + �3) + Xx:d(x) 6=D(1��) 1 � n(e�� + �3) + �nportanto ne��(1� �)(1� �3e�) � E(j[F�j) � ne��(1 + (�3 + �)e�);ou seja, E(j[F�j) = �(n):Note que, tomando �4 = maxf� + (1� �)�3e�; (�3 + �)e�g temosne��(1� �4) � E(j[F�j) � ne��(1 + �4)56

isto �e E(j[F�j) = ne��(1� �4)ou E(j[F�j) ��4 ne��:Limitase superiormente a variancia de jSF�j, utilizando-se deVar(j[F�j) = Xx2V Var(Yx) + Xx;y2V :x 6=yXCov(Yx; Yy):Note que Cov(Yx; Yy) = E(YxYy)� E(Yx)E(Yy)= (1� p)d(x)+d(y)�d(x;y) � (1� p)d(x)+d(y) = (1� p)d(x)+d(y)((1� p)�d(x;y) � 1)� (1� p)�d(x;y) � 1 < epd(x;y) � 1 < e�� � 1 < �5e esse �5 pode ser t~ao pequeno quanto desejado ajustando-se �.Para o primeiro somando temosXx2V Var(Yx) � Xx2V E(Yx) = E(j[F�j) = o((E(j[F�j))2):Portanto, dado �5 existe um n0 tal que se n � no ent~aoE(j[F�j) � �5(E(j[F�j))2e assim podemos limitar a variancia como segueVar(j[F�j) � �5(E(j[F�j))2 + �5n2e j�a que E(jSF�j �e da ordem de n2� �5(E(j[F�j))2 + �5C2(E(j[F�j))2para alguma constante C2. Tomando �6 � �5(1 + C2), ainda temos que esse �6 pode setornar t~ao pequeno quanto desejado ajustando-se �5 (que por sua vez se controla com �...).Tomamos �6 � �24 e obtemosVar(j[F�j) � �6(E(j[F�j))2:Vamos ajustar agora a proximidade de jSF�j e a sua esperan�ca para poder aplicar adesigualdade de Chebyshev. Para tal efeito, precisamos determinar um � tal quej j[F�j � E(j[F�j) j� �E(j[F�j):57

Pela de�ni�c~ao de �4 temosne��(1��4)(1��) � E(j[F�j)(1��) � j[F�j � E(j[F�j)(1+�) � ne��(1+�4)(1+�);portanto basta tomar �7 = �4 + �+ �4� e � � �4. Se � = �4 temosne��(1� �7) � j[F�j � ne��(1 + �7)j[F�j ��7 ne��ou j[F�j = (1� �7)ne��:Agora, aplicando a desigualdade de Chebyshev,P �j[F�j = ne��(1� �7)� = P �j j[F�j � E(j[F�j) j� �E(j[F�j)�� 1� �6�2 = 1� �6�24 ! 1pela escolha de �6, para n su�cientemente grande. Da�� (v) vale quase sempre.(vi) Come�camos observando que dado x 2 V e F0 2 F com x 2 F0, temosjfF 2 F : x 62 F; F \ F0 6= ;gj ��8 (r � 1)D:Pois, se fx; yg � F ent~aojfF 0 2 F : fx; yg � F 0; gj � �D:Portanto quase todas as arestas (a menos de �D delas) incidentes aos outros v�ertices deF (distintos de x), n~ao cont�em x e s~ao em quantidade (r � 1)D � �D.Assumindo que x =2 SR, observamos que F0 =2 R quando F =2 R, para toda arestaF que cont�em algum vertice y 2 F0, y 6= x. Consideremos agora o que acontece com asarestas do conjunto no r-grafo transformado F�. Nenhuma de tais arestas est�a em R comprobabilidade (1� p)(r�1)D ��9 e�p(r�1)D = e��(r�1);P (F 2 F� j x 62 R) = (1� p)(r�1)D = e�(r�1)� � �10;assim d�(x) � B((1� �)D; e��(r�1) � �10) eE(d�(x)) = D(e��(r�1) � �11):Para cada F incidente a x (tem mais ou menos D deles), de�nimosXF = ( 1 se F 2 F�;0 caso contrario.58

Da�� d�(x) = XF2F :x2F XFE(d�(x)) = XF2F :x2F E(XF )e se F; F 0 2 F com x 2 F e x 2 F 0. Para Sop(F ) sendo o n�umero de arestas de F queincidem a F e n~ao est~ao em R,Cov(XF ; XF 0) = (1� p)jSop(F )[Sop(F 0)j � (1� p)2(r�1)D= (1� p)2(r�1)D((1� p)�n�umero de arestas comuns � 1)= (1� p)2(r�1)D(e�(r�1)2� � 1) < �12:Portanto Var(d�(x)) = XF :x2F Var(XF ) + XF :x2F XF 0:x2F 0 Cov(XF ; XF 0)� E(d�(x)) + XF :x2F XF 0:x2F 0 �12 = E(d�(x)) + �13D2e a desigualdade de Chebyshev garante (vi).23.1.2 O algoritmoTeorema 3.1.2 (Pippenger, cf. F�uredi, '88; [11]) Para todo inteiro r � 2 e n�umerosreais K � 1 e � > 0 existe um � > 0 para o qual vale o seguinte. Se, para algum d, or-grafo F = (V;F) sobre n v�ertices satisfaz(i) d(x) < Kd para todo x 2 V ,(ii) d(x) �� d vale para, no m��nimo, (1� �)n dos v�ertices,(iii) d(x; y) < �d para todo x 6= y,ent~ao Cob(F) < (n=r)(1 + �):Para a demonstra�c~ao consideremos o seguinte algoritmo.Algoritmo 3.1.3 Entrada: r � 2, K � 1, � > 0 e um r-grafo F satisfazendo (i), (ii) e(iii) do Teorema 2.3.5.Sa��da: Uma cobertura de F .1. Ponha (V0;F0) = (V;F), 59

�0 > 0 tal que �0=(1� e��0) + r�0 < 1 + �,t 2 N o menor inteiro tal que (1� �)t < �,�0 > 0 tal que (1 + �0)(�0=(1� e��0) + r�0) < 1 + �e de�na uma seq�uencia �0; �1; : : : ; �t tal que �s+1 � �se��0(r�1).2. Para s = 0 at�e s = t� 1 fa�caCalcule Rs+1 e Fs+1 = F�s aplicando o Lema 2.3.4 a Fs.3. Para cada v�ertice n~ao coberto por algum Rs escolha arbitrariamente uma arestacontendo-o e seja Rt o conjunto de tais arestas.4. Devolva R = Sts=0Rs.Lema 3.1.4 (Invariantes) Em cada itera�c~ao s do Algoritmo 3.1.3, temosjRsj ��s �ne��sr ;j[Fsj ��s ne��s:As a�rmativas deste lema decorrem por indu�c~ao das a�rmativas (iv) e (v), respectiva-mente, do Lema 2.3.4.Lema 3.1.5 (Corretude) A cobertura R = Sts=0Rs, devolvida pelo Algoritmo 3.1.3 sa-tisfaz jRj � nr (1 + �):Com efeito, pela primeira a�rmativa do lema anterior e do fato de ser jVsj ��t ne��0t,temos jRj = t�1Xs=0Rs +Rt � t�1Xs=0 �0nr e��0s + ne��0t= nr (�0 (1� e��0t)(1� e��0) + re��0t) � nr ( �0(1� e��0) + r�0) ;sendo a �ultima desigualdade garantida pela escolha de t; de onde temos a tese, pela escolhade �0.2 60

3.2 Conseq�uencias: a conjectura de Erd}os e HananiRecordemos do Cap��tulo 1 a conjectura de Erd}os e Hanani. Dados inteiros n, k e r(r � k � n), de�nimos M(k; r; n) como a cardinalidade de um sistema m��nimo de k-conjuntos (subconjuntos de tamanho k) de [n] = f1; :::; ng tal que todo r-conjunto de [n]est�a contido em, no m��nimo, um dos k-conjuntos do sistema. Analogamente denotamospor m(k; r; n) a cardinalidade de um sistema maximo de k-conjuntos de [n] tal que todor-conjunto de [n] est�a contido, no m�aximo, num k-conjunto do sistema.Conjectura 3.2.1 (Erd}os e Hanani, '63; [8]) Para todo r � k �xos, temoslimn!+1m(k; r; n) kr! nr!�1 = limn!+1M(k; r; n) kr! nr!�1 = 1Foi para provar essa conjectura que R�odl [17], estabeleceu os resultados expostos naSe�c~ao 1 do Cap��tulo 2. Aqui comentamos como essa conjetura �e conseq�uencia do Teoremade Frankl e R�odl na vers~ao de Pippenger.Consideremos o �kr�-grafo F com v�ertices [n](r) = Knr , onde um conjunto F de �kr�arestas de Knr formam uma aresta de F se F [F ] �= Kkr . Veri�ca-se ent~ao o seguinte.Dados �kr� > 2, � > 0, existe � > (k � r)=(n� r) e K > 0 tal que(i) dF(x) < K�n�rk�r� para todo x 2 [n](r),(ii) dF(x) �� �n�rk�r� para todo x 2 [n](r),(iii) dF(x; y) < ��n�rk�r� para todos x, y 2 [n](r), x 6= y.Ent~ao, pelo Teorema 2.3.5, temosCob(F) < nr! kr!�1(1 + �):Assim Cob(F) = nr! kr!�1(1 + o(1))onde o(1)! 0 quando n! +1.Seja C uma tal cobertura (de v�ertices por arestas) de F , digamosC = fF1; : : : ; FCob(F)g.Ponha C = fV1; : : : ; VCob(F)g onde Vi �e a uni~ao dos r-conjuntos que formam a aresta Fipara todo i. Ent~ao C �e um sistema de k-conjuntos de [n] tal que todo r-conjunto de [n]est�a contido em, no m��nimo, um dos k-conjuntos de C. Portantolimn!+1M(k; r; n) kr! nr!�1 = 1:61

Vamos construir agora um empacotamento que veri�que o limitante inferior.Com efeito, de�nimosX = fx 2 [n](r) : x �e coberto pelo menos duas vezes por C gP = fF 2 C : 9x 2 X; x 2 Fg:A seguir consideramos os graus com respeito a C.Xx2[n](r) dC(x) = jCj kr! � nr!(1 + �)Xx2[n](r) dC(x) � Xx2[n](r) 1 + Xx2X(dC(x)� 1) � nr!+ jXjportanto jXj � � nr!:Consideremos agoraXx2[n](r) dC(x) = Xx 62X 1 + Xx2X dC(x) � (1� �) nr!+ jP jdo limitante superior obtemos jP j � 2� nr!:De�nimos agora o empacotamento E = C n P e temosjEj = jC n P j = jCj � jP j� nr! kr!�1 � 2� nr! � 1� 2� kr!! nr! kr!�1e portanto limn!+1m(k; r; n) kr! nr!�1 = 1:62

3.3 Apendice: Desenvolvimento hist�orico da t�ecnicade R�odl3.3.1 O trabalho seminal de R�odl e os coment�arios de SpencerEm 1985 R�odl [17] inaugura uma t�ecnica na investiga�c~ao de empacotamentos e coberturasde hipergrafos; apresentamos nesta subse�c~ao s�o os principais lemas auxiliares do artigocitado, deixando seu resultado central para ser derivado como conseq�uencia de resultadosmais gerais que apresentaremos em se�c~oes posteriores.Doravante denotaremos por X(r) a fam��lia dos subconjuntos de tamanho r de umconjunto X.De�ni�c~ao 3.3.1 Seja dado um r-grafo k-partido F � [Skj=1 Vj](r) e L � Skj=1 Vj comjLj � r. Aqui e a seguir, assumimos que V (F) = Skj=1 Vj �e sempre a k-parti�c~ao associadaa F . Dizemos que L �e completo sobre jLj v�ertices se [L](r) � F , ou seja F [L] �= KjLjr ,o r-grafo completo sobre jLj v�ertices. Se L �e um conjunto completo e jLj = k dizemos queF [L] �= Kkr �e um k-�agono, e se jLj < k denotamos com �L(F) o n�umero de k-�agonos deF contendo L.Para todo I � [k] com jIj = r, pomos �I(F) = jFI j, ondeFI = fF 2 F : F \ Vi 6= ;; para todo i 2 Ig:Neste caso vamos tomar ao acaso um sistema K de k-�agonos e de�nir como o r-grafotransformado F� o formado pelas arestas n~ao cobertas por nenhum k-�agono de K.Lema 3.3.2 (A transforma�c~ao) Seja dado um r-grafo k-partido F � [Skj=1 Vj](r) comjVjj = n para todo j, e suponha que � e �l (r � l � k � 1) s~ao reais positivos menores doque 1 tais que(i) �I(F) � �nr para todo I 2 [k](r),(ii) �L(F) � �lnk�l para todo L completo em F com r � jLj = l < k.Ent~ao para todo � > 0 e n su�cientemente grande pode-se selecionar um sistema K dek-�agonos de F tais que se pomosF� = F n fF 2 F : existe K 2 K; F 2 Kg = F n [K2KK;temos(iii) �I(F�) � �nr exp(���r) para todo I 2 [k](r),(iv) �L(F�) � �lnk�l exp ����r ��kr�� �lr��� para todo L completo em F� (r � jLj =l < k), 63

(v) jffK1; K2g : K1; K2 2 K; K1 \K2 6= ;gj � 2��rjSK2KKj.O sistema K �e escolhido ao acaso, pondo um k-�agono de F em K com probabilidadep = �=nk�r e considerando estes eventos independentes. Para I 2 [k](r) mostra-se quea probabilidade de que uma aresta F 2 FI, n~ao coberta por k-�agonos, perten�ca a F�I �eaproximadamente exp(���r) e da�� obtem-se (iii). A prova de (iv) �e por indu�c~ao. Para (v)estima-se a cardinalidade do conjunto usando-se a desigualdade de Markov.Lema 3.3.3 (O algoritmo) Seja dado um r-grafo k-partido F � [Skj=1 Vj](r), onde jVjj =n para todo j, e suponha que � e �l (r � l � k � 1) s~ao reais positivos menores do que 1tais que(i) �I(F) � �nr para todo I 2 [k](r),(ii) �L(F) � �lnk�l para todo L completo em F com r � jLj = l < k.Ent~ao existe um sistema K de k-�agonos de F tais que(iii) jSK2KKj = jFj(1� o(1)),(iv) jKj � jFj�kr��1(1 + o(1)).Para a prova, considera-se o seguinte algoritmo.Algoritmo 3.3.4 Entrada: Um r-grafo k-partido F satisfazendo (i) e (ii) do Lema 2.1.3.Sa��da: Um sistema K de k-�agonos de F satisfazendo (iii) e (iv) do Lema 2.1.3.1. Ponha (V0;F0) = (V;F) e � = �=4�r.2. Para s = 0 at�e s = d(1=��r) log(2=�)e fa�caEscolha Ks e F�s segundo o Lema 3.3.2.De�na Fs+1 = F�t .3. Devolva K = Sd(1=��r) log(2=�)es=0 KsLema 3.3.5 (Invariantes) Em cada itera�c~ao do Algoritmo 3.3.4, temos(i) �L(Fs) � �lnk�l exp ����rs ��kr�� �lr��� para todo L completo em Fs e r � jLj < k,(ii) �I(Fs) � �nr exp(���r) para todo I 2 [k](r),64

(iii) jKsj � �1 + �2� jF � Fsj�kr��1.Lema 3.3.6 (Corretude) O sistema K de k-�agonos de F devolvido pelo Algoritmo 3.3.4satisfaz (iii) e (iv) do Lema 2.1.3.Observe que a estrat�egia do Algoritmo 3.3.4 �e cobrir um pouco de l-conjuntos completospor k-�agonos, retir�a-los, cobrir mais um pouco, retir�a-los, etc.No mesmo ano, Spencer [19], revisita o artigo de R�odl, esclarecendo um pouco mais anova t�ecnica; ele introduz certas no�c~oes de \regularidade" para sua vers~ao do resultado deR�odl. Vamos tomar algumas de suas id�eias b�asicas adaptando a discuss~ao �a nossa nota�c~aotentando conservar o esp��rito original.De�ni�c~ao 3.3.7 Dizemos que um r-grafo F = (V;F) sobre n v�ertices �e quase-aleat�oriocom densidade � e tolerancia � se(i) jFj �� ��nr�,(ii) �F (F) �� �(kr)�1�n�rk�r� para todo F 2 F .Observe que a classe de r-grafos para a qual foi provado o Lema 2.1.2 de R�odl est�acontida na classe de r-grafos quase aleat�orios com densidade � e tolerancia �, sendo que ahip�otese (ii) do Lema 2.1.2 �e relaxada na classe maior. �E essa a primeira aprimora�c~ao doresultado.Lema 3.3.8 (A transforma�c~ao) Sejam �, ��, � > 0 n�umeros reais positivos. Ent~aoexiste � > 0 e n0 tal que dado um r-grafo quase-aleat�orio F = (V;F) sobre n v�ertices,com densidade � e tolerancia �, existe uma fam��lia K de k-�agonos de F satisfazendojKj �� �� nr! kr!�1e tal que se F� = FnSK2KK, ent~ao F� �e quase-aleat�orio com densidade �e�� e tolerancia��. Isto �e(i) jF�j ��� �e���nr�,(ii) �F (F) ��� (�e��)(kr)�1�n�rk�r� para todo F 2 F .N~ao vamos entrar nos detalhes do artigo de Spencer, o qual �e, na verdade, tangencial�a discuss~ao deste cap��tulo; em vez disso, vamos citar a \vis~ao intuitiva" do seu x1, quecremos faz um bom resumo da t�ecnica de R�odl:Algoritmo 3.3.9 (Spencer, '85; [19]) 65

\Sejam r < k �xos e n arbitrariamente grande. Seja Knr o r-grafo completo sobre oconjunto de v�ertices [n]. Seja � um n�umero real positivo arbitrariamente pequeno (�xamos� primeiro e tomamos depois n grande.) Seja K0 uma cole�c~ao aleat�oria de ��nr��kr��1 k-�agonos de Knr e seja F1 a fam��lia das r-hiperarestas de Knr que n~ao est~ao contidas emnenhum Kkr 2 K0. J�a que K0 �e � vezes o tamanho de uma cobertura perfeita de Knr (sealguma existe), ele (K0) cobriria, se (entre seus elementos) n~ao h�a sobreposi�c~ao, umapropor�c~ao � das r-hiperarestas de Knr . De fato, sobreposi�c~ao �e a considera�c~ao cr��tica. Ahiperaresta t��pica �e coberta uma m�edia de � vezes por K0. Existem muitos k-conjuntoscobrindo uma aresta dada e cada um deles tem s�o uma pequena chance de ser postoem K0. Portanto o n�umero de k-conjuntos de K0 cobrindo uma r-hiperaresta dada �edado por uma distribui�c~ao Poisson com m�edia �. Isto �e, �e�� das r-hiperarestas s~aocobertas exatamente uma vez, (�2=2)e�� s~ao cobertas exatamente duas vezes, (�i=i!)e��s~ao cobertas exatamente i vezes e e�� n~ao s~ao cobertas nenhuma vez e permanecem emF1. Quando � �e su�cientemente pequeno, a propor�c~ao das r-hiperarestas cobertas duasou mais vezes, grosseiramente �2=2, �e uma propor�c~ao desprez��vel da propor�c~ao dos r-conjuntos, grosseiramente �, que s~ao cobertos uma vez s�o. Isto �e, K0 �e uma excelente,embora n~ao perfeita, cobertura de Knr n F1.Continuamos o processo com F1. Escolhemos K1 entre os k-�agonos de F1. Isto �eessencial pois n~ao queremos que nenhuma das �kr� r-hiperarestas cobertas por algum Kkr 2K1 j�a esteja coberta por K0. Tomamos K1 ao acaso escolhendo a cardinalidade de modoque se n~ao h�a sobreposi�c~ao uma propor�c~ao � de F1 ser�a coberta. Seja F2 dado pelas rhiperarestas restantes|aquelas n~ao cobertas por nenhum Kkr 2 K1. Novamente o n�umerode k-conjuntos cobrindo uma r-hiperaresta de F1 �e dado por uma distribui�c~ao Poissoncom m�edia � e K1 �e uma cobertura excelente de F1 n F2.Iteramos este processo|dado Fi achamos Ki e pomos Fi+1 igual �as r-hiperarestasrestantes|at�e atingir um Ft com uma propor�c~ao desprez��vel de r-hiperarestas. J�a quecada jFi+1j � e��jFij tomamos t su�cientemente grande de modo que e��t seja muitopequeno. Neste ponto as r-hiperarestas restantes s~ao cobertas uma a uma. Embora istoseja muito custoso (queremos k-conjuntosK para cobrir �kr� novas r-hiperarestas, mas aquiusamos um k-conjunto K para cobrir uma r-hiperaresta) aceitamos tal custo j�a que jFtj�e pequeno. Com � e e��t su�cientemente pequenos a cobertura total tem uma propor�c~aomuito pequena de desperd��cio."Naturalmente, a constru�c~ao de uma tal cobertura era o objetivo de R�odl em [17] comoveremos na Se�c~ao 2.4. A estrat�egia de cobrir uma a uma as hiperarestas restantes, quando�cam poucas por cobrir, vai ser um novo passo costumeiro nas provas algor��tmicas dossucessivos desenvolvimentos desta t�ecnica.Deixamos agora estas discuss~oes iniciais para passar ao pr�oximo passo no desenvolvi-mento desta t�ecnica.66

3.3.2 O teorema de Frankl e R�odlAinda no mesmo ano, Frankl e R�odl [10] conseguem impor outras condi�c~oes su�cientespara a existencia de uma cobertura quase perfeita num r-grafo; eles trocam as condi�c~oesde regularidade que Spencer tinha imposto sobre o n�umero de arestas do r-grafo e aquantidade de cliques contendo um conjunto completo por condi�c~oes sobre o grau dosv�ertices. Examinemos rapidamente sua proposta.De�ni�c~ao 3.3.10 Dado um hipergrafo F = (V;F) e X � V , de�nimosF(X) = fF 2 F : X � Fge d(X) = jF(X)j:No caso de ser X = fxg, escrevemos simplesmente F(x) e d(x) e se X = fx; yg escreve-mos F(x; y) e d(x; y).Uma cobertura (de v�ertices por arestas ) K em F �e um conjunto de hiperarestasde F tal que cada v�ertice est�a, no m��nimo, numa hiperaresta de K. Um empacotamen-to P em F �e um conjunto de hiperarestas tal que todo v�ertice est�a, no m�aximo, numahiperaresta de P. Uma cobertura ou um empacotamento �e perfeito se cada v�ertice est�aem exatamente uma de suas hiperarestas. Neste caso os conceitos coincidem. Denotamospor �(F) a cardinalidade de um empacotamento m�aximo e por Cob(F) a cardinalidade deuma cobertura m��nima de F .Embora seja introduzida uma nova condi�c~ao um pouco restritiva ((ii) abaixo), a novatransforma�c~ao j�a n~ao requer retirar um sistema de k-�agonos de F para que o r-graforestante F� satisfa�ca as teses, simplesmente retiramos um conjunto de arestas e de�nimoscomo o hipergrafo transformafo F� o formado pelas arestas que n~ao se intersectam comas arestas retiradas: mais uma simpli�ca�c~ao.Lema 3.3.11 (A transforma�c~ao) Sejam dados � > 0 e um r-grafo F = (V;F) sobre nv�ertices tal que, para todo x, y 2 V , dado � > 0, existe � = �(�) > 0 tal que se F satisfaz(i) jF(x)j �� D,(ii) jF(x; y)j < D=(logn)a para algum a > 3 �xo,ent~ao para n > n0(�; �) existe R � F tal quejRj �2� �n=r;j[Rj �4� n(1� e��);e o r-grafo F� = fF 2 F : F \R = ;; para todo R 2 Rg com v�ertices V n SR satisfaz67

(iii) jF�(x)j �6� De��(r�1),(iv) jF�(x; y)j < De��(r�1)=(logn)a�o(1).O resultado central desta se�c~ao �e o seguinte.Teorema 3.3.12 (Frankl e R�odl, '85; [10]) Sejam dados � > 0 arbitr�ario, um r-grafoF = (V;F) sobre n v�ertices e a > 3 um n�umero real. Existe um n�umero real positivo� = �(�) tal que se para algum D temos(i) d(x) �� D para todo x 2 V ,(ii) d(x; y) < D=(logn)a para todo x, y, x 6= y,ent~ao, para todo n > n0(�), temos Cob(F) � nr (1 + �):Para a prova considera-se o seguinte algoritmo.Algoritmo 3.3.13 Entrada: � > 0, a > 3 e um r-grafo F satisfazendo (i) e (ii) doTeorema 2.2.3.Sa��da: Uma cobertura de F de tamanho � nr (1 + �).1. Ponha (V0;F0) = (V;F), � = �=3 e t o maior inteiro maior que (log r)=2 tal quePt�1s=0 �nr e��s + e��tn � nr (1 + �)2. Para s = 0 at�e s = t� 1 fa�caCalcule Rs e Fs+1 = F�s aplicando o Lema 3.3.11 a Fs.3. Para cada v�ertice n~ao coberto por algum Rs escolha uma aresta contendo-o. SejaRt o conjunto de tais arestas.4. Devolva R = Sts=0Rs.Lema 3.3.14 (Invariante) Em cada itera�c~ao do Algoritmo 3.3.13 temosjRs+1j ��=3 �nr e��s:A prova �e feita por indu�c~ao, usando no passo indutivo o Lema 2.2.2 e observando queem cada passo jV �s+1j = j[F�s+1j � e��j[Fsj = e��jVsj:68

Lema 3.3.15 (Corretude) O conjunto R = Sts=0Rs devolvido pelo Algoritmo 3.3.13 �euma cobertura de F e satisfaz jRj � nr (1 + �):Na de�ni�c~ao de t, os termos da somat�oria correspondem �a cardinalidade dos conjuntosRs do Passo 2 e como um caso particular da argumenta�c~ao para o invariante, no �nal dopasso do Algoritmo 3.3.13, temos quejV �t j = j[F�t j � e��j[Ft�1j = e��jVt�1j � e��tjV0j = e��tn�e a quantidade de v�ertices que �caram sem cobrir no Passo 2. Tais v�ertices s~ao cobertosno Passo 3, e o Lema 2.2.6 segue da de�ni�c~ao de t.3.3.3 A extens~ao de Pippenger e SpencerAlguns anos depois, em 1989, Pippenger e Spencer [16] obtem um resultado bem maisforte que o de Frankl e R�odl, sob hip�oteses menos restritivas. Parafraseando o sum�ariodo artigo: Numa cole�c~ao de r-grafos com grau m��nimo assint�otico ao grau m�aximo � etal que o n�umero de hiperarestas contendo qualquer par de v�ertices �xos �e desprez��vel emrela�c~ao ao grau m�aximo, tem-se que o ��ndice crom�atico �e assint�otico ao grau m�aximo. Istoquer dizer que as hiperarestas podem ser particionadas em empacotamentos ou coberturasquase-perfeitos.A seguir apresentamos o novo resultado.De�ni�c~ao 3.3.16 Dado um hipergrafo F = (V;F) o��ndice crom�atico �0(F) �e o n�umerom��nimo de empacotamentos nos quais as hiperarestas de F podem ser particionadas. De-notamos com �(F) o tamanho m�aximo de uma cole�c~ao disjunta de coberturas de F .Teorema 3.3.17 (Pippenger e Spencer, '89; [16]) Para todo r � 2 e � > 0 existem� > 0 e n0 tais que se um r-grafo F = (V;F) sobre n v�ertices satisfaz(i) d(x) �� �(F) para todo x 2 V ,(ii) d(x; y) � ��(F) para todo x, y 2 V ,ent~ao �0(F) �� �(F);�(F) �� �(F):Observe como �e mais geral a nova extens~ao: a condi�c~ao (ii) do Teorema 2.3.2 inclui aclasse de r-grafos que satisfaz (ii) do Teorema 2.2.3, e �e uma condi�c~ao bem mais simples.Veja como a extens~ao �e mais forte: ela garante que podemos cobrir as arestas do r-grafocom �(F) coberturas, bastante mais do que a �unica cobertura devolvida pelo Teorema2.2.3. 69

Referencias Bibliogr�a�cas[1] M. Ajtai, J. Koml�os, J. Pintz, J. Spencer, e E. Szemer�edi. Extremal UncrowdedHypergraphs. Journal of Combinatorial Theory, Series A, 32(3):321{335, 1982.[2] M. Ajtai, J. Koml�os, e E. Szemer�edi. A Dense In�nite Sidon Sequence. EuropeanJournal of Combinatorics, 2(1):1{11, 1981.[3] N. Alon, H. Lefman, e V. R�odl. On an Anti-Ramsey Type Result. Colloquia Mathe-matica Societatis J�anos Bolyai, 60:10{22, 1991.[4] S. Chowla. On a problem of Erd}os e Tur�an in additive number theory.Proc.Natn.Acad.Sci.India, 14:1{2, 1944.[5] R. A. Duke, H. Lefmann, e V. R}odl. On Uncrowded Hypergraphs. Reom Structurese Algorithms, 6(2 e 3):209{212, 1995.[6] P. Erd}os. On a problem of Sidon in additive number theory; addendum. Journal ofthe London Mathematical Society, 19:208, 1944.[7] P. Erd}os. Some of my Favourite Problems in Number Theory, Combinatorics, eGeometry. Resenhas do Instituto de Matem�atica e Estat��stica da USP, 2(2):165{196,1995.[8] P. Erd}os e Hanani H. On a Limit Theorem in Combinatorial Analysis. Publ. Math.Debrecen, 10:10{13, 1963.[9] P. Erd}os e Tur�an. On a problem of sidon in additive number theory e some relatedproblems. Journal of the London Mathematical Society, 16:212{215, 1941.[10] P. Frankl e V. R�odl. Near Perfect Coverings in Graphs e Hypergraphs. EuropeanJournal of Combinatorics, 6(4):317{326, December 1985.[11] Z. F�uredi. Matchings e Covers in Hypergraphs. Graphs e Combinatorics, 4(2):115{206, 1988.[12] H. Halberstam e K. F. Roth. Sequences, volume I. Oxford University Press, Oxford,1966. 70

[13] J. H. Kim. The Ramsey Number r(3; t) Has Order of Magnitude t2= log t. ReomStructures e Algorithms, 7(3):173{207, 1995.[14] J. Koml�os, J. Pintz, e E. Szemer�edi. A Lower Bound for Heilbroon's Problem. Journalof the London Mathematical Society, 2(25):13{24, 1982.[15] Kr}uckeberg. B2 Folgen und verwete Zahlenfolgen. Journal f�ur reine und angeweteMathematik, Be 206:53{60, 1961.[16] N. Pippenger e J. Spencer. Asymptotic Behavior of the Chromatic Index for Hyper-graphs. Journal of Combinatorial Theory, Series A, 51(1):24{42, 1989.[17] V. R�odl. On a Packing e Covering Problem. European Journal of Combinatorics,6(1):69{78, 1985.[18] K. F. Roth. On a Problem of Heilbronn. Appendix. Journal of the London Mathe-matical Society, 26:198{204, 1951.[19] J. Spencer. Asymptotically Good Coverings. Paci�c Journal of Mathematics,118(2):575{586, 1985.

71