Dois resultados em combinatória contemporânea Guilherme

Dois resultados emcombinatória contemporânea

Guilherme Oliveira Mota

Tese apresentadaao

Instituto de Matemática e Estatísticada

Universidade de São Paulopara

obtenção do títulode

Doutor em Ciências

Programa: Ciência da ComputaçãoOrientador: Prof. Dr. Yoshiharu Kohayakawa

Durante o desenvolvimento deste trabalho o autor recebeu auxílio financeiro doCNPq (140882/2009-0) e da FAPESP (2009/06294-0 e 2012/00036-2)

São Paulo, agosto de 2013

Dois resultados emcombinatória contemporânea

Esta é a versão original da tese elaborada pelocandidato Guilherme Oliveira Mota, tal como

submetida à Comissão Julgadora.

Agradecimentos

Primeiramente agradeço a meus pais, que nunca pouparam esforços para que eu tivesse umaformação de qualidade, sempre me apoiando e me ajudando em tudo e, apesar de estaremtão longe, sempre fazem o possível para ficarem mais próximos de mim. Agradeço tambémao meu irmão George e ao meu primo Fábio (um irmão para mim) pelos vários momentosde alegria que me proporcionam sempre que vou a Fortaleza.

Não posso deixar de prestar meus sinceros agradecimentos ao Yoshi, que sempre me ofere-ceu oportunidades para que eu pudesse crescer intelectualmente. Além disso, suas qualidadesde excelente professor e pesquisador servem constantemente como fonte de inspiração paramim e me motivam a continuar buscando melhorar.

Entre muitas coisas boas que me aconteceram em São Paulo durante o meu doutorado,certamente uma das melhores foi conhecer a Suelen, essa pessoa maravilhosa na qual tenhoo prazer de ter como minha companheira. Sussu teve um papel fundamental durante odesenvolvimento da minha pesquisa, sempre me incentivando e me apoiando nos momentosmais difíceis, sendo o alicerce que me manteve firme ao longo desses últimos anos. Ressaltotambém sua contribuição importantíssima na revisão final da tese.

Muitos amigos também me ajudaram durante a realização dessa tese. Sou muito grato aoLeandro Lima, por ter me incentivado a fazer doutorado na USP. Um agradecimento especialvai para Roberto e Rafinha, que estiveram sempre presentes, ajudando nos momentos difíceise tornando os momentos felizes ainda mais especiais. Agradeço à Naty, essa pessoa queridaque veio se juntar ao trio cearense. Não posso deixar de agradecer também à Iasmin, Patríciae Tixa, pelo carinho e pelas longas conversas, especialmente quando eu me encontrava longedo país.

Agradeço de todo o coração à nova família que ganhei na Alemanha, em Hamburgo: Andrée Philip, por serem parceiros para toda hora, irmãos brasileiros que ganhei na Alemanha, eTia Dô, por ter me acolhido como um filho em sua casa, com a alegria e carinho que lhe épeculiar.

Sou também muito agradecido aos meus orientadores alemães, Anusch e Mathias, porterem me ajudado no desenvolvimento de meu projeto de pesquisa e por terem me recebidotão bem na Alemanha.

Por fim, agradeço a todos os parceiros de jiu-jitsu que tive durante esses anos, especi-almente ao meu mestre Adriano Silva. Certamente os treinos foram essenciais para que eumantivesse a mente leve para trabalhar melhor nos problemas matemáticos.

i

ii

Resumo

Mota, G. O. Dois resultados em combinatória contemporânea. Tese – Instituto deMatemática e Estatística, Universidade de São Paulo, São Paulo, 2013.

Dois problemas combinatórios são estudados: (i) determinar a quantidade de cópias deum hipergrafo fixo em um hipergrafo uniforme pseudoaleatório, e (ii) estimar números deRamsey de ordem dois e três para grafos com largura de banda pequena e grau máximolimitado.

Apresentamos um lema de contagem para estimar a quantidade de cópias de um hiper-grafo k-uniforme linear livre de conectores (conector é uma generalização de triângulo, parahipergrafos) que estão presentes em um hipergrafo esparso pseudoaleatório G. Considere umhipergrafo k-uniforme linear H que é livre de conectores e um hipergrafo k-uniforme G comn vértices. Seja dH = maxδ(J) : J ⊂ H e DH = minkdH ,∆(H). Estabelecemos que, seos vértices de G não possuem grau grande, famílias pequenas de conjuntos de k−1 elementosde V (G) não possuem vizinhança comum grande, e a maioria dos pares de conjuntos em(V (G)k−1

)possuem a quantidade “correta” de vizinhos, então a quantidade de imersões de H

em G é (1+o(1))n|V (H)|p|E(H)|, desde que p n1/DH e |E(G)| =(nk

)p. Isso generaliza um re-

sultado de Kohayakawa, Rödl e Sissokho [Embedding graphs with bounded degree in sparsepseudorandom graphs, Israel J. Math. 139 (2004), 93–137], que provaram que, para p dadocomo acima, esse lema de imersão vale para grafos, onde H é um grafo livre de triângulos.

Determinamos assintoticamente os números de Ramsey de ordem dois e três para grafosbipartidos com largura de banda pequena e grau máximo limitado. Mais especificamente,determinamos assintoticamente o número de Ramsey de ordem dois para grafos bipartidoscom largura de banda pequena e grau máximo limitado, e o número de Ramsey de ordemtrês para tais grafos, com a suposição adicional de que ambas as classes do grafo bipartidotêm aproximadamente o mesmo tamanho.

Palavras-chave: Pseudoaleatoriedade, hipergrafos, imersão, Ramsey, regularidade.

iii

iv

Abstract

Mota, G. O. Two results in modern combinatorics. Tese – Instituto de Matemática eEstatística, Universidade de São Paulo, São Paulo, 2013.

Two combinatorial problems are studied: (i) determining the number of copies of a fixedhipergraph in uniform pseudorandom hypergraphs, and (ii) estimating the two and threecolor Ramsey numbers for graphs with small bandwidth and bounded maximum degree.

We give a counting lemma for the number of copies of linear k-uniform connector-freehypergraphs (connector is a generalization of triangle for hypergraphs) that are containedin some sparse hypergraphs G. Let H be a linear k-uniform connector-free hypergraphand let G be a k-uniform hypergraph with n vertices. Set dH = maxδ(J) : J ⊂ H andDH = minkdH ,∆(H). We proved that if the vertices of G do not have large degree,small families of (k − 1)-element sets of V (G) do not have large common neighbourhoodand most of the pairs of sets in

(V (G)k−1

)have the ‘right’ number of common neighbours, then

the number of embeddings of H in G is (1 + o(1))n|V (H)|p|E(H)|, given that p n1/DH and|E(G)| =

(nk

)p. This generalizes a result by Kohayakawa, Rödl and Sissokho [Embedding

graphs with bounded degree in sparse pseudorandom graphs, Israel J. Math. 139 (2004), 93–137], who proved that, for p as above, this result holds for graphs, where H is a triangle-freegraph.

We determine asymptotically the two and three Ramsey numbers for bipartite graphswith small bandwidth and bounded maximum degree. More generally, we determine asymp-totically the two color Ramsey number for bipartite graphs with small bandwidth and boun-ded maximum degree and the three color Ramsey number for such graphs with the additionalassumption that both classes of the bipartite graph have almost the same size.

Keywords: Pseudorandomness, hypergraphs, embedding, Ramsey, regularity.

v

vi

Sumário

1 Introdução 1

2 Preliminares 52.1 Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Hipergrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3 Lema de contagem para hipergrafos pseudoaleatórios 93.1 Lemas principais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.2 Resultados auxiliares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3.2.1 Alguns resultados combinatórios . . . . . . . . . . . . . . . . . . . . . 123.2.2 Generalizando as propriedades LMT e CG . . . . . . . . . . . . . . . 13

3.3 Lema de Extensão e corolários . . . . . . . . . . . . . . . . . . . . . . . . . . 193.3.1 Lema de Extensão . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.3.2 Corolários do Lema de Extensão . . . . . . . . . . . . . . . . . . . . . 21

3.4 Provas dos lemas principais . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.4.1 Prova do Lema CG2→t . . . . . . . . . . . . . . . . . . . . . . . . . . 243.4.2 Prova do Lema de contagem modificado . . . . . . . . . . . . . . . . 27

4 Números de Ramsey para grafos bipartidos 314.1 Visão geral da prova do Teorema 3-Ramsey . . . . . . . . . . . . . . . . . . . 334.2 Resultados auxiliares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.2.1 Método da Regularidade . . . . . . . . . . . . . . . . . . . . . . . . . 364.2.2 Explosão regular de uma árvore . . . . . . . . . . . . . . . . . . . . . 384.2.3 Intervalos balanceados . . . . . . . . . . . . . . . . . . . . . . . . . . 40

4.3 Prova do Teorema 3-Ramsey . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.4 Ideia da prova do Teorema 2-Ramsey . . . . . . . . . . . . . . . . . . . . . . 48

5 Considerações finais 51

Referências Bibliográficas 53

vii

viii SUMÁRIO

Capítulo 1

Introdução

Uma classe de problemas particularmente importante em combinatória diz respeito a deter-minar se existe uma cópia de um grafo fixo em grafos maiores. O clássico Lema de Regu-laridade de Szemerédi [53] afirma que, desde que um grafo seja suficientemente grande, seuconjunto de vértices pode ser particionado em no máximo um número constante de classescom aproximadamente o mesmo tamanho, de modo que as arestas, na maioria dos grafosbipartidos induzidos pelos vértices dessas classes e pelas arestas entre as classes, são bemdistribuídas (uma partição satisfazendo essa propriedade é dita regular). Porém, dado umgrafo G = (V,E) com n vértices, a partição de V obtida pelo Lema de Regularidade contémuma quantidade quadrática de pares não regulares, de modo que, se a quantidade de arestasdo grafo em questão é o(n2), elas podem estar quase totalmente contidas somente nos paresnão regulares. Nesse caso, o subgrafo de G induzido pelos pares regulares é muito esparso.Logo, o Lema de Regularidade é útil somente para grafos densos (grafos com Ω(n2) arestas).Para uma descrição mais formal do Lema de Regularidade, veja a Seção 4.2.1.

Lemas de Imersão são resultados que garantem a existência de cópias de grafos fixos Hem grafos maiores, tipicamente em partições regulares. Quando, em vez de garantir somentea existência, a quantidade de cópias de H é estimada, temos o que chamamos de Lemasde Contagem. Assim, a combinação do Lema de Regularidade com lemas de contagem émuito útil na solução de problemas que objetivam encontrar cópias de um grafo H emgrafos maiores. Para uma discussão aprofundada sobre regularidade, lemas de contagempara grafos densos e aplicações, veja [40, 43].

O grafo aleatório binomial de Erdős e Rényi G ∈ G(n, p) é um grafo com um conjuntode n vértices, onde cada dois vértices são adjacentes com probabilidade p e essas adja-cências são independentes. Dado um grafo H, a 2-densidade de H é dada por d2(H) =(|E(H)| − 1)/(|V (H)| − 2). Um grafo H é dito 2-balanceado se a 2-densidade de H é maiorou igual que a 2-densidade de qualquer de seus subgrafos que contêm pelo menos três vér-tices. Kohayakawa e Rödl introduziram uma versão do Lema de Regularidade para grafosesparsos, i.e., grafos com uma quantidade subquadrática de arestas (veja, e.g. [33, 36]). To-davia, durante muito tempo, não se conheciam lemas de contagem que funcionassem nesse

1

2 INTRODUÇÃO 1.0

contexto esparso. Kohayakawa, Łuczak e Rödl [35] conjecturaram um resultado de contagemprobabilístico, conhecido como Conjectura KŁR, que, durante muito tempo foi sido provadoapenas para algumas classes particulares de grafos (veja [23, 25, 26, 34, 38]). Em 2012, foiprovada uma versão da Conjectura KŁR para subgrafos de G(n, p) [15], uma versão paragrafos 2-balanceados [2] e, finalmente, a conjectura foi provada em toda sua generalidadeno trabalho de Saxton e Thomason [52], através de uma técnica de contagem de conjuntosindependentes em hipergrafos uniformes.

Pelo que foi discutido nos parágrafos anteriores, já sabemos da utilidade de lemas decontagem e sabemos também que os problemas relacionados a esses lemas têm sido ex-tensivamente estudados desde o surgimento do Lema de Regularidade. Em particular, umproblema que tem chamado a atenção dos pesquisadores é a obtenção de lemas de contagemde grafos fixos em grafos “pseudoaleatórios”, como pode ser visto nos trabalhos de Conlon,Fox e Zhao [13], e Kohayakawa, Rödl, Schacht e Skokan [39]. Diante desses resultados en-volvendo grafos, o interesse na resolução de problemas para hipergrafos cresceu de formasignificativa (veja [14, 21, 22]). Um dos problemas em que estamos interessados aqui é ainvestigação de lemas de contagem de hipergrafos fixos em hipergrafos pseudoaleatórios.

Existem, na literatura, diversas noções bem conhecidas de pseudoaleatoriedade paragrafos (veja, e.g., [10, 9, 44, 54]). Algumas dessas noções são relacionadas com o grau e cograudos vértices, e com a distribuição das arestas do grafo. Tais conceitos de pseudoaleatoriedadeforam generalizados de algumas maneiras diferentes para hipergrafos (veja [21, 22]). Em [21],intuitivamente, um hipergrafo uniforme G é definido como pseudoaleatório se, (i) para todoconjunto ‘pequeno’ de vértices S, a quantidade de arestas que contêm S é próxima daquantidade esperada em um hipergrafo uniforme aleatório, e (ii) para todo par de conjuntos‘pequenos’ de vértices S1 e S2, o cograu de S1 e S2, i.e., a quantidade de arestas de G quecontêm S1 e S2, não é muito maior do que a quantidade esperada em um hipergrafo uniformealeatório. Em [22], a noção de pseudoaleatoriedade considerada é mais forte, no sentido queé preciso ter o controle não somente dos graus e cograus dos vértices, mas de algumas outrasestruturas do hipergrafo. No Capítulo 3 discutimos uma noção de pseudoaleatoriedade parahipergrafos, que se assemelha à noção utilizada em [21], e provamos um lema de contagemem hipergrafos suficientemente pseudoaleatórios.

Dado um grafo H, defina dH = maxδ(J) : J ⊂ H e DH = min2dH ,∆(H), ondeδ(H) e ∆(H) são, respectivamente, os graus mínimo e máximo de H. Em [37], Kohayakawa,Rödl e Sissokho provaram que, dado um grafo fixo H livre de triângulos e p = o(1) comp n−1/DH vale o seguinte. Para todo ε > 0, existem δ > 0 tal que se G é um grafo comn vértices suficientemente grande, onde |EG| =

(n2

)p, a vizinhança comum de subconjuntos

pequenos de vértices de G não é ‘grande’ e, para a maioria dos vértices v e pares de vérticesu, v de G, o grau de v e o cograu de u, v é próximo do valor esperado em G(n, p), então oseguinte vale:

∣∣∣|I(H,G)| − nv(H)pe(H)∣∣∣ < εnv(H)pe(H), onde I(H,G) é o conjunto de todas as

imersões de H em G. O lema de contagem apresentado no Capítulo 3 generaliza o resultadode Kohayakawa, Rödl e Sissokho para hipergrafos lineares k-uniformes, onde estimamos a

1.0 3

quantidade de imersões de um hipergrafo linear (duas arestas compartilham no máximo umvértice) k-uniforme livre de conectores em hipergrafos k-uniformes pseudoaleatórios, ondeum conector é uma aresta e ∈ EH tal que existem x ∈ VH \ e e k arestas e1, . . . , ek quecontêm x, com |e ∩ ei| = 1 para todo i = 1, . . . , k.

Outro problema investigado nesta tese diz respeito à Teoria de Ramsey. Em 1930, Ramseyprovou um importante e clássico resultado, que é conhecido pelo nome de “Teorema deRamsey” [48], dando origem a uma área de pesquisa que hoje é conhecida por Teoria deRamsey. O teorema provado por Ramsey, que é uma generalização do princípio da casa dospombos, diz que, para todo par de inteiros r, s, existe um inteiro n tal que todo grafocompleto com pelo menos n vértices, cujas arestas são coloridas com duas cores (digamos,azul e vermelho), possui uma cópia do grafo completo com r vértices, onde todas as arestassão azuis, ou possui uma cópia do grafo completo com s vértices, onde todas as arestas sãovermelhas. O menor desses inteiros n tal que vale a propriedade acima é chamado de númerode Ramsey e denotado por R(r, s). Uma generalização natural dos números de Ramsey surgequando, em vez de grafos completos com r e s vértices, consideramos grafos arbitrários G1 eG2. Denotamos por R(G1, G2) o menor inteiro tal que todo grafo completo com pelo menosR(G1, G2) vértices, cujas arestas são coloridas com as cores azul e vermelho, possui umacópia azul de G1 ou uma cópia vermelha de G2. Dizemos que R(G1, G2) é o número deRamsey de ordem 2 para G1 e G2.

Podemos generalizar também a noção de números de Ramsey permitindo mais coresna coloração. Definimos o número de Ramsey de ordem r, denotado por R(G1, G2, . . . , Gr),como o menor inteiro positivo n tal que, se as arestas de um grafo completo com n vérticessão particionadas em r classes de cores distintas, fornecendo r grafos H1, H2, . . . , Hr, então,pelo menos um dos grafos Hi (1 ≤ i ≤ r) contém um subgrafo isomorfo a Gi.

Apesar dos muitos esforços ao longo dos anos, o problema de se determinar o valor dosnúmeros de Ramsey está longe de ser resolvido totalmente. Diversos resultados recentesmelhoraram os limitantes conhecidos para diversos números de Ramsey de ordem dois (veja,por exemplo, [11, 12, 16, 19, 20]).

Seja Pn um caminho com n ≥ 2 vértices. Um resultado clássico de Gerencsér e Gyár-fás [24] afirma que R(Pn, Pn) = b(3n − 2)/2c. Para alguns grafos particulares, o valor donúmero de Ramsey é conhecido de forma assintótica. Dada uma árvore T , escrevemos t1e t2, com t2 ≥ t1, para os tamanhos das classes de vértices de T , quando vista como umgrafo bipartido. Uma construção simples mostra que R(T, T ) ≥ max2t1 + t2, 2t2 − 1.Haxell, Łuczak e Tingley [32] determinaram assintoticamente o valor de R(T, T ) para ár-vores T com ∆(T ) = o(t2), provando que R(T, T ) = (1 + o(1))(2t1 + t2) se 2t1 ≥ t2, eR(T, T ) = (1 + o(1))2t2 se 2t1 < t2.

Dizemos que um grafo H = (W,EH) possui largura de banda (“bandwidth”) no máximob, se existe uma rotulação dos vértices de H com os números 1, . . . , n, de modo que, paracada aresta ij ∈ EH , temos |i−j| ≤ b. No Capítulo 4, apresentamos uma versão do resultadode Haxell, Łuczak e Tingley para grafos bipartidos com largura de banda pequena e grau

4 INTRODUÇÃO 1.0

máximo limitado. Mostramos que, para todo número natural ∆, existe uma constante β > 0tal que, para todo grafo bipartido H com n vértices, largura de banda no máximo βn e graumáximo limitado superiormente por ∆, onde existe uma 2-coloração própria χ : VH → [2],com t1 = |χ−1(1)|, t2 = |χ−1(2)| e t1 ≤ t2, temos R(H,H) = (1 + o(1)) max2t1 + t2, 2t2.

Para números de Ramsey de ordem três, poucos resultados são conhecidos. Em [30],prova-se que, desde que n seja suficientemente grande, R(Pn, Pn, Pn) = 2n − 1 quando né ímpar, e R(Pn, Pn, Pn) = 2n − 2 quando n é par. Esse resultado também foi provado,de forma assintótica, em [18]. Aprimorando técnicas em [29], Benevides e Skokan [3] resol-veram completamente o problema para circuitos pares suficientemente grandes, mostrandoque R(Cn, Cn, Cn) = 2n para n suficientemente grande. No Capítulo 4, estendemos assin-toticamente esses resultados para grafos bipartidos com largura de banda pequena e graumáximo limitado, onde as classes do grafo possuem aproximadamente o mesmo tamanho(grafos satisfazendo essa condição são chamados de balanceados). Mostramos que para todonúmero natural ∆, existe uma constante β > 0 tal que, para todo grafo bipartido balanceadoH com n vértices, largura de banda no máximo βn e grau máximo limitado superiormentepor ∆, temos R(H,H,H) = (2+o(1))n. Como corolário de nossos resultados, determinamosassintoticamente os números de Ramsey de ordem dois e três para grades.

Organizamos os capítulos subsequentes como segue. No Capítulo 2, introduzimos algunsconceitos e fixamos a notação que será utilizada ao longo deste trabalho. No Capítulo 3, dis-cutimos e provamos o lema de imersão de hipergrafos fixos em hipergrafos pseudoaleatórios.Os resultados sobre números de Ramsey são apresentados no Capítulo 4 e encerramos, noCapítulo 5, com alguns comentários finais sobre os resultados obtidos.

Capítulo 2

Preliminares

Neste capítulo introduzimos alguns conceitos importantes e fixamos a notação básica queserá utilizada nos capítulos subsequentes. Denotamos por [k] o conjunto 1, . . . , k. Dadasfunções f, g : N → R+ e um natural n, dizemos que f(n) = o(g(n)) se e somente se, paratodo ε > 0, existe n0 tal que, se n ≥ n0, então f(n) < εg(n). Algumas vezes escrevemosf(n) g(n) ao invés de f(n) = o(g(n)). A seguir introduzimos, respectivamente, conceitosrelacionados a grafos e hipergrafos.

2.1 Grafos

Um grafo G é um par de conjuntos finitos (VG, EG), onde VG é chamado de conjunto devértices de G, e EG, o conjunto de arestas de G, é um conjunto de pares não ordenadosde elementos distintos de VG. Escrevemos e(G) e v(G), respectivamente, para representara cardinalidade de E(G) e V (G). Escrevemos, por simplicidade, vw (ou wv) para denotara aresta v, w ∈ EG, e se vw /∈ EG, então vw é chamada de não-aresta de G. Dizemosque vw incide em v e em w (ou é incidente a v e w), e v e w são as extremidades daaresta vw. Nesse caso, dizemos que os vértices v e w são vizinhos. Se duas arestas possuemuma extremidade comum, então dizemos que essas arestas são adjacentes. Dado um vérticev ∈ VG, definimos o grau de v, denotado por dG(v), como a quantidade de vizinhos de v, istoé, dG(v) = |w ∈ VG : vw ∈ EG|. Quando estiver claro a que grafo G estamos nos referindo,escrevemos simplesmente d(v). Por fim, definimos o grau máximo e o grau mínimo de G,respectivamente, como ∆(G) = maxd(v) : v ∈ VG e δ(G) = mind(v) : v ∈ VG.

Dado um grafo G = (VG, EG) com n vértices e dois subconjuntos de vértices A e B, nãovazios e disjuntos, denotamos por EG(A,B) o subconjunto de arestas de EG que possuemuma extremidade em A e outra em B. Ademais, a cardinalidade de EG(A,B) é denotadapor eG(A,B). A densidade de G é dada por dG = e(G)/

(n2

)e dizemos que

dG(A,B) = eG(A,B)|A||B|

5

6 PRELIMINARES 2.2

é a densidade de G entre A e B.Se G é um grafo tal que VG pode ser dividido em dois subconjuntos disjuntos A e B e te-

mos EG = EG(A,B), então dizemos queG é um grafo bipartido e escrevemosG = (A,B;EG).Um grafo com n vértices que possui todas as

(n2

)arestas possíveis é chamado de grafo com-

pleto ou clique e é denotado por Kn.Um grafo H é dito subgrafo de um grafo G, e escrevemos H ⊂ G, se VH ⊂ VG e EH ⊂ EG.

Ademais, se VH = VG, então dizemos que H é um subgrafo gerador de G. Se um grafo G nãocontém nenhum subgrafo isomorfo a H, dizemos que G é livre de H. Dado um subconjuntode vértices W ⊂ VG, denotamos por G[W ] o grafo com conjunto de vértices W tal que oconjunto de arestas de G[W ] é composto pelo subconjunto de arestas de G que possuem asduas extremidades em W . Dizemos que o grafo G[W ] é o subgrafo de G induzido por W .

Um grafo P com conjunto de vértices VP = v1, . . . , vk é chamado de caminho seEP = v1v2, v2v3, . . . , vk−1vk. Se um grafo P ′ possui conjunto de vértices VP ′ = v1, . . . , vke conjunto de arestas dado por EP ∪ vkv1, então P ′ é chamado de circuito. Um grafo G éconexo se existe um caminho entre qualquer par de vértices v, w. Ademais, se T é um grafoconexo e não possui circuitos, então dizemos que T é uma árvore. Por fim, dado um grafoG, um emparelhamento M em G é um conjunto de arestas de G duas a duas não adjacentes.

Uma partição P = V1, . . . , Vk dos vértices de um grafo G é uma família de conjuntosVi ⊂ VG, para 1 ≤ i ≤ k, tal que esses conjuntos são disjuntos dois a dois e V1∪ . . .∪Vk = VG.Dizemos que cada Vi é uma classe da partição P .

Dado um grafo G, uma k-coloração dos vértices de G é uma função χV : VG → 1, . . . , k,isto é, uma função que atribui uma ‘cor’ para cada vértice de G, dentre k cores disponíveis.Analogamente, uma k-coloração das arestas de G é uma função χE : EG → 1, . . . , k. Se χVatribui cores distintas para todo par de vértices v, w tal que u é vizinho de w, então χV édita uma coloração própria dos vértices de G. Analogamente, se arestas adjacentes recebemcores distintas da coloração χE, então χE é dita uma coloração própria das arestas de G.Se, dada uma coloração das arestas de um grafo G, todas as arestas de um subgrafo H ⊂ G

possuem a mesma cor, então dizemos que H é monocromático.

2.2 Hipergrafos

Um hipergrafo H é um par de conjuntos finitos (VH , EH), onde VH é o conjunto de vérticesde H e o conjunto de hiperarestas EH é uma coleção de subconjuntos de vértices. Porsimplicidade, referimo-nos às hiperarestas simplesmente por ‘arestas’. Se todas as arestasde EH são subconjuntos com k vértices, dizemos que H é um hipergrafo k-uniforme. Noteque um grafo é um hipergrafo 2-uniforme. Um hipergrafo H é dito linear se cada par dearestas compartilha no máximo um vértice. Nesta seção introduzimos alguns conceitos quesão utilizados no Capítulo 3.

Denotamos por(VH

i

)o conjunto de todos os subconjuntos de VH com tamanho i e de-

2.2 HIPERGRAFOS 7

notamos por V iH o subconjunto de todas as sequências de VH com i elementos, isto é, cada

elemento de V iH é composto por i vértices de H, de modo que a ordem desses i vértices é

relevante.As seguintes definições estão relacionadas com a noção de vizinhança em hipergrafos

k-uniformes. Para 1 ≤ i ≤ k − 1, dado x1, . . . , xi ∈(VH

i

), defina

NH(x1, . . . , xi) =xi+1, . . . , xk ∈

(VHk − i

): x1, . . . , xk ∈ EH

,

i.e., NH(x1, . . . , xi) é o conjunto de elementos de(VH

k−i

)que, juntamente com x1, . . . , xi,

formam uma aresta de H. Defina dH(x1, . . . , xi) = |NH(x1, . . . , xi)| como sendo o graude x1, . . . , xi. Em particular, se x ∈ VH , então

NH(x) =x1, . . . , xk−1 ∈

(VHk − 1

): x, x1, . . . , xk−1 ∈ EH

.

Ademais, seja N conH (x) =

y : ∃x1, . . . , xk−1 ∈ NH(x) com y ∈ x1, . . . , xk−1

o conjunto

dos vértices deH que pertencem a alguma aresta que contém x. Dada uma coleçãoX ⊂(VH

k−1

)de conjuntos com k − 1 vértices, defina

NH(X) =x : x ∈ NH(x1, . . . , xk−1) para todo x1, . . . , xk−1 ∈ X

,

i.e., NH(X) é a vizinhança comum dos elementos de X.Finalizando, uma imersão de um hipergrafo H em um hipergrafo G é um mapeamento

injetivo φ : VH → VG tal que φ(v1), . . . , φ(vk) ∈ EG sempre que v1, . . . , vk ∈ EH .

8 PRELIMINARES 2.2

Capítulo 3

Lema de contagem para hipergrafospseudoaleatórios

Existem várias noções de pseudoaleatoriedade para hipergrafos 2-uniformes (grafos) na li-teratura. Algumas tratam da uniformidade na distribuição das arestas do grafo e outras,por exemplo, são baseadas no valor do segundo maior autovalor (em valor absoluto) damatriz de adjacências do grafo. Uma noção também importante de pseudoaleatoriedade emgrafos é relacionada com a quantidade de circuitos de tamanho 4 que o grafo possui (veja[10, 9, 8, 44, 54]).

Os conceitos de pseudoaleatoriedade citados no parágrafo anterior levam em conta ca-racterísticas globais do grafo. No entanto, algumas noções possuem um caráter mais local,sendo relacionadas ao grau dos vértices e ao cograu dos pares de vértices. Em [22], esseconceito é generalizado para hipergrafos uniformes. Por simplicidade, consideremos, por ora,apenas hipergrafos 3-uniformes. Sejam v1, . . . , vt vértices de um hipergrafo 3-uniforme G eseja J um grafo com conjunto de vértices [t]. Denotamos por dJ,G(v1, . . . , vt) a quantidadede vértices x ∈ G tais que vi, vj, x ∈ E(G) para toda aresta i, j ∈ E(J). Em [22], umanoção de pseudoaleatoriedade é dada pela definição abaixo.

Definição 3.1. Um hipergrafo 3-uniforme G é dito (ε, p)-uniforme se, para todo grafo au-xiliar J com t ≤ 7 vértices e s ≤ 6 arestas, e para toda escolha de vértices distintosv1, . . . , vt ∈ VG temos

|dJ,G(v1, . . . , vt)− nps| ≤ εnps.

A condição apresentada na definição acima é um pouco forte. De fato, no mesmo trabalhoem que a condição acima é apresentada (veja [22]), uma definição de pseudoaleatoriedadenecessita do controle de somente 5 grafos auxiliares, a saber:

J1: grafo com dois vértices e uma aresta;

J2: grafo com quatro vértices e duas arestas não adjacentes;

J3: grafo com três vértices e duas arestas;

9

10 LEMA DE CONTAGEM PARA HIPERGRAFOS PSEUDOALEATÓRIOS 3.0

J4: grafo com quatro vértices e três arestas formando um caminho;

J5: grafo com sete vértices e seis arestas formando dois caminhos de mesmo tamanho quese interceptam em exatamente um vértice interno de cada caminho.

Assim, consideremos a seguinte definição de hipergrafos (ε, p)-uniformes utilizada em [22].

Definição 3.2. Um hipergrafo 3-uniforme G é dito (ε, p)-uniforme se para i = 1, . . . , 5, epara toda escolha de vértices distintos v1, . . . , v|V (Ji)| ∈ VG temos

∣∣∣dJ,G(v1, . . . , v|V (Ji)|)− np|E(Ji)|∣∣∣ ≤ εnp|E(Ji)|.

Definimos agora algumas propriedades de hipergrafos que dizem respeito à vizinhançacomum de alguns subconjuntos de vértices. Com essas propriedades, vamos definir o conceitode pseudoaleatoriedade que iremos considerar neste capítulo. No que segue, tome k ≥ 2.

Propriedade 3.3 (LMT – Propriedade do limitante). Definimos LMTk(C, t) como a famíliade hipergrafos k-uniformes G com |VG| = n e p = |E(G)|/

(nk

)tais que, para todo 1 ≤ r ≤ t

e todos subconjuntos distintos S1, . . . , Sr ∈(VG

k−1

), temos

|NG(S1) ∩ . . . ∩NG(Sr)| ≤ Cnpr.

Propriedade 3.4 (CG – Propriedade do cograu). Definimos CGkε(t) como a família de

hipergrafos k-uniformes G com |VG| = n e p = |E(G)|/(nk

)tal que, para todo 1 ≤ r ≤ t,

temos que ∣∣∣|NG(S1) ∩ . . . ∩NG(Sr)| − npr∣∣∣ < εnpr

para mais que (1− ε)(( n

k−1)r

)famílias S1, . . . , Sr de subconjuntos distintos de

(VG

k−1

).

Se um hipergrafo k-uniforme G pertence a LMTk(C, t1) e CGkε(t2), dizemos que G é um

hipergrafo (C, t1, t2, ε)-pseudoaleatório. O lema de contagem que será apresentado nesta seçãodiz respeito à imersão de hipergrafos k-uniformes em hipergrafos G que contêm propriedadespseudoaleatórias mais fracas que as apresentadas na Definição 3.2, a saber, consideramos hi-pergrafos G que são (C, t, 2, δ)-pseudoaleatórios. Por exemplo, para hipergrafos 3-uniformes(C, t, 2, δ)-pseudoaleatórios, precisamos ter controle total somente sobre os grafos auxiliaresJ1, J2 e J3. Ademais, esse controle não precisa ser para toda escolha de pares de vérticesdistintos em G, e sim para a maioria dos pares, como pode ser visto na definição da pro-priedade CGk

ε(2). Uma noção de pseudoaleatoriedade semelhante à que consideramos nestecapítulo é utilizada em [21].

Dado um hipergrafo linear k-uniforme H, um conector é uma aresta e ∈ EH tal queexistem x ∈ VH \ e e k arestas e1, . . . , ek que contêm x, onde |e ∩ ei| = 1 para todoi = 1, . . . , k. Dizemos que um hipergrafo H é livre de conectores se não possui conectores.Ademais, note que os grafos (hipergrafos 2-uniformes) livres de conectores são os grafos livres

3.1 LEMAS PRINCIPAIS 11

de triângulos. Defina dH = maxδ(J) : J ⊂ H eDH = minkdH ,∆(H), onde δ(H) e ∆(H)são, respectivamente, os graus mínimo e máximo de H. Kohayakawa, Rödl e Sissokho [37]provaram que, dado um grafo fixo H livre de triângulos e p n−1/DH com p = o(1), paratodo ε > 0, existem δ > 0 e um natural n0 tal que, se n ≥ n0 e G é um grafo com n vértices,onde |E(G)| =

(n2

)p, G ∈ LMT2(C,DH) para algum C > 1 e G ∈ CG2

δ(2), então

∣∣∣|I(H,G)| − nv(H)pe(H)∣∣∣ < εnv(H)pe(H),

onde I(H,G) é o conjunto de todas as imersões de H em G. O resultado principal destecapítulo, Teorema 3.5, estende esse resultado para hipergrafos lineares k-uniformes livre deconectores.

Teorema 3.5. Sejam C > 1, m ≥ 4 inteiros e considere um hipergrafo linear k-uniformeH com m vértices e livre de conectores. Se p = p(n) = o(1) tal que p n−1/DH , então, paratodo ε > 0, existe δ > 0 e um inteiro n0 > 0 tal que o seguinte vale. Se uma sequência dehipergrafos k-uniformes Gn∞n=1 com |V (Gn)| = n é tal que, para todo n, o hipergrafo Gn é(C,DH , 2, δ)-pseudoaleatório e p = p(n) = e(Gn)/

(nk

), então, para todo n ≥ n0,

∣∣∣|I(H,Gn)| − nmpe(H)∣∣∣ < εnmpe(H).

Na Seção 3.1 enunciamos dois lemas que, juntos, compõem a prova do Teorema 3.5. A Se-ção 3.2 contém alguns resultados que são necessários para a prova do Lema 3.6, apresentadona Seção 3.1. Na Seção 3.3 apresentamos o Lema de Extensão, um importante resultado, útilpara a prova do outro lema (Lema 3.7) apresentado na Seção 3.1. Finalmente, na Seção 3.4,provamos os Lemas 3.6 e 3.7.

3.1 Lemas principais

Os próximos dois lemas, juntos, compõem a prova do Teorema 3.5.

Lema 3.6 (Lema CG2→t). Sejam t ≥ 2 e C > 1. Suponha que p = p(n) satisfaz p n−1/t.Seja Gn∞n=1 uma sequência de hipergrafos k-uniformes com Gn ∈ LMTk(C, 2) e |E(Gn)| =(nk

)p para todo n. Então, temos o seguinte:Para todo δ1 > 0, existem δ2 > 0 e n1 > 0 tais que, se n ≥ n1 e Gn ∈ CGk

δ2(2), entãoGn ∈ CGk

δ1(t).

O próximo resultado é muito similar ao Teorema 3.5. Trocamos apenas a propriedadeCGk

δ (2) por CGkδ (dH).

Lema 3.7 (Lema de contagem modificado). Sejam C > 1, m ≥ 4 e considere um hipergrafolinear k-uniforme H com m vértices e livre de conectores. Se p = p(n) = o(1) tal quep n−1/DH , então para todo ε > 0 existe δ > 0 e um inteiro n2 > 0 tal que o seguinte vale:


Se uma sequência de hipergrafos k-uniformes Gn∞n=1 com |V (Gn)| = n é tal que, paratodo n, o hipergrafo Gn é (C,DH , dH , δ)-pseudoaleatório e p = p(n) = e(Gn)/

(nk

), então,

para todo n ≥ n2, ∣∣∣|I(H,Gn)| − nmpe(H)∣∣∣ < εnmpe(H).

Apresentamos agora a prova do Teorema 3.5, utilizando os Lemas 3.6 e 3.7, que sãoprovados na Seção 3.4.

Prova do Teorema 3.5. Fixe C > 1 e m ≥ 4. Seja H um hipergrafo linear k-uniforme livrede conectores com |VH | = m. Tome p = p(n) = o(1) tal que p n−1/DH e fixe ε > 0.

Agora fazemos uso dos Lemas 3.6 e 3.7. Uma aplicação do Lema 3.7 com parâmetros m,ε e C nos retorna uma constante δ1 > 0 e um inteiro n2 > 0. Aplicando o Lema 3.6 comparâmetros t = dH , C e δ1, recebemos uma constante δ2 > 0 e um inteiro n1 > 0. Tomen0 = maxn1, n2 e considere n ≥ n0.

Seja Gn um hipergrafo k-uniforme Gn com n vértices e |E(Gn)| =(nk

)p. Suponha que Gn

é (C,DH , 2, δ2)-pseudoaleatório, i.e., Gn ∈ LMTk(C,DH) e Gn ∈ CGkδ2(2). Note que, desta

forma, também temos que Gn ∈ LMTk(C, 2). Ademais, p n−1/DH n−1/dH . Assim, oLema 3.6 garante que Gn ∈ CGk

δ1(dH). Portanto, pelo Lema 3.7, concluímos que∣∣∣|I(H,Gn)| − nv(H)pe(H)

∣∣∣ < εnv(H)pe(H).

3.2 Resultados auxiliares

Nesta seção apresentamos alguns resultados que são necessários para provar o Lema 3.6.Na Seção 3.2.1, introduzimos algumas desigualdades combinatórias e, na Seção 3.2.2, ge-neralizamos as propriedades LMT e CG para vértices, em vez de conjuntos de vértices detamanho k − 1.

3.2.1 Alguns resultados combinatórios

Primeiramente, introduzimos o seguinte lema, cuja prova pode ser vista em [37].

Lema 3.8. Para todo δ > 0, existe γ > 0 tal que, se uma família de números reais ai ≥ 0,para 1 ≤ i ≤ N , satisfaz as condições

(i) ∑Ni=1 ai ≥ (1− γ)Na,

(ii) ∑Ni=1 ai

2 ≤ (1 + γ)Na2,

então ∣∣∣i : |ai − a| < δa∣∣∣ > (1− δ)N.

3.2 RESULTADOS AUXILIARES 13

Os seguintes lemas apresentam algumas desigualdades combinatórias que serão utilizadascom frequência.

Lema 3.9. Para todos ε > 0, r ≥ 1 e 0 < α < 1, existe n0 tal que, se n ≥ n0, então(nα

r

)≥ (1− ε)αr

(n

r

).

Demonstração. Fixe ε > 0, r ≥ 1 e 0 < α < 1. Tome δ = 1− (1− ε)1/r e considere n ≥ n0,onde n0 = d(r − 1)(1 + (1− α)/αδ)e. Note que, para todo 0 ≤ k ≤ r − 1, as escolhas de n0

e δ implicam que

nα− k =(

1− (1− α)kα(n− k)

)(n− k)α ≥ (1− δ)(n− k)α = (1− ε)1/r(n− k)α.

Portanto, (nα

r

)=

r−1∏k=0

nα− kr − k

≥ (1− ε)αrr−1∏k=0

n− kr − k

= (1− ε)αr(n

r

).

Lema 3.10. Para todos ε > 0, r ≥ 1 e b > 0, existe n0 tal que, se n ≥ n0, então(nb

r

)≤ (1 + ε)br

(n

r

).

Demonstração. Fixe ε > 0, r ≥ 1 e b > 0. Agora fixe δ = (1 + ε)1/r − 1 e considere n ≥ n0,onde n0 = d(r − 1)(1 + (b− 1)/bδ)e. Note que, para todo 0 ≤ k ≤ r − 1, se b ≤ 1, temos

nb− k ≤ (1 + ε)1/r(n− k)b.

Por outro lado, se b > 1, as escolhas de n0 e δ implicam que

nb− k =(

1 + (b− 1)kb(n− k)

)(n− k)b ≤ (1 + δ)(n− k)b = (1 + ε)1/r(n− k)b.

Portanto, (nb

r

)=

r−1∏k=0

nb− kr − k

≤ (1 + ε)brr−1∏k=0

n− kr − k

= (1 + ε)br(n

r

).

3.2.2 Generalizando as propriedades LMT e CG

Considere constantes C > 1 e β > 0. Suponha que um hipergrafo k-uniforme Gn com n

vértices é (C, 2, 2, β)-pseudoaleatório. Para referências futuras, enunciamos abaixo as con-sequências desse fato.


• Para todo S ∈(VG

k−1

):

|N(S)| ≤ Cnp; (3.1)

• Para todos conjuntos distintos S1, S2 ∈(VG

k−1

):

|N(S1) ∩N(S2)| ≤ Cnp2; (3.2)

• Para mais que (1− β)(

nk−1

)conjuntos S ∈

(VG

k−1

):

∣∣∣|N(S)| − np∣∣∣ < βnp; (3.3)

• Para mais que (1− β)(( n

k−1)2

)conjuntos distintos S1, S2 ∈

(VG

k−1

):

∣∣∣|N(S1) ∩N(S2)| − np2∣∣∣ < βnp2; (3.4)

Se um hipergrafo k-uniforme G com n vértices pertence a LMTk(C, 2), então não existeum conjunto com k−1 vértices que possui vizinhança ‘grande’, e pares de conjuntos distintoscom k − 1 vértices também não possuem vizinhança comum ‘grande’. O próximo resultadoafirma que, se G pertence a LMTk(C, 2), então isto é verdade não somente para conjuntosde k − 1 vértices, mas para qualquer conjunto com i vértices, onde 1 ≤ i ≤ k − 1. Particu-larmente, o caso i = 1 é importante para nossa prova. Isso pode ser visto como uma versãode LMTk(C, 2) para vértices, em vez de conjuntos com k − 1 vértices.

Lema 3.11. Seja G um hipergrafo k-uniforme com n vértices. Se G satisfaz LMTk(C, 2),então, para cada 1 ≤ i ≤ k − 1, vale |N(S1)| ≤ Cnk−ip e |N(S1) ∩ N(S2)| ≤ Cnk−ip2 paratodos os subconjuntos distintos S1, S2 ∈

(VG

i

). Em particular,

(i) d(u) ≤ Cnk−1p, para todo u ∈ VG,

(ii) |N(u) ∩N(v)| ≤ Cnk−1p2, para todos u, v ∈(VG

2

).

Demonstração. Seja G um hipergrafo k-uniforme com n vértices e suponha G ∈ LMTk(C, 2).A prova segue por indução em i.

Pela definição de LMTk(C, 2), o resultado é válido para i = k − 1. Agora assuma que ascondições (i) e (ii) são válidas para 1 < i < k − 1. Vamos mostrar que o resultado é válidopara i− 1.

Fixe conjuntos distintos S1, S2 ∈(VG

i−1

). Começamos provando que |N(S1)| ≤ Cnk−(i−1)p.

Sabemos que |N(S1)| = ∑u∈VG\S1 |N(S1∪u)|. Portanto, utilizando a hipótese indutiva, temos

que |N(S1)| ≤ n(Cnk−ip) = Cnk−(i−1)p. Para verificar a outra condição, utilizamos a mesmaideia. Como |N(S1) ∩ N(S2)| = ∑

u∈VG\(S1∪S2) |N(S1 ∪ u) ∩ N(S2 ∪ u)|, a hipótese indutivagarante que |N(S1) ∩N(S2)| ≤ n(Cnk−ip2) = Cnk−(i−1)p2.


O próximo lema afirma que, se G é um hipergrafo (C, 2, 2, β)-pseudoaleatório k-uniformecom n vértices, então a maioria dos vértices de G possui grau ‘próximo’ de np, e para amaioria dos pares de vértices de G, a quantidade de vizinhos em comum é ‘próxima’ de np2.Isso pode ser visto como uma versão de CGk

β(2) para vértices, em vez de conjuntos com k−1vértices.

Lema 3.12. Seja C > 1 uma constante fixa e suponha que p = p(n) satisfaz p n−(k−1)/2.Se Gn∞n=1 é uma sequência de hipergrafos k-uniformes com Gn ∈ LMTk(C, 2) para todo n,onde |E(Gn)| =

(nk

)p, então o seguinte é válido para Gn∞n=1:

Para todo δ > 0, existem β > 0 e n0 > 0 tais que, se n ≥ n0 e Gn ∈ CGkβ(2), então

(i)∣∣∣d(u)−

(nk−1

)p∣∣∣ < δ

(nk−1

)p para mais que (1− δ)n vértices u ∈ VG;

(ii)∣∣∣|N(u) ∩N(v)| −

(nk−1

)p2∣∣∣ < δ

(nk−1

)p2 para mais que (1− δ)

(n2

)pares u, v ∈

(VG

2

).

Demonstração. As provas dos itens (i) e (ii) são similares, mas, por completude, apresenta-mos as duas provas. Fixe C > 1 e suponha que p n−(k−1)/2. Fixe δ > 0 e seja γ > 0 obtidopor uma aplicação do Lema 3.8 com parâmetro δ > 0. Tome

β = min

1− (1− γ)1/4, (1 + γ/2)1/3 − 1, γ/2(1 + 2C2).

Pela suposição sobre p, sabemos que, para n suficientemente grande, temos

p ≥(β−1(1 + β)C2(k − 1)k−1

)n−(k−1)/2.

No que segue supomos n ≥ n0, onde n0 é uma constante suficientemente grande, de modoque a desigualdade acima é satisfeita. Considere um hipergrafo k-uniforme G = Gn com n

vértices e |E(Gn)| =(nk

)p. Suponha que Gn ∈ LMTk(C, 2) e Gn ∈ CGk

β(2).Começamos provando o item (i). Vamos mostrar que as duas condições do Lema 3.8 são

satisfeitas. As equações (3.5) e (3.10) a seguir podem ser vistas como as condições requeridaspelo Lema 3.8.

Primeiramente, note que∑u∈VG

d(u) =∑

S∈( VGk−1)|N(S)|

≥∑

S∈( VGk−1) : |N(S)|≥(1−β)np

|N(S)|

≥ (1− β)2(

n

k − 1

)np

≥ (1− γ)n(

n

k − 1

)p.

(3.5)

onde a primeira desigualdade é trivial, a segunda segue de (3.3) e a última é consequência daescolha de β. Assim, a primeira condição do Lema 3.8 é satisfeita. Para a segunda, observe


que ∑u∈VG

d(u)2 =∑

S1,S2∈( VGk−1)|N(S1) ∩N(S2)|

= 2∑

S1,S2∈((VGk−1)

2 )|N(S1) ∩N(S2)|+

∑S∈( VG

k−1)|N(S)|.

(3.6)

Limitaremos os dois termos da igualdade acima. Por (3.1), temos

∑S∈( VG

k−1)|N(S)| ≤

(n

k − 1

)Cnp.

Como p ≥ ((k − 1)k−1C/β)n−(k−1), podemos concluir que C ≤ β(

nk−1

)p. Portanto,

∑S∈( VG

k−1)|N(S)| ≤ βn

((n

k − 1

)p

)2

. (3.7)

Agora definimos A =S1, S2 ∈

(( VGk−1)

2

): |N(S1) ∩ N(S2)| ≤ (1 + β)np2

e, por fim,

B =S1, S2 ∈

(( VGk−1)

2

): |N(S1) ∩N(S2)| > (1 + β)np2

. Note que

∑S1,S2∈((

VGk−1)

2 )|N(S1) ∩N(S2)| =

∑S1,S2∈A

|N(S1) ∩N(S2)|+∑

S1,S2∈B|N(S1) ∩N(S2)|

Mas, claramente,

∑S1,S2∈A

|N(S1) ∩N(S2)| ≤ (1 + β)2 n

((n

k − 1

)p

)2

. (3.8)

Por (3.2) e (3.4),

∑S1,S2∈B

|N(S1) ∩N(S2)| ≤ βC

2 n

((n

k − 1

)p

)2

. (3.9)

Substituindo (3.7), (3.8) e (3.9) em (3.6), obtemos

∑u∈VG

d(u)2 ≤ (β + (1 + β) + βC)n((

n

k − 1

)p

)2

≤ (1 + γ)n((

n

k − 1

)p

)2

,

(3.10)

onde a última desigualdade segue de β ≤ γ/(2 + C).


Assim, pelo Lema 3.8, concluímos que, para mais de (1− δ)n vértices u ∈ VG, temos∣∣∣∣∣d(u)−

(n

k − 1

)p

∣∣∣∣∣ < δ

(n

k − 1

)p,

como queríamos.Para concluir a prova precisamos verificar o item (ii). A estratégia é a mesma que utili-

zamos na verificação do item (i).

∑u,v∈(VG

2 )|N(u) ∩N(v)| =

∑S∈( VG

k−1)

(|N(S)|

2

)

≥∑

S∈( VGk−1) : |N(S)|≥(1−β)np

(|N(S)|

2

)

≥ (1− β)(

n

k − 1

)((1− β)pn

2

)

≥ (1− β)4(n

2

)(n

k − 1

)p2

≥ (1− γ)(n

2

)(n

k − 1

)p2.

(3.11)

onde a primeira desigualdade é trivial e a segunda segue de (3.3). Na terceira, aplicamos oLema 3.9 com parâmetros ε = β, r = 2 e α = (1 − β)p, e a última desigualdade segue deβ ≤ 1− (1− γ)1/4.

Provaremos uma desigualdade que, juntamente com (3.11), nos permite fazer uso doLema 3.8.

∑u,v∈(VG

2 )|N(u) ∩N(v)|2 =

∑S1,S2∈( VG

k−1)

(|N(S1) ∩N(S2)|

2

)

= 2∑

S1,S2∈((VGk−1)

2 )

(|N(S1) ∩N(S2)|

2

)+

∑S1∈( VG

k−1)

(|N(S1)|

2

).

(3.12)Limitaremos os dois termos da igualdade acima. Por (3.1),

∑S1∈( VG

k−1)

(|N(S1)|

2

)≤(

n

k − 1

)(Cnp

2

).

Uma aplicação do Lema 3.10 com parâmetros ε = β, r = 2 e b = Cp implica que(n

k − 1

)(Cnp

2

)≤ (1 + β)C2

(n

2

)(n

k − 1

)p2.

Como p ≥ ((1 + β)C2(k − 1)k−1/β)1/2n−(k−1)/2, concluímos que (1 + β)C2 ≤ β(

nk−1

)p2.


Portanto, ∑S1∈( VG

k−1)

(|N(S1)|

2

)≤ β

(n

2

)((n

k − 1

)p2)2

. (3.13)

Para limitar o termo remanescente, defina

A =S1, S2 ∈

((VG

k−1

)2

): |N(S1) ∩N(S2)| ≤ (1 + β)np2

,

e também defina

B =S1, S2 ∈

((VG

k−1

)2

): |N(S1) ∩N(S2)| > (1 + β)np2

.

Note que

∑S1,S2∈((

VGk−1)

2 )

(|N(S1) ∩N(S2)|

2

)=

∑S1,S2∈A

(|N(S1) ∩N(S2)|

2

)

+∑

S1,S2∈B

(|N(S1) ∩N(S2)|

2

).

Aplicando o Lema 3.10 com parâmetros ε = β, r = 2 e b = (1 + β)p2, obtemos

∑S1,S2∈A

(|N(S1) ∩N(S2)|

2

)≤ 1

2

(n

k − 1

)2((1 + β)p2n

2

)

≤ (1 + β)3

2

(n

2

)((n

k − 1

)p2)2

.

(3.14)

Por (3.2), (3.4) e pelo Lema 3.10 aplicado com parâmetros ε = β, r = 2 e b = Cp2,

∑S1,S2∈B

(|N(S1) ∩N(S2)|

2

)≤ β

2

(n

k − 1

)2(Cp2n

2

)

≤ β(1 + β)C2

2

(n

2

)((n

k − 1

)p2)2

.

(3.15)

Substituindo (3.13), (3.14) e (3.15) em (3.12), obtemos

∑u,v∈(VG

2 )|N(u) ∩N(v)|2 ≤

(β + (1 + β)3 + β(1 + β)C2

)(n2

)((n

k − 1

)p2)2

≤ (1 + γ)(n

2

)((n

k − 1

)p2)2

,

(3.16)

onde a última desigualdade segue da escolha de β.Equações (3.11) e (3.16) podem ser vistas como as condições requeridas pelo Lema 3.8.

3.3 LEMA DE EXTENSÃO E COROLÁRIOS 19

Assim, concluímos que, para mais de (1− δ)(n2

)pares de vértices u, v ∈

(VG

2

), temos

∣∣∣∣∣|N(u) ∩N(v)| −(

n

k − 1

)p2∣∣∣∣∣ < δ

(n

k − 1

)p2.

3.3 Lema de Extensão e corolários

Nesta seção, enunciamos e provamos um resultado que chamamos de Lema de Extensão.Desse lema, derivamos dois corolários, essenciais para a prova do Lema 3.7.

3.3.1 Lema de Extensão

Primeiramente, definimos alguns conceitos e enunciamos o lema. Feito isso, provamos doisresultados que, juntos, compõem a prova do Lema de Extensão, que é apresentada no finaldesta subseção.

Considere hipergrafos k-uniformes G e H. Dadas sequências F = (f1, . . . , f`) ∈ VH` e

X = (x1, . . . , x`) ∈ VG`, defina I(H,G, F,X) como o conjunto das imersões f ∈ I(H,G)

tais que f(fi) = xi para todo 1 ≤ i ≤ `. Ademais, escrevemos Y con = y1, . . . , y` parao conjunto dos vértices que fazem parte da sequência Y = (y1, . . . , y`). Dizemos que umsubconjunto V ′ ⊂ VH é estável se não existe aresta de H completamente contida em V ′, i.e.,E(H[V ′]) = ∅.

SejaH um hipergrafo comm vértices. Uma ordenação de VH é simplesmente uma sequên-cia (v1, . . . , vm) ∈ V m

H . Dizemos que H é d-degenerado se existe uma ordenação (v1, . . . , vm)de seus vértices de modo que dHi

(vi) ≤ d para todo 1 ≤ i ≤ m, onde Hi = H[v1, . . . , vi].Nesse caso, dizemos que (v1, . . . , vm) é uma ordenação d-degenerada dos vértices de H. Dadauma sequência F ∈ V `

H , denotamos por ω(H,F ) a quantidade de arestas de H que não estãocontidas em F con, isto é, ω(H,F ) = |EH | − |E(H[F con])|.

Lema 3.13 (Lema de Extensão). Sejam G e H hipergrafos k-uniformes, onde H é linear,|VH | = m, |VG| = n e p = p(n) = e(G)/

(nk

). Suponha que 0 ≤ ` ≤ maxk, dH, e sejam

F ∈ VH` e X ∈ VG` fixos. Considere uma constante C > 1 e suponha que G ∈ LMTk(C,DH).Então

|I(H,G, F,X)| ≤ Cm−`nm−`pω(H,F ).

Em particular, se F con ⊂ VH é estável, então |I(H,G, F,X)| ≤ Cm−`nm−`pe(H).

As seguintes duas afirmativas compõem a prova do Lema 3.13. O Lema 3.14 é seme-lhante ao Lema 3.13, com a suposição adicional de que existe uma ordenação DH-degenerada(v1, . . . , vm) de VH tal que F con = v1, . . . , v`. Já o Lema 3.15 confirma que tal ordenaçãoexiste.


Lema 3.14. Sejam G e H hipergrafos k-uniformes, onde H é linear, com |VH | = m, |VG| = n

e p = p(n) = e(G)/(nk

). Suponha que 0 ≤ ` ≤ maxk, dH, e sejam F ∈ VH

` e X ∈ VG`

fixos. Considere uma constante C > 1 e suponha que G ∈ LMTk(C,DH). Se existe umaordenação DH-degenerada v1, . . . , vm de VH tal que F con = v1, . . . , v`, então

|I(H,G, F,X)| ≤ Cm−`nm−`pω(H,F ).

Visão geral da demonstração. Utilizamos indução em h, com ` ≤ h ≤ m, para provarque |I(Hh, G, F,X)| ≤ Cm−`nm−`pω(H,F ), onde Hh = H[v1, . . . , vh], de acordo com umaordenação DH-degenerada v1, . . . , vm. Assim, como dHh

(vh) ≤ DH , podemos usar o fatode G ∈ LMTk(C,DH) para limitar a quantidade de imersões I(Hh, G, F,X) obtidas pelaextensão de imersões em I(Hh−1, G, F,X), que sabemos não ser um conjunto muito grande,por conta da hipótese indutiva.

Demonstração. Considere hipergrafos k-uniformesG eH, onde |VH | = m eH é linear, |VG| =n e p = p(n) = e(G)/

(nk

). Fixe 0 ≤ ` ≤ maxk, dH, F ∈ VH` e X ∈ VG`. Considere uma

constante fixa C > 1 e suponha que G ∈ LMTk(C,DH).Suponha que existe uma ordenação DH-degenerada L = (v1, . . . , vm) de VH tal que

F con = v1, . . . , v`. Vamos provar por indução em h que, para todo ` ≤ h ≤ m, temos

|I(Hh, G, F,X)| ≤ Ch−`nh−`pω(Hh,F ), (3.17)

onde Hh = H[v1, . . . , vh]. Se h = `, o resultado é trivial. Suponha que ` < h ≤ m eque (3.17) é verdade para valores menores de h. Note que dHh

(vh) ≤ DH , dado que L éDH-degenerada. Mas sabendo que G ∈ LMTk(C,DH), qualquer imersão de a Hh−1 pode serestendida para uma imersão de Hh de, no máximo, CnpdHh

(vh) maneiras diferentes. Comoω(Hh, F ) = ω(Hh−1, F ) + dHh

(vh), aplicando a hipótese indutiva, concluímos que

|I(Hh, G, F,X)| ≤ CnpdHh(vh)|I(Hh−1, G, F,X)|

≤ CnpdHh(vh)Ch−1−`nh−1−`pω(Hh−1,F )

= Ch−`nh−`pω(Hh,F ).

Tomando h = m, a prova está terminada.

Seja H um hipergrafo linear k-uniforme com m vértices e considere uma ordenaçãoL = (v1, . . . , vm) dos vértices de H. Dado um conjunto W ⊂ VH , escrevemos L \W paraa ordenação de VH \ W obtida de L após a remoção dos vértices de W . Por exemplo,se W = v1, v3, vm, então L \W = (v2, v4, v5, . . . , vm−1). Dada uma sequência de vérticesY = (vi1 , . . . , vi`) ∈ V `

H , escrevemos a sequência L′ = (vi1vi2 . . . . .vi` .L \Y con) para denotara ordenação L′ de VH obtida quando removemos Y e a colocamos antes dos elementos de L.


Lema 3.15. Seja H um hipergrafo linear k-uniforme tal que existe uma ordenação dH-degenerada dos vértices de H. Suponha que 0 ≤ ` ≤ maxk, dH. Se F ∈ VH`, então existeuma ordenação DH-degenerada (v1, . . . , v|VH |) com F con = v1, . . . , v`.

Demonstração. Por simplicidade, defina d = dH . Se DH = ∆(H), então qualquer ordenaçãodos vértices de H é DH-degenerada. Assim, suponha que DH = kd. Note que o resultado étrivial se F = ∅. Desta forma, assumimos que 1 ≤ |F | = ` ≤ maxk, d.

Seja L uma ordenação dH-degenerada de VH . Tome L′ = (F.L\F con). Dado um vérticex de H, definimos o grau à esquerda de x em L′ como a quantidade de arestas tal que x é oelemento mais à direita da aresta, levando em conta a ordenação L′. Deste modo, note queo grau à esquerda de cada vértice de H em L′ é no máximo |F |+ d, pois L é uma ordenaçãod-degenerada e, pela linearidade de H, tal vértice pode estar presente em no máximo |F |arestas que contêm vértices de F .

Suponha que d > k. Assim, |F | ≤ d e o grau à esquerda de qualquer vértice de H em L′

é no máximo 2d ≤ kd = DH , pois |F | ≤ d. Assim, L′ é uma ordenação DH-degenerada deVH .

Suponha que 2 ≤ d ≤ k. Logo, |F | ≤ k. Portanto, o grau à esquerda de cada vértice de Hem L′ é no máximo k+d ≤ kd = DH , pois k ≥ 2. Assim, L′ é uma ordenação DH-degeneradade VH .

Por fim, seja d = 1. Aqui, temos |F | ≤ k. Note que a única possibilidade de algumvértice x ter grau à esquerda maior que kd = k em L′ é se x pertencer a uma aresta quecontém um vértice f , para cada vértice f ∈ F , onde |F | = k e f é o elemento que está maisà direita na aresta. Mas assim, só pode existir um vértice x com essa característica, dadoque d = 1. Então, considere a ordenação L′′ = (F.x.L \ F con ∪ x). Assim, é claro quetodo vértice de H possui grau à esquerda no máximo 2 = kd = DH .

Prova do Lema de Extensão (Lema 3.13). Sejam G e H hipergrafos k-uniformes onde H élinear, com |V (H)| = m, |V (G)| = n e p = p(n) = e(G)/

(nk

). Suponha 0 ≤ ` ≤ maxk, dH,

e tome F ∈ V (H)` e X ∈ V (G)` fixos. Seja C > 1 uma constante e suponha que G ∈LMTk(C,DH).

É fácil ver que existe uma ordenação dH-degenerada L dos vértices de H. Assim, peloLema 3.15, sabemos que existe uma ordenação DH-degenerada L′ = v1, . . . , vm de V (H)com F con = v1, . . . , v`. Então, podemos aplicar Lema 3.14 para concluir que

|I(H,G, F,X)| ≤ Cm−`nm−`pω(H,F ).

3.3.2 Corolários do Lema de Extensão

Dados hipergrafos k-uniformes G e H, escrevemos Ini(H,G) para o conjunto de imersões nãoinduzidas de I(H,G). Ademais, denotamos por I ind(H,G) o conjunto de imersões induzidas


de I(H,G). O seguinte corolário limita superiormente a cardinalidade de Ini(H,G), quandoH é linear e G possui algumas propriedades.

Corolário 3.16. Para todos C ≥ 1, m ≥ 1, k ≥ 2, η > 0 e p = p(n) = o(1), existe n0 > 0tal que, para todos os hipergrafos k-uniformes G e H, onde |VG| = n e H é linear com|VH | = m, se G ∈ LMTk(C,DH), |E(G)| ≤ nkp e n ≥ n0, então

|Ini(H,G)| < ηnmpe(H).

Visão geral da demonstração do Corolário 3.16. Sabemos que qualquer imersão não induzidamapeia pelo menos uma não-aresta deH em uma aresta de G. Assim, aplicamos o Lema 3.13,pondo F como sendo uma ordenação de uma não-aresta de H, e pondo X como sendouma ordenação de uma aresta de G. Para finalizar a prova, contamos de quantas maneiraspodemos escolher tal não-aresta de H e tal aresta de G.

Demonstração. Fixe C ≥ 1, m ≥ 1, k ≥ 2, η > 0 e tome p = p(n) = o(1). Sejam hipergrafosk-uniformes G e H, onde |VG| = n e H é linear com |VH | = m e seja n0 um inteiro positivo talque se n ≥ n0 então p(n) < η

((k!)2Cm−k

(mk

))−1. Suponha que n ≥ n0 e G ∈ LMTk(C,DH)

com |E(G)| ≤ nkp.Se k > m, o resultado segue trivialmente, dado que neste caso o conjunto de arestas de H

é vazio. Portanto, assumimos k ≤ m. Fixe uma aresta x1, . . . , xk ∈ E(G) e uma não-arestav1, . . . , vk ∈

(VH

k

)de H. Aplicamos o Lema 3.13 pondo F = (v1, . . . , vk) e G = (x1, . . . , xk),

obtendo que o número de imersões f de VH em VG tais que f(vi) = xi para 1 ≤ i ≤ k élimitado por cima por Cm−knm−kpEH . Mas note que existem no máximo nkp escolhas parax1, . . . , xk em E(G) e no máximo

(mk

)escolhas para v1, . . . , vk em

(VH

k

). Assim, podemos

escolher (x1, . . . , xk) e (v1, . . . , vk), respectivamente, de k!nkp e k!(mk

)maneiras. Portanto,

|Ini(H,G)| ≤(k!nkp

)(k!(m

k

))Cm−knm−kpe(H)

=(

(k!)2Cm−k(m

k

)p

)nmpe(H)

< ηnmpe(H),

onde a última desigualdade segue da escolha de n0.

Sejam G e H hipergrafos k-uniformes e considere X ⊂(VH

k−1

). Se f é uma imersão de

H em G, denotamos por fk−1(X) a família de conjuntos f(x1), . . . , f(xk−1), para todox1, . . . , xk−1 ∈ X.

Para 1 ≤ r ≤ k, dado X = X1, . . . , Xr, onde Xi = xi,1, . . . , xi,k−1 ∈(VH

k−1

), para

1 ≤ i ≤ r, definimos Xcon = x1,1, . . . , x1,k−1, . . . , xr,1, . . . , xr,k−1.


Seja Gn um hipergrafo k-uniforme com n vértices. Para r ≥ 1 e δ > 0, defina

B(δ, r) =

X ∈((

VG

k−1

)r

):∣∣∣|NGn(X)| − npr

∣∣∣ ≥ δnpr

,Em outras palavras, B(δ, r) é composto por famílias X com r membros de

(VG

k−1

)tais que

a quantidade de vizinhos comuns dos membros de X não é próxima de npr. Dizemos queX ∈

(( VGk−1)r

)é δ-ruim seX ∈ Best(δ, r), onde Best(δ, r) = X ∈ B(δ, r) : Xcon é estável em Gn.

Seja H um hipergrafo com m vértices e seja (v1, . . . , vm) uma ordenação dH-degeneradade VH . Defina Hi = H[v1, . . . , vi]. Dizemos que uma imersão f : V (Hh−1)→ V (Gn) é δ-limpase o conjunto fk−1(NHh

(vh)) não é δ-ruim. Isto é, fk−1(NHh(vh)) /∈ Best(δ, dHh

(vh)). Sef : V (Hh−1) → V (Gn) não é δ-limpa, dizemos que f é δ-poluída. Denotamos o conjuntodas imersões f ∈ I(Hh−1, Gn) tais que f é δ-poluída por Iδ−pol(Hh−1, Gn). Similarmente,denotamos por Iδ−limpa(Hh−1, Gn) o conjunto das imersões f ∈ I(Hh−1, Gn) tais que f éδ-limpa.

Corolário 3.17. Sejam δ > 0, C > 1 e m ≥ 4 constantes fixas. Considere um hipergrafolinear k-uniforme H livre de conectores com m vértices e seja (v1, . . . , vm) uma ordenaçãodH-degenerada de VH . Suponha que 1 < h ≤ m e defina r = dHh

(vh). Se Gn é (C,DH , dH , δ)-pseudoaleatório, então

|Iδ−pol(Hh−1, Gn)| ≤ δ(r!((k − 1)!)rCh−1−r(k−1)

)nh−1pe(Hh−1),

onde p = e(Gn)/(nk

).

Visão geral da demonstração do Corolário 3.17. Se uma imersão f ∈ I(Hh−1, Gn) é δ-poluída, então fk−1(NHh

(vh)) é δ-ruim. Mas podemos limitar a quantidade de conjuntosδ-ruins utilizando a propriedade CGk

δ (dH). Desta forma, finalizamos a prova utilizando oLema 3.13, não esquecendo que H é linear e livre de conectores, para estimar de quantasmaneiras podemos realizar a imersão da vizinhança de vH em conjuntos δ-ruins de G.

Demonstração. Fixe constantes δ > 0, C > 1 e m ≥ 4. Seja H um hipergrafo lineark-uniforme livre de conectores com m vértices e considere uma ordenação dH-degenerada(v1, . . . , vm) de VH . Considere 1 < h ≤ m e defina r = dHh

(vh). Suponha que Gn ∈ CGkδ (dH)

e Gn ∈ LMTk(C,DH).Sabemos que uma imersão f : V (Hh−1)→ V (Gn) é δ-poluída se fk−1(NHh

(vh)) ∈ Best(δ, r).Fixe uma sequência F = (T1, . . . , Tr) composta de r conjuntos de k − 1 vértices de H talque T1, . . . , Tr = NHh

(vh) e seja Ford = (u1,1, . . . , u1,k−1, u2,1, . . . , u2,k−1, . . . , ur,1 . . . , ur,k−1)uma ordenação de tais vértices tal que Ti = ui,1, . . . , ui,k−1 para todo 1 ≤ i ≤ r. Portanto,

Iδ−pol(Hh−1, Gn) =⋃X

⋃Xord

I(Hh−1, Gn, Ford, Xord) ,


onde a primeira união é sobre todas as famílias X = S1, . . . , Sr ∈ Best(δ, r) de r conjun-tos de k − 1 vértices e a segunda união é sobre todas as possíveis ordenações de Si, para1 ≤ i ≤ r, e toda ordenação de X. Portanto, podemos limitar a quantidade de imersões|Iδ−pol(Hh−1, Gn)| como segue.

|Iδ−pol(Hh−1, Gn)| ≤∑X

∑Xord

|I(Hh−1, Gn, Ford, Xord)|.

Dadas Ford e Xord, como N conHh

(vh) é estável em Hh (isso é verdade, uma vez que Hh ⊂ H élivre de conectores e linear) e Gn ∈ LMTk(C,DH), sabemos, pelo Lema 3.13, que

|I(Hh−1, Gn, Ford, Xord)| ≤ Ch−1−r(k−1)nh−1−r(k−1)pe(Hh−1),

pois |Ford| = r(k − 1). Como r = dHh(vh) ≤ dH , podemos concluir da propriedade CGk

δ (dH)que |Best(δ, r)| ≤ δnr(k−1). Assim, a primeira soma possui no máximo δnr(k−1) termos. Asegunda soma é sobre não mais que r!((k − 1)!)r termos. Portanto,

|Iδ−pol(Hh−1, Gn)| ≤ δ(r!((k − 1)!)rCh−1−r(k−1)

)nh−1pe(Hh−1).

3.4 Provas dos lemas principais

Provamos nesta seção os Lemas 3.6 e 3.7, que são os resultados que compõem a prova doTeorema 3.5 (veja Seção 3.1).

3.4.1 Prova do Lema CG2→t

Visão geral da demonstração do Lema CG2→t (Lema 3.6). Tome t ≥ 2 e fixe 2 ≤ r ≤ t.Queremos aplicar o Lema 3.8 com parâmetros a = npr e N =

(( nk−1)r

), onde colocamos

ai = |N(S1 ∩ . . . ∩ Sr)| para cada i = S1, . . . , Sr ∈(( Gn

k−1)r

). Assim, verificando que as duas

condições do Lema 3.8 são válidas, o resultado está provado, dado que a conclusão do lemaé precisamente o que queremos provar.

Para verificar a condição ∑Ni=1 ai ≥ (1 − γ)Na, notamos que ∑N

i=1 ai = ∑u∈VG

(d(u)r

)e

fazemos uso dos Lemas 3.9 e 3.12. Para provar que ∑Ni=1 ai

2 ≤ (1 + γ)Na2, primeiramenteobservamos que podemos escrever ∑N

i=1 ai2 como ∑u,v∈VG

(|N(u)∩N(v)|

r

). Feito isso, utilizando

os Lemas 3.10, 3.11 e 3.12, conseguimos verificar que a condição é válida.

Prova do Lema 3.6. Fixe t ≥ 2, C > 1 e suponha que p n−1/t. Agora, fixe 2 ≤ r ≤ t eδ > 0. Considere γ > 0 obtido por uma aplicação do Lema 3.8 com parâmetro δ > 0. Faça

α = min1− (1− γ)1/(r+2), (1 + γ/2)1/(r+1) − 1, γ/(6Cr(k − 1)r(k−1)).

3.4 PROVAS DOS LEMAS PRINCIPAIS 25

Considere agora β e n1 obtidos por uma aplicação do Lema 3.12 com parâmetro α. Pelasuposição sobre p, sabemos que existe n2 > 0 tal que p ≥ (α−12Cr(k − 1)r(k−1))−1/rn−1/r

para todo n ≥ n2. Aplicando o Lema 3.9 com parâmetros α, r e (1− α)p, obtemos n3 > 0.Por fim, uma aplicação do Lema 3.10 com α, r e C(k−1)k−1p fornece uma constante n4 > 0.

Assuma n ≥ n0 = minn1, n2, n3, n4. Considere um hipergrafo k-uniforme G = Gn

com n vértices e |E(Gn)| =(nk

)p. Suponha que Gn ∈ LMTk(C, 2) e Gn ∈ CGk

β(2). PeloLema 3.12, temos o seguinte: para mais de (1− α)n vértices u ∈ VG, segue que

∣∣∣∣∣d(u)−(

n

k − 1

)p

∣∣∣∣∣ < α

(n

k − 1

)p. (3.18)

Para mais de (1− α)(n2

)pares de vértices u, v ∈

(VG

2

), segue que

∣∣∣∣∣|N(u) ∩N(v)| −(

n

k − 1

)p2∣∣∣∣∣ < α

(n

k − 1

)p2. (3.19)

Precisamos verificar que as condições do Lema 3.8 são válidas. Para provar que a primeiradas condições é válida, note que

∑Distintos S1,...,Sr∈( VG

k−1)|N(S1) ∩ . . . ∩N(Sr)| =

∑u∈VG

(d(u)r

)

≥∑

u : |N(u)|≥(1−α)( nk−1)p

(d(u)r

)

≥ (1− α)n(

(1− α)p(

nk−1

)r

)

≥ (1− α)r+2((

nk−1

)r

)(npr)

≥ (1− γ)((

nk−1

)r

)(npr),

(3.20)

onde a primeira desigualdade é trivial e a segunda segue de (3.18). A terceira segue daaplicação que fizemos do Lema 3.9, e a última segue da escolha de α.

Resta mostrar que a condição (ii) do Lema 3.8 é válida. Note que


k−1)

∣∣∣∣∣r⋂i=1

N(Si)∣∣∣∣∣2

=∑

u,v∈VG

(|N(u) ∩N(v)|

r

)

= 2∑

u,v∈(VG2 )

(|N(u) ∩N(v)|

r

)+∑u∈VG

(d(u)r

).

(3.21)

Vamos estimar separadamente os dois termos do lado direito na igualdade acima. Pelo


Lema 3.11, ∑u∈VG

(d(u)r

)≤ n

(Cnk−1p

r

).

Nossa aplicação do Lema 3.10 garante que

n

(Cnk−1p

r

)≤ n

(C(k − 1)k−1p

(nk−1

)r

)≤ C ′

((nk−1

)r

)npr,

onde fazemos C ′ = (1 + α)Cr(k − 1)r(k−1). Como p ≥ (C ′/α)1/rn−1/r, podemos concluir queC ′ ≤ αnpr. Portanto, ∑

u∈VG

(d(u)r

)≤ α

((nk−1

)r

)(npr)2. (3.22)

Agora vamos estimar o termo remanescente. Defina

A =u, v ∈

(VG2

): |N(u) ∩N(v)| ≤ (1 + α)

(n

k − 1

)p2.

Defina também

B =u, v ∈

(VG2

): |N(u) ∩N(v)| > (1 + α)

(n

k − 1

)p2.

Note que

∑u,v∈(VG

2 )

(|N(u) ∩N(v)|

r

)=

∑u,v∈A

(|N(u) ∩N(v)|

r

)+

∑u,v∈B

(|N(u) ∩N(v)|

r

). (3.23)

Lema 3.10 aplicado com parâmetros α, r e (1 + α)p2 implica

∑u,v∈A

(|N(u) ∩N(v)|

r

)≤ n2

2

((1 + α)p2

(nk−1

)r

)

≤ (1 + α)r+1

2

((nk−1

)r

)(npr)2.

(3.24)

Por (3.19), Lema 3.10 aplicado com α, r e C(k − 1)k−1p2 e Lema 3.11, temos

∑u,v∈B

(|N(u) ∩N(v)|

r

)≤ α

2n2(C(k − 1)k−1p2

(nk−1

)r

)

≤ α(1 + α)Cr(k − 1)r(k−1)

2

((nk−1

)r

)(npr)2.

(3.25)

Substituindo (3.24) e (3.25) em (3.23), obtemos um limitante que, ao ser substituído junta-


mente com (3.22) em (3.21), implica o seguinte.


k−1)

∣∣∣∣∣r⋂i=1

N(Si)∣∣∣∣∣2

≤(α + (1 + α)r+1 + α(1 + α)Cr(k − 1)r(k−1)

)(( nk−1

)r

)(npr)2

≤ (1 + γ)((

nk−1

)r

)(npr)2,

(3.26)onde a última desigualdade segue da escolha de α.

Equações (3.20) e (3.26) podem ser vistas como as condições (i) e (ii) do Lema 3.8. Assim,concluímos que, para mais de (1− δ)

(( nk−1)r

)conjuntos distintos S1, . . . , Sr ∈

(VG

k−1

), temos

∣∣∣|N(S1) ∩ . . . ∩N(Sr)| − npr∣∣∣ < δnpr.

3.4.2 Prova do Lema de contagem modificado

Visão geral da demonstração do Lema de contagem modificado (Lema 3.7). Utilizamos in-dução em h, com 1 ≤ h ≤ m para provar que

∣∣∣|I(Hh, G)| − nhpe(Hh)∣∣∣ ≤ εnhpe(Hh), onde

Hh = H[v1, . . . , vh] de acordo com uma ordenação dH-degenerada v1, . . . , vm. Fazemosuso dos Corolários 3.16 e 3.17 para garantir que a maioria das imersões de Hh−1 em G sãolimpas e induzidas e, desta forma, podemos focar somente nesse tipo de imersões.

Considere uma imersão limpa e induzida f ′ de Hh−1 em Gn. Como H é linear e livre deconectores, N con

Hh(vh) é estável em Hh. Mas como f ′ é induzida, sabemos que f ′(N con

Hh(vh))

é estável em Gn. Porém, como f ′ é limpa, podemos concluir que |NGn(f ′k−1(NHh(vh))) −

npr| < δnpr. Desta forma, provamos o limite inferior utilizando esses fatos e fazendo algumascontagens. Para o limite superior, precisamos utilizar o fato de Gn ∈ LMTk(C,DH).

Prova do Lema 3.7. Começamos fixando C > 1 e m ≥ 4. Considere um hipergrafo lineark-uniforme H com m vértices e livre de conectores. Assuma que npdH npDH 1.

Sabemos que existe uma ordenação dH-degenerada (v1, . . . , vm) dos vértices de H (é fácilver que tal ordenação existe). Tome Hh = H[v1, . . . , vh] para 1 ≤ h ≤ m.

Nossa prova segue por indução em h, onde consideramos n suficientemente grande. Prova-remos que, para todo 1 ≤ h ≤ m e para todo ε > 0, existe δ > 0 tal que se G é um hipergrafok-uniforme com n vértices e e(Gn) =

(nk

)p, tal que Gn ∈ LMTk(C,DH) e Gn ∈ CGk

δ (dH),então ∣∣∣|I(Hh, Gn)| − nhpe(Hh)

∣∣∣ < εnhpe(Hh). (3.27)

Fixe ε > 0. Se h = 1, então o resultado é trivial. Assim, suponha que 1 < h ≤ m e queo resultado é válido para h′ < h.

Primeiramente, mostraremos que |I(Hh, Gn)| > (1−ε)nhpe(Hh). Tome ε′ = minε/4, ε/6C


e considere δ′ = δ′(ε′) dada pela hipótese indutiva de modo que∣∣∣|I(Hh−1, Gn)| − nh−1pe(Hh−1)

∣∣∣ < ε′nh−1pe(Hh−1). (3.28)

Fixe η = ε′/2 e defina r = dHv(vh) ≤ dH . Uma aplicação do Corolário 3.16 com parâmetrosC, e(Hh−1), k, η e p fornece o seguinte limitante na quantidade de imersões não induzidas.

∣∣∣Ini(Hh−1, Gn)∣∣∣ ≤ ηnh−1pe(Hh−1). (3.29)

Tome δ = minδ′, ε/8, η/(r!((k − 1)!)rCh−1−r(k−1)). Aplicando o Corolário 3.17 com parâ-metros δ, C e m, concluímos que

|Iδ−pol(Hh−1, Gn)| ≤ ηnh−1pe(Hh−1). (3.30)

Utilizando (3.29) e (3.30), obtemos∣∣∣Ini(Hh−1, Gn) ∪ Iδ−pol(Hh−1, Gn)

∣∣∣ ≤ 2ηnh−1pe(Hh−1) = ε′nh−1pe(Hh)−r.

Por (3.28), concluímos que

(1− 2ε′)nh−1pe(Hh)−r <∣∣∣I indδ−limpa(Hh−1, Gn)

∣∣∣ < (1 + ε′)nh−1pe(Hh)−r. (3.31)

O próximo passo é limitar por baixo o número de maneiras que podemos estender umaimersão f ′ ∈ I ind

δ−limpa(Hh−1, Gn) para uma imersão f ∈ I(Hh, Gn). Dada tal imersão f ′,como f ′ é limpa, sabemos que f ′k−1(NHh

(vh)) /∈ Best(δ, r), i.e., ou f ′(N conHh

(vh)) não é estávelem Gn, ou |NGn(f ′k−1(NHh

(vh)))− npr| < δnpr.Lembre que H é linear e livre de conectores. Portanto, N con

Hh(vh) é estável em Hh. Mas

como f ′ é uma imersão induzida, sabemos que f ′(N conHh

(vh)) é estável em Gn. Desta forma,concluímos que

|NGn(f ′k−1(NHh(vh)))− npr| < δnpr. (3.32)

Para obter uma extensão f ∈ I(Hh, Gn) de f ′ ∈ I(Hh−1, Gn) é preciso selecionar f(vh)em NGn(f ′k−1(NHh

(vh)))\f ′(V (Hh−1)). Assim, a quantidade de tais extensões é limitada porbaixo por

∣∣∣NGn(f ′k−1(NHh(vh))) \ f ′(V (Hh−1))

∣∣∣ ≥ (1− δ)npr − (h− 1) ≥ (1− 2δ)npr, (3.33)

onde a primeira desigualdade é devido a (3.32) e a última segue do fato de npr 1. Por (3.31)


e (3.33), temos

|I(Hh, Gn)| ≥ |I indδ−limpa(Hh, Gn)|

≥∣∣∣I indδ−limpa(Hh−1, Gn)

∣∣∣ ∣∣∣NGn(f ′k−1(NHh(vh))) \ f ′(V (Hh−1))

∣∣∣> (1− 2ε′)(1− 2δ)nh−1pe(Hh)−rnpr

≥ (1− ε)nhpe(Hh),

(3.34)

onde a última desigualdade segue da escolha de ε′ e δ.Precisamos mostrar que |I(Hh, Gn)| < (1+ε)nhpe(Hh). Fixe uma imersão f ′ ∈ I(Hh−1, Gn).

Deixe-nos considerar primeiramente o caso f ′ ∈ I indδ−limpa(Hh−1, Gn). Note que a quantidade

de extensões de f ′ para imersões de Hh em Gn é no máximo |NGn(f ′k−1(NHh(vh)))|. Portanto,

por (3.31) e (3.32), a quantidade de imersões de Hh em Gn, onde a imersão de Hh−1 é limpae induzida é no máximo∣∣∣I ind

δ−limpa(Hh−1, Gn)∣∣∣ ∣∣∣NGn(f ′k−1(NHh

(vh)))∣∣∣ ≤ (1 + ε′)nh−1pe(Hh)−r(1 + δ)npr

≤ (1 + ε/2)nhpe(Hh),(3.35)

onde a última desigualdade segue da escolha de ε′ e δ.Suponha agora que f ′ ∈

I(Hh−1, Gn) \ I ind

δ−limpa(Hh−1, Gn). Por (3.28) e (3.31), temos

∣∣∣I(Hh−1, Gn) \ I indδ−limpa(Hh−1, Gn)

∣∣∣ ≤ 3ε′nh−1pe(Hh−r). (3.36)

Mas como r = dHh(vh) ≤ dH ≤ DH e Gn ∈ LMTk(C,DH), sabemos que cada imersão f ′ de

Hh−1 em Gn pode ser estendida a no máximo Cnpr imersões f ∈ I(Hh, Gn). De fato, paraver isso, precisamos somente fazer uso da propriedade LMTk(C,DH) na seguinte família deconjuntos de k − 1 vértices:

f ′(S1), . . . , f ′(S|NHh

(vh)|),

onde S1, S2, . . . , S|NHh(vh)| é a vizinhança de vh em Hh. Esse fato, juntamente com (3.36),

implica que a quantidade de imersões de Hh em Gn, onde as imersões de Hh−1 não sãoδ-limpas ou não são induzidas é no máximo (3ε′C)nhpe(Hh) ≤ (ε/2)nhpe(Hh). Colocando issojuntamente com (3.35), obtemos |I(Hh, Gn)| < (1 + ε)nhpe(Hh), finalizando a prova.


Capítulo 4

Números de Ramsey para grafosbipartidos

Para grafos G1, G2, . . . , Gr, o número de Ramsey R(G1, G2, . . . , Gr) é o menor inteiro posi-tivo n tal que, se as arestas de um grafo completo Kn são particionadas em r classes de coresdistintas, fornecendo r grafos H1, H2, . . . , Hr, então pelo menos um dos grafos Hi (1 ≤ i ≤ r)contém um subgrafo isomorfo a Gi. A existência de tal inteiro positivo segue do clássico Te-orema de Ramsey. O número R(G1, G2, . . . , Gr) é chamado de número de Ramsey de ordemr para os grafos G1, G2, . . . , Gr. Determinar R(G1, G2, . . . , Gr) para grafos gerais se mostrouser um problema difícil (veja, e.g., [28] ou [47]).

Para números de Ramsey de ordem dois, um conhecido teorema de Gerencsér e Gyár-fás [24] afirma que

R(Pn, Pn) =⌊3n− 2

2

⌋,

onde Pn denota o caminho com n ≥ 2 vértices. Em [32], árvores mais gerais foram conside-radas. Para uma árvore T , escrevemos t1 e t2, com t2 ≥ t1, para os tamanhos das classes devértices de T , quando vista como um grafo bipartido. Note que R(T, T ) ≥ 2t1 + t2− 1, dadoque a seguinte coloração das arestas de K2t1+t2−2 não possui cópia monocromática de T .Particione os vértices em duas classes V1 e V2 tais que |V1| = t1− 1 e |V2| = t1 + t2− 1, entãouse a cor ‘vermelha’ para todas as arestas dentro das duas classes e use a cor ‘azul’ paratodas as arestas entre as classes. Ademais, uma coloração semelhante das arestas de K2t2−2

com duas classes, ambas de tamanho t2 − 1, mostra que R(T, T ) ≥ 2t2 − 1, onde aqui a corque colocamos nas arestas que estão dentro das classes com t1 vértices é arbitrária. Assim,

R(T, T ) ≥ max2t1 + t2, 2t2 − 1. (4.1)

Haxell, Łuczak e Tingley [32] provaram que o limitante em (4.1) é assintoticamente corretopara árvores T com ∆(T ) = o(t2). Apresentamos uma versão desse resultado para certosgrafos bipartidos. Dizemos que um grafo H = (W,EH) possui largura de banda no máximob, se existe uma rotulação dos vértices de H com os números 1, . . . , n, de modo que, para

31

32 NÚMEROS DE RAMSEY PARA GRAFOS BIPARTIDOS 4.0

cada aresta ij ∈ EH , temos |i − j| ≤ b. Concentramos nossa atenção na seguinte classe degrafos bipartidos.

Definição 4.1. Um grafo H é chamado de (β,∆)-bigrafo se é bipartido, possui largura debanda no máximo β|VH | e seu grau máximo não é maior que ∆. Ademais, dizemos queH é um (β,∆)-bigrafo balanceado se existe uma 2-coloração própria χ : VH → [2] tal que∣∣∣|χ−1(1)| − |χ−1(2)|

∣∣∣ ≤ β|χ−1(2)|.

Por exemplo, foi provado em [7] que grafos planares suficientemente grandes com graumáximo não maior que ∆ são (β,∆)-bigrafos para qualquer β > 0. O primeiro teorema destecapítulo é um resultado análogo ao resultado em [32], para (β,∆)-bigrafos.

Teorema 4.2 (Teorema 2-Ramsey). Para todo γ > 0 e número natural ∆, existem umaconstante β > 0 e um número natural n0 tais que, para todo (β,∆)-bigrafo H com n ≥ n0

vértices que contém uma 2-coloração própria χ : VH → [2], onde t1 = |χ−1(1)| e t2 = |χ−1(2)|,com t1 ≤ t2, temos

R(H,H) ≤ (1 + γ) max2t1 + t2, 2t2.

Para resultados relacionados com números de Ramsey de grafos com número cromáticoalto e largura de banda sublinear, veja o trabalho de Allen, Brightwell e Skokan [1].

Menos ainda é conhecido sobre números de Ramsey de ordem três. Seja T uma árvore econsidere t1 e t2, com t2 ≥ t1, os tamanhos das classes de vértices de T quando vista como umgrafo bipartido. A seguinte construção dá um limitante inferior para R(T, T, T ). Particioneos vértices de T em quatro classes, uma classe especial V0 com |V0| = t1 e três classes V1, V2

e V3 de tamanho t2 − 1. A cor para as arestas que estão dentro de V0 é arbitrária. Use a cori dentro da classe Vi e a cor i entre as classes Vi e V0 para 1 ≤ i ≤ 3. Finalmente, use a cork ∈ [3] \ i, j para arestas entre as classes Vi e Vj para 1 ≤ i < j ≤ 3. É fácil verificar queessa coloração não gera nenhuma cópia monocromática de T . Assim,

R(T, T, T ) ≥ t1 + 3t2 − 2. (4.2)

Estabelecendo a validade de uma conjectura de Faudree e Schelp [17], foi provado em [29]que essa construção é ótima para caminhos longos, i.e., para n suficientemente grande, temosque

R(Pn, Pn, Pn) =

2n− 1 para n ímpar,2n− 2 para n par.

Assintoticamente, esse resultado foi provado, independentemente, por Figaj e Łuczak [18].Benevides e Skokan [3] provaram que R(Cn, Cn, Cn) = 2n para n par suficientemente grande.O segundo teorema que apresentamos neste capítulo estende assintoticamente esses resulta-dos para (β,∆)-bigrafos.

Teorema 4.3 (Teorema 3-Ramsey). Para todo γ > 0 e todo número natural ∆, existe umaconstante β > 0 e um número natural n0 tal que, para todo (β,∆)-bigrafo balanceado H com

4.1 VISÃO GERAL DA PROVA DO TEOREMA 3-RAMSEY 33

n ≥ n0 vértices, temos queR(H,H,H) ≤ (2 + γ)n.

Em particular, os Teoremas 4.2 e 4.3 fornecem assintoticamente os números de Ramseyde ordem dois e três. Uma grade bi-dimensional Ga,b é o grafo com conjunto de vérticesV = [a]× [b] tal que existe uma aresta entre dois vértices se e somente se eles são iguaisem uma coordenada e consecutivos na outra. Note que qualquer grade Ga,b satisfaz ∆(G) ≤4 e possui largura de banda no máximo

√ab. Logo, Ga,b é um (β, 4)-bigrafo balanceado

para qualquer β > 0 fixo, desde que ab seja suficientemente grande. Consequentemente, osTeoremas 4.2 e 4.3 combinados com (4.1) e (4.2) implicam o seguinte corolário.

Corolário 4.4. Para grades Ga,b, temos

R(Ga,b, Ga,b) = (3/2 + o(1))ab,

R(Ga,b, Ga,b, Ga,b) = (2 + o(1))ab,

onde o(1) tende a 0 quando ab tende a infinito.

Observe que valores similares valem para grafos bipartidos planares com grau limitado epara grades de dimensão maior.

Apresentamos neste capítulo a prova detalhada do Teorema 4.3. Primeiramente, naSeção 4.1, é dada uma visão geral da prova do Teorema 4.3. Na Seção 4.2, fornecemos asferramentas necessárias para provar o Teorema 4.3, que é provado em todos os seus detalhesna Seção 4.3. A prova do Teorema 4.2 é muito similar à prova do Teorema 4.3, de modo queapresentamos somente uma ideia geral de sua prova, na Seção 4.4.

4.1 Visão geral da prova do Teorema 3-Ramsey

Aqui discutimos as principais ideias envolvidas na prova do Teorema 4.3, tentando ao máximoevitar os detalhes técnicos, que são postergados até a Seção 4.3. A prova faz uso do métododa regularidade, que é explicado na Seção 4.2.1. Dividimos a prova em duas partes.

A primeira parte da prova segue o mesmo padrão da prova de Figaj e Łuczak [18] parao caso em que H é um caminho. A saber, aplicamos a versão multicolorida do Lema deRegularidade de Szemerédi [53], obtendo uma partição dos vértices de KN , com as arestascoloridas com 3 cores, onde N = (2 + γ)n, tal que essa partição possui um grafo reduzido Rcorrespondente suficientemente denso. Cada aresta do grafo reduzido R herda uma das coresque aparece mais vezes no par correspondente em KN . Aplicando o Lema 8 de [18], obtemosuma árvore monocromática T no grafo reduzido R que contém um emparelhamento M

cobrindo quase metade dos vértices de R.Voltando nossa atenção novamente ao grafo completo KN e à 3-coloração de suas arestas,

denotamos por GT o subgrafo de KN , cujos vértices estão contidos nas classes representadas


pelos vértices de T , e cujas arestas estão entre pares representados pelas arestas de T epossuem a mesma cor das arestas de T . Assim, GT é um subgrafo monocromático de KN

tal que os pares regulares estão dispostos em uma estrutura que espelha a estrutura deT . Ademais, a densidade de arestas desses pares é pelo menos 1/3. Por fim, localizamossubgrafos super-regulares ‘quase-geradores’ nos pares de GT representados por arestas deM ,e denotamos por GM ⊂ GT o subgrafo formado pela união desses pares. Completamos assima primeira parte da prova.

Para entender a motivação para a segunda parte da prova, tenha em mente que nossoobjetivo é realizar a imersão de H em GT . Note que GM possui vértices suficientes paraacomodar todos os vértices de H. De fato, a maioria dos vértices de H serão mapeadosem GM e iremos precisar utilizar somente algumas partes de GT \ GM , pois precisaremosconectar as várias partes de H imersas em GM . Deixe-nos explicar isso de forma mais precisa,assumindo, por ora, que H é simplesmente um caminho. Seja m um inteiro que é somenteum pouco menor que o tamanho das classes de GT (que assumimos serem todas do mesmotamanho). Aplicando o Lema de Explosão de Komlós, Sárközy e Szemerédi [41], realizamosa imersão dos primeiros m vértices de cada uma das duas classes de cor de H no parsuper-regular, representado pela primeira aresta do emparelhamento M (lembre que H ébalanceado).

Para conseguirmos ‘alcançar’ o próximo par super-regular em GM , onde podemos realizara imersão dos próximos m + m vértices de H, precisamos fazer uso do fato de os vérticesrepresentando esses dois pares serem conectados por um caminho em T . Esse caminho setraduz em uma sequência de pares regulares em GT , de modo que, em cada um deles, fazemosa imersão de uma aresta intermediária de H, ‘caminhando’ assim para o próximo par super-regular em GM . Desta forma, utilizamos somente poucas arestas de pares regulares que estãoem GT \GM , os mantendo regulares por todo o caminho e deixando um pouco de espaço nospares super-regulares de GM , o que nos permite caminhar por eles novamente. Observamosque faremos uso de um corolário do Lema de Explosão, que encapsula toda a ideia descritaacima (veja Lema 4.7).

No parágrafo anterior, consideramos H como sendo um caminho. Portanto, a tarefa paraessa segunda parte da prova é reestruturar o (β,∆)-bigrafo balanceado H de modo que elese comporte de forma semelhante a um caminho na abordagem de imersão descrita acima.Aqui, dois problemas podem ocorrer:

• Problema 1: Suponha, por exemplo, que H é um grafo consistindo de um caminhocom conjunto de vértices [n], contendo algumas arestas adicionais entre os vérticescujos rótulos diferem de no máximo βn e possuem paridade diferente (pois H deveser bipartido). Para tal grafo, ‘realizar as conexões’ como explicado anteriormente éum pouco mais complicado. Suponha, por exemplo, que temos uma cadeia de paresregulares (Vi, Vi+1) em GT para i = 1, . . . , 4 e queremos utilizá-la para ‘caminhar’com H, da classe V1 até a classe V5. Não podemos simplesmente mapear o vértice 1


à classe V1, o vértice 2 à classe V2 e assim por diante, até mapear o vértice 5 à classeV5, pois talvez 2, 5 seja uma aresta de H, mas (V2, V5) não forma um par regular emGT , de modo que não poderíamos aplicar o Lema de Explosão nesse ponto.

Solução: Caminhar mais lentamente: mapeie o vértice 1 à classe V1, então, com osvértices 2, 3, . . . , βn + 1, alterne entre V2 e V3. Os próximos βn vértices continuam opadrão de zigue-zague entre V3 e V4 até o penúltimo vértice, de modo que o últimovértice é mapeado em V5. Por que razão essa é uma boa estratégia? Considere, porexemplo, o último vértice y que foi mapeado em V5. Devido à condição de largurade banda (a vizinhança de todo vértice i está contida em [i − βn, i + βn]), todos ospotenciais vizinhos de y foram mapeados em V3 ou V4, e, devido à condição de paridade,todos eles devem estar em V4. Mas isso é muito bom, pois (V4, V5) é um par regular.

• Problema 2: Por definição, H possui uma 2-coloração de seus vértices que utiliza asduas cores aproximadamente a mesma quantidade de vezes, no total. Porém, isso nãonecessariamente vale localmente. Isto é, dentre os primeiros m + m vértices de H,podem existir muitos vértices com a cor 1 e poucos vértices com a cor 2, o que significaque nossa abordagem para mapeá-los em pares super-regulares com duas classes demesmo tamanho irá falhar.

Solução: Balancear H de modo que as cores fiquem melhor distribuídas. Utilizamosuma ordenação de H com largura de banda no máximo βn e ‘fatiamos’ H em pequenosblocos de tamanho ξn, onde βn ξn m. Então, não é difícil ver que podemos obteruma nova ordenação dos vértices de H mudando a ordem em que os blocos aparecem,de modo que em cada intervalo de blocos que somam m vértices consecutivos, asduas cores são balanceadas, a menos de ξn vértices. Podemos assim mapear os blocoscompostos por esses intervalos em pares super-regulares de GM , o que nos permiteaplicar o Lema de Explosão nos pares super-regulares.

Com certeza, os dois problemas citados podem ocorrer ao mesmo tempo, mas mostrare-mos que é possível combinar as soluções para os dois problemas. Portanto, podemos, simi-larmente ao exemplo de caminhos que fornecemos anteriormente, realizar a imersão de Hem GT , finalizando a prova.

4.2 Resultados auxiliares

O principal objetivo desta seção é apresentar as ferramentas necessárias para a prova do Teo-rema 4.3. Um dos principais resultados utilizados na prova é o Lema de Regularidade de Sze-merédi [53]. Discutimos o Método da Regularidade, na Seção 4.2.1. Nas Seções 4.2.2 e 4.2.3fornecemos alguns resultados que nos permitirão aplicar com sucesso o método da regulari-dade para provar o Teorema 4.3.


4.2.1 Método da Regularidade

Introduzimos aqui as ferramentas necessárias para aplicar com sucesso o Método da Regu-laridade no contexto que precisamos. Mais especificamente, apresentamos uma versão doLema de Regularidade de Szemerédi para 3-colorações de arestas e um corolário do lema decontagem (Lema de Explosão) de Komlós, Sárközy e Szemerédi [41], apropriado para nossospropósitos.

Um grafo bipartido G = (A,B;E) é chamado de ε-regular se, para todo X ⊂ A, Y ⊂ B

com |X| > ε|A| e |Y | > ε|B| temos

|dG(X, Y )− dG(A,B)| < ε.

Ademais, dizemos que um grafo bipartido G = (A,B;E) é (ε, d)-regular se G é ε-regularcom dG(A,B) ≥ d. Ademais, se degG(a) > d|B| para todo a ∈ A, e degG(b) > d|A| paratodo b ∈ B, então dizemos que G é (ε, d)-super-regular .

Dado um grafo G = (V,E), uma partição (Vi)i∈[s] de V é dita (ε, d)-regular (resp. super-regular) em um grafo R com conjunto de vértices contido em [s] se o subgrafo bipartidode G induzido pelo par Vi, Vj é (ε, d)-regular (resp. super-regular) sempre que ij ∈ E(R).Dizemos que R é um grafo (ε, d)-reduzido de (Vi)i∈[s] (ou de G).

A prova do Teorema 4.3 é baseada na seguinte versão do Lema de Regularidade deSzemerédi [53] para 3-colorações de arestas.

Lema 4.5 (Lema de Regularidade). Para todo ε > 0 e todo inteiro k0 > 0 existe um inteiropositivo K0(ε, k0) tal que, para n ≥ K0, o seguinte vale. Para todos os grafos G1, G2 e G3

com V (G1) = V (G2) = V (G3) = V , onde |V | = n, existe uma partição de V em k + 1classes

V = V0 ∪ V1 ∪ V2 ∪ · · · ∪ Vk

tal que

• k0 ≤ k ≤ K0,

• |V1| = |V2| = · · · = |Vk|,

• |V0| < εn,

• pelo menos (1− ε)(k2

)pares Vi, Vj são ε-regulares em G1, G2 e G3.

Para um estudo aprofundado acerca do Lema de Regularidade e suas aplicações, veja [40]e [43]. Um componente chave do método da regularidade é o Lema de Explosão [41] (vejatambém [42, 49, 51] para provas alternativas). Esse lema garante que subgrafos geradoresbipartidos de grau limitado podem ser imersos em pares super-regulares. Na verdade, aafirmação é mais geral, e permite a imersão de grafos r-cromáticos na união de r classes devértices que formam

(r2

)pares super-regulares.


Aqui utilizamos uma versão do Lema de Explosão que nos permite realizar a imersão degrafos H com grau limitado em um grafo G, quando G e H possuem partições ‘compatíveis’,no sentido explicado na Definição 4.6 dada a seguir. Em nossa prova, vamos realizar a imersãode H por partes, considerando uma partição de um subgrafo monocromático G de KN , ondeo grafo reduzido correspondente contém uma árvore T contendo um emparelhamento M

‘grande’, onde os grafos bipartidos de G que correspondem às arestas de M são pares super-regulares.

Definição 4.6. Seja H = (W,EH) um grafo. Considere uma árvore T = ([s], ET ) e umsubgrafo M = ([s], EM) de T , onde EM é um emparelhamento. Dada uma partição (Wi)i∈[s],seja Ui o conjunto de vértices em Wi com vizinhança em algum Wj, onde ij ∈ ET \ EM .Defina U := ⋃

Ui e U ′i := NH(U) ∩ (Wi \ U).Dizemos que (Wi)i∈[s] é (ε, T,M)-compatível com uma partição (Vi)i∈[s] dos vértices de

um grafo G = (V,E) se o seguinte vale.

(i) xy ∈ EH para x ∈ Wi e y ∈ Wj implica que ij ∈ ET . Em outras palavras, o ma-peamento de W para [s] dado pela partição (Wi)i∈[s] é um homomorfismo de H emT ,

(ii) |Wi| ≤ |Vi| para todo i ∈ [s],

(iii) |Ui| ≤ ε|Vi| para todo i ∈ [s],

(iv) |U ′i |, |U ′j| ≤ εmin|Vi|, |Vj| para toda aresta ij ∈ EM .

O seguinte corolário do Lema de Explosão afirma que, seguindo a configuração da Defi-nição 4.6, grafos H com grau limitado podem ser imersos em G, se G admite uma partiçãosuficientemente regular em T e super-regular em M .

Lema 4.7 (Lema de Explosão [5, 6]). Para todo d > 0 e todo ∆ > 0, existe ε = ε(d,∆) > 0tal que o seguinte vale. Seja G = (V,E) um grafo com N vértices que possui uma partição(Vi)i∈[s] de V com um grafo (ε, d)-reduzido T com conjunto de vértices [s] que é (ε, d)-super-regular em um subgrafo M ⊂ T . Ademais, seja H = (W,EH) um grafo com n vértices, comgrau máximo ∆(H) ≤ ∆ e n ≤ N , tal que H possui uma partição (Wi)i∈[s] de seus vérticesque é (ε, T,M)-compatível com (Vi)i∈[s]. Então H ⊂ G.

Encerramos esta seção com dois fatos simples, que seguem das definições de pares regu-lares e super-regulares (para provas, veja, respectivamente, [27] e [45]).

Afirmativa 4.8. Seja B = (V1, V2;E) um grafo bipartido ε-regular e tome V ′1 ⊂ V1 e V ′2 ⊂ V2

com |V ′1 | ≥ α|V1| e |V ′2 | ≥ α|V2| para algum α > ε. Então B′ = (V ′1 , V ′2 ;EB(V ′1 , V ′2)) é umgrafo ε′-regular com ε′ = maxε/α, 2ε tal que |dB(V1, V2)− dB′(V ′1 , V ′2)| < ε.


Afirmativa 4.9. Considere um grafo G = (V,E) com uma partição (ε, d)-regular de seusvértices (Vi)i∈[s] com |Vi| = m para 1 ≤ i ≤ s e seja T a árvore com conjunto de vértices[s] contida no grafo (ε, d)-reduzido correspondente. Seja EM um emparelhamento contido emT . Então, para cada vértice i coberto por EM , o conjunto associado Vi em G contém umsubconjunto V ′i de tamanho (1− εr)m, para qualquer r ≥ 1, tal que, para cada aresta ij deEM , o grafo bipartido G′ = (V ′i , V ′j ;E(G)(V ′i , V ′j )) é (ε/(1− εr), d− (1 + r)ε)-super-regular.

4.2.2 Explosão regular de uma árvore

Nesta seção, mostramos que, para qualquer 3-coloração de E(KN), existe um subgrafo mo-nocromático de KN , denso e regular, que possui algumas propriedades estruturais interes-santes, de modo que será possível realizar a imersão de H nesse subgrafo. Aqui, a noçãode emparelhamento conexo (originada em [46], veja também [18, 29, 30, 31]) tem um papelfundamental. Um emparelhamento conexo em um grafo R é um emparelhamento EM tal queas arestas de EM estão em um mesmo componente conexo de R. Um resultado importanteafirma que, em toda 3-coloração das arestas de um grafo ‘quase completo’, existe um em-parelhamento EM que cobre quase metade dos vértices do grafo, onde EM está contido emuma árvore monocromática.

Lema 4.10 (Figaj–Łuczak [18]). Para todo δ > 0, existem ε0 > 0 e um natural k0 tal que,para todo ε ≤ ε0 e k ≥ k0 e, para toda 3-coloração das arestas de um grafo R com k vérticese densidade pelo menos 1 − ε, existe um emparelhamento EM com pelo menos (1 − δ)k/4arestas em R que está contido em uma árvore monocromática T ⊂ R.

Esse lema pode ser visto em uma forma estrutural mais forte em [29]. De fato, é provadoque, ou existe um emparelhamento conexo monocromático que cobre mais da metade dosvértices, ou o grafo R é próximo a um de dois casos extremais, de modo que, em ambos oscasos extremais, existe um emparelhamento EM de tamanho pelo menos (1 − δ)|V (R)|/4.Iremos também fazer uso da seguinte afirmativa.

Afirmativa 4.11. Se uma árvore T contém um emparelhamento EM com ` arestas, entãoos vértices cobertos pelo emparelhamento podem ser rotulados com x1, y1, . . . , x`, y` de modoque EM =

xiyi : i = 1, . . . , `

e os vértices xi e xj estão a uma distância par em T , para

todo 1 ≤ i < j ≤ `.

De fato, considere uma 2-coloração própria χ : V (T )→ [2]. Rotule com xi as extremidadesque estão em χ−1(1) e rotule com yi as extremidades que estão em χ−1(2). Claramente, adistância em T entre xi e xj é par, pois pertencem a uma mesma classe da bipartição.

Dada uma coloração c : E(KN)→ [3], denotamos por K1N o subgrafo gerador de KN tal

que ij ∈ E(K1N) se e somente se c(ij) = 1.

Lema 4.12. Para todo γ > 0, existe ε0 tal que, para todo ε ≤ ε0, existe um natural K0 talque, para todo n ≥ K0/(2 + γ) e para toda coloração c : E(KN) → [3], onde N = (2 + γ)n,


vale o seguinte: existe uma cor (digamos que seja a cor 1), inteiros `, `′, k com `, `′ ≤ k ≤ K0

e ` ≥ (1− γ/4)k/4, uma árvore T com conjunto de vértices x1, . . . , x`, y1, . . . , y`, z1, . . . , z`′contendo um emparelhamento EM = xiyi : i = 1, . . . , ` com uma distância par entre quais-quer xi e xj, tal que existe uma partição (Vi)0≤i≤k de VK1

Nque é (ε, 1/3)-regular em T , com

|V1| = . . . = |Vk| ≥ (1− ε)N/k.

O Lema 4.12 faz uso do Lema de Regularidade (Lema 4.5) e do Lema 4.10 para en-contrar uma estrutura monocromática no grafo KN que será útil na prova do Teorema 4.3.Na Figura 4.1 é possível visualizar melhor a estrutura do subgrafo monocromático de KN

induzido pelas classes de vértices que representam os vértices da árvore T .

X1 X2

X3

X`

Y1 Y2

Y3

Y`

Z1

Z2 Z3

· · ·

X1 X2

X3

X`

Y1 Y2

Y3

Y`

Z1

Z2 Z3

· · ·

Figura 4.1: Subgrafo monocromático de KN induzido pelas classes de vértices que representamos vértices da árvore T obtida no Lema 4.12. Classes formando pares regulares são conectadas porduas linhas paralelas.

Demonstração do Lema 4.12. Fixe γ > 0 e defina δ = γ/4. Sejam ε0 e k0 as constantesobtidas pelo Lema 4.10 aplicado com δ. Fixe ε ≤ ε0 e seja K0 obtido por uma aplicação doLema de Regularidade (Lema 4.5) com parâmetros ε e k0. Por fim, fixe N = (2 + γ)n ≥ K0.

Considere uma 3-coloração arbitrária c : E(KN) → [3] das arestas de KN e subgrafosgeradores G1, G2 e G3 de KN , onde ij ∈ E(Gs) se e somente se c(ij) = s, para s = 1, 2, 3.Pelo Lema de Regularidade, sabemos que existe uma partição (V0, V1, . . . , Vk) dos vérticesde KN tal que

|Vi| = m ≥ (1− ε)Nk,

para 1 ≤ i ≤ k, e pelo menos (1− ε)(k2

)pares Vi, Vj, para 1 ≤ i < j ≤ k, são ε-regulares

em todos os três grafos G1, G2 e G3, onde k0 ≤ k ≤ K0.Definimos o seguinte grafo reduzido: seja R o grafo com conjunto de vértices [k], onde

ij ∈ E(R) se e somente se Vi, Vj é ε-regular em G1, G2 e G3. Assim, |E(R)| ≥ (1− ε)(k2

).

Portanto, sabemos que R é um grafo com k vértices e densidade pelo menos (1− ε). Agora,defina a coloração c′ : E(R) → [3] das arestas de R de modo que c′(i, j) = s se s ∈ [3] é omaior inteiro tal que |EGs(Vi, Vj)| ≥ |EGr(Vi, Vj)| para 1 ≤ r ≤ 3, i.e., a aresta ij recebe uma


das cores que mais aparece nas arestas de EKN(Vi, Vj) com relação à coloração c de E(KN).

Claramente, se c′(ij) = s, então |EGs(Vi, Vj)| ≥ |Vi||Vj|/3.Como k ≥ k0 e a densidade de R é pelo menos (1 − ε), pelo Lema 4.10, sabemos que

R contém uma árvore monocromática T que contém um emparelhamento EM de tamanho` ≥ (1− δ)k/4. Sem perda de generalidade, supomos que as arestas de T são coloridas coma cor 1. Pela Afirmativa 4.11, podemos rotular EM = xiyi : i = 1, . . . , ` de modo que xi exj estão a uma distância par em T , para 1 ≤ i < j ≤ `.

Sejam z1, . . . , z`′ os vértices de T que não são cobertos por arestas do emparelha-mento EM . Como todas as arestas de T estão presentes em R, sabemos que, para todas asarestas ij ∈ E(T ), os pares Vi, Vj são ε-regulares em G1 com |EG1(Vi, Vj)| ≥ |Vi||Vj|/3.Assim, o lema está provado, uma vez que podemos considerar o grafo G composto pelas clas-ses Vi, para todo i ∈ V (T ), pondo E(G)(Vi, Vj) = EG1(Vi, Vj) para todos os pares (Vi, Vj),onde i, j ∈ V (T ).

4.2.3 Intervalos balanceados

Seja H um grafo que admite uma 2-coloração de seus vértices que utiliza as 2 cores aproxi-madamente a mesma quantidade de vezes, no total. Esse fato pode não ser válido localmente.Nesta seção mostramos como balancear um grafo H de modo que as duas cores sejam utili-zadas, localmente, aproximadamente a mesma quantidade de vezes.

Dado um grafo H = (W,E), com W = w1, . . . , wn e uma 2-coloração χ : W → [2],defina a função Cχ

i (ou Ci) tal que, se W ′ ⊂ W , então Ci(W ′) = |χ−1(i)∩W ′| para i = 1, 2.Isto é, Ci(W ′) é a quantidade de vértices deW ′ que recebem a cor i da coloração χ. Dizemosque χ é uma coloração β-balanceada de W se temos |Cχ

1 (W )− Cχ2 (W )| ≤ βCχ

2 (W ). Umsubconjunto I ⊂ W é chamado de intervalo se existem naturais p e q, com p ≤ q taisque I = wp, wp+1, . . . , wq. Finalmente, sejam `′ e ˆ inteiros positivos com `′ ≤ ˆ e sejaσ : [`′]→ [ˆ] uma função injetora. Considere uma partição deW em um conjunto de intervalosI = I1, . . . , Iˆ. Definimos Ci(I, σ, a) = ∑a

j=1 Ci(Iσ(j)) para i = 1, 2. Se é claro qual é apartição de intervalos estamos considerando, então escrevemos simplesmente Ci(σ, a).

O lema abaixo diz que, dada uma 2-coloração suficientemente balanceada dos vérticesde um grafo H, toda partição de VH em intervalos de aproximadamente o mesmo tamanhopode ser reordenada de modo que, após a ordenação, se excluirmos qualquer quantidade deintervalos no final da ordenação, então, nos vértices restantes, a quantidade de vértices querecebem a cor 1 não difere muito da quantidade de vértices que recebem a cor 2.

Lema 4.13. Para todo inteiro ˆ ≥ 1, existe n0 tal que, se H = (W,E) é um grafo comW = w1, . . . , wn, onde n ≥ n0, então para toda 2-coloração β-balanceada χ de W comβ ≤ 2/ˆ, e toda partição de W em intervalos I1, . . . , Iˆ com |I1| ≤ . . . ≤ |Iˆ| ≤ |I1|+ 1, existeuma permutação σ : [ˆ]→ [ˆ] tal que, para i = 1, . . . , ˆ, temos

|C1(σ, i)− C2(σ, i)| ≤ nˆ + 1.


Demonstração. Fixe ˆ ≥ 1 e tome n0 = 2ˆ3. Seja H = (W,E) um grafo com conjunto devértices W = w1, . . . , wn, onde n ≥ n0. Fixe uma 2-coloração β-balanceada χ de W , ondeβ ≤ 2/ˆ, e uma partição de W em intervalos I1, . . . , Iˆ com |I1| ≤ . . . ≤ |Iˆ| ≤ |I1|+ 1.

Vamos construir uma permutação σ iterativamente. Podemos pegar qualquer inteiro em[ˆ] para ser σ(1), pois o tamanho dos intervalos é no máximo n/ˆ+ 1. Agora, suponha quetenhamos definido σ(1), . . . , σ(i) de modo que |C1(σ, i)−C2(σ, i)| ≤ n/ˆ+ 1, onde i ≤ ˆ− 1.

Se C1(σ, i) = C2(σ, i), então claramente σ(i + 1) pode ser definido como sendo qual-quer dos inteiros remanescentes em [ˆ]. Assim, sem perda de generalidade, assuma queC1(σ, i) = C2(σ, i) + k, onde 1 ≤ k ≤ n/ˆ+ 1. Mas, como C1(σ, i) + C2(σ, i) ≤ i(n/ˆ+ 1),podemos concluir que

C2(σ, i) ≤ in

2ˆ−k − i

2 . (4.3)

Iremos mostrar que existe algum r ∈ [ˆ] \ ⋃ij=1 σ(j) tal que C2(Ir) ≥ k/2. Suponha,por contradição, que C2(Ir) < k/2 para todos os ˆ− i inteiros r ∈ [ˆ] \ ⋃ij=1 σ(j). Esse fato,juntamente com (4.3), implica o seguinte.

C2(W ) < C2(σ, i) + (ˆ− i)k2= in

2ˆ + (ˆ− i− 1)k2 + i

2

≤

ˆ− 1ˆ

n

2 +ˆ2

=1−

1ˆ−

ˆn

n

2 ,

(4.4)

onde a última desigualdade segue de k ≤ n/ˆ+ 1 e i ≤ ˆ− 1. Como C1(W ) + C2(W ) = n,utilizando (4.4), concluímos que

C1(W )C2(W ) = n

C2(W ) − 1

> 1 + 2(n− ˆ2)n(ˆ− 1) + ˆ2

≥ 1 + β,

onde a última desigualdade segue da escolha de n0, dado que β ≤ 2/ˆ. Mas isso contradiz oβ-balanceamento da 2-coloração χ de W . Portanto, sabemos que existe r ∈ [ˆ] \ ⋃ij=1 σ(j)


com C2(Ir) ≥ k/2. Tome σ(i+ 1) = r. Então

C1(σ, i+ 1) = C1(σ, i) + C1(Ir)

≤ (C2(σ, i) + k) +(nˆ + 1− k

2

)

=(C2(σ, i) + k

2

)+ n

ˆ + 1

≤ C2(σ, i+ 1) + nˆ + 1.

Pela desigualdade acima, e notando que, claramente, C1(σ, i+ 1) ≥ C2(σ, i+ 1)− (n/ˆ+ 1),concluímos que |C1(σ, i+ 1)− C2(σ, i+ 1)| ≤ n/ˆ+ 1.

Seja H = (W,E) um grafo com W = w1, . . . , wn e seja χ : W → [2] uma 2-coloraçãode W . Considere uma partição de W definida pelos intervalos I = I1, . . . , Iˆ. DefinimosCi(I, σ, a, b) = ∑b

j=aCi(Iσ(j)) para i = 1, 2. Se é claro qual a partição de intervalos queestamos considerando, então escrevemos somente Ci(σ, a, b).

O seguinte corolário diz que, após a reordenação dos intervalos de vértices de H, aquantidade de vértices com a cor 1 não difere muito da quantidade de vértices com a cor 2em qualquer intervalo formado por intervalos de vértices reordenados.

Corolário 4.14. Para todo inteiro ˆ≥ 1, existe n0 tal que, se H = (W,E) é um grafo comW = w1, . . . , wn, onde n ≥ n0, então para toda 2-coloração β-balanceada χ de W comβ ≤ 2/ˆ, e para toda partição de W em intervalos I1, . . . , Iˆ com |I1| ≤ . . . ≤ |Iˆ| ≤ |I1|+ 1,existe uma permutação σ : [ˆ]→ [ˆ] tal que, para todos os inteiros 1 ≤ a < b ≤ ˆ, temos

|C1(σ, a, b)− C2(σ, a, b)| ≤ 2(nˆ + 1

). (4.5)

Demonstração. Fixe ˆ≥ 1 e seja n0 obtido pelo Lema 4.13 aplicado com ˆ. Seja H = (W,E)o grafo com conjunto de vértices W = w1, . . . , wn, onde n ≥ n0. Fixe uma 2-coloraçãoβ-balanceada χ de W e uma partição de W em intervalos I1, . . . , Iˆ tal que os tamanhos dosintervalos satisfazem |I1| ≤ . . . ≤ |Iˆ| ≤ |I1|+ 1, onde β ≤ 2/ˆ.

Seja σ a permutação dada pelo Lema 4.13. Fixe inteiros 1 ≤ a < b ≤ ˆ e suponha s.p.g.que C1(σ, a, b) ≥ C2(σ, a, b). Portanto, pela conclusão do Lema 4.13, temos

C1(σ, a, b) = C1(σ, b)− C1(σ, a− 1)

≤ (C2(σ, b) + n/ˆ+ 1)− (C2(σ, a− 1)− (n/ˆ+ 1))

= C2(σ, a, b) + 2(n/ˆ+ 1).

O lema seguinte, resultado principal desta seção, afirma que, para toda 2-coloração ba-lanceada χ de VH e para qualquer partição de VH em intervalos, é possível reordenar esses

4.3 PROVA DO TEOREMA 3-RAMSEY 43

intervalos, de modo que χ é balanceada em qualquer intervalo suficientemente grande for-mado pela união dos intervalos de vértices de H. Esse resultado garante o balanceamentolocal que precisamos para aplicar o Lema de Explosão.

Lema 4.15. Para todo ξ > 0 e todo inteiro ˆ≥ 1, existe n0 tal que se H = (W,E) é um grafocom W = w1, . . . , wn, onde n ≥ n0, então para toda 2-coloração β-balanceada χ de W comβ ≤ 2/ˆ, e para toda partição de W em intervalos I1, . . . , Iˆ com |I1| ≤ . . . ≤ |Iˆ| ≤ |I1| + 1existe uma permutação σ : [ˆ] → [ˆ] tal que, para todos os inteiros 1 ≤ a < b ≤ ˆ comb− a ≥ 7/ξ, temos

|C1(σ, a, b)− C2(σ, a, b)| ≤ ξC2(σ, a, b),

Demonstração. Fixe ξ > 0, ˆ ≥ 1 e seja n0 obtido pelo Corolário 4.14 aplicado com ˆ.Seja H = (W,E) um grafo com W = w1, . . . , wn, onde n ≥ maxn0, (4/3)ˆ, e fixeuma 2-coloração β-balanceada χ de W , onde β ≤ 2/ˆ, e uma partição de W em intervalosI1, . . . , Iˆ, com |I1| ≤ . . . ≤ |Iˆ| ≤ |I1|+ 1.

Seja σ a permutação dada pelo Corolário 4.14. Fixe inteiros 1 ≤ a < b ≤ ˆ tais queb− a > 7/ξ. Lembre que a conclusão do Corolário 4.14 implica que

|C1(σ, a, b)− C2(σ, a, b)| ≤ 2(n/ˆ+ 1). (4.6)

A desigualdade acima e o fato de C1(σ, a, b) + C2(σ, a, b) = (b− a)n/ˆ implicam que

C2(σ, a, b) ≥(b− a

2

)nˆ − (n/ˆ+ 1).

Pela escolha de a, b e n0, temos

C2(σ, a, b) ≥ (2/ξ)(n/ˆ+ 1). (4.7)

Combinando as desigualdades (4.6) e (4.7), concluímos a prova.

4.3 Prova do Teorema 3-Ramsey

Antes de detalhar a prova, explicamos rapidamente de que modo conectaremos os resultadosdiscutidos na Seção 4.2. Para uma abordagem mais geral sobre as ideias envolvidas na provado Teorema 3-Ramsey (Teorema 4.3), veja a Seção 4.1.

Para todo γ > 0 e todo n suficientemente grande, dada uma 3-coloração arbitrária dasarestas de KN , para N = (2 + γ)n, provaremos que se H é um (β,∆)-bigrafo balanceadocom n vértices, então KN possui uma cópia monocromática de H.

A estratégia para provar o Teorema 4.3 é aplicar o Lema de Explosão (Lema 4.7) paraencontrar a cópia desejada de H em KN . Para fazer isso, utilizaremos o Lema 4.12 para en-contrar um subgrafo monocromático G de KN composto por pares regulares suficientemente


densos. Assim, utilizando as Afirmativas 4.8 e 4.9, é fácil ver que, removendo poucos vérticesde G, podemos encontrar um subgrafo monocromático G′ ⊂ G que contém uma partiçãoregular contendo pares super-regulares que cobrem (1 + o(1))n vértices.

Por fim, construímos uma partição de VH e fazemos uso do Lema 4.15 para mostrar queessa partição é compatível com a partição regular de G′. Assim, podemos aplicar o Lema deExplosão para encontrar a cópia monocromática de H, concluindo a prova.

Prova do Teorema 3-Ramsey (Teorema 4.3)

Fixe γ > 0 e um natural ∆ ≥ 1. O Lema 4.12, aplicado com γ, fornece ε0. Agora, aplicamoso Lema 4.7 com parâmetros d = 1/4 e ∆, recebendo ε1. Defina

ε = minε0, ε1/2, γ/19.

Como ε ≤ ε0, Lema 4.12 fornece um natural K0. Fixe ξ = γ/304 e seja n0 dado por umaaplicação do Lema 4.15 com parâmetros ξ e K0. Defina

β = εξ(1 + 2ξ)/36∆2K20 .

Seja H = (W,EH) um (β,∆)-bigrafo balanceado com n ≥ maxn0, K0/(2 + γ) vértices.Defina N = b(2 + γ)nc e considere uma coloração arbitrária χKN

: E(KN) → [3]. Nossoobjetivo é mostrar que a coloração χKN

leva a uma cópia monocromática de H.

Particionando os vértices de KN .

Vamos encontrar um subgrafo monocromático G′ de KN suficientemente regular. PeloLema 4.12, sabemos que existe uma cor (digamos que seja a cor 1), inteiros `, `′, k com`, `′ ≤ k ≤ K0 e ` ≥ (1− γ/4)k/4, uma árvore T com conjunto de vértices

V (T ) = x1, . . . , x`, y1, . . . , y`, z1, . . . , z`′,

contendo um emparelhamento EM = xiyi : i = 1, . . . , `, onde a distância entre quaisquerxi e xj em T é par, tal que existe uma partição (Vi)i∈[k] de V = VKN

, onde K1N é (ε, 1/3)-

regular em T e |V1| = . . . = |Vk| = m ≥ (1− ε)N/k. Seja GT o subgrafo de K1N induzido

pelas classes em (Vi)i∈[k] que correspondem aos vértices de T .Para aplicar o Lema de Explosão, precisamos que as classes de GT que correspon-

dem às arestas do emparelhamento EM formem pares super-regulares, e os outros paresde classes sejam suficientemente regulares. Podemos garantir isso deletando alguns poucosvértices de GT . De fato, aplicando a Afirmativa 4.9 e depois aplicando a Afirmativa 4.8,é fácil ver que encontramos um subgrafo G′T ⊂ GT com classes A1, . . . , A`, B1, . . . , B`,

C1, . . . , C`′ de tamanho pelo menos (1 − ε)m, correspondendo, respectivamente, aos vér-


tices x1, . . . , x`, y1, . . . , y`, z1, . . . , z`′ da árvore T , de modo que os grafos bipartidos induzidospor Ai e Bi são (2ε, 1/3−ε)-super-regulares, e os grafos bipartidos induzidos por todos os ou-tros pares são (2ε, 1/3− ε)-regulares. Ademais, seja Dmin o conjunto de menor cardinalidadedentre os conjuntos A1, . . . , A`, B1, . . . , B`, C1, . . . , C`′ . Como ε ≤ γ/19, m ≥ (1 − ε)N/k e` ≥ (1− γ/4)k/4, podemos facilmente verificar que

|Dmin| ≥ (1 + γ/152)n/2`. (4.8)

Particionando os vértices de H.

Agora iremos construir uma partição de W pronta para uma aplicação do Lema 4.7.Como H é um (β,∆)-bigrafo balanceado, sabemos que existe uma coloração χ : VH → [2]tal que

∣∣∣|χ−1(1)| − |χ−1(2)|∣∣∣ ≤ β|χ−1(2)|.

Seja (w1, . . . , wn) uma ordenação de W que respeita a largura de banda, i.e., |i− j| ≤ βn

para toda aresta wiwj ∈ EH . Defina ˆ como o menor inteiro dividindo n tal que ˆ ≥(7K0/ξ) + ` ≥ `(7/ξ + 1). Considere a partição de VH em intervalos I1, . . . , Iˆ, com |I1| =. . . = |Iˆ| = n/ˆ, levando em conta a ordenação (w1, . . . , wn), i.e., Ii = w(i−1)n/ˆ+1, . . . , win/ˆ

para i = 1, . . . , ˆ. Pelo Lema 4.15, como β ≤ 2/ˆ, existe uma permutação σ : [ˆ]→ [ˆ] tal que

|C1(σ, a, b)− C2(σ, a, b)| ≤ ξC2(σ, a, b)

para todos os inteiros 1 ≤ a < b ≤ ˆ com b− a ≥ 7/ξ. Defina ai = (i− 1)ˆ/`+ 1 e bi = iˆ/`,e considere os blocos Ji = Iσ(ai), Iσ(ai+1), . . . , Iσ(bi) para i = 1, . . . , `. Por simplicidade,escrevemos C1(Ji) para C1(σ, ai, bi) e C2(Ji) para C2(σ, ai, bi). Assim, para i = 1, . . . , `,como bi − ai = ˆ/`− 1 ≥ 7/ξ, temos

|C1(Ji)− C2(Ji)| ≤ ξC2(Ji), (4.9)

Lembre que a árvore T possui conjunto de vértices x1, . . . , x`, y1, . . . , y`, z1, . . . , z`′ econtém o emparelhamento M = xiyi : i = 1, . . . , `, onde a distância em T entre quaisquerxi e xj é par. A partição de W será composta por classes X1, . . . , X`, Y1, . . . , Y`, Z1, . . . , Z`′

que correspondem, respectivamente, aos vértices x1, . . . , x`, y1, . . . , y`, z1, . . . , z`′ .para todo i ∈ [`], colocaremos a maioria dos vértices de Ji nas classes Xi e Yi, dependendo

da cor que recebem de χ. Os restantes serão distribuídos de modo a tornar possível ‘caminhar’entre as classes Xi e Yi. Vamos nos referir às classes Xi e Yi como classes emparelhadas.

Dividimos cada intervalo Ii em duas partes. A primeira, chamada de conector de Ii, édenotada por CONi. Os conectores são responsáveis por fazer a conexão entre duas classesemparelhadas. Pomos CONˆ = ∅. Para 1 ≤ i ≤ ˆ− 1, se Ii e Ii+1 estão no mesmo blocoJr, então CONi = ∅. Suponha agora que Ii ∈ Jr e Ii+1 ∈ Js com r 6= s e 1 ≤ i ≤ ˆ− 1.Seja PT (r, s) o caminho em T entre xr e xs, e considere o caminho P ′T (r, s) ⊂ PT (r, s),


obtido a partir da remoção dos vértices do conjunto xr, yr, xs, ys de PT (r, s), i.e., P ′T (r, s)é a parte ‘interna’ do caminho de T que é utilizado para alcançar xs a partir de xr. Porsimplicidade, faça tr,s = |P ′T (r, s)|. Nesse caso, dividimos os (tr,s + 1)βn últimos vérti-ces de Ii em tr,s + 1 ‘pedaços’ de tamanho βn, obedecendo a sequência em que estãono intervalo. O j-ésimo pedaço é denotado por CONi(j) para 1 ≤ j ≤ tr,s + 1. PomosCONi = CONi(1), . . . ,CONi(tr,s),CONi(tr,s + 1)

Agora que já descrevemos os conectores, podemos definir a parte principal dos intervalos.Definimos NUCi = Ii \ CONi como o núcleo do intervalo Ii, que será colocado nas classesemparelhadas Xi e Yi.

Construiremos agora as classes que irão compor a partição de VH . Inicialmente, cadaclasse em X1, . . . , X`, Y1, . . . , Y`, Z1, . . . , Z`′ está vazia. Para cada 1 ≤ i ≤ `, considere obloco Ji. Agora, para cada intervalo Ip ∈ Ji, incluímos em Xi todos os vértices w do núcleoNUCp com χ(w) = 1 e incluímos em Yi todos os vértices w de NUCp com χ(w) = 2.

O próximo passo é acomodar todos os vértices que estão em conectores. Fixe 1 ≤ i ≤ ˆ− 1.Iremos acomodar os conectores de Ii. Assuma que Ii está contido em Jr e que Ii+1 está con-tido em Js com r 6= s, caso contrário, os conectores que estamos considerando são vazios enão há nada a fazer. Seja u1, . . . , utr,s o caminho interno P ′T (r, s) e seja u0 e utr,s+1, respec-tivamente, os vértices de T conectados a u1 e utr,s em PT (r, s). Lembre que a árvore T possuiconjunto de vértices x1, . . . , x`, y1, . . . , y`, z1, . . . , z`′. Sem perda de generalidade, suponhaque u0 = xr. Então, colocamos os vértices w de CONi(1) com χ(w) = 1 em Xr e aquelescom χ(w) = 2 nós colocamos na classe correspondente a u1. Agora, pomos os vértices w deCONi(2) com χ(v) = 2 na classe correspondente a u1 e aqueles com χ(w) = 1 nós coloca-mos na classe correspondente a u2. Continuando o procedimento, ponha os vértices w deCONi(3) com χ(w) = 1 na classe correspondente a u2 e aqueles com χ(w) = 2 nós colocamosna classe correspondente a u3, e assim por diante, até que precisamos cuidar dos vérticesem CONi(tr,s). Suponha, s.p.g., que tr,s é par. Assim, como xr e xs estão à distância par emT , sabemos que wtr,s+1 = ys. Assim, para o último pedaço do conector de Ii, colocamos osvértices w de CONi(tr,s + 1) com χ(w) = 1 na classe correspondente a utr,s e aqueles comχ(w) = 2 colocamos em Ys. Note que não existem arestas dentro das classes, e se existemarestas entre duas classes, então a aresta correspondente está presente em T .

Aplicando o Lema de Explosão.

Seja M o grafo com o mesmo conjunto de vértices de T e com conjunto de arestas EM(Lembre que EM é o emparelhamento obtido por nossa aplicação do Lema 4.12). Iremosmostrar que a partição de VH que construímos é (2ε1, T,M)-compatível com a partição deVG′ que construímos. Assim, podemos aplicar o Lema de Explosão para encontrar a cópiadesejada de H em KN .

Primeiramente, limitamos por cima o tamanho de cada classe na partição de VH dadapelas classes X1, . . . , X`, Y1, . . . , Y`, Z1, . . . , Z`′ . Para todo 1 ≤ i ≤ ` sabemos que C1(Ji) +


C2(Ji) = n/`. Utilizando esse fato e (4.9), podemos facilmente obter que, para todo 1 ≤ i ≤ `,

(1− ξ) n2` ≤ C1(Ji), C2(Ji) ≤ (1 + ξ) n2`. (4.10)

Por construção, todo Xi (Yi) é composto somente por vértices v com χ(v) = 1 (χ(v) = 2).Ademais, esses vértices podem vir dos núcleos dos intervalos de Ji e de no máximo doispedaços de cada conector. Assim,

|Xi|, |Yi| ≤ (1 + ξ) n2` + 2ˆβn

=(1 + ξ + 4`ˆβ

) n2`

≤ |Dmin|,

(4.11)

onde a última desigualdade segue de (4.8) e da escolha de ξ e β.Para as classes Zi com 1 ≤ i ≤ `′, sabemos que essas classes são compostas somente por

vértices em no máximo dois pedaços de cada conector. Logo,

|Zi| ≤ 2ˆβn

= (4ˆ β) n2`≤ ε

∆2 |Dmin|,

(4.12)

onde a última desigualdade segue de (4.8) e da escolha de β.Agora podemos verificar que as partições de VH e VG′ que construímos são compatíveis.

Baseado na Definição 4.6, definimos conjuntos U ′j, para 1 ≤ j ≤ 2` + `′, relacionados àpartição X1, . . . , X`, Y1, . . . , Y`, Z1, . . . , Z`′ de VH . Ponha Wj = Xj se 1 ≤ j ≤ `, definaWj = Yj−` se ` + 1 ≤ j ≤ 2`, e defina Wj = Zj−2` se 2` + 1 ≤ j ≤ 2` + `′. Iremos verificarque as quatro condições da Definição 4.6 são satisfeitas:

(i): Pela construção da partição de VH , se existe uma aresta entre duas classes, então aaresta correspondente está presente em T .

(ii): Por (4.8), sabemos que cada conjunto D em A1, . . . , A`, B1, . . . , B`, C1, . . . , C`′ pos-sui tamanho |D| ≥ |Dmin|. Assim, as desigualdades (4.11) e (4.12) confirmam que acondição (ii) é satisfeita.

(iii): Fixe 1 ≤ j ≤ 2` + `′. Defina Uj como o conjunto de vértices em Wj com vizinhos emalgum Wk com j 6= k e j, k /∈M . Considere os seguintes casos.

(a) 2`+ 1 ≤ j ≤ 2`+ `′: Temos Uj = Zj−2`. Por (4.12), |Uj| ≤ ε|Dmin|/∆.

(b) 1 ≤ j ≤ 2`: Neste caso, Uj é composto somente por vizinhos de vértices emexatamente um conjunto em Z1, . . . , Z`′. Assim, como ∆ é o grau máximode H, por (4.12), concluímos que |Uj| ≤ ε|Dmin|/∆.


Portanto, para todo j = 1, . . . , 2`+ `′, temos

|Uj| ≤ε

∆ |Dmin|, (4.13)

o que confirma que a condição (iii) é satisfeita.

(iv): Defina o conjunto U ′j = NH(U)∩ (Wj \U), onde U = ⋃2`+`′i=1 Ui. Considere os seguintes

casos.

(a) 2` + 1 ≤ j ≤ 2` + `′: Note que U ′j = ∅ se 2` + 1 ≤ j ≤ 2` + `′, pois cada vérticede Zj−2` pertence a Uj. Assim, é óbvio que |U ′j| ≤ ε|Dmin|.

(b) ` + 1 ≤ j ≤ 2`: Aqui, temos U ′j ⊂ Wj = Yj−`. Logo, U ′j é composto somentepor vizinhos de vértices em Uj−` ⊂ Xj−`. Portanto, utilizando (4.13), obtemos|U ′j| ≤ ∆|Uj−`| ≤ ε|Dmin|.

(c) 1 ≤ i ≤ `: Este caso é análogo ao anterior.

Isso mostra que a condição (iv) é satisfeita.

Portanto, provamos que as quatro condições da Definição 4.6 são satisfeitas. Assim, a par-tição X1, . . . , X`, Y1, . . . , Y`, Z1, . . . , Z`′ de VH é (2ε, T,M)-compatível (logo, é (ε1, T,M)-compatível) com a partição A1, . . . , A`, B1, . . . , B`, C1, . . . , C`′ de VG′ . Com isso, usamoso Lema 4.7 para concluir que H ⊂ G′, finalizando a prova, dado que G′ é um subgrafomonocromático de KN .

4.4 Ideia da prova do Teorema 2-Ramsey

Queremos provar que, para todo γ > 0 e inteiro positivo ∆, existe uma constante β > 0tal que, para todo (β,∆)-bigrafo H suficientemente grande com uma 2-coloração própriaχ : VH → [2], onde t1 = |χ−1(1)| e t2 = |χ−1(2)|, com t1 ≤ t2, podemos encontrar umacópia monocromática de H em toda 2-coloração das arestas de KN , onde aqui consideramosN = (1 + γ) max2t1 + t2, 2t2. Seja H um grafo satisfazendo essas condições e suponha que2t1 ≥ t2.

A prova do Teorema 4.2 é semelhante à prova do Teorema 4.3, de modo que, para oTeorema 4.2, também realizamos a imersão de H em partes, considerando uma partiçãode um subgrafo monocromático GT de KN . A partição que precisamos construir deve sercomposta por uma classe especial W e classes X1, Y1, . . . , Xm, Ym correspondendo a umemparelhamento M = xi, yi : i = 1, . . . ,m ‘grande’, de modo que todos os pares Xi, Yisão super-regulares e os pares Xi,W são regulares, para i = 1, . . . ,m.

O problema na preparação do grafo monocromático GT é o fato de H não ser balanceado,como no contexto do Teorema 4.3. Assim, para fazer a imersão de H em GT , precisamos que|Yi|/|Xi| = t2/t1. Felizmente, por um resultado de [32], como t2/t1 ≤ 1/2 no caso que estamos

4.4 IDEIA DA PROVA DO TEOREMA 2-RAMSEY 49

considerando, podemos achar tal partição de VG. Pela Afirmativa 4.9, podemos facilmentetornar os pares correspondentes às arestas do emparelhamento em pares super-regulares.

Agora precisamos preparar o grafo H para a imersão. Consideramos a ordenação dosvértices de H respeitando a condição de largura de banda e dividimos seu conjunto devértices em intervalos. Assim, podemos encontrar uma permutação de tais intervalos demodo que blocos de intervalos ‘cabem’ nos pares super-regulares de GT . Por fim, é possívelmostrar que, utilizando poucos vértices, é possível ‘caminhar’ de um par super-regular aoutro, como feito no Teorema 4.3. Com isso, a prova é finalizada.


Capítulo 5

Considerações finais

O primeiro problema estudado nesta tese é relacionado à imersão em hipergrafos pseudo-aleatórios. Objetivamos determinar a quantidade de cópias de certos hipergrafos fixos emhipergrafos suficientemente pseudoaleatórios. Outro tipo de problema abordado neste traba-lho faz parte da clássica Teoria de Ramsey, onde deseja-se determinar o menor tamanho queum grafo completo pode ter, garantindo a existência de cópias monocromáticas de certosgrafos em uma coloração arbitrária de suas arestas.

Com relação aos problemas de imersão em hipergrafos, provamos um lema de contagemque generaliza um resultado de Kohayakawa, Rödl e Sissokho [37]. Mostramos que, dadoum hipergrafo k-uniforme H, linear e livre de conectores, a quantidade de cópias de Hem um hipergrafo suficientemente pseudoaleatório G é (1 + o(1))n|V (H)|p|E(H)|, desde quep n−1/DH e |E(G)| =

(nk

)p.

Seria interessante investigar algumas aplicações do lema de imersão provado neste traba-lho. Acreditamos que seja possível introduzir um lema de regularidade para hipergrafos que,juntamente com o lema de imersão apresentado, nos permita obter resultados relacionados àimersão de hipergrafos fixos em hipergrafos maiores. Dizemos que um grafo G = (V,E) satis-faz a propriedade Q(η, δ, α) se todo subgrafo G[S] induzido por S ⊂ V com |S| ≥ η|V | é talque (α− δ)

(|S|2

)< |E(G[S])| < (α + δ)

(|S|2

). Talvez seja possível estender, para hipergrafos,

o seguinte resultado provado em [50]:

Teorema 5.1. Para todos k ≥ 1 e α, η > 0, existem δ > 0 e um inteiro n0 > 0 tais quepara todo n ≥ n0 vale o seguinte: se G é um grafo com n vértices que satisfaz a propriedadeQ(η, δ, α), então G contém todos os grafos com k vértices como subgrafos induzidos.

Provamos também dois resultados na área de Teoria de Ramsey. Determinamos as-sintoticamente o número de Ramsey de ordem dois para para grafos bipartidos com lar-gura de banda pequena e grau máximo limitado, e o número de Ramsey de ordem trêspara os mesmos grafos bipartidos, mas com a hipótese adicional de que ambas as classesdo grafo bipartido possuam aproximadamente o mesmo tamanho. Como corolário dessesdois resultados, mostramos que, para grades Ga,b, temos R(Ga,b, Ga,b) = (3/2 + o(1))ab eR(Ga,b, Ga,b, Ga,b) = (2 + o(1))ab, onde o(1) tende a zero quando ab tende a infinito.

51

52 CONSIDERAÇÕES FINAIS

Acreditamos que, através do uso das técnicas utilizadas para determinar os números deRamsey para grafos bipartidos com largura de banda pequena e grau máximo limitado, sejapossível obter resultados similares para outras classes de grafos. Por exemplo, partindo deuma recente extensão do conhecido “Blow-up Lemma” [4], esperamos obter alguns resulta-dos para grafos a-ordenáveis, i.e., grafos tais que seus vértices podem ser ordenados como(v1, . . . , vn) de modo que

∣∣∣N(N(vi, Di), Ei)∣∣∣ ≤ a para todo 1 ≤ i ≤ n, onde Ei = v1, . . . , vi

e Di = vi+1, . . . , vn. Não é difícil ver que todo grafo G com ∆(G) ≤ a é (a2 − a + 1)-ordenável. Por fim, sabe-se também que grafos planares são 10-ordenáveis.

Referências Bibliográficas

[1] P. Allen, G. Brightwell, and J. Skokan, Ramsey-goodness – and otherwise, Combinato-rica, to appear.

[2] J. Balogh, R. Morris, and W. Samotij, Independent sets in hypergraphs, 2011, submitted.

[3] F. S. Benevides and J. Skokan, The 3-colored Ramsey number of even cycles, J. Combin.Theory Ser. B 99 (2009), no. 4, 690–708.

[4] J. Böttcher, Y. Kohayakawa, A. Taraz, and A. Würfl, An extension of the blow-uplemma to arrangeable graphs, ArXiv e-prints (2013).

[5] J. Böttcher, Embedding large graphs – the Bollobás–Komlós conjecture and beyond,Ph.D. thesis, Technische Universität München, 2009.

[6] J. Böttcher, P. Heinig, and A. Taraz, Embedding into bipartite graphs, SIAM J. DiscreteMath. 24 (2010), no. 4, 1215–1233.

[7] J. Böttcher, K. P. Pruessmann, A. Taraz, and A. Würfl, Bandwidth, expansion, tre-ewidth, separators and universality for bounded-degree graphs, European J. Combin. 31(2010), no. 5, 1217–1227.

[8] F. Chung and R. Graham, Sparse quasi-random graphs, Combinatorica 22 (2002), no. 2,217–244, Special issue: Paul Erdős and his mathematics.

[9] , Quasi-random graphs with given degree sequences, Random Structures Algo-rithms 32 (2008), no. 1, 1–19.

[10] F. Chung, R. Graham, and R. Wilson, Quasirandom graphs, Proc. Nat. Acad. Sci.U.S.A. 85 (1988), no. 4, 969–970.

[11] D. Conlon, The ramsey number of dense graphs, ArXiv e-prints (2009).

[12] D. Conlon, J. Fox, C. Lee, and B. Sudakov, Ramsey numbers of cubes versus cliques,ArXiv e-prints (2012).

[13] D. Conlon, J. Fox, and Y. Zhao, Extremal results in sparse pseudorandom graphs, ArXive-prints (2012).

[14] , A relative Szemerédi theorem, ArXiv e-prints (2013).

[15] D. Conlon, T. Gowers, W. Samotij, and M. Schacht, On the KŁR conjecture in randomgraphs, Submitted.

[16] D. Conlon, J. Fox, and B. Sudakov, On two problems in graph Ramsey theory, Combi-natorica 32 (2012), no. 5, 513–535.

53

54 REFERÊNCIAS BIBLIOGRÁFICAS

[17] R. J. Faudree and R. H. Schelp, Path Ramsey numbers in multicolorings, J. Combina-torial Theory Ser. B 19 (1975), no. 2, 150–160.

[18] A. Figaj and T. Łuczak, The Ramsey number for a triple of long even cycles, J. Combin.Theory Ser. B 97 (2007), no. 4, 584–596.

[19] G. Fiz Pontiveros, S. Griffiths, and R. Morris, The triangle-free process and R(3,k),ArXiv e-prints (2013).

[20] G. Fiz Pontiveros, S. Griffiths, R. Morris, D. Saxton, and J. Skokan, The Ramseynumber of the clique and the hypercube, ArXiv e-prints (2013).

[21] A. Frieze and M. Krivelevich, Packing Hamilton cycles in random and pseudo-randomhypergraphs, Random Structures Algorithms 41 (2012), no. 1, 1–22.

[22] A. Frieze, M. Krivelevich, and P.-S. Loh, Packing tight Hamilton cycles in 3-uniformhypergraphs, Random Structures Algorithms 40 (2012), no. 3, 269–300.

[23] Z. Füredi, Random Ramsey graphs for the four-cycle, Discrete Math. 126 (1994), no. 1-3, 407–410.

[24] L. Gerencsér and A. Gyárfás, On Ramsey-type problems, Ann. Univ. Sci. Budapest.Eötvös Sect. Math. 10 (1967), 167–170.

[25] S. Gerke, H. J. Prömel, T. Schickinger, A. Steger, and A. Taraz, K4-free subgraphs ofrandom graphs revisited, Combinatorica 27 (2007), no. 3, 329–365.

[26] S. Gerke, T. Schickinger, and A. Steger, K5-free subgraphs of random graphs, RandomStructures Algorithms 24 (2004), no. 2, 194–232.

[27] S. Gerke and A. Steger, The sparse regularity lemma and its applications, Surveys incombinatorics 2005, London Math. Soc. Lecture Note Ser., vol. 327, Cambridge Univ.Press, Cambridge, 2005, pp. 227–258.

[28] R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey theory, second ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons Inc.,New York, 1990, A Wiley-Interscience Publication.

[29] A. Gyárfás, M. Ruszinkó, G. N. Sárközy, and E. Szemerédi, Three-color Ramsey numbersfor paths, Combinatorica 27 (2007), no. 1, 35–69.

[30] , Tripartite Ramsey numbers for paths, J. Graph Theory 55 (2007), no. 2, 164–174.

[31] P. E. Haxell, T. Łuczak, Y. Peng, V. Rödl, A. Ruciński, M. Simonovits, and J. Skokan,The Ramsey number of hypergraph cycles. I, J. Combin. Theory Ser. A 113 (2006),no. 1, 67–83.

[32] P. E. Haxell, T. Łuczak, and P. W. Tingley, Ramsey numbers for trees of small maximumdegree, Combinatorica 22 (2002), no. 2, 287–320, Special issue: Paul Erdős and hismathematics.

[33] Y. Kohayakawa, Szemerédi’s regularity lemma for sparse graphs, Foundations of com-putational mathematics (Rio de Janeiro, 1997), Springer, Berlin, 1997, pp. 216–230.

REFERÊNCIAS BIBLIOGRÁFICAS 55

[34] Y. Kohayakawa and B. Kreuter, Threshold functions for asymmetric Ramsey propertiesinvolving cycles, Random Structures Algorithms 11 (1997), no. 3, 245–276.

[35] Y. Kohayakawa, T. Łuczak, and V. Rödl, On K4-free subgraphs of random graphs,Combinatorica 17 (1997), no. 2, 173–213.

[36] Y. Kohayakawa and V. Rödl, Szemerédi’s regularity lemma and quasi-randomness, Re-cent advances in algorithms and combinatorics, CMS Books Math./Ouvrages Math.SMC, vol. 11, Springer, New York, 2003, pp. 289–351.

[37] Y. Kohayakawa, V. Rödl, and P. Sissokho, Embedding graphs with bounded degree insparse pseudorandom graphs, Israel J. Math. 139 (2004), 93–137.

[38] Y. Kohayakawa, T. Łuczak, and V. Rödl, Arithmetic progressions of length three insubsets of a random set, Acta Arith. 75 (1996), no. 2, 133–163.

[39] Y. Kohayakawa, V. Rödl, M. Schacht, and J. Skokan, On the triangle removal lemmafor subgraphs of sparse pseudorandom graphs, An irregular mind, Bolyai Soc. Math.Stud., vol. 21, János Bolyai Math. Soc., Budapest, 2010, pp. 359–404.

[40] J. Komlós and M. Simonovits, Szemerédi’s regularity lemma and its applications ingraph theory, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), Bolyai Soc.Math. Stud., vol. 2, János Bolyai Math. Soc., Budapest, 1996, pp. 295–352.

[41] J. Komlós, G. N. Sárközy, and E. Szemerédi, Blow-up lemma, Combinatorica 17 (1997),no. 1, 109–123.

[42] J. Komlós, G. N. Sárközy, and E. Szemerédi, An algorithmic version of the blow-uplemma, Random Structures Algorithms 12 (1998), no. 3, 297–312.

[43] J. Komlós, A. Shokoufandeh, M. Simonovits, and E. Szemerédi, The regularity lemmaand its applications in graph theory, Theoretical aspects of computer science (Tehran,2000), Lecture Notes in Comput. Sci., vol. 2292, Springer, Berlin, 2002, pp. 84–112.

[44] M. Krivelevich and B. Sudakov, Pseudo-random graphs, More sets, graphs and numbers,Bolyai Soc. Math. Stud., vol. 15, Springer, Berlin, 2006, pp. 199–262.

[45] D. Kühn, D. Osthus, and A. Taraz, Large planar subgraphs in dense graphs, J. Combin.Theory Ser. B 95 (2005), no. 2, 263–282.

[46] T. Łuczak, R(Cn, Cn, Cn) ≤ (4 + o(1))n, J. Combin. Theory Ser. B 75 (1999), no. 2,174–187.

[47] S. P. Radziszowski, Small Ramsey numbers, Electron. J. Combin. 1 (1994 (Lastestupdate: 2011)), Dynamic Survey 1, 84 pp. (electronic).

[48] F. P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. 30 (1930), 264–286.

[49] V. Rödl, A. Ruciński, and A. Taraz, Hypergraph packing and graph embedding, Combin.Probab. Comput. 8 (1999), no. 4, 363–376, Random graphs and combinatorial structures(Oberwolfach, 1997).

[50] V. Rödl, On universality of graphs with uniformly distributed edges, Discrete Math. 59(1986), no. 1-2, 125–134.

56 REFERÊNCIAS BIBLIOGRÁFICAS

[51] V. Rödl and A. Ruciński, Perfect matchings in ε-regular graphs and the blow-up lemma,Combinatorica 19 (1999), no. 3, 437–452.

[52] D. Saxton and A. Thomason, Hypergraph containers, 2013, submitted.

[53] E. Szemerédi, Regular partitions of graphs, Problèmes combinatoires et théorie desgraphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Colloq. Internat. CNRS,vol. 260, CNRS, Paris, 1978, pp. 399–401.

[54] A. Thomason, Pseudorandom graphs, Random graphs ’85 (Poznań, 1985), North-Holland Math. Stud., vol. 144, North-Holland, Amsterdam, 1987, pp. 307–331.

Documents

Dois resultados em combinatória contemporânea Guilherme