Números de Ramsey Induzidos e Semi-induzidos

Marcio Grossi de Almeida

DISSERTAÇÃO APRESENTADA

AO

INSTITUTO DE MATEMÁTICA E ESTATÍSTICA

DA

UNIVERSIDADE DE SÃO PAULO

PARA OBTENÇÃO DO GRAU DE MESTRE

EM

CIÊNCIA DA COMPUTAÇÃO

Orientador: Prof. Dr. Yoshiharu Kohayakawa

Durante a elaboração deste trabalho, o autor recebeu apoio financeiro do CNPq.

- São Paulo, Junho de 2000 -

Números de Ramsey Induzidos e Semi-induzidos

Este exemplar corresponde à redação final da dissertação devidamente corrigida e defendida por Marcio Grossi de Almeida e aprovada pela comissão julgadora.

São Paulo, 16 de Junho de 2000.

Banca examinadora:

Membros Titulares

Prof. Dr. Yoshiharu Kahayakawa (Presidente)  IME-USP
Prof. Dr. Paulo Feofiloff  IME-USP
Prof. Dr. Carlos Gustavo Tamm de Araujo Moreira  IMPA

Membros Suplentes

Prof. Dr. Piotr Koszmider  IME-USP
Prof. Dr. Nicolau Corção Saldanha  IMPA

Agradecimentos

Aos meus pais e familiares, pelo apoio incondicional durante os meus estudos,

Aos professores Paulo Feofiloff e Carlos Gustavo Tamm de Araujo Moreira, pela leitura cuidadosa deste texto e pelas valiosas críticas e sugestões,

Ao professor Yoshiharu Kahayakawa, pelas grandes idéias, pela paciência e pela amizade que tanto contribuíram para a realização deste trabalho,

meu sincero agradecimento.

Marcio Grossi de Almeida

Resumo

Dados dois grafos G e H quaisquer, chamamos de número de Ramsey semi-induzido r_{sind}(G, H) e de número de Ramsey semi-induzido para arestas r̂_{sind}(G, H), respectivamente, a menor ordem e o menor número de arestas possíveis para um grafo Γ com a propriedade de que sempre que suas arestas são coloridas com as cores vermelha e azul, ou Γ possui uma cópia vermelha de G ou Γ possui uma cópia azul induzida de H. Para o caso em que T é uma árvore e H é um grafo qualquer, nós mostramos que r_{sind}(T, H) ≤ (t − 1)h^{2} e r̂_{sind}(T, H) ≤ [(t − 1)h]^{2}|E(H)|, se h = |V (H)| ≥ 2 e t = |V (T)| ≥ 2. No caso em que T possui grau máximo limitado, nós mostramos que, para todo ε > 0, se h = |V (H)| ≥ h_{0}(ε), t = |V (T)| ≥ t_{0}(ε) e d = Δ(T) então r̂_{sind}(T, H) < cd^{9/2}(h^{2}t^{3/2})^{1+ε}|E(H)|, onde c é uma constante que depende somente de ε.

Nós também investigamos o número de Ramsey induzido r_{ind}(G, H), que é definido como sendo a menor ordem possível para um grafo Γ com a propriedade de que sempre que suas arestas são coloridas com as cores vermelha e azul, ou Γ possui uma cópia vermelha induzida de G ou Γ possui uma cópia azul induzida de H. Nós mostramos que se o grafo G pertence à classe EH^{var}({K^{1}, K^{2}, I^{2}}) — que equivale à classe dos grafos simples definida em Erdős e Hajnal [5] — então r_{ind}(G, H) < |V (H)|^{f}, onde f é uma constante que depende somente de G.

Abstract

For any given graphs G and H, we define the semi-induced Ramsey number r_{sind}(G, H) and the edge semi-induced Ramsey number r̂_{sind}(G, H) as the smallest order and the smallest number of edges of a graph Γ having the property that, whenever its edges are coloured red and blue, either a red copy of G arises or else a blue induced copy of H arises. When T is a tree and H is a graph, we show that r_{sind}(T, H) ≤ (t − 1)h^{2} and r̂_{sind}(T, H) ≤ [(t − 1)h]^{2}|E(H)|, where h = |V (H)| ≥ 2 and t = |V (T)| ≥ 2. When T has bounded maximum degree, we show that, for any ε > 0, if we have h = |V (H)| ≥ h_{0}(ε), t = |V (T)| ≥ t_{0}(ε) and d = Δ(T) then r̂_{sind}(T, H) < cd^{9/2}(h^{2}t^{3/2})^{1+ε}|E(H)|, where c is a constant that only depends on ε.

We also investigate the induced Ramsey number r_{ind}(G, H), which is defined as the smallest order of a graph Γ having the property that, whenever its edges are coloured red and blue, either a red induced copy of G arises or else a blue induced copy of H arises. We show that if G belongs to a class of graphs called EH^{var}({K^{1}, K^{2}, I^{2}}) — which is the Erdős and Hajnal [5] class of simple graphs — then r_{ind}(G, H) < |V (H)|^{f}, where f is a constant that only depends on G.

Sumário

Introdução 7 1. Teoria de Ramsey: algumas definições e notações 7 2. Alguns resultados na teoria de Ramsey 9

Capítulo 1. Os Resultados para o Caso Semi-Induzido 13 1. Introdução 13 2. A prova do Teorema 7 13 3. A prova do Teorema 8 16

Capítulo 2. O Resultado para o Caso Induzido 23 1. Introdução 23 2. A construção do grafo aleatório R 23 3. A Propriedade P 24 4. A Propriedade R 26 5. A prova do Teorema 15 35

Apêndice A. Planos Projetivos Finitos 37

Apêndice B. Um Limitante para Grandes Desvios 43

Apêndice C. Grafos Expansores e Árvores Pequenas 45

Apêndice D. Algumas Relações entre EH e EH^{var} 49 1. Introdução 49 2. A prova do Teorema 38 49 3. A prova do Teorema 39 51 4. A prova do Teorema 40 52 5. A prova do Teorema 41 55

Apêndice. Índice Remissivo 57

Apêndice. Referências Bibliográficas 59

Introdução

1. Teoria de Ramsey: algumas definições e notações

Nesta seção, apresentamos algumas definições e notações utilizadas neste texto. Todos os grafos mencionados neste texto não possuem loops e são não-orientados. A notação básica adotada, extraída em quase toda sua totalidade de Diestel [4], é dada a seguir.

Denotamos por ℕ o conjunto de números naturais incluindo o número ℕ zero e pomos ℕ^{∗} = ℕ\{0}. Dado um conjunto X qualquer, denotamos por ℕ^{∗} |X| a sua cardinalidade. Dado um número real x qualquer, denotamos por |X| ⌊x⌋ o maior inteiro menor ou igual a x e por ⌈x⌉ o menor inteiro maior ou ⌊x⌋, ⌈x⌉ igual a x. Um conjunto A = {A_{1}, …, A_{k}} de subconjuntos disjuntos de um conjunto A é uma partição de A se A = ⋃_{i=1}^{k} A_{i}. Se A = {A_{1}, …, A_{k}} é uma partição partição de A e A_{i} ≠ ∅ para todo 1 ≤ i ≤ k dizemos que A é uma partição partição própria própria de A. Dado um conjunto A definimos [A]_{i}^{j} := {S ⊆ A: i ≤ |S| ≤ j} [A]_{i}^{j} e escrevemos [A]^{k} no lugar de [A]_{k}^{k}. [A]^{k}

Chamamos de grafo um par G = (V, E) de conjuntos satisfazendo E ⊆ grafo [V]^{2}; observe que estamos assumindo que os elementos de E são subconjuntos de V com cardinalidade igual a 2. Os elementos de V são chamados de vérti- vértices ces do grafo G e os elementos de E são chamados de arestas do grafo G. arestas Definimos como \overline{G} := (V, [V]^{2}\E) o grafo complementar de G.

\overline{G}

Se H é um grafo, V (H) denota o seu conjunto de vértices (escrevemos V (H), v(H) v(H) no lugar de |V (G)|), E(H) denota o seu conjunto de arestas (escre- E(H), e(H) vemos e(H) no lugar de |E(H)|). Chamamos também v(H) de ordem do ordem grafo H.

Dizemos que M ⊆ E(H) é um emparelhamento em H se as arestas em emparelhamento M são duas a duas disjuntas; denotamos por ν(H) a cardinalidade de um ν(H) emparelhamento de tamanho máximo em H.

Se v ∈ V (H), dizemos que um vértice v′ ∈ V (H)\{v} é adjacente a adjacente, vizinho (ou vizinho de) v em H se {v, v′} ∈ E(H); denotamos Γ_{H}(v) = {v′ ∈ Γ_{H}(v) V (H): v′ é vizinho de v em H} como a vizinhança de v no grafo H e pomos vizinhança, d_{H}(v) d_{H}(v) = |Γ_{H}(v)|. Chamamos d_{H}(v) de grau de v no grafo H. Se X ⊆ grau, Γ_{H}(X) V (H), pomos Γ_{H}(X) = ⋃_{v∈X} Γ_{H}(v). Denotamos o grau mínimo de H grau mínimo de H, δ(H) por δ(H) = min{d_{H}(v): v ∈ V (H)} e o grau máximo de H por Δ(H) grau máximo de H, Δ(H) = max{d_{H}(v): v ∈ V (H)}.

Se G e H são grafos tais que V (G) ⊆ V (H) e E(G) ⊆ E(H), dizemos que G é um subgrafo de H e escrevemos G ⊆ H. Se G é um subgrafo de H tal subgrafo, G ⊆ H subgrafo induzido que E(G) = {e ∈ E(H): e ⊆ V (G)}, dizemos que G é um subgrafo induzido H[X] de H. Dado X ⊆ V (H), definimos H[X], o grafo gerado pelo conjunto de

vértices X em H, como sendo o grafo dado por (X, {e ∈ E(H): e ⊆ X}). Se G e H são grafos tais que existe uma função f: V (G) ↦ V (H) bijetora que satisfaz {v_{1}, v_{2}} ∈ E(G) se e somente se {f(v_{1}), f(v_{2})} ∈ E(H) para

grafos isomorfos todo {v_{1}, v_{2}} ∈ [V (G)]^{2} então dizemos que o grafo G é isomorfo ao grafo H isomorfismo e que f é um isomorfismo entre G e H. K^{n} Denotamos por K^{n} o grafo completo — i.e. com todas as arestas pos-I^{n} síveis — com n vértices e por I^{n} o grafo com n vértices e sem nenhuma ares-

ta. Se P é um grafo da forma P = ({v_{1}, …, v_{k}}, {{v_{1}, v_{2}}, …, {v_{k−1}, v_{k}}},

caminho, P^{k} dizemos que P é um caminho e denotaremos P por P^{k}, onde k = v(P). Em caminho entre v_{1} e v_{k} particular, se P ⊆ G, dizemos que P é um caminho entre v_{1} e v_{k} em G. Se

em G

G é um grafo tal que para quaisquer dois vértices v, v′ ∈ V (G) existe um

grafo conexo caminho entre v e v′ em G, então dizemos que G é um grafo conexo. Se T

é um grafo tal que para quaisquer dois vértices v, v′ ∈ V (T) existe um e

árvore somente um caminho entre v e v′ em T, então dizemos que T é uma árvore.

Se T é uma árvore e v ∈ V (T) é tal que d_{T} (v) = 1, dizemos que o vértice v

folha é uma folha de T.

Apresentamos abaixo as definições e notações que são específicas da teoria de Ramsey.

Γ ⟶ (G, H) Dados três grafos Γ, G e H, escrevemos Γ ⟶ (G, H) se, em qualquer coloração das arestas de Γ com as cores vermelha e azul, podemos encontrar um subgrafo vermelho de Γ isomorfo a G ou um subgrafo azul de Γ isomorfo

Γ ⟶^{ind} (G, H) a H. De forma análoga, definimos Γ ⟶^{ind} (G, H), com a diferença que, neste caso, exigimos que os subgrafos de Γ isomorfos a H ou a G na definição acima sejam induzidos em Γ.

Parte de nossa pesquisa está focada em uma relação “intermediária” às

Γ ⟶^{s,i} (G, H) duas descritas acima. Assim como Γ ⟶^{ind} (G, H), temos que Γ ⟶^{s,i} (G, H) difere da relação Γ ⟶ (G, H) somente pelo fato de que é exigido que apenas o subgrafo de Γ isomorfo a H seja induzido em Γ. A notação “s, i” denota que exigimos G como subgrafo de Γ e H como subgrafo induzido de Γ. Observe que é fácil verificar que

(1)  Γ ⟶^{ind} (G, H) ⟹ Γ ⟶^{s,i} (G, H) ⟹ Γ ⟶ (G, H).

Um teorema clássico de Ramsey [15] mostra que, para qualquer par de grafos (G, H), existe um grafo Γ tal que Γ ⟶ (G, H). Desta forma, da-

r(G, H) do um par de grafos (G, H), chamaremos de número de Ramsey r(G, H) a menor ordem possível para um grafo Γ tal que Γ ⟶ (G, H). Mais formalmente, temos r(G, H) = min{|V (Γ)|: Γ ⟶ (G, H)}. No caso “diagonal”,

r(H), r(n) escrevemos r(H) no lugar de r(H, H). Também costumamos escrever r(n)

no lugar de r(K^{n}). Da mesma forma, definimos o número de Ramsey pa-

r̂(G, H) ra arestas como r̂(G, H) = min{|E(Γ)|: Γ ⟶ (G, H)}. Pomos, também,

r̂(H), r̂(n)  r̂(H) = r̂(H, H) e r̂(n) = r̂(K^{n}).

Um outro resultado clássico descoberto independentemente por Deuber [3], Erdős, Hajnal e Pósa [6] e Rödl [16] garante que, para qualquer par de grafos (G, H), existe um grafo Γ tal que Γ ⟶^{ind} (G, H). Assim, dado um par de grafos (G, H), temos que a noção de número de Ramsey r(G, H) pode ser estendida para o número de Ramsey induzido r_{ind}(G, H), trocando-se a r_{ind}(G, H) relação ⟶ por ⟶^{ind}. Devido a (1), podemos também estender esta noção para o número de Ramsey semi-induzido r_{sind}(G, H), trocando a relação ⟶ r_{sind}(G, H) por ⟶^{s,i}. Analogamente, estendemos a noção de r̂(G, H) para r̂_{ind}(G, H) e r̂_{ind}(G, H) r̂_{sind}(G, H). r̂_{sind}(G, H)

Para finalizar esta seção, observamos que, para quaisquer grafos G e H, as desigualdades

r(G, H) ≤ r_{sind}(G, H) ≤ r_{ind}(G, H)
(2)  e
r̂(G, H) ≤ r̂_{sind}(G, H) ≤ r̂_{ind}(G, H).

decorrem imediatamente de (1) e das definições acima.

2. Alguns resultados na teoria de Ramsey

Esta seção traz alguns resultados na teoria de Ramsey que são relevantes para os focos de estudo desta dissertação.

2.1. Números de Ramsey para vértices e arestas. Como visto na seção anterior, Ramsey em [15] provou um resultado que garante a existência de r(n) para todo n inteiro positivo. Este resultado não só garante a existência de r(n), como também fornece um limitante superior, a saber, r(n) ≤ 2^{\binom{n}{2}}. Em 1947 Erdős provou um resultado que mostra que r(n) é limitado inferiormente por 2^{n/2} quando n é um inteiro maior ou igual a 3. Os melhores limitantes de r(n) conhecidos atualmente implicam que

(3)  2^{1/2} ≤ lim inf_{n→∞} r(n)^{1/n} ≤ lim sup_{n→∞} r(n)^{1/n} ≤ 4.

Temos, assim, que a taxa precisa do crescimento exponencial de r(n) é ainda desconhecida. Saber se lim_{n→∞} r(n)^{1/n} existe e, no caso positivo, determinar o seu valor, são problemas importantes que permanecem em aberto na área.

Apesar de o número de Ramsey apresentar um crescimento exponencial para grafos completos, é razoável se esperar que, para um grafo H com poucas arestas, r(H) seja menor que r(v(H)). De fato, existem algumas classes relativamente grandes de grafos para as quais o número de Ramsey apresenta um crescimento polinomial. Como exemplo, apresentamos a seguir um resultado sobre uma classe de pares de grafos que, em particular, está no primeiro foco de estudo desta dissertação. O teorema abaixo, extraído de Chvátal [2], constitui um dos raros casos onde o número de Ramsey de uma classe de grafos é conhecido com exatidão.

Teorema 1. Para toda árvore T com n vértices, temos r(T, K^{m}) = 1 + (n − 1)(m − 1).

Um outro problema também considerado na literatura consiste na versão para arestas do problema descrito acima. A partir do Teorema 1 é fácil estabelecer um limitante superior “trivial” para r̂(T_{n}, K^{m}), onde T_{n} é uma árvore qualquer de ordem n:

r̂(T_{n}, K^{m}) ≤ \binom{r(T_{n}, K^{m})}{2} < \frac{(nm)^{2}}{2} .

A seguir, temos um resultado extraído de Ke [10] que, através da utilização de métodos probabilísticos e uma técnica sofisticada de imersão de árvores devida a Friedman e Pippenger^{1} [7], fornece um limitante superior melhor para este problema quando a árvore T_{n} possui grau limitado.

Teorema 2. Se d é um inteiro positivo fixo e n e m são inteiros positivos satisfazendo m^{β} < n < m^{γ} para duas constantes positivas β e γ, então, para n suficientemente grande, toda árvore T_{n,d} de ordem n e grau máximo d satisfaz

c_{1}m^{2}n ≤ r̂(T_{n,d}, K^{m}) ≤ c(d, β, γ)m^{2}n log n,

onde c_{1} é uma constante absoluta e c(d, β, γ) depende apenas de d, β e γ.

Como o nosso primeiro foco de estudo tem por objetivo determinar limitantes superiores para r_{sind}(T_{n}, H), r̂_{sind}(T_{n}, H) e r̂_{sind}(T_{n,d}, H) — para o caso em que H é um grafo qualquer — temos, pela Equação 2, que os Teoremas 1 e 2 funcionam como “referenciais” para o nosso trabalho.

2.2. Números de Ramsey induzidos. O caso induzido do problema tratado nos Teoremas 1 e 2 também faz parte do nosso foco de interesse. Uma diferença está no fato que os resultados listados aqui referem-se a um limitante superior para r_{ind}(T, H) e r̂_{ind}(T, H), onde T é uma árvore e H é um grafo qualquer.

Apesar da dificuldade trazida pelo fato de exigirmos cópias induzidas de T e H, é conhecido que tanto r_{ind}(T, H) como r̂_{ind}(T, H) apresentam crescimento polinomial em relação a v(H) e v(T). Abaixo segue um teorema de Kohayakawa, Prömel e Rödl [11] que estabelece um limitante superior para r_{ind}(T, H).

Teorema 3. Dados uma árvore T e um grafo arbitrário H, temos

(4)  r_{ind}(T, H) ≤ ct^{2}h^{4} (\frac{ln(th^{2})}{ln ln ln(th^{2})})^{2} ,

onde t = v(T), h = v(H) e c é uma constante absoluta.

1O enunciado e a demonstração do teorema de Friedman e Pippenger encontram-se no Apêndice C. Este resultado também é utilizado na demonstração de um limitante superior para r̂_{sind}(T, H), onde T é uma árvore de grau máximo limitado e H é um grafo qualquer, no Capítulo 1.

Apesar de não constar explicitamente como um resultado, a demonstração do Teorema 3 em Kohayakawa, Prömel e Rödl [11] também fornece um limitante superior para r̂_{ind}(T, H), que enunciamos a seguir.

Teorema 4. Dados uma árvore T e um grafo arbitrário H, temos

(5)  r̂_{ind}(T, H) ≤ ct^{3}h^{4} (\frac{ln(th^{2})}{ln ln ln(th^{2})})^{3} e(H),

onde t = v(T), h = v(H) e c é uma constante absoluta.

Assim como os Teoremas 1 e 2, temos, pela Equação 2, que os Teoremas 3 e 4 funcionam como “referenciais” dentro do nosso primeiro foco de estudo.

Já o nosso segundo foco de estudo está voltado para um outro problema clássico da teoria de Ramsey. Considere o problema de se estimar f(n) = max r_{ind}(H), onde o máximo é sobre todos os grafos H de ordem n.

Um resultado não publicado de Rödl [8] fornece que f(n) ≤ 2^{2^{n^{1+o(1)}}} .

O seguinte problema é devido a Graham e Rödl.

Problema 5. Existe uma contante C para a qual vale que f(n) ≤ C^{n}?

Rödl provou através de seus métodos em [16] que r_{ind}(H) ≤ C^{v(H)} para alguma constante C se H é um grafo bipartido. Łuczak e Rödl [12] provaram recentemente que r_{ind}(H) ≤ v(H)^{d} para alguma constante d = d(Δ(H)) que depende apenas do grau máximo Δ(H) de H, resolvendo assim positivamente um problema levantado por Trotter [8]. Observe que se a resposta ao Problema 5 for positiva, temos que o resultado, a menos pelo valor da constante C, é o melhor possível, pois existem grafos H para os quais r_{ind}(H) é exponencial em v(H) (basta tomar, por exemplo, o grafo K^{n}).

Antes de prosseguirmos, vamos introduzir mais algumas definições. Dados dois grafos G e H quaisquer, denotamos por I(G, H) o grafo obtido I(G, H) pela união disjunta de uma cópia de G com uma cópia de H. Analogamente, denotamos por K(G, H) o grafo I(G, H) adicionado de todas as arestas K(G, H) possíveis entre as cópias de G e H. Agora, seja G um conjunto de grafos qualquer. Considere EH_{0}(G) := G e, para todo i ∈ ℕ^{∗}, defina^{2} EH_{i}(G)

EH_{i}(G) := {G: ∃G_{1}, G_{2} ∈ ⋃_{j<i} EH_{j}(G) tal que

G = K(G_{1}, G_{2}) ou G = I(G_{1}, G_{2})}.

Denotamos por EH(G) a menor classe de grafos que contém EH_{i}(G), para EH(G) todo i ∈ ℕ. Note que se G ∈ EH_{i}(G) com i ∈ ℕ^{∗}, então existe uma partição própria {V_{1}, V_{2}} de V (G) tal que G[V_{1}], G[V_{2}] ∈ ⋃_{j<i} EH_{j}(G) e G = K(G[V_{1}], G[V_{2}]) ou G = I(G[V_{1}], G[V_{2}]).

2Denominamos esta classe de grafos por EH devido à semelhança de sua construção com a da classe de grafos simples definida em Erdős e Hajnal [5].

Tratando de um caso particular do Problema 5, Kohayakawa, Prömel e Rödl [11] verificaram que o crescimento de r_{ind}(G, H) é polinomial em v(H) se G ∈ EH({K^{1}}).

Teorema 6. Para todo grafo G ∈ EH({K^{1}}) existe uma constante f = f(G) que depende apenas de G tal que, para todo grafo H, temos

r_{ind}(G, H) ≤ v(H)^{f}.

Dados dois grafos G e H e um vértice v ∈ V (G) quaisquer, denotamos

G(v → H) por G(v → H) o grafo obtido de G pela substituição de v por uma cópia do grafo H e pela adição, para todo v′ ∈ V (G)\{v} com {v, v′} ∈ E(G), de todas as arestas possíveis entre os vértices da cópia do grafo H e v′. Seja

EH_{i}^{var}(G) G um conjunto de grafos qualquer. Considere EH_{0}^{var}(G) := G e, para todo i ∈ ℕ^{∗}, defina

EH_{i}^{var}(G) := {G: ∃G_{1}, G_{2} ∈ ⋃_{j<i} EH_{j}^{var}(G)

e v ∈ G_{1} tais que G = G_{1}(v → G_{2})}.

EH^{var}(G) Analogamente, denotamos por EH^{var}(G) a menor classe de grafos que contém

EH_{i}^{var}(G), para todo i ∈ ℕ.

Na segunda parte desta dissertação nós utilizamos a mesma técnica empregada na demonstração do Teorema 6 em [11], juntamente com uma idéia adicional extraída de Alon, Pach e Solymosi [1] e mostramos que r_{ind}(G, H) também possui crescimento polinomial em v(H) se G é um grafo pertencente a EH^{var}({K^{1}, K^{2}, I^{2}}) fixo. Infelizmente descobrimos, após a conclusão destes estudos, que as classes EH({K^{1}}) e EH^{var}({K^{1}, K^{2}, I^{2}}) são equivalentes^{3}. Desta forma, temos que o nosso estudo na segunda parte desta dissertação apenas fornece uma demonstração diferente para o Teorema 6.

3Veja o Teorema 39 do Apêndice D.

CAPÍTULO 1 Os Resultados para o Caso Semi-Induzido

1. Introdução

O nosso objetivo neste capítulo consiste no estudo de limitantes superiores para os números r_{sind}(T, H) e r̂_{sind}(T, H), onde T é uma árvore e H é um grafo qualquer. Abaixo segue o primeiro resultado deste capítulo.

Teorema 7. Suponha que uma árvore T e um grafo H sejam dados. Se h = v(H) ≥ 2 e t = v(T) ≥ 2 então

r_{sind}(T, H) ≤ (t − 1)h^{2} e r̂_{sind}(T, H) ≤ [(t − 1)h]^{2}e(H).

O segundo resultado deste capítulo trata de um caso especial do Teorema 7, onde T possui grau máximo limitado.

Teorema 8. Suponha que uma árvore T e um grafo H sejam dados. Para todo ε > 0 existem constantes positivas c = c(ε), h_{0} = h_{0}(ε) ≥ 1 e t_{0} = t_{0}(ε) ≥ 1 que dependem apenas de ε tais que se h = v(H) ≥ h_{0}, t = v(T) ≥ t_{0} e d = Δ(T) então

r̂_{sind}(T, H) < cd^{9/2}(h^{2}t^{3/2})^{1+ε}e(H).

Na demonstração do Teorema 8 utilizamos um grafo aleatório que é construído sobre um plano projetivo finito. Para o leitor não familiarizado com planos projetivos finitos, incluímos, no Apêndice A, uma breve introdução cobrindo as propriedades mais relevantes destas estruturas.

O restante deste capítulo está basicamente dividido em duas partes. A Seção 2 traz a demonstração do Teorema 7 e a Seção 3 traz a demonstração do Teorema 8.

2. A prova do Teorema 7

Esta seção está dividida em duas partes. A Subseção 2.1 contém alguns lemas auxiliares e a Subseção 2.2 traz a demonstração do Teorema 7.

2.1. Os Lemas Auxiliares. Apresentamos, nesta subseção, três lemas auxiliares que serão utilizados na prova do Teorema 7 na Subseção 2.2.

Lema 9. Seja G um grafo não-vazio. Se T é uma árvore com v(T) ≤ δ(G) + 1 então existe T̄ ⊆ G isomorfo a T.

Demonstração: A demonstração é feita por indução em v(T).

• Caso 1 (v(T) ≤ 1):

Se v(T) = 0, temos T ⊆ G e não há o que demonstrar.

Se v(T) = 1, temos que T é a árvore constituída por apenas um vértice. Como G é um grafo não-vazio, temos claramente v(G) > 0 e, portanto, existe T̄ ⊆ G isomorfo a T.

• Caso 2 (v(T) > 1):

Suponha que a hipótese de indução valha para os valores menores que v(T). Sejam v ∈ V (T) uma folha de T e e = {u, v} ∈ E(T) a aresta de E(T) que incide em v. Tome T′ = (V (T)\{v}, E(T)\{e})

— T′ é a árvore obtida pela remoção de v em T.

Como v(T′) < v(T) temos, pela hipótese de indução, que existe T̄′ ⊆ G isomorfo a T′. Seja ū ∈ V (T̄′) o vértice correspondente a u em um isomorfismo qualquer entre T′ e T̄′.

Como v(T̄′) = v(T′) < v(T) ≤ δ(G) + 1, temos v(T̄′) ≤ δ(G) e portanto vale dT̄′(ū) ≤ δ(G) − 1. Mas d_{G}(ū) ≥ δ(G), o que implica Γ_{G}(ū)\ΓT̄′(ū) ≠ ∅. Tomando v̄ ∈ Γ_{G}(ū)\ΓT̄′(ū) qualquer e ē = {ū, v̄}, temos que T̄ = (V (T̄′)∪{v̄}, E(T̄′)∪{ē}) é um subgrafo de G isomorfo a T.

□

O próximo lema, que também é utilizado na prova do Teorema 8 na próxima seção, garante a existência de um subgrafo com o grau mínimo limitado inferiormente dentro de um grafo arbitrário.

Lema 10. Todo o grafo não-vazio G possui um subgrafo G′ com δ(G′) ≥ e(G)/v(G).

Demonstração: Suponha G nas condições do enunciado e seja D = (G_{0}, G_{1}, …, G_{k}) uma seqüência maximal de subgrafos de G que obedece as seguintes restrições:

• G_{0} = G;

• para todo 0 ≤ i < k existe v_{i} ∈ V (G_{i}) tal que d_{G_{i}}(v_{i}) < e(G)/v(G), V (G_{i+1}) = V (G_{i})\{v_{i}} e E(G_{i+1}) = E(G_{i})\{e ∈ E(G_{i}): v_{i} ∈ e}.

Observe que G_{0} ⊃ G_{1} ⊃ ⋯ ⊃ G_{k}. Note também que, para 0 ≤ i < k, temos v(G_{i}) − v(G_{i+1}) = 1 e e(G_{i}) − e(G_{i+1}) < e(G)/v(G). Desta forma, temos que para 0 < i ≤ k vale

(6)  v(G_{0}) − v(G_{i}) = i

e

(7)  e(G_{0}) − e(G_{i}) < i × e(G)/v(G).

Observe que (6) garante k ≤ v(G_{0}). Mas note que não podemos ter k = v(G_{0}) pois, neste caso, teríamos v(G_{k}) = v(G_{0}) − k = 0 e por (7) teríamos e(G_{k}) > e(G_{0}) − k × e(G)/v(G) = 0, o que seria um absurdo.

Desta forma temos k < v(G_{0}) e, por (6), segue que v(G_{k}) > 0. Fazendo G′ = G_{k} temos, pela maximalidade de D, que δ(G′) ≥ e(G)/v(G). □

Antes de apresentarmos o próximo lema, vamos generalizar a noção de G(v → H) enunciada na introdução deste texto. Suponha que sejam dados dois grafos G e H e um conjunto V = {v_{1}, …, v_{k}} ⊆ V (G) com k = |V | quaisquer. Considere G_{0} = G e, para todo 1 ≤ i ≤ k, faça G_{i} = G_{i−1}(v_{i} → H). Denotamos por G(V → H) o grafo G_{k} obtido ao final do procedimento G(V → H) descrito acima.

O lema que segue abaixo, que também é utilizado na demonstração dos Lemas 22 e 23 no próximo capítulo, é em sua essência o Lema 13 de Kohayakawa, Prömel e Rödl [11].

Lema 11. Suponha G = H(V (H) → I), onde H é um grafo que satisfaz v(H) ≥ 2 e I é um grafo qualquer. Se as arestas de G forem coloridas com as cores vermelha e azul de forma que não haja uma cópia azul induzida de H em G então G possui pelo menos v(I)^{2} arestas vermelhas.

Demonstração: Sejam G, H e I nas condições do enunciado. Observe que se v(I) = 0 o resultado é imediato. Suponha, então, v(I) > 0.

Para todo v ∈ V (H) considere I_{v} ⊆ V (G) o conjunto de vértices que induz uma cópia do grafo I em G e que corresponde à “explosão” do vértice v no grafo original H. Observe que I = {I_{v}: v ∈ V (H)} é uma partição própria de V (G).

Agora considere F = {V ⊆ V (G): ∀v ∈ V (H), |V ∩ I_{v}| = 1}, ou seja, F é a família de todos os subconjuntos de V (G) que possuem exatamente um elemento em comum com cada conjunto I_{v} ∈ I. Observe que |F| = v(I)^{v(H)} e que para todo V ∈ F temos que G[V], o grafo induzido por V em G, é isomorfo a H. Considere também E = {e ∈ E(G): ∃V ∈ F tal que e ∈ E(G[V])} ⊆ E(G), ou seja, E = E(G)\ ⋃_{v∈V (H)} E(G[I_{v}]). Note que para toda aresta e ∈ E temos

(8)  |{V ∈ F: e ∈ G[V]}| = v(I)^{v(H)−2}.

Agora suponha que as arestas de G sejam coloridas com as cores vermelha e azul de forma que não haja uma cópia azul induzida de H em G. Vamos mostrar que G possui pelo menos v(I)^{2} arestas vermelhas.

De fato, suponha que a afirmação anterior seja falsa e que, portanto, o número de arestas vermelhas em G seja inferior a v(I)^{2}. Observe então que, por (8), menos de v(I)^{2} × v(I)^{v(H)−2} conjuntos de F induzem em G um grafo que contenha alguma aresta na cor vermelha. Como |F| = v(I)^{v(H)}, temos que existe V ∈ F tal que G[V] possui somente arestas azuis. Mas isto contradiz a nossa hipótese sobre a coloração das arestas de G pois G[V] é isomorfo a H. □

2.2. A prova do Teorema 7. O Teorema 7 decorre de uma aplicação dos três lemas auxiliares vistos na subseção anterior.

Demonstração do Teorema 7: Sejam T, H, t e h como no enunciado do Teorema 7 e considere G = H(V (H) → I^{(t−1)h}). Observe que v(G) = (t−1)h^{2} e e(G) = [(t−1)h]^{2}e(H). Vamos mostrar que G ⟶^{s,i} (T, H).

Suponha que as arestas de G sejam coloridas com as cores vermelha e azul de forma que não haja uma cópia azul induzida de H em G. Vamos mostrar que existe T̄ ⊆ G isomorfo a T e composto apenas por arestas vermelhas.

Pelo Lema 11 temos que existe um conjunto E_{R} de arestas vermelhas de G satisfazendo |E_{R}| ≥ [(t − 1)h]^{2}. Considere o grafo R = (V (G), E_{R}) ⊆ G. Relembrando que v(G) = (t − 1)h^{2} temos, pelo Lema 10, que existe R′ ⊆ R tal que δ(R′) ≥ t − 1. Como v(T) = t ≤ δ(R′) + 1 temos, pelo Lema 9, que existe T̄ ⊆ R′ isomorfo a T.

Desta forma temos G ⟶^{s,i} (T, H) e, portanto, segue que r_{sind}(T, H) ≤ v(G) = (t − 1)h^{2} e r̂_{sind}(T, H) ≤ e(G) = [(t − 1)h]^{2}e(H). □

3. A prova do Teorema 8

Esta seção está dividida em quatro subseções. Na Subseção 3.1 apresentamos a construção do grafo aleatório R, que serve de base para o desenvolvimento do nosso trabalho no resto desta seção. A Subseção 3.2 enuncia o Lema 13 que, como veremos, implica o Teorema 8. Na Subseção 3.3 enunciamos e provamos o Lema 14, que é um resultado auxiliar necessário para a demonstração do Lema 13. Por fim, a Subseção 3.4 traz a demonstração do Lema 13.

É importante salientarmos que a técnica de demonstração que utilizamos para provar o Teorema 8 é fortemente baseada na técnica de demonstração empregada na prova do Teorema 3 encontrada em Kohayakawa, Prömel e Rödl [11].

3.1. A construção do grafo aleatório R. Sejam H, T, h, t, d e ε dados nas condições do Teorema 8. Considere

(9)  q = ⌈\sqrt{8(d + 2)^{3}t ln[(d + 2)^{3}h^{2}t]^{3/2}} ⌉ .

Suponha que seja dado um plano projetivo finito P = (V, L) de ordem r satisfazendo

(10)  q^{2}h^{2} ≤ |V| = |L| = n = r^{2} + r + 1 ≤ 4q^{2}h^{2}.

Pelo Lema 30 do Apêndice A, temos que se r é uma potência de um número primo então existe um plano projetivo finito de ordem r. Para mostrarmos que existe um plano projetivo finito P de ordem r que satisfaz (10), considere o seguinte lema.

Lema 12. Para todo inteiro k ≥ 2, existe m ≥ 1 tal que k ≤ 2^{m} < 2k.

Demonstração: Vamos mostrar, por indução em k, que a hipótese do enunciado vale para todos os valores de k ≥ 2.

• Caso 1 (k = 2): basta tomar m = 1.

• Caso 2 (k > 2): suponha que a hipótese de indução valha para todos os valores menores de k e seja, então, um inteiro m′ ≥ 1 tal que k − 1 ≤ 2^{m′} < 2(k − 1). Se 2^{m′} ≥ k então basta tomar m = m′. Se 2^{m′} = k − 1 temos k < 2(k − 1) = 2^{m′+1} < 2k e, portanto, basta tomar m = m′ + 1.

□

Por (9), sabemos que qh é um inteiro maior que 1. Desta forma, temos que o Lema 12 garante que existe um inteiro m ≥ 1 tal que qh ≤ 2^{m} < 2qh. Observe que o Lema 30 garante a existência de um plano projetivo finito P de ordem 2^{m}. Tomando r = 2^{m}, temos que q^{2}h^{2} ≤ r^{2} < r^{2} + r + 1 < (r + 1)^{2} ≤ 4q^{2}h^{2} e, portanto, o plano projetivo finito P de ordem r = 2^{m} satisfaz (10).

Agora vamos descrever a construção do grafo aleatório R = R_{n}(P, H, t, d). Seja L ∈ L uma linha de P. Escolha aleatoriamente q subconjuntos W_{1}, …, W_{q} ⊆ L dois a dois disjuntos, todos de cardinalidade h. Note que isto é possível pois, por (10), temos qh < r + 1 = |L|. Agora, insira aleatoriamente q cópias de H em L usando os subconjuntos W_{i} como os conjuntos de vértices destas cópias. Repita este procedimento para todas as linhas L ∈ L, fazendo todas as escolhas aleatórias independentemente. O grafo R = R_{n}(P, H, t, d) é o grafo aleatório resultante. Observe que, pelo fato de estarmos construindo o grafo R sobre o plano projetivo finito P, temos que todas as cópias do grafo H inseridas nas linhas de P pelo procedimento descrito acima são induzidas^{1} no grafo resultante R = R_{n}(P, H, t, d).

Observe que a construção de R = R_{n}(P, H, t, d) e (10) implicam

(11)  e(R) = q|L|e(H) ≤ 4q^{3}h^{2}e(H).

A partir de (9), podemos escolher c′ > 0, h′_{0} ≥ 0 e t′_{0} ≥ 0 tais que se h ≥ h′_{0} e t ≥ t′_{0} então

(12)  q < \sqrt{12(d + 2)^{3}t ln[(t + 1)^{3}h^{2}t]} + 1 ≤ c′d^{3/2}h^{2ε/3}t^{(1+ε)/2}.

De (11) e (12), temos que existem c′ > 0, h′_{0} ≥ 0 e t′_{0} ≥ 0 tais que se h ≥ h′_{0} e t ≥ t′_{0} então

(13)  e(R) < 4c′^{3}d^{9/2}(h^{2}t^{3/2})^{1+ε}e(H).

1Veja a Definição 26 no Apêndice A para maiores detalhes.

3.2. Apresentação do Lema 13. Enunciamos abaixo o lema principal desta seção.

Lema 13. Existem constantes positivas h′′_{0} ≥ 1 e t′′_{0} ≥ 1 para as quais vale o que segue. Sejam H um grafo de ordem h ≥ h′′_{0}, t ≥ t′′_{0} e d ≥ 0 inteiros e P = (V, L) um plano projetivo finito de ordem r que satisfaça (9) e (10) dados. Então, existe um grafo R = R_{n}(P, H, t, d) tal que

(14)  R ⟶^{s,i} (T, H)

para qualquer árvore T de ordem t e grau máximo d.

Observe que se tomarmos c′, h′_{0} e t′_{0} como em (13) então o lema acima implica o Teorema 8 com c = 4c′^{3}, h_{0} = max{h′_{0}, h′′_{0}} e t_{0} = max{t′_{0}, t′′_{0}}.

É interessante mencionar que a prova do Lema 13, de fato, fornece uma versão “universal” de (14). Ou seja, a árvore T em (14) pode ser substituída por T_{d}^{t}, a família de todas as árvores de ordem t e grau máximo d. Dada uma coloração das arestas de R nas cores vermelha e azul, temos que se não existir uma cópia azul induzida de H em R então todas as árvores em T_{d}^{t} aparecerão como subgrafos de R com arestas vermelhas.

3.3. Um lema técnico sobre R = R_{n}(P, H, t, d). Sejam H um grafo, P = (V, L) um plano projetivo finito e t e d inteiros como na Subseção 3.1 fixos. Considere o grafo aleatório R = R_{n}(P, H, t, d) e seja W ⊆ V. Vamos

ρ_{R}(W) definir

(15) ρ_{R}(W) := ∑_{L∈L} ν(R[L ∩ W])

= ∑_{L∈L} max{|M|: M ⊆ E(R) emparelhamento
tal que ∀e ∈ M, e ⊆ L ∩ W }.

Ou seja, temos que ρ_{R}(W) nos fornece um limitante superior para e(G) se G ⊆ R é tal que V (G) = W e as arestas de G formam um emparelhamento em todas as linhas de L.

Temos, a seguir, o enunciado e a demonstração do Lema 14, que servirá de base para a prova do Lema 13.

Lema 14. Sejam H um grafo de ordem h ≥ 1, t ≥ 1 e d ≥ 0 inteiros e P = (V, L) um plano projetivo finito de ordem r que satisfaça (9) e (10) dados. Considere um grafo R = R_{n}(P, H, t, d). Então

Pr \{∃W ∈ [V]_{1}^{2(d+2)t}: \frac{ρ_{R}(W)}{|W |} > \frac{q}{2(d + 2)}\} → 0,

quando n → ∞. Em particular, existem constantes absolutas h′′_{0} ≥ 1 e t′′_{0} ≥ 1 tais que se v(H) = h ≥ h′′_{0} e t ≥ t′′_{0}, então existe pelo menos um grafo R′ = R_{n}(P, H, t, d) que satisfaz

\frac{ρ_{R′}(W)}{|W |} ≤ \frac{q}{2(d + 2)}

para todo W ∈ [V]_{1}^{2(d+2)t}.

Demonstração: Suponha que H, h, t, d, P e R sejam dados nas condições do enunciado. Vamos definir, para todos W ∈ [V]_{1}^{2(d+2)t}, L ∈ L e e ∈ [V]^{2}, as seguintes variáveis aleatórias:

X_{L,W} (R) := ν(R[L ∩ W]), X_{W} (R) := ∑_{L∈L} X_{L,W} (R) = ρ_{R}(W)

e

Y_{e}(R) := \{ \begin{matrix}1, & se e ∈ E(R) \\ 0, & caso contrário. \end{matrix}

Seja W ∈ [V]_{1}^{2(d+2)t} qualquer. Observando que n > 4(d + 2)^{2}h^{2}t, podemos estimar superiormente a esperança de X_{W}. De fato, temos

(16) E(X_{W}) ≤ E(e(R[W])) = E( ∑_{e∈[W]^{2}} Y_{e})

= ∑_{e∈[W]^{2}} E(Y_{e}) = ∑_{e∈[W]^{2}} \frac{e(H)q}{\binom{r+1}{2}} = \frac{\binom{|W |}{2}e(H)q}{\binom{r+1}{2}}

≤ \frac{|W |^{2}e(H)q}{n} < \frac{|W |h^{2}(d + 2)tq}{n} < \frac{|W |q}{4(d + 2)}.

Observe que, pela construção de R, temos que X_{W} é uma soma de variáveis aleatórias independentes. Para toda linha L ∈ L, defina

ξ_{L}(W) := max{X_{L,W} (R′): R′ = R_{n}(P, H, t, d)}.

Utilizando o Teorema 31 do Apêndice B e (16), temos:

(17) Pr \{\frac{X_{W}}{|W |} > \frac{q}{2(d + 2)}\} ≤ Pr \{X_{W} ≥ E(X_{W}) + \frac{|W |q}{4(d + 2)}\}

≤ exp \{−\frac{2(q|W |/[4(d + 2)])^{2}}{∑_{L∈L}[ξ_{L}(W)]^{2}} \} .

Vamos, agora, estimar um limitante superior para ∑_{L∈L}[ξ_{L}(W)]^{2}. Suponha L′ ∈ L fixo. Pela definição de ξ_{L′}(W), temos |L′∩W | ≥ 2ξ_{L′}(W). Como sabemos que ξ_{L′}(W) é um número inteiro não-negativo, temos

(18) \binom{|L′ ∩ W |}{2} ≥ \binom{2ξ_{L′}(W)}{2} = ξ_{L′}(W)[2ξ_{L′}(W) − 1] ≥ [ξ_{L′}(W)]^{2}.

Como sabemos que para quaisquer dois pontos distintos x, y ∈ W existe uma e somente uma linha L′′ ∈ L tal que {x, y} ⊆ L′′, temos

(19)  \binom{|W |}{2} = ∑_{L∈L} \binom{|L ∩ W |}{2}.

Aplicando (18) em (19), temos

(20)  \frac{|W |^{2}}{2} > \binom{|W |}{2} = ∑_{L∈L} \binom{|L ∩ W |}{2} ≥ ∑_{L∈L}[ξ_{L}(W)]^{2}.

Aplicando (20) em (17), temos

(21) Pr \{\frac{X_{W}}{|W |} > \frac{q}{2(d + 2)}\} ≤ exp \{−\frac{2(q|W |/[4(d + 2)])^{2}}{∑_{L∈L}[ξ_{L}(W)]^{2}} \}

< exp \{−\frac{q^{2}}{4(d + 2)^{2}} \} ≤ exp \{−2(d + 2)t ln[(d + 2)^{3}h^{2}t]^{3/2}\} ,

onde a última desigualdade decorre de (9).

Supondo n suficientemente grande, por (9) e (10) temos

(22)  [(d + 2)^{3}h^{2}t]^{3/2} ≥ n^{5/4}.

Aplicando (22) em (21), temos

Pr \{\frac{X_{W}}{|W |} > \frac{q}{2(d + 2)}\} < exp \{\frac{−5(d + 2)t ln n}{2}\}

e, portanto, temos

Pr \{∃W′ ∈ [V]_{1}^{2(d+2)t}: \frac{ρ_{R}(W′)}{|W′|} > \frac{q}{2(d + 2)}\}
≤ ∑_{W′∈[V]_{1}^{2(d+2)t}} Pr \{\frac{X_{W′}}{|W′|} > \frac{q}{2(d + 2)}\} < ∑_{W′∈[V]_{1}^{2(d+2)t}} e^{−5[(d+2)t ln n]/2}

= ∑_{i=1}^{2(d+2)t} \binom{n}{i}e^{−5[(d+2)t ln n]/2} ≤ e^{− ln n} ∑_{i=1}^{2(d+2)t} \binom{n}{i}e^{−2(d+2)t ln n}

≤ n^{−1} ∑_{i=1}^{2(d+2)t} (\frac{ne}{i})^{i} e^{−2(d+2)t ln n} ≤ n^{−1} ∑_{i=1}^{2(d+2)t} (\frac{ne}{i})^{i} e^{−i ln n}

= n^{−1} ∑_{i=1}^{2(d+2)t} (\frac{e}{i})^{i} < n^{−1} ∑_{i=0}^{∞} \frac{e^{i}}{i!} = \frac{e^{e}}{n} → 0,

quando n → ∞. □

3.4. A prova do Lema 13. Em posse do Lema 14, podemos provar o Lema 13 que, como já sabemos, implica o Teorema 8.

Demonstração do Lema 13: Sejam h′′_{0} e t′′_{0} fixados nas condições do Lema 14. Suponha que um grafo H de ordem h ≥ h′′_{0} e os inteiros t ≥ t′′_{0} e d ≥ 0 sejam dados. Seja P = (V, L) um plano projetivo finito de ordem r que satisfaça (9) e (10). Considere um grafo R = R_{n}(P, H, t, d) tal que ρ_{R}(W)/|W | ≤ q/2(d+2) para todo W ∈ [V]_{1}^{2(d+2)t} — observe que o Lema 14 garante a existência de um grafo R = R_{n}(P, H, t, d) com esta propriedade. A seguir, vamos mostrar que, sob tais condições, temos

(23)  R ⟶^{s,i} (T, H)

para qualquer árvore T de ordem t e grau máximo d.

Para provar (23), considere uma coloração das arestas de R com as cores vermelha e azul tal que não haja uma cópia azul induzida de H em R. Vamos mostrar, então, que toda árvore T de ordem t e grau máximo d aparecerá como subgrafo de R com todas as suas arestas na cor vermelha.

Primeiro observe que, dentro de cada linha de L, todas as q cópias disjuntas de H inseridas possuem pelo menos uma aresta vermelha. Desta forma, temos que existe uma coleção E de arestas vermelhas de R que possui exatamente q|L| = qn arestas e forma um emparelhamento dentro de cada linha de L.

Seja V_{E} = {v ∈ V: ∃ e ∈ E, v ∈ e} e considere o grafo G = (V_{E}, E). Como |V_{E}| ≤ |V| = n, o Lema 10 garante a existência de um grafo G′ ⊆ G tal que δ(G′) ≥ q.

Vamos mostrar agora que G′ contém todas as árvores de ordem t e grau máximo d. Para isso, vamos mostrar que para todo W ⊆ V (G′) com |W | ≤ 2t − 2 temos |Γ_{G′}(W)| ≥ (d + 1)|W |. Com este resultado, poderemos aplicar o Teorema 34 do Apêndice C que garante que G′ contém todas as árvores de ordem t e grau máximo d. Observe a condição acima é trivial quando |W | = 0.

Suponha, então, que a hipótese do parágrafo anterior seja falsa e que, portanto, exista W′ ∈ [V (G′)]_{1}^{2t−2} tal que |Γ_{G′}(W′)| < (d+1)|W′|. Considere W′′ = W′ ∪ Γ_{G′}(W′) e seja G′′ = G′[W′′]. Vamos mostrar que e(G′′) ≥ q|W′|/2. De fato, observe que pela definição de W′′ e G′′, temos que para qualquer v ∈ W′ vale d_{G′′}(v) = d_{G′}(v) ≥ q. Portanto, temos

e(G′′) = \frac{1}{2} ∑_{v∈V (G′′)} d_{G′′}(v) ≥ \frac{1}{2} ∑_{v∈W′} d_{G′′}(v) ≥ \frac{1}{2} ∑_{v∈W′} q = \frac{q|W′|}{2}.

Como v(G′′) = |W′′| ≤ |W′| + |Γ_{G′}(W′)| < |W′| + (d + 1)|W′| = (d + 2)|W′|, temos

(24)  \frac{e(G′′)}{v(G′′)} > \frac{q|W′|/2}{(d + 2)|W′|} = \frac{q}{2(d + 2)}.

Mas observe que G′′ ⊆ G. Lembrando a escolha de E(G) = E, temos que E(G′′) forma um emparelhamento em cada linha de L. Baseado em (15) e relembrando que G′′ ⊆ R, temos e(G′′) ≤ ρ_{R}(W′′). Pela escolha de R e pelo fato de 1 ≤ v(G′′) = |W′′| < (d + 2)|W′| < 2(d + 2)t, temos

\frac{e(G′′)}{v(G′′)} = \frac{e(G′′)}{|W′′|} ≤ \frac{ρ_{R}(W′′)}{|W′′|} ≤ \frac{q}{2(d + 2)},

contradizendo (24).

Portanto, temos que para todo W ⊆ V (G′) com |W | ≤ 2t − 2 vale que |Γ_{G′}(W)| ≥ (d + 1)|W |. Aplicando o Teorema 34, temos que G′ contém todas as árvores de ordem t e grau máximo d. Relembrando que G′ é um subgrafo de R formado apenas por arestas vermelhas, o resultado segue. □

CAPÍTULO 2 O Resultado para o Caso Induzido

1. Introdução

Neste capítulo nós mostramos que, para todo grafo H, o número de Ramsey induzido r_{ind}(G, H) possui crescimento polinomial em v(H) se G ∈ EH^{var}({K^{1}, K^{2}, I^{2}}). Segue, abaixo, o resultado principal deste capítulo que fornece uma demonstração diferente para o resultado do Teorema 6^{1}.

Teorema 15. Para todo grafo G ∈ EH^{var}({K^{1}, K^{2}, I^{2}}) existe uma constante f = f(G) que depende apenas de G tal que, para todo grafo H, temos

r_{ind}(G, H) ≤ v(H)^{f}.

Assim como na demonstração Teorema 8, o grafo aleatório utilizado na demonstração do Teorema 15 é construído sobre um plano projetivo finito^{2}.

O restante deste capítulo traz a demonstração do Teorema 15 e está dividido da seguinte forma. Na Seção 2 apresentamos a construção do grafo aleatório R. A Seção 3 enuncia a propriedade P, juntamente com um resultado relacionado à mesma. Na Seção 4 enunciamos a propriedade R e fornecemos mais alguns resultados. Finalmente, a Seção 5 traz a demonstração do Teorema 15.

É importante salientarmos que a técnica de demonstração que utilizamos para provar o Teorema 15 consiste na técnica de demonstração empregada na prova do Teorema 6 em Kohayakawa, Prömel e Rödl [11], adicionada da técnica de demonstração utilizada no Teorema 1.1 de Alon, Pach e Solymosi [1] em seu argumento principal.

2. A construção do grafo aleatório R

Nesta seção nós descrevemos a construção do grafo aleatório R, que servirá de base para o nosso trabalho no restante deste capítulo.

Seja H um grafo qualquer não-vazio. Suponha que seja dado um plano projetivo finito P = (V, L) com |V| = |L| = n. Vamos descrever a construção do grafo aleatório R = R(P, H) baseada somente em P e H.

Tomamos o conjunto de pontos de P como o conjunto de vértices de R, ou seja, temos V (R) = V. O conjunto de arestas de R é definido da seguinte forma. Suponha que, para cada L ∈ L, seja dada uma partição Π_{L} = {L_{v}: v ∈ V (H)} de L indexada pelos vértices v ∈ V (H) e considere Π = {Π_{L}: L ∈ L}. Sejam a, b ∈ V quaisquer e seja L ∈ L a única linha de P que contém os pontos a e b. Considere a partição Π_{L} ∈ Π e sejam u, v ∈ V (H) tais que a ∈ L_{u} e b ∈ L_{v} com L_{u}, L_{u} ∈ Π_{L}. Então

1Veja no Apêndice D algumas relações entre as classes EH e EH^{var}.

2Veja o Apêndice A para maiores detalhes sobre os planos projetivos finitos.

{a, b} ∈ E(R) ⟺ {u, v} ∈ E(H).

Observe que, para obtermos o grafo aleatório R = R(P, H), basta escolhermos a família de partições Π = {Π_{L}: L ∈ L} aleatoriamente. Para isso, dada uma linha L ∈ L, construímos a partição Π_{L} de L indexada pelos vértices do grafo H da seguinte forma. Escolhemos, independentemente para cada ponto x ∈ L, um vértice v ∈ V (H) de maneira uniforme — i.e. com probabilidade 1/v(H) para todo v ∈ V (H) — e fazemos x ∈ L_{v}. As escolhas de Π_{L} são feitas independentemente para todas as linhas L ∈ L.

R(P, H, Π) Desta forma, definimos o grafo aleatório R como

R = R(P, H) = R(P, H, Π).

Note que a aleatoriedade de R = R(P, H) decorre somente da escolha aleatória de Π. Uma vez escolhido Π, temos o grafo R determinado.

3. A Propriedade P

Nesta seção enunciamos a propriedade P, juntamente com um resultado relacionado à mesma.

Suponha que sejam dados um grafo H, um plano projetivo finito P = (V, L) com |V| = |L| = n, um conjunto X ⊆ V e uma família Π = {Π_{L}: L ∈ L} de partições das linhas de P indexadas pelos vértices do grafo H quais-

L(P, H, X, Π) quer. Defina

L(P, H, X, Π) := {L ∈ L: ∀v ∈ V (H),

\frac{3|X|}{4v(H)\sqrt{n}} ≤ |X ∩ L_{v}| ≤ \frac{4|X|}{3v(H)\sqrt{n}}\} .

propriedade Dada uma constante 0 < ε̃ ≤ 1/2 dizemos que a propriedade P(P, H, ε̃, Π)

P(P, H, ε̃, Π)

é válida se, para todo conjunto X ⊆ V com |X| ≥ n^{1/2+ε̃}, temos

|L(P, H, X, Π)| ≥ \frac{8n}{9}.

O teorema que enunciamos a seguir é, em sua essência, o Corolário 11 de Kohayakawa, Prömel e Rödl [11] e fornece uma condição suficiente para

a ≪ b a validade da propriedade P(P, H, ε̃, Π) — abaixo escrevemos a ≪ b se

a/b → 0 quando v(H) → ∞.

Teorema 16. Sejam H um grafo, P = (V, L) um plano projetivo finito com |V| = |L| = n e 0 < ε̃ ≤ 1/2 uma constante fixa. Suponha que n seja uma função de v(H) satisfazendo ln n ≪ v(H) ≪ n^{ε̃/2}. Então temos

Pr{P(P, H, ε̃, Π) vale} → 1

quando v(H) → ∞. Em particular, se v(H)^{f} < n < 9v(H)^{f} com f > 2/ε̃ constante, então existe uma constante h_{0} = h_{0}(f) ≥ 2 que depende apenas de f para a qual vale o que segue. Se v(H) ≥ h_{0} então existe uma família Π = {Π_{L}: L ∈ L} de partições das linhas de P indexadas pelos vértices do grafo H para a qual a propriedade P(P, H, ε̃, Π) é válida.

Antes de demonstrarmos o Teorema 16, vamos apenas enunciar um resultado que decorre do Corolário 10 de Kohayakawa, Prömel e Rödl [11].

Lema 17. Sejam H um grafo e P = (V, L) um plano projetivo finito com |V| = |L| = n. Suponha que n seja uma função de v(H) satisfazendo v(H) ≤ n para v(H) suficientemente grande e que α e β sejam funções de n satisfazendo n^{−1/2} ≪ αβ. Então a probabilidade de que exista um conjunto X ⊆ V com |X| ≥ αn tal que

|L\L(P, H, X, Π)| ≥ v(H)^{2}\sqrt{n} + βn

é no máximo

∑_{αn≤i≤n} \binom{n}{i} exp (−cv(H)i + \frac{1}{2}v(H)^{2}\sqrt{n} ln n),

onde c é uma constante absoluta.

Apesar de o enunciado do Teorema 16 possuir algumas diferenças em relação ao enunciado do Corolário 11 de Kohayakawa, Prömel e Rödl [11], temos que os passos da sua demonstração continuam exatamente os mesmos. Por isso, optamos por apenas fornecer um esboço de sua demonstração.

Esboço da demonstração do Teorema 16: Sejam H, P = (V, L), n e ε̃ nas condições do enunciado. Observe que temos v(H) < n^{ε̃/2} ≤ n^{1/4} < n para v(H) suficientemente grande.

Considere α = α(n) = n^{−1/2+ε̃} e β = β(n) = n^{−ε̃/2}. Pela hipótese sobre n, v(H) e ε̃, temos

v(H)^{2}\sqrt{n} ≪ nε̃\sqrt{n} ≤ n

e, como ε̃ > 0, temos

βn = n^{−ε̃/2}n ≪ n

portanto, segue

(25)  v(H)^{2}\sqrt{n} + βn ≪ n.

Pelo Lema 17 temos que a probabilidade de que exista um conjunto X ⊆ V com |X| ≥ αn tal que

(26)  |L\L(P, H, X, Π)| ≥ v(H)^{2}\sqrt{n} + βn

é no máximo

∑_{αn≤i≤n} \binom{n}{i} exp (−cv(H)i + \frac{1}{2}v(H)^{2}\sqrt{n} ln n)

≤ ∑_{αn≤i≤n} (\frac{ne}{i})^{i} exp (−cv(H)i + \frac{1}{2}v(H)^{2}\sqrt{n} ln n)

≤ ∑_{αn≤i≤n} exp (i − i ln α − cv(H)i + \frac{1}{2}v(H)^{2}\sqrt{n} ln n)

= ∑_{αn≤i≤n} exp (i + (1/2 − ε̃)i ln n − cv(H)i + \frac{1}{2}v(H)^{2}\sqrt{n} ln n).

Mas observe que, pelo fato de termos i ≥ αn = n^{1/2+ε̃} dentro da somatória acima e pela hipótese de ln n ≪ v(H) ≪ n^{ε̃/2}, temos

\frac{1}{2}v(H)^{2}\sqrt{n} ln n ≪ cn^{1/2+ε̃} ln n ≪ cn^{1/2+ε̃}v(H) ≤ cv(H)i

e

i + (1/2 − ε̃)i ln n ≪ cv(H)i.

Desta forma, se supormos v(H) suficientemente grande, temos

(27) ∑_{αn≤i≤n} \binom{n}{i} exp (−cv(H)i + \frac{1}{2}v(H)^{2}\sqrt{n} ln n)

< ∑_{αn≤i≤n} exp (−cv(H)i/2) < ∑_{αn≤i≤n} exp [−(ci ln n)/2]

= ∑_{αn≤i≤n} n^{−ci/2} < ∑_{αn≤i≤n} n^{−\sqrt{n}} < n^{1−\sqrt{n}} → 0,

quando v(H) → ∞.

De (25), (26) e (27) segue que

Pr{P(P, H, ε̃, Π) vale} → 1

quando v(H) → ∞. □

4. A Propriedade R

Esta seção traz a definição da propriedade R e mais alguns resultados. Antes de enunciarmos a propriedade R, precisamos introduzir mais uma definição. Dados um número real M e três grafos Γ, G e H, escrevemos

Γ ⟶^{M} (G, H) Γ ⟶^{M} (G, H) se, em qualquer coloração das arestas de Γ com as cores vermelha e azul, podemos encontrar um subgrafo azul induzido de Γ isomorfo a H ou então pelo menos M subgrafos vermelhos induzidos de Γ isomorfos a G.

Suponha que duas constantes 0 < ε ≤ 1/2 e 0 < ρ < 1 e um grafo G

propriedade R(ε, ρ, G) sejam dados. Dizemos que a propriedade R(ε, ρ, G) é válida se existem duas constantes f̃ = f̃(ε, ρ, G) > 0 e 0 < ε̃ = ε̃(ε, ρ, G) ≤ 1/2 para as quais vale o que segue. Para todo grafo H com v(H) ≥ 2 e todo plano projetivo finito P = (V, L) com n = |V| = |L| ≥ v(H)f̃ temos que se para uma família Π = {Π_{L}: L ∈ L} de partições das linhas de P indexadas pelos vértices do grafo H a propriedade P(P, H, ε̃, Π) é válida, então, para todo X ⊆ V com |X| ≥ n^{1/2+ε}, temos

(28)  R_{n}(P, H, Π)[X] ⟶^{M} (G, H),

onde M = |X|^{(1−ρ)v(G)}.

Dado um grafo G, diremos que G é R-satisfatível se a propriedade R-satisfatível R(ε, ρ, G) vale para quaisquer constantes 0 < ε ≤ 1/2 e 0 < ρ < 1. De forma análoga, dado um conjunto de grafos G, diremos que G é R-satisfatível se todo grafo G ∈ G é R-satisfatível.

O restante desta seção está dividido em duas partes. Na Subseção 4.1 estudamos duas propriedades relevantes dos grafos R-satisfatíveis e na Subseção 4.2 demonstramos que os grafos K^{1}, K^{2} e I^{2} são R-satisfatíveis.

4.1. Duas propriedades dos grafos R-satisfatíveis. A primeira propriedade dos grafos R-satisfatíveis que enunciamos nesta subseção diz respeito ao crescimento assintótico do número r_{ind}(G, H) para o caso em que o grafo G é R-satisfatível. O resultado que listamos abaixo implica que se G é um grafo R-satisfatível então, para todo grafo H, o número de Ramsey induzido r_{ind}(G, H) possui crescimento polinomial em v(H).

Lema 18. Para todo grafo R-satisfatível G existe uma constante f = f(G) que depende apenas de G tal que, para todo grafo H, temos

r_{ind}(G, H) ≤ v(H)^{f}.

Para demonstrarmos o Lema 18, precisamos do seguinte resultado auxiliar.

Lema 19. Seja k ≥ 4 um número real. Então existe um plano projetivo finito P = (V, L) com k < |V| = |L| < 9k.

Demonstração: Seja k nas condições do enunciado. Pelo Lema 12, cujo enunciado e demonstração encontram-se na Subseção 3.1 do capítulo anterior, temos que existe um inteiro m ≥ 1 tal que ⌈\sqrt{k}⌉ ≤ 2^{m} < 2⌈\sqrt{k}⌉.

Se tomarmos r = 2^{m} temos, pelo Lema 30 do Apêndice A, que existe um plano projetivo finito P = (V, L) de ordem r. Observe que k ≤ r^{2} < r^{2} + r + 1 = |V| = |L| < (r + 1)^{2} ≤ (2⌈\sqrt{k}⌉)^{2} < 4(\sqrt{k} + 1)^{2} ≤ 9k. □

Demonstração do Lema 18: Sejam G um grafo R-satisfatível e H um grafo qualquer. Observe que se v(H) = 1, temos que a afirmação do enunciado é verdadeira para qualquer constante f. Suponha, então, v(H) ≥ 2 e considere duas constantes 0 < ε ≤ 1/2 e 0 < ρ < 1 quaisquer. Seja (f̃, ε̃) um par de constantes associadas à validade da propriedade R(ε, ρ, G) e faça f′ := max{3/ε̃, f̃}.

Seja h_{0} = h_{0}(f′) nas condições do Teorema 16. Se v(H) < h_{0} então considere um grafo H′ com v(H′) = h_{0} que contenha H como subgrafo induzido. Caso contrário, faça H′ = H. Observe que em ambos os casos temos v(H′) ≤ v(H)^{log_{2} h_{0}}.

Como v(H′)^{f′} ≥ v(H)^{f′} ≥ v(H)^{6} ≥ 2^{6} > 4 temos, pelo Lema 19, que existe um plano projetivo finito P = (V, L) com v(H′)^{f′} < n = |V| = |L| < 9v(H′)^{f′}. Observe que, pela escolha de f′, h_{0} e P temos, pelo Teorema 16, que existe uma família Π = {Π_{L}: L ∈ L} de partições das linhas de P = (V, L) indexadas pelos vértices do grafo H′ para a qual a propriedade P(P, H′, ε̃, Π) é válida.

Considere o grafo R = R_{n}(P, H′, Π). Pelas escolhas de Π e n > v(H′)^{f′} ≥ v(H′)f̃ com v(H′) ≥ 2, temos, pela definição da propriedade R(ε, ρ, G), que

R_{n}(P, H′, Π)[V] ⟶^{M} (G, H′),

onde M = n^{(1−ρ)v(G)} > 1. Ou seja, temos

R_{n}(P, H′, Π) ⟶^{ind} (G, H′)

e portanto

R_{n}(P, H′, Π) ⟶^{ind} (G, H),

pois H é subgrafo induzido de H′.

Observe que

v(R) = n < 9v(H′)^{f′} ≤ 9v(H)^{f′ log_{2} h_{0}} < v(H)^{4+f′ log_{2} h_{0}}.

Portanto, se tormarmos f := 4 + f′ log_{2} h_{0} temos que f depende apenas de G e, para todo grafo H, vale

r_{ind}(G, H) ≤ v(H)^{f},

como queríamos demonstrar. □

A próxima propriedade dos grafos R-satisfatíveis que apresentamos nesta subseção consiste no fato de que um grafo obtido pela substituição de um vértice de um grafo R-satisfatível por outro grafo R-satisfatível também é um grafo R-satisfatível. Segue abaixo o Lema 20 que garante tal propriedade dos grafos R-satisfatíveis. É importante salientar que o argumento utilizado na demonstração do Lema 20 é fortemente baseado no argumento da demonstração do Teorema 1.1 de Alon, Pach e Solymosi [1].

Lema 20. Se G_{1} e G_{2} são grafos R-satisfatíveis então todo grafo G = G_{1}(v → G_{2}) com v ∈ V (G_{1}) também é R-satisfatível.

Demonstração: Suponha que G_{1} e G_{2} sejam dados nas condições do enunciado. Se v(G_{1}) = 1 temos G = G_{2} e não há o que demonstrar.

Suponha, então, v(G_{1}) ≥ 2 e seja v ∈ V (G_{1}) qualquer. Tome G = G_{1}(v → G_{2}) e suponha que sejam dadas duas constantes 0 < ε ≤ 1/2 e 0 < ρ < 1 quaisquer. Vamos mostrar que a propriedade R(ε, ρ, G) é válida.

Defina ε_{1} := ε, ε_{2} := ε/2, ρ_{2} := ρ/4 e

ρ_{1} := min \{\frac{ε}{v(G_{1})(3 + 6ε)}, \frac{ρ}{12v(G_{1})}\} .

Por hipótese, as propriedades R(ε_{1}, ρ_{1}, G_{1}) e R(ε_{2}, ρ_{2}, G_{2}) são válidas. Considere, então, (f̃_{1}, ε̃_{1}) e (f̃_{2}, ε̃_{2}) dois pares de constantes associadas à validade das propriedades R(ε_{1}, ρ_{1}, G_{1}) e R(ε_{2}, ρ_{2}, G_{2}), respectivamente. Defina

f̃:= max \{f̃_{1}, f̃_{2}, \frac{log_{2}(2e)}{ρ_{1}}\} e ε̃:= min\{ε̃_{1}, ε̃_{2}\}.

Vamos mostrar que f̃ e ε̃ como definidos acima demonstram a validade da propriedade R(ε, ρ, G). Para isso, suponha que sejam dados um grafo H com v(H) ≥ 2, um plano projetivo finito P = (V, L) com n = |V| = |L| ≥ v(H)f̃, uma família Π = {Π_{L}: L ∈ L} de partições das linhas de P indexadas pelos vértices do grafo H tal que a propriedade P(P, H, ε̃, Π) seja válida e um conjunto X ⊆ V com |X| = m ≥ n^{1/2+ε} quaisquer. Considere R = R_{n}(P, H, Π) e seja R′ = R[X]. Suponha que as arestas de R′ sejam coloridas com as cores vermelha e azul de forma que não haja cópia azul induzida de H em R′. Vamos mostrar, então, que R′ deve possuir pelo menos m^{(1−ρ)v(G)} cópias vermelhas induzidas de G.

Seja G_{0} o grafo obtido de G_{1} pela remoção do vértice v. Se J_{0} é um subconjunto de V (R′) tal que R′[J_{0}] é composto apenas por arestas vermelhas e isomorfo a G_{0}, denotamos por V_{J_{0}} o maior subconjunto de V (R′)\J_{0} com a propriedade de que para todo v′ ∈ V_{J_{0}} vale que R′[J_{0} ∪ {v′}] possui apenas arestas vermelhas e existe um isomorfismo entre R′[J_{0} ∪ {v′}] e G_{1} que mapeia v′ em v. Sejam

J := {J ⊆ V (R′): R′[J] é isomorfo a G_{0}, composto

apenas por arestas vermelhas e |V_{J}| ≥ m^{1−2v(G_{1})ρ_{1}}},

J̄ := {J̄ ⊆ V (R′): R′[J̄] é isomorfo a G_{0}, composto

apenas por arestas vermelhas e |VJ̄| < m^{1−2v(G_{1})ρ_{1}}}

e

K := {K ⊆ V (R′): R′[K] é isomorfo a G_{1} e composto apenas por arestas vermelhas}.

Vamos calcular um limitante inferior para |J |.

Primeiramente observe que

(29) |J̄| ≤ |{J̄ ⊆ V (R′): |J̄| = v(G_{0})}|

= \binom{v(R′)}{v(G_{0})} = \binom{m}{v(G_{1}) − 1} ≤ m^{v(G_{1})−1}.

Note também que, para todo K ∈ K, existem J′ ∈ J ∪ J̄ e v′ ∈ V_{J′} tal que J′ ∪ {v′} = K. Portanto, segue

(30)  K ⊆ {J′ ∪ {v′}: J′ ∈ J ∪ J̄, v′ ∈ V_{J′}}.

De (29) e (30), temos

(31) m|J | + m^{(1−2ρ_{1})v(G_{1})} ≥ m|J | + m^{1−2v(G_{1})ρ_{1}}|J̄|

> ∑_{J′∈J ∪J̄} |V_{J′}| ≥ |{J′ ∪ {v′}: J′ ∈ J ∪ J̄, v′ ∈ V_{J′}}| ≥ |K|.

Observando que |V (R′)| = |X| = m ≥ n^{1/2+ε} = n^{1/2+ε_{1}} temos, pela validade da propriedade R(ε_{1}, ρ_{1}, G_{1}) com as constantes f̃ e ε̃, que |K| ≥ m^{(1−ρ_{1})v(G_{1})}. Aplicando esta desigualdade em (31), temos

(32)  |J | > m^{v(G_{1})−1−2v(G_{1})ρ_{1}}(m^{v(G_{1})ρ_{1}} − 1).

Mas como m > n^{1/2} ≥ v(H)^{f̃/2} e f̃ ≥ [log_{2}(2e)]/ρ_{1}, temos m^{v(G_{1})ρ_{1}} > v(H)^{f̃v(G_{1})ρ_{1}/2} ≥ v(H)^{f̃ρ_{1}} ≥ v(H)^{log_{2}(2e)} ≥ 2e. Aplicando esta desigualdade em (32) e observando que ρ_{1} ≤ ρ/[12v(G_{1})] < {ρ[v(G_{1})−1]}/[4v(G_{1})], temos

(33)  |J | > m^{v(G_{1})−1−2v(G_{1})ρ_{1}} > m^{(1−ρ/2)[v(G_{1})−1]}.

Agora, para todo J ∈ J, defina W_{J} como um subconjunto de V_{J} de maior tamanho possível com a propriedade de que todos os seus vértices possuem a mesma vizinhança dentro J. Vamos calcular um limitante inferior para |W_{J}|, onde J ∈ J.

Observe que, para todo J ∈ J, os vértices de V_{J} podem estar ligados aos vértices de J no máximo de \binom{v(G_{1})−1}{⌈[v(G_{1})−1]/2⌉} maneiras diferentes e, pelo

fato de |V_{J}| ≥ m^{1−2v(G_{1})ρ_{1}}, temos

(34) |W_{J}| ≥ \frac{|V_{J}|}{\binom{v(G_{1})−1}{⌈[v(G_{1})−1]/2⌉}} ≥ \frac{m^{1−2v(G_{1})ρ_{1}}}{\binom{v(G_{1})−1}{⌈[v(G_{1})−1]/2⌉}} ≥ \frac{m^{1−2v(G_{1})ρ_{1}}}{(\frac{[v(G_{1})−1]e}{⌈[v(G_{1})−1]/2⌉})⌈[v(G_{1})−1]/2⌉}

≥ \frac{m^{1−2v(G_{1})ρ_{1}}}{(\frac{2e[v(G_{1})−1]}{v(G_{1})−1})v(G_{1})/2} = \frac{m^{1−2v(G_{1})ρ_{1}}}{m^{[v(G_{1}) log_{m}(2e)]/2}} > \frac{m^{1−2v(G_{1})ρ_{1}}}{m^{[v(G_{1}) log_{v(H)^{f̃/2}}(2e)]/2}}

= m^{1−2v(G_{1})ρ_{1}−[v(G_{1}) log_{v(H)}(2e)]/f̃} ≥ m^{1−2v(G_{1})ρ_{1}−[v(G_{1}) log_{2}(2e)]/f̃}

≥ m^{1−3v(G_{1})ρ_{1}},

onde a última desigualdade decorre da escolha de f̃. Observe também que, pelo fato de termos escolhido ρ_{1} ≤ ε/[v(G_{1})(3 + 6ε)] e ε_{2} = ε/2, temos

(35)  |W_{J}| ≥ n^{(1/2+ε)[1−3v(G_{1})ρ_{1}]} ≥ n^{(1/2+ε)[1−ε/(1+2ε)]} = n^{1/2+ε_{2}}.

4. A PROPRIEDADE R 31

Agora, para todo J ∈ J, defina

U_{J} := {U ⊆ V (R′): U ⊃ J, R′[U] é isomorfo a G

e composto apenas por arestas vermelhas}

e

V_{J} := {V ⊆ W_{J}: R′[V] é isomorfo a G_{2}

e composto apenas por arestas vermelhas}.

Vamos calcular um limitante inferior para |U_{J}|, onde J ∈ J.

Observe que, por (35) e pela validade da propriedade R(ε_{2}, ρ_{2}, G_{2}) com as constantes f̃ e ε̃, temos |V_{J}| ≥ |W_{J}|^{(1−ρ_{2})v(G_{2})}. Mas observe que para todo V′ ∈ V_{J} vale J ∩ V′ = ∅ e J ∪ V′ ∈ U_{J}. Portanto, por (34) e pelas de escolhas de ρ_{1} ≤ ρ/[12v(G_{1})] e ρ_{2} = ρ/4, temos

(36) |U_{J}| ≥ |V_{J}| ≥ |W_{J}|^{(1−ρ_{2})v(G_{2})} ≥ m^{[1−3v(G_{1})ρ_{1}](1−ρ_{2})v(G_{2})}

≥ m^{(1−ρ/4)^{2}v(G_{2})} > m^{(1−ρ/2)v(G_{2})}.

Agora defina

U := {U′ ⊆ V (R′): R′[U′] é isomorfo a G

e composto apenas por arestas vermelhas}.

Observe que |U| nos fornece exatamente o número de cópias vermelhas induzidas de G em R′. Vamos mostrar que |U| > m^{(1−ρ)v(G)}.

Observe que para todo J ∈ J temos U_{J} ⊆ U. Para todo U′ ∈ U, defina J_{U′} := {J ∈ J : U′ ∈ U_{J}} = {J ∈ J : J ⊂ U′}. Observe que, para todo U′ ∈ U, temos

(37) |J_{U′}| ≤ |{U′′ ⊂ U′: |U′′| = v(G_{1}) − 1}|

≤ \binom{v(G)}{⌈\frac{v(G)}{2}⌉} < 2^{v(G)} < (2e)^{v(G)} = m^{v(G) log_{m}(2e)}

< m^{2v(G)[log_{v(H)}(2e)]/f̃} < m^{ρv(G)/2},

onde as duas últimas desigualdades decorrem do fato de termos escolhido m > n^{1/2} ≥ v(H)^{f̃/2} e f̃ ≥ log_{2}(2e)/ρ_{1} ≥ log_{v(H)}(2e)/ρ_{1} > 4 log_{v(H)}(2e)/ρ.

Portanto, por (33), (36) e (37), temos

|U| ≥ | ⋃_{J∈J} U_{J} | ≥ \frac{∑_{J∈J} |U_{J}|}{max\{|J_{U′}|: U′ ∈ U\}} ≥ \frac{|J | min\{|U_{J}|: J ∈ J \}}{max\{|J_{U′}|: U′ ∈ U\}}

> m^{(1−ρ/2)[v(G_{1})+v(G_{2})−1]−ρv(G)/2} = m^{(1−ρ)v(G)}.

□

4.2. Alguns grafos R-satisfatíveis. Nesta subseção nós provamos que os grafos K^{1}, K^{2} e I^{2} são R-satisfatíveis.

Lema 21. O grafo K^{1} é R-satisfatível.

Demonstração: Suponha que as constantes 0 < ε ≤ 1/2 e 0 < ρ < 1 sejam dadas. Vamos mostrar que a propriedade R(ε, ρ, K^{1}) é válida.

Suponha que sejam dados um grafo H com v(H) ≥ 2, um plano projetivo finito P = (V, L), uma família Π = {Π_{L}: L ∈ L} de partições das linhas de P indexadas pelos vértices do grafo H e um conjunto X ⊆ V com |X| ≥ n^{1/2+ε} quaisquer. Considere o grafo R = R_{n}(P, H, Π).

Note que R[X] possui exatamente

|X| > |X|^{1−ρ}

cópias induzidas de K^{1}. Como K^{1} não possui arestas, temos que em qualquer coloração das arestas de R[X] nas cores vermelha e azul vale que R[X] possui pelo menos |X|^{1−ρ} cópias vermelhas induzidas de K^{1}. Portanto, segue que R[X] ⟶^{M} (K^{1}, H), onde M = |X|^{1−ρ}. □

Lema 22. O grafo K^{2} é R-satisfatível.

Demonstração: Suponha que as constantes 0 < ε ≤ 1/2 e 0 < ρ < 1 sejam dadas e defina

f̃:= \frac{3}{ρ(1 + 2ε)}  e  ε̃:= ε.

Vamos mostrar que f̃ e ε̃ como definidos acima demonstram a validade da propriedade R(ε, ρ, K^{2}). Para isso, suponha que sejam dados um grafo H com v(H) ≥ 2, um plano projetivo finito P = (V, L) com n = |V| = |L| ≥ v(H)f̃, uma família Π = {Π_{L}: L ∈ L} de partições das linhas de P indexadas pelos vértices do grafo H tal que a propriedade P(P, H, ε̃, Π) seja válida e um conjunto X ⊆ V com |X| ≥ n^{1/2+ε} quaisquer. Considere R = R_{n}(P, H, Π) e suponha que as arestas de R[X] sejam coloridas com as cores vermelha e azul de forma que não haja cópia azul induzida de H em R[X]. Vamos mostrar, então, que R[X] deve possuir pelo menos |X|^{(1−ρ)2} arestas vermelhas.

Primeiramente observe que, pela hipótese da validade da propriedade P(P, H, ε̃, Π) e pelo fato de termos |X| ≥ n^{1/2+ε} = n^{1/2+ε̃}, temos

(38)  |L(P, H, X, Π)| ≥ \frac{8n}{9}.

Agora considere L ∈ L(P, H, X, Π) qualquer e seja Π_{L} = {L_{v}: v ∈ V (H)} a partição dos vértices de L indexada pelos vértices do grafo H em Π. Observe que, pela definição de L(P, H, X, Π), temos

|X ∩ L_{v}| ≥ \frac{3|X|}{4v(H)\sqrt{n}}

para todo v ∈ V (H). Desta forma, se tomarmos s = ⌈3|X|/[4v(H)\sqrt{n}]⌉ então a construção do grafo R = R_{n}(P, H, Π) implica que R[X ∩ L] contém um subgrafo induzido S_{L} isomorfo a H(V (H) → I^{s}). Mas como S_{L} é também um subgrafo induzido de R[X] e, por hipótese, R[X] não possui cópia azul induzida de H, temos então que S_{L} também não possui cópia azul induzida de H. Aplicando o Lema 11 do Capítulo 1 em S_{L}, temos o número de arestas vermelhas em S_{L} é pelo menos

(39)  s^{2} ≥ (\frac{3|X|}{4v(H)\sqrt{n}})^{2} = \frac{9|X|^{2}}{16v(H)^{2}n}.

Note que, pelo fato de construirmos o grafo R = R_{n}(P, H, Π) sobre o plano projetivo finito P, temos que para quaisquer L, L′ ∈ L(P, H, X, Π) distintos vale que E(S_{L}) ∩ E(S_{L′}) = ∅. Pela consideração acima e por (38) e (39) temos que o número de arestas vermelhas em R[X] é pelo menos

∑_{L∈L(P,H,X,Π)} s^{2} ≥ \frac{8n}{9} × \frac{9|X|^{2}}{16v(H)^{2}n} = \frac{|X|^{2}}{2v(H)^{2}} .

Pela escolha de f̃ = 3/[ρ(1 + 2ε)] e pelas hipóteses de |X| ≥ n^{1/2+ε}, n ≥ v(H)f̃ e v(H) ≥ 2 temos então que R[X] possui pelo menos

(40) \frac{|X|^{2}}{2v(H)^{2}} = \frac{|X|^{(1−ρ)2}|X|^{2ρ}}{2v(H)^{2}} ≥ \frac{|X|^{(1−ρ)2}n^{(1+2ε)ρ}}{2v(H)^{2}}

≥ \frac{|X|^{(1−ρ)2}v(H)^{f̃(1+2ε)ρ}}{2v(H)^{2}} = \frac{|X|^{(1−ρ)2}v(H)}{2} ≥ |X|^{(1−ρ)2}

arestas vermelhas.

De (40) segue que R[X] ⟶^{M} (K^{2}, H), onde M = |X|^{(1−ρ)2}. □

Lema 23. O grafo I^{2} é R-satisfatível.

Demonstração: Suponha que as constantes 0 < ε ≤ 1/2 e 0 < ρ < 1 sejam dadas e defina

f̃:= max \{\frac{71}{50ε}, \frac{4}{ρ(1 + 2ε)}\} e ε̃:= ε.

Vamos mostrar que f̃ e ε̃ como definidos acima demonstram a validade da propriedade R(ε, ρ, I^{2}). Para isso, suponha que sejam dados um grafo H com v(H) ≥ 2, um plano projetivo finito P = (V, L) com n = |V| = |L| ≥ v(H)f̃, uma família Π = {Π_{L}: L ∈ L} de partições das linhas de P indexadas pelos vértices do grafo H tal que a propriedade P(P, H, ε̃, Π) seja válida e um conjunto X ⊆ V com |X| ≥ n^{1/2+ε} quaisquer. Considere o grafo R = R_{n}(P, H, Π). Vamos mostrar que R[X] possui pelo menos |X|^{(1−ρ)2} cópias induzidas de I^{2}. Observe que isto é suficiente para provarmos a validade da propriedade R(ε, ρ, I^{2}) pois, como I^{2} não possui arestas, temos que em qualquer coloração das arestas de R[X] nas cores vermelha e azul vale que R[X] possui pelo menos |X|^{(1−ρ)2} cópias vermelhas induzidas de I^{2}.

Assim como na demonstração do Lema 22, a hipótese da validade da propriedade P(P, H, ε̃, Π) e o fato de termos |X| ≥ n^{1/2+ε} = n^{1/2+ε̃} implicam

(41)  |L(P, H, X, Π)| ≥ \frac{8n}{9}.

Agora considere L ∈ L(P, H, X, Π) qualquer e seja Π_{L} = {L_{v}: v ∈ V (H)} a partição dos vértices de L indexada pelos vértices do grafo H em Π. Pela definição de L(P, H, X, Π) temos

|X ∩ L_{v}| ≥ \frac{3|X|}{4v(H)\sqrt{n}}

para todo v ∈ V (H). Desta forma, se tomarmos s = ⌈3|X|/[4v(H)\sqrt{n}]⌉ então a construção do grafo R = R_{n}(P, H, Π) implica que R[X ∩ L] contém uma coleção I_{L,1}, …, I_{L,v(H)} de subgrafos induzidos dijuntos nos vértices e isomorfos a I^{s}. Observe que pelas hipóteses de |X| ≥ n^{1/2+ε} ≥ v(H)^{εf̃}\sqrt{n} e v(H) ≥ 2 e pela escolha de f̃ ≥ 71/(50ε) temos que

s ≥ \frac{3|X|}{4v(H)\sqrt{n}} ≥ \frac{3v(H)^{εf̃−1}}{4} ≥ \frac{3v(H)^{21/50}}{4} ≥ \frac{3 × 2^{21/50}}{4} > 1.

Desta forma, se definirmos I_{L} como o conjunto de todas as cópias induzidas de I^{2} em R[X ∩ L] temos

(42) |I_{L}| ≥ ∑_{1≤i≤v(H)} \binom{v(I_{L,i})}{2} = v(H)\binom{s}{2}

≥ v(H) (\frac{3|X|}{8v(H)\sqrt{n}})^{2} = \frac{9|X|^{2}}{64v(H)n}.

Note que pelo fato de termos construído o grafo R = R_{n}(P, H, Π) sobre o plano projetivo finito P, temos que para quaisquer L, L′ ∈ L(P, H, X, Π) distintos vale que I_{L} ∩ I_{L′} = ∅. Pela consideração acima e por (41) e (42) temos que o número de cópias induzidas de I^{2} em R[X] é pelo menos

∑_{L∈L(P,H,X,Π)} |I_{L}| ≥ \frac{8n}{9} × \frac{9|X|^{2}}{64v(H)n} = \frac{|X|^{2}}{8v(H)}.

Pela escolha de f̃ ≥ 4/[ρ(1 + 2ε)] e pelas hipóteses de |X| ≥ n^{1/2+ε}, n ≥ v(H)f̃ e v(H) ≥ 2 temos então que R[X] possui pelo menos

(43) \frac{|X|^{2}}{8v(H)} = \frac{|X|^{(1−ρ)2}|X|^{2ρ}}{8v(H)} ≥ \frac{|X|^{(1−ρ)2}n^{(1+2ε)ρ}}{8v(H)}

≥ \frac{|X|^{(1−ρ)2}v(H)^{f̃(1+2ε)ρ}}{8v(H)} ≥ \frac{|X|^{(1−ρ)2}v(H)^{3}}{8} ≥ |X|^{(1−ρ)2}

cópias induzidas de I^{2}.

De (43) segue que R[X] ⟶^{M} (I^{2}, H), onde M = |X|^{(1−ρ)2}. □

5. A prova do Teorema 15

Considere o seguinte lema auxiliar.

Lema 24. Seja G um conjunto de grafos R-satisfatível qualquer. Então EH^{var}(G ∪ {K^{1}, K^{2}, I^{2}}) também é R-satisfatível.

Observe que o Teorema 15 decorre da aplicação do Lema 18 no lema listado acima com G = ∅.

Demonstração do Lema 24: Seja G nas condições do enunciado. Primeiramente vamos mostrar, por indução em i, que EH_{i}^{var}(G ∪ {K^{1}, K^{2}, I^{2}}) é R-satisfatível para todo i ∈ ℕ.

• Caso 1 (i = 0): Observe que os Lemas 21, 22 e 23 implicam que o conjunto {K^{1}, K^{2}, I^{2}} é R-satisfatível. Pela hipótese sobre G temos que EH_{0}^{var}(G∪ {K^{1}, K^{2}, I^{2}}) = G ∪ {K^{1}, K^{2}, I^{2}} é R-satisfatível.

• Caso 2 (i > 0): Suponha que a hipótese de indução valha para os valores menores que i e seja G ∈ EH_{i}^{var}(G ∪ {K^{1}, K^{2}, I^{2}}) qualquer. Vamos mostrar que G é R-satisfatível.

De fato, pela definição de EH_{i}^{var}(G ∪ {K^{1}, K^{2}, I^{2}}) com i > 0 temos que existem G_{1}, G_{2} ∈ ⋃_{j<i} EH_{j}^{var}(G ∪ {{K^{1}, K^{2}, I^{2}}) e v ∈ V (G_{1}) tais que G = G_{1}(v → G_{2}). Pela hipótese de indução temos que G_{1} e G_{2} são R-satisfatíveis e, pelo Lema 20, segue que G também é R-satisfatível.

Como EH^{var}(G ∪ {K^{1}, K^{2}, I^{2}}) é a menor classe de grafos que contém EH_{i}^{var}(G ∪{K^{1}, K^{2}, I^{2}}) para todo i ∈ ℕ, segue que EH^{var}(G ∪{K^{1}, K^{2}, I^{2}}) é R-satisfatível. □

Como já foi discutido na introdução deste texto, temos que os resultados dos Teoremas 6 e 15 são equivalentes. Mas é válido fazermos algumas considerações sobre o resultado obtido neste capítulo.

Um resultado que pode ser facilmente demonstrado a partir do Lema 17 de Kohayakawa, Prömel e Rödl [11] é dado a seguir.

Lema 25. Seja G um conjunto de grafos R-satisfatível qualquer. Então EH(G ∪ {K^{1}}) também é R-satisfatível.

Assim como acontece com o Teorema 15, a única forma de se fortalecer o Teorema 6 mantendo a demonstração encontrada em Kohayakawa, Prömel e Rödl [11] seria através do Lema 25, ou seja, através da descoberta de novos grafos R-satisfatíveis. Desta forma, o Teorema 38 do Apêndice D garante que a classe de grafos obtida pelo Lema 25 está sempre contida na classe obtida pelo Lema 24, quando consideramos o mesmo conjunto de grafos G R-satisfatível. Mas segundo o Teorema 40 do Apêndice D, bastaria descobrirmos um único grafo R-satisfatível não pertencente a EH({K^{1}}) para que melhorássemos o resultado fornecido pelo técnica empregada em [11], mesmo considerando o Lema 25.

Tendo este objetivo em mente, um fato que pode ser facilmente verificado é que um subgrafo induzido de um grafo R-satisfatível também é um grafo R-satisfatível. Desta forma, pelo Teorema 41 do Apêndice D temos que a tarefa de descobrir um grafo R-satisfatível não pertencente a EH({K^{1}}) seria pelo menos tão difícil quanto mostrar que o grafo P^{4}, o caminho com 4 vértices, é R-satisfatível. Apesar dos nossos esforços neste sentido, não encontramos indícios de que o grafo P^{4} seja R-satisfatível.

APÊNDICE A Planos Projetivos Finitos

O nosso objetivo neste apêndice é fornecer ao leitor uma breve introdução aos planos projetivos finitos. Os resultados aqui apresentados são apenas os necessários para o desenvolvimento do nosso trabalho. Todo o conteúdo deste apêndice é baseado no Capítulo 8 de Matoušek e Nešetřil [13].

Definição 26 (Plano projetivo finito). Sejam X um conjunto finito e L uma família de subconjuntos de X. O par (X, L) é chamado de plano projetivo finito se satisfaz os seguintes axiomas:

A0: Existe um conjunto com quatro elementos F ⊆ X tal que |L ∩

F | ≤ 2 para todo conjunto L ∈ L. A1: Quaisquer dois conjuntos distintos L_{1}, L_{2} ∈ L intersectam em

exatamente um elemento, ou seja, temos |L_{1} ∩ L_{2}| = 1. A2: Para quaisquer dois elementos distintos x_{1}, x_{2} ∈ X, existe exa-

tamente um conjunto L ∈ L tal que x_{1}, x_{2} ∈ L. Se P = (X, L) é um plano projetivo finito, chamamos os elementos em pontos e linhas

de P

X de pontos de P e os conjuntos em L de linhas de P. Se x é um ponto de P e L é uma linha de P com x ∈ L, dizemos que “o ponto x está na linha L” e que “a linha L passa pelo ponto x”. Dados dois pontos distintos a e b de P, denotamos por \overline{ab} a única linha L de P que contém ambos os pontos

\overline{ab}

a e b. Analogamente, dadas duas linhas distintas L e L′ de P, denotamos por L ∩ L′ o único ponto^{1} x de P que pertence às linhas L e L′. L ∩ L′

Listamos abaixo as principais propriedades dos planos projetivos finitos. Proposição 27. Seja P = (X, L) um plano projetivo finito. Então

todas as suas linhas possuem o mesmo número de pontos, ou seja, |L| = |L′| para quaisquer L, L′ ∈ L.

Demonstração: Sejam L, L′ ∈ L duas linhas quaisquer de P. Primeiramente vamos mostrar que existe x ∈ X tal que x ∉ L ∪ L′.

Considere F ⊆ X nas condições do axioma A0 da Definição 26. Se F ⊈ L ∪ L′ temos claramente que existe x ∈ F tal que x ∉ L ∪ L′ e não há o que demonstrar. Suponha, então, F ⊆ L ∪ L′. Observe que, pela escolha de F, temos |F ∩L|, |F ∩L′| ≤ 2. Desta forma, a única possibilidade que podemos ter é dada, sem perda de generalidade, por F ∩ L = {a, c} e F ∩ L′ = \{b, d\} com F = \{a, b, c, d\}. Vamos mostrar que x = \overline{ab} ∩ \overline{cd} não pertence nem a L e nem a L′. De fato, suponha x ∈ L. Se x ≠ a temos \overline{ab} = \overline{xa} = L e se x ≠ c temos \overline{cd} = \overline{xc} = L. Note que sempre algum dos dois casos ocorre, o que é absurdo, pois b, d ∉ L. Portanto, temos x ∉ L — o raciocínio para mostrar que x ∉ L′ é análogo.

1Note o pequeno abuso de notação que cometemos aqui, pois, a rigor, L ∩ L′ nos fornece um conjunto com um único ponto.

Agora, para mostrar que |L| = |L′|, vamos construir uma bijeção entre os pontos de |L| e |L′|. Considere a função φ: L → L′ definida por φ(y) = \overline{xy} ∩ L′ para todo ponto y de L. Note que, para todo z ∈ L′, temos φ(\overline{xz} ∩ L) = \overline{x(\overline{xz} ∩ L)} ∩ L′ = \overline{xz} ∩ L′ = z, ou seja, temos que φ é uma função sobrejetora. Por outro lado, suponha que existam y, y′ ∈ L distintos tais que φ(y) = φ(y′) = z. Neste caso, temos y ∈ \overline{xy} = \overline{xz} e y′ ∈ \overline{xy′} = \overline{xz}, ou seja, temos \overline{yy′} = \overline{xz}. Mas L = \overline{yy′} e, portanto, temos x ∈ L, o que contraria a escolha de x. Temos, desta forma, que φ é também uma função injetora. □

Provada a Proposição 27, podemos definir o conceito de ordem de um plano projetivo finito.

Definição 28 (Ordem de um plano projetivo finito). A ordem de um plano projetivo finito P = (X, L) é o número |L| − 1, onde L é uma linha qualquer de P.

Enunciamos abaixo mais algumas propriedades dos planos projetivos finitos.

Proposição 29. Seja P = (X, L) um plano projetivo finito de ordem n. Então temos

(1) Exatamente n + 1 linhas passam por cada ponto de P.

(2) |X| = n^{2} + n + 1.

(3) |L| = n^{2} + n + 1.

Demonstração de 1: Seja x um ponto qualquer de P. Vamos mostrar, primeiramente, que existe uma linha L de P que não contém o ponto x. Considere F ⊆ X nas condições do axioma A0 da Definição 26 e sejam a, b e c três pontos de F distintos de x. Observe que x não pode pertencer a \overline{ab} e a \overline{ac} ao mesmo tempo. De fato, se tivermos x ∈ \overline{ab} e x ∈ \overline{ac}, então vale que \overline{ab} = \overline{ax} = \overline{ac}, o que significa que existe uma linha em P que contém os pontos a, b e c, contrariando a escolha de F. Desta forma, temos que existe L ∈ L tal que x ∉ L, como queríamos mostrar.

Agora considere uma linha L′ de P tal que x ∈ L′ e tome x′ = L ∩ L′. Como x′ ∈ L, temos x ≠ x′. Observando que x, x′ ∈ L′, temos que L′ = \overline{xx′}. Desta forma, temos que o número de linhas distintas que passam por x é igual ao número de linhas distintas da forma \overline{xy}, onde y ∈ L.

Sejam, então, y e z dois pontos de L. Observe que não podemos ter \overline{xy} = \overline{xz}, pois neste caso teríamos x ∈ \overline{yz} = L, contrariando a escolha de L. Portanto, temos que o número de linhas que passam por x é dado por |L| = n + 1. □

Demonstração de 2: Sejam x e L como na demonstração do item anterior. Relembre que exatamente |L| = n + 1 linhas distintas passam por x, todas da forma \overline{xy}, onde y ∈ L.

Seja x′ um ponto qualquer de P distinto de x. Observe que x, x′ ∈ \overline{xx′}, ou seja, existe uma linha que passa por x e que contém x′. Desta forma, temos X = ⋃_{y∈L} \overline{xy}.

Agora tome y e y′ dois pontos distintos quaisquer de L. Já sabemos, pela demonstração do item anterior, que \overline{xy} ≠ \overline{xy′}. Assim, temos \overline{xy} ∩ \overline{xy′} = x e, portanto, vale |X| = | ⋃_{y∈L} \overline{xy}| = 1 + ∑_{y∈L}(|\overline{xy}| − 1) = 1 + (n + 1)n = n^{2} + n + 1. □

Demonstração de 3: Seja L uma linha qualquer de P. Para todo x ∈ L, considere L_{x} = {L ∈ L: x ∈ L} — observe que, pelo item 1, temos |L_{x}| = n + 1.

Seja L′ uma linha qualquer de P distinta de L. Observe que L′ ∈ L_{L∩L′}, ou seja, existe um ponto x de L tal que L′ ∈ L_{x}. Desta forma, temos L = ⋃_{x∈L} L_{x}.

Agora tome x e x′ dois pontos distintos quaisquer de L. Observe que L_{x} ∩ L_{x′} = \overline{xx′} = L. Temos, portanto, |L| = | ⋃_{x∈L} L_{x}| = 1 + ∑_{x∈L}(|L_{x}| − 1) = 1 + (n + 1)n = n^{2} + n + 1. □

Enunciamos e provamos abaixo o resultado que fornece uma condição suficiente para a existência de um plano projetivo finito.

Lema 30. Seja n um inteiro positivo. Se n é uma potência de um número primo então existe um plano projetivo finito de ordem n.

Demonstração: Suponha que n seja dado nas condições do enunciado. Como é bastante conhecido no estudo da Álgebra, temos que o fato de n ser uma potência de um número primo implica a existência de um corpo K com n elementos. Utilizaremos este corpo K como base para a construção de um plano projetivo finito de ordem n.

Suponha, sem perda de generalidade, que os elementos neutros da adição e da multiplicação de K são, respectivamente, 0 e 1. Considere T = {(1, x, y): x, y ∈ K} ∪ {(0, 1, x): x ∈ K} ∪ {(0, 0, 1)} — observe que T é composto por todas as triplas de K^{3}\{(0, 0, 0)} cujo primeiro componente não-nulo é igual a 1. Para todo (x, y, z) ∈ T, defina P_{(x,y,z)} := {(x′, y′, z′) ∈ T: xx′ + yy′ + zz′ = 0} — note que não é difícil verificar que |P_{(x,y,z)}| ≥ 2. Considere P = (X, L), onde X = T e L = {P_{(x,y,z)} : (x, y, z) ∈ T }. Vamos mostrar que P satisfaz os axiomas A0, A1 e A2 da Definição 26.

Para demonstrarmos que P satisfaz o axioma A0, tome F = {(1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 1)} ⊆ X e seja L = P_{(x,y,z)} ∈ L, com (x, y, z) ∈ X, qualquer. Se (x, y, z) possui no máximo uma componente nula, é fácil verificar que existem pelo menos dois elementos de {(1, 0, 0), (0, 1, 0), (0, 0, 1)} ⊂ F que não pertencem a P_{(x,y,z)} = L, ou seja, temos |L ∩ F | ≤ 2. Se (x, y, x) possui duas componentes nulas, então temos que (x, y, z) só pode ser igual a (1, 0, 0) ou (0, 1, 0) ou (0, 0, 1). Nos três casos é fácil verificar que somente (x, y, z) e (1, 1, 1) não pertencem a P_{(x,y,z)} = L, ou seja, vale |L ∩ F | = 2. Desta forma, temos que para todo L ∈ L vale |L ∩ F | ≤ 2, o que implica que P satisfaz o axioma A0.

Para mostrarmos que P satisfaz os axiomas A1 e A2, basta verificarmos que, para quaisquer (x, y, z), (x′, y′, z′) ∈ T = X distintos, temos

(44) |{(x′′, y′′, z′′) ∈ T: xx′′ + yy′′ + zz′′ = x′x′′ + y′y′′ + z′z′′ = 0}| = 1.

De fato, se L e L′ são duas linhas distintas de P, temos, pela definição de L, que existem (x, y, z), (x′, y′, z′) ∈ T distintos tais que T = P_{(x,y,z)} e T′ = P_{(x′,y′,z′)}. Portanto, temos que (44) implica

|L ∩ L′| = |P_{(x,y,z)} ∩ P_{(x′,y′,z′)}| =
|{(x′′, y′′, z′′) ∈ T: xx′′ + yy′′ + zz′′ = x′x′′ + y′y′′ + z′z′′ = 0}| = 1,

o que prova que P satisfaz axioma A1 da Definição 26. Observe também que (44) implica L ≠ L′ — pois temos |L ∩ L′| = 1 < |L|, |L′|. Desta forma, não é difícil verificar que se (44) vale, então

(45)  \begin{matrix}(x, y, z), (x′, y′, z′) ∈ T & & P_{(x,y,z)}, P_{(x′,y′,z′)} ∈ L \\ e & ⟺ & e \\ (x, y, z) ≠ (x′, y′, z′) & & P_{(x,y,z)} ≠ P_{(x′,y′,z′)} \end{matrix}

também vale.

Por outro lado, observe que, para qualquer ponto (x, y, z) de P, temos que o conjunto formado pelas linhas que passam por (x, y, z) é dado por {L ∈ L: (x, y, z) ∈ L} = {P_{(x′,y′,z′)} : (x′, y′, z′) ∈ T e xx′ + yy′ + zz′ = 0}. Desta forma, se (x, y, z) e (x′, y′, z′) são dois pontos dintintos de P, temos que (44) implica

|{L′′ ∈ L: (x, y, z) ∈ L′′} ∩ {L′′ ∈ L: (x′, y′, z′) ∈ L′′}| =
|{P_{(x′′,y′′,z′′)} ∈ L: xx′′ + yy′′ + zz′′ = x′x′′ + y′y′′ + z′z′′ = 0}| =
|{(x′′, y′′, z′′) ∈ T: xx′′ + yy′′ + zz′′ = x′x′′ + y′y′′ + z′z′′ = 0}| = 1,

onde a última igualdade decorre de (45). Portanto, temos que (44) também implica que P satisfaz o axioma A2 da Definição 26.

Para provarmos (44), considere (x, y, z), (x′, y′, z′) ∈ T, com (x, y, z) ≠ (x′, y′, z′), quaisquer. Não é difícil verificar que, para qualquer escolha de (x, y, z) e (x′, y′, z′), temos que não existe λ ∈ K (λ ≠ 0) tal que (x, y, z) = λ(x′, y′, z′). Ou seja, se olharmos para as triplas (x, y, z) e (x′, y′, z′) como vetores de dimensão 3 sobre o corpo K, temos que eles são linearmente independentes. Desta forma, temos que a matriz

(46)  ( \begin{matrix}x & y & z \\ x′ & y′ & z′ \end{matrix} )

possui posto^{2} 2.

2Estamos considerando independência linear e posto sobre o corpo K.

Vamos, agora, olhar para as colunas da matriz em (46) como vetores de dimensão 2. Como três vetores em um espaço de dimensão 2 são obrigatoriamente linearmente dependentes, temos que existem x′′, y′′, z′′ ∈ K, não todos iguais a 0, tais que

(47)  x′′(x, x′) + y′′(y, y′) + z′′(z, z′) = (0, 0).

Observe que se escrevermos as coordenadas separadamente, temos xx′′ + yy′′ + zz′′ = x′x′′ + y′y′′ + z′z′′ = 0.

Por outro lado, como o posto da matriz em (46) é 2, temos que existem duas colunas linearmente independentes. Suponha, por exemplo, que estas colunas sejam (x, x′) e (y, y′). Isto significa que, para qualquer vetor (u, v) ∈ K^{2}, a equação x′′(x, x′) + y′′(x, x′) = (u, v) possui uma única solução. Em outras palvras, dado o valor de z′′, temos que os valores de x′′ e y′′ são determinados de forma única. Assim, temos que todas as soluções de (47) são da forma λ(x′′, y′′, z′′) com λ ∈ K\{0}. Não é difícil verificar que exatamente uma destas possíveis soluções pertence a T, o que prova (44).

Temos, portanto, que P é um plano projetivo finito. Como é fácil verificar que

|X| = |T | = |{(1, x, y): x, y ∈ K}| + |{(0, 1, x): x ∈ K}|

+ |{(0, 0, 1)}| = n^{2} + n + 1

temos, pelo item 2 da Proposição 29, que a única ordem possível para P é dada por n. □

APÊNDICE B Um Limitante para Grandes Desvios

Neste apêndice enunciamos e provamos parte do Teorema 2.5 de McDiarmid [14]. Este resultado, cujo enunciado segue abaixo, nos fornece uma desigualdade exponencial para a probabilidade de grandes desvios de uma somatória de variáveis aleatórias independentes.

Teorema 31. Sejam X_{1}, …, X_{n} variáveis aleatórias independentes e suponha que, para todo 1 ≤ k ≤ n, existam constantes a_{k} e b_{k} tais que a_{k} ≤ X_{k} ≤ b_{k}. Considere S_{n} = ∑_{k=1}^{n} X_{k} e μ = E(S_{n}). Então, para todo t ≥ 0, temos

Pr{S_{n} ≥ μ + t} ≤ e^{−2t^{2}/ ∑_{k=1}^{n}(b_{k}−a_{k})^{2}}.

Para demonstrarmos o Teorema 31, precisaremos de dois lemas auxiliares. Este primeiro lema é extraído de Hoeffding [9].

Lema 32. Seja X uma variável aleatória satisfazendo E(X) = 0 e a ≤ X ≤ b para duas constantes a e b. Então, para todo h > 0, temos

E(e^{hX}) ≤ e^{\frac{1}{8} h^{2}(b−a)^{2}}.

Demonstração: Como e^{hx} é uma função convexa de x, temos que, para todo a ≤ x ≤ b, vale

e^{hx} ≤ \frac{x − a}{b − a}e^{hb} + \frac{b − x}{b − a}e^{ha}.

Portanto, temos

E(e^{hX}) ≤ \frac{b}{b − a}e^{ha} − \frac{a}{b − a}e^{hb} = (1 − p)e^{−py} + pe^{(1−p)y}

= e^{−py}(1 − p + pe^{y}) = e^{f(y)},

onde p = −a/(b − a), y = (b − a)h e f(x) = −px + ln(1 − p + pe^{x}). Mas observe que

f′(x) = −p + \frac{pe^{x}}{(1 − p) + pe^{x}} = −p + \frac{p}{p + (1 − p)e^{−x}}

e

f′′(x) = \frac{p(1 − p)e^{−x}}{[p + (1 − p)e^{−x}]^{2}} ≤ \frac{1}{4}

— pois a média geométrica é limitada superiormente pela média aritmética.

44 B. UM LIMITANTE PARA GRANDES DESVIOS

Como f(0) = f′(0) = 0, temos, pelo teorema de Taylor, que vale

f(y) ≤ \frac{1}{8}y^{2} = \frac{1}{8}(b − a)^{2}h^{2},

o que fornece a desigualdade desejada. □ O próximo lema enuncia a conhecida desigualdade de Markov. Lema 33. Seja X uma variável aleatória não-negativa. Então Pr{X ≥

t} ≤ E(X)/t para todo t > 0.

Demonstração: Suponha que X esteja definida sobre o espaço de probabilidade Ω e defina Ω_{t} := {ω ∈ Ω: X(ω) ≥ t}. Observando que

E(X) = ∑_{ω∈Ω} X(ω) Pr(ω) ≥ ∑_{ω∈Ω_{t}} t Pr(ω) = t ∑_{ω∈Ω_{t}} Pr(ω) = t Pr{X ≥ t},

o resultado segue. □

Demonstração do Teorema 31: Temos, pelo Lema 32, que para todo h > 0 vale

E(e^{h(S_{n}−μ)}) = E( ∏_{k=1}^{n} e^{h[X_{k}−E(X_{k})]}) = ∏_{k=1}^{n} E(e^{h[X_{k}−E(X_{k})]})

≤ e^{\frac{1}{8} h^{2} ∑_{k=1}^{n}(b_{k}−a_{k})^{2}}.

Pelo Lema 33, temos Pr{S_{n} − μ ≥ t} = Pr{e^{h(S_{n}−μ)} ≥ e^{ht}} ≤ e^{−ht}E(e^{h(S_{n}−μ)})

≤ e^{−ht+ \frac{1}{8} h^{2} ∑_{k=1}^{n}(b_{k}−a_{k})^{2}}.

Tomando h = 4t/ ∑_{k=1}^{n}(b_{k} − a_{k})^{2}, o resultado segue. □

APÊNDICE C Grafos Expansores e Árvores Pequenas

Neste apêndice enunciamos e demonstramos um resultado que estabelece uma condição suficiente para que um grafo contenha cópias de árvores de grau máximo limitado. O teorema que segue abaixo, bem como a sua demonstração, são retirados de Friedman e Pippenger [7].

Teorema 34. Sejam d e n inteiros dados. Se H é um grafo não-vazio tal que, para todo X ⊆ V (H) com |X| ≤ 2n − 2, vale

|Γ_{H}(X)| ≥ (d + 1)|X|,

então H contém uma cópia de toda árvore T com v(T) ≤ n e Δ(T) ≤ d.

Antes de demonstrarmos o Teorema 34, vamos introduzir algumas definições. Se T é uma árvore e H é uma grafo, chamaremos a função f: V (T) ↦ V (H) de imersão de T em H se f é injetora e f(v) e f(w) são adjacentes imersão em H sempre que v e w são adjacentes em T. Chamaremos uma árvore árvore pequena T de pequena se v(T) ≤ n e Δ(T) ≤ d, onde n e d são constantes fixadas nas condições do enunciado do Teorema 34. Chamaremos um grafo H de grafo expansor expansor se, para todo X ⊆ V (H) com |X| ≤ 2n − 2, vale

|Γ_{H}(X)| ≥ (d + 1)|X|.

Seja f uma imersão de uma árvore T em um grafo H. Se x ∈ V (H),

definimos J_{f} (x), B_{f} (x)

J_{f}(x) := \{ \begin{matrix}d_{T} (f^{−1}(x)), & se x ∈ f(V (T)) \\ 0, & caso contrário \end{matrix} e B_{f}(x) := d − J_{f}(x).

Se X ⊆ V (H), definimos A_{f} (X), B_{f} (X), C_{f} (X)

A_{f}(X) := |Γ_{H}(X)\f(V (T))|, B_{f}(X) := ∑_{x∈X} B_{f}(x) e

C_{f}(X) := A_{f}(X) − B_{f}(X).

Os seguintes lemas também serão necessários para a demonstração do Teorema 34.

Lema 35. Suponha que sejam dados um grafo expansor H, uma árvore pequena T, uma árvore S ⊂ T obtida de T pela remoção de uma folha qualquer e uma imersão f de S em H. Se X ⊆ V (H) é tal que |X| ≤ 2n−2 e C_{f}(X) = 0, então temos |X| ≤ n − 1.

Demonstração: Como H é um grafo expansor e |X| ≤ 2n − 2, temos

|Γ_{H}(X)| ≥ (d + 1)|X|.

Como T é uma árvore pequena e a árvore S é obtida de T pela remoção de uma folha, temos v(S) ≤ n − 1 e assim

(48)  A_{f}(X) = |Γ_{H}(X)\f(V (S))| ≥ (d + 1)|X| − (n − 1).

Por outro lado, para todo x ∈ X temos J_{f}(x) ≥ 0, o que implica B_{f}(x) ≤ d. Desta forma, temos

(49)  B_{f}(X) ≤ d|X|.

Como C_{f}(X) = 0, temos A_{f}(X) = B_{f}(X) e, juntamente com (48) e (49), temos |X| ≤ n − 1. □

Lema 36. Suponha que sejam dados um grafo H, uma árvore T e uma imersão f de T em H. Então a função C_{f} é submodular, isto é,

C_{f}(X ∪ Y) + C_{f}(X ∩ Y) ≤ C_{f}(X) + C_{f}(Y)

para quaisquer X, Y ⊆ V (H).

Demonstração: Como B_{f}(X) é definido por uma soma sobre os elementos de X, para todo X ⊆ V (H), temos que B_{f} é modular, ou seja,

B_{f}(X ∪ Y) + B_{f}(X ∩ Y) = B_{f}(X) + B_{f}(Y)

para quaisquer X, Y ⊆ V (H).

Observando que C_{f}(X) = A_{f}(X) − B_{f}(X) para todo X ⊆ V (H), temos que basta provar que A_{f} é submodular. Mas note que isto é uma conseqüência imediata das relações Γ_{H}(X∪Y) = Γ_{H}(X)∪Γ_{H}(Y) e Γ_{H}(X∩Y) ⊆ Γ_{H}(X) ∩ Γ_{H}(Y), onde X e Y são subconjuntos quaisquer de V (H). □

Lema 37. Suponha que sejam dados um grafo expansor H, uma árvore pequena T, uma árvore S ⊂ T obtida de T pela remoção de uma folha qualquer e uma imersão f de S em H satisfazendo C_{f}(X) ≥ 0 para todo X ⊆ V (H) com |X| ≤ 2n − 2. Se X, Y ⊆ V (H) são tais que |X|, |Y | ≤ n − 1 e C_{f}(X) = C_{f}(Y) = 0, então temos |X ∪ Y | ≤ n − 1 e C_{f}(X ∪ Y) = 0.

Demonstração: Como |X ∪ Y |, |X ∩ Y | ≤ 2n − 2 temos, pela hipótese do enunciado, que vale C_{f}(X ∪ Y), C_{f}(X ∩ Y) ≥ 0. Pelo Lema 36, temos C_{f}(X ∪ Y) ≤ C_{f}(X ∪ Y) + C_{f}(X ∩ Y) ≤ C_{f}(X) + C_{f}(Y) = 0. Portanto, temos C_{f}(X ∪ Y) = 0. O Lema 35 implica |X ∪ Y | ≤ n − 1. □

Em posse das definições e dos lemas listados acima, podemos finalmente demonstrar o Teorema 34.

Demonstração do Teorema 34: Suponha que seja dado um grafo H nas condições do enunciado. Vamos mostrar, por indução em v(T), que, para toda árvore pequena T, existe uma imersão f de T em H satisfazendo C_{f}(X) ≥ 0 para todo X ⊆ V (H) com |X| ≤ 2n − 2.

• Caso 1: v(T) = 1. Como H é um grafo não-vazio, temos que existe uma imersão f de T em H. Vamos mostrar que C_{f}(X) ≥ 0 para todo X ⊆ V (H) com |X| ≤ 2n − 2.

Suponha, então, X ⊆ V (H) com |X| ≤ 2n − 2. Como H é expansor, temos

|Γ_{H}(X)| ≥ (d + 1)|X|.

Como f(V (T)) corresponde a apenas um vértice de H, temos

A_{f}(X) = |Γ_{H}(X)\f(V (T))| ≥ d|X|.

Por outro lado, temos J_{f}(x) = 0 para todo x ∈ V (H), o que implica

B_{f}(X) = d|X|.

Portanto, temos C_{f}(X) = A_{f}(X) − B_{f}(X) ≥ 0.

• Caso 2: v(T) > 1. Suponha que a hipótese de indução valha para os valores menores que v(T). Sejam S ⊂ T obtido pela remoção de uma folha v de T e w ∈ V (T) o único vértice vizinho de v em T. Pela hipótese de indução, temos que existe uma imersão f de S em H satisfazendo C_{f}(X) ≥ 0 para todo X ⊆ V (H) com |X| ≤ 2n−2.

Considere G o conjunto de imersões de T em H que são extensões de f e seja Y = Γ_{H}(f(w))\f(V (S)). Observe que, para todo g ∈ G, a função g ↦ g(v) é claramente uma bijeção entre G e Y. Vamos mostrar que existe g ∈ G tal que C_{g}(X) ≥ 0 para todo X ⊆ V (H) com |X| ≤ 2n − 2.

Suponha, por absurdo, que não exista g ∈ G tal que C_{g}(X) ≥ 0 para todo X ⊆ V (H) com |X| ≤ 2n − 2. Então, para todo g ∈ G, existe um conjunto X_{g} ⊆ V (H) com |X_{g}| ≤ 2n − 2 tal que C_{g}(X_{g}) < 0. Por outro lado, temos C_{f}(X_{g}) ≥ 0 para todo g ∈ G. Como g(V (T)) = f(V (S))∪g(v), temos, para todo X ⊆ V (H) com |X| ≤ 2n − 2 e todo g ∈ G,

A_{g}(X) = A_{f}(X) − I(g(v), Γ_{H}(X)),

onde I(z, Z) é 1 se z ∈ Z e 0 no caso contrário. Como E(T) = E(S) ∪ {{w, v}}, temos

B_{g}(X) = B_{f}(X) − I(f(w), X) − I(g(v), X).

Desta forma, temos

C_{g}(X) = C_{f}(X) − I(g(v), Γ_{H}(X)) + I(f(w), X) + I(g(v), X).

Observe que, para todo g ∈ G, temos C_{g}(X_{g}) < 0 e C_{f}(X_{g}) ≥ 0, o que implica que temos obrigatoriamente C_{f}(X_{g}) = 0, I(g(v), Γ_{H}(X_{g})) = 1, I(f(w), X_{g}) = 0 e I(g(v), X_{g}) = 0. Desta forma temos que, para todo g ∈ G, vale C_{f}(X_{g}) = 0, g(v) ∈ Γ_{H}(X_{g}), f(w) ∉ X_{g} e g(v) ∉ X_{g}.

Como, para todo g ∈ G, temos C_{f}(X_{g}) = 0 e |X_{g}| ≤ 2n − 2, o Lema 35 implica |X_{g}| ≤ n − 1. Agora considere o conjunto

X^{∗} = ⋃_{g∈G} X_{g}.

Vamos mostrar que C_{f}(X^{∗}) = 0 e |X^{∗}| ≤ n−1. De fato, se |G| = 0 não há o que provar. Se |G| ≥ 1, o resultado segue por indução usando o Lema 37.

Agora considere X′ = X^{∗} ∪ {f(w)}. Observe que, por termos |X′| ≤ n e pela escolha de f, vale C_{f}(X′) ≥ 0. Mas como g(v) ∈ Γ_{H}(X_{g}) para todo g ∈ G, temos Y ⊆ Γ_{H}(X^{∗}), o que implica

A_{f}(X′) = A_{f}(X^{∗}).

Observe que, pelo fato de termos f(w) ∉ X_{g} para todo g ∈ G, temos f(w) ∉ X^{∗}, o que implica

B_{f}(X′) = B_{f}(X^{∗}) + B_{f}(f(w)).

Como T é pequena, temos que w possui grau menor ou igual d em T e, portanto, grau menor ou igual a d − 1 em S. Desta forma temos J_{f}(f(w)) ≤ d − 1, o que implica B_{f}(f(w)) ≥ 1. Portanto, temos

C_{f}(X′) = A_{f}(X′) − B_{f}(X′) = A_{f}(X^{∗}) − B_{f}(X^{∗}) − B_{f}(f(w)) < C_{f}(X^{∗}) = 0,

o que é um absurdo.

□

APÊNDICE D Algumas Relações entre EH e EH^{var}

1. Introdução

O nosso objetivo neste apêndice consiste no estudo de algumas relações entre as classes EH e EH^{var}. O primeiro resultado que apresentamos nos mostra como é possivel obter os grafos de uma classe EH em uma classe EH^{var}.

Teorema 38. Seja G um conjunto de grafos qualquer. Então EH(G) ⊆ EH^{var}(G ∪ {K^{2}, I^{2}}).

Um problema que decorre do estudo que realizamos no Capítulo 2 consiste em saber se a inclusão do Teorema 38 é própria. O segundo resultado deste apêndice implica que para o menor caso possível, onde tomamos G = {K^{1}}, a inclusão no Teorema 38 não é própria.

Teorema 39. EH({K^{1}}) = EH^{var}({K^{1}, K^{2}, I^{2}}).

Curiosamente, o terceiro resultado que apresentamos neste apêndice implica que se G for composto pelo K^{1} e por algum grafo não pertencente a EH({K^{1}}) então a inclusão no Teorema 38 é própria.

Teorema 40. Para todo grafo G ∉ EH({K^{1}}) temos EH({K^{1}, G}) ⊂ EH^{var}({K^{1}, K^{2}, I^{2}, G}).

O último resultado deste apêndice fornece uma caracterização diferente para os grafos pertencentes à classe EH({K^{1}}). Vale mencionar que esta classe é equivalente à classe dos grafos simples definida em Erdős e Hajnal [5].

Teorema 41. Um dado grafo G pertence a EH({K^{1}}) se e somente se G não possui um subgrafo induzido isomorfo a P^{4}.

O restante deste apêndice está basicamente dividido em quatro seções, que trazem as demonstrações dos Teoremas 38, 39, 40 e 41, respectivamente.

2. A prova do Teorema 38

Para provarmos o Teorema 38 precisamos de um lema auxiliar. Salientamos que o lema listado abaixo também é utilizado nas seções subseqüentes deste apêndice.

Lema 42. Seja G um conjunto de grafos qualquer. Se G ∈ EH(G) e G′ ∈ EH^{var}(G) então existem i, i′ ∈ ℕ tais que G ∈ EH_{i}(G) e G′ ∈ EH_{i′}^{var}(G). Ademais, se H ∈ EH(G), H′ ∈ EH^{var}(G) e v ∈ V (G′) então K(G, H), I(G, H) ∈ EH(G) e G′(v → H′) ∈ EH^{var}(G).

50 D. ALGUMAS RELAÇÕES ENTRE EH E EH^{var}

Demonstração: Seja G nas condições do enunciado. Primeiramente vamos mostrar que para todo G ∈ EH(G) existe i ∈ ℕ tal que G ∈ EH_{i}(G). De fato, suponha, por contradição, que exista G ∈ EH(G) tal que G ∉ EH_{i}(G) para todo i ∈ ℕ. Observe que isto é um absurdo, pois EH(G) é definida como a menor classe de grafos que contém EH_{i}(G) para todo i ∈ ℕ. Analogamente, temos que para todo G′ ∈ EH^{var}(G) existe i′ ∈ ℕ tal que G′ ∈ EH_{i′}^{var}(G).

Agora, considere G, H, G′, H′ e v nas condições do enunciado e sejam i, j, i′, j′ ∈ ℕ tais que G ∈ EH_{i}(G), H ∈ EH_{j}(G), G′ ∈ EH_{i′}^{var}(G) e H′ ∈ EH_{j′}^{var}(G). Defina k := max{i, j} e k′ := max{i′, j′}. Temos, então

{K(G, H), I(G, H)} ⊆ EH_{k+1}(G) ⊆ EH(G)

e

G′(v → H′) ∈ EH_{k′+1}^{var}(G) ⊆ EH^{var}(G).
□

Em posse do Lema 42, podemos demonstrar o Teorema 38.

Demonstração do Teorema 38: Seja G nas condições do enunciado. Primeiramente vamos mostrar, por indução em i, que EH_{i}(G) ⊆ EH^{var}(G ∪ {K^{2}, I^{2}}) para todo i ∈ ℕ.

• Caso 1 (i = 0): Neste caso, temos EH_{0}(G) = G ⊆ EH_{0}^{var}(G ∪{K^{2}, I^{2}}) ⊆ EH^{var}(G ∪ {K^{2}, I^{2}}).

• Caso 2 (i > 0): Suponha que a hipótese de indução valha para os valores menores que i e seja G ∈ EH_{i}(G) qualquer. Vamos mostrar que G ∈ EH^{var}(G ∪ {K^{2}, I^{2}}).

Pela definição de EH_{i}(G) com i > 0 temos que existe uma partição própria {V_{1}, V_{2}} de V (G) tal que G[V_{1}], G[V_{2}] ∈ ⋃_{j<i} EH_{j}(G) e G = K(G[V_{1}], G[V_{2}]) ou G = I(G[V_{1}], G[V_{2}]).

Agora considere v_{1}, v_{2} ∉ V (G) com v_{1} ≠ v_{2} quaisquer. Se G = I(G[V_{1}], G[V_{2}]), tome H = I^{2} = ({v_{1}, v_{2}}, ∅); caso contrário, tome H = K^{2} = ({v_{1}, v_{2}}, {{v_{1}, v_{2}}}). Observe que em ambos os casos temos H ∈ {K^{2}, I^{2}} ⊆ EH_{0}^{var}(G ∪{K^{2}, I^{2}}) ⊆ EH^{var}(G ∪{K^{2}, I^{2}}). Observe também que

(50)  G = [H(v_{1} → V_{1})](v_{2} → V_{2}).

Pela hipótese de indução temos G[V_{1}], G[V_{2}] ∈ EH^{var}(G∪{K^{2}, I^{2}}). Aplicando duas vezes o Lema 42 em (50), temos G ∈ EH^{var}(G ∪ {K^{2}, I^{2}}).

Como EH(G) é a menor classe de grafos que contém EH_{i}(G) para todo i ∈ ℕ, segue que EH(G) ⊆ EH^{var}(G ∪ {K^{2}, I^{2}}). □

3. A prova do Teorema 39

Considere o seguinte lema. Lema 43. EH({K^{1}}) ⊇ EH^{var}({K^{1}, K^{2}, I^{2}}). Observe que o lema acima juntamente com o Teorema 38 implicam o

Teorema 39. Mas, antes de provarmos o Lema 43, vamos enunciar e provar alguns lemas auxiliares.

Lema 44. Se G ∈ EH^{var}({K^{1}, K^{2}, I^{2}})\{K^{1}, K^{2}, I^{2}} então existem G_{1}, G_{2} ∈ EH^{var}({{K^{1}, K^{2}, I^{2}}) com v(G_{1}), v(G_{2}) > 1 e v ∈ V (G_{1}) tais que G = G_{1}(v → G_{2}).

Demonstração: Lembrando que EH_{0}^{var}({K^{1}, K^{2}, I^{2}}) = {K^{1}, K^{2}, I^{2}} basta mostrarmos, por indução em i, que a afirmação do enunciado vale para todo G ∈ EH_{i}^{var}({K^{1}, K^{2}, I^{2}})\{K^{1}, K^{2}, I^{2}} com i ≥ 1.

• Caso 1 (i = 1):

Seja G ∈ EH_{1}^{var}({K^{1}, K^{2}, I^{2}})\{K^{1}, K^{2}, I^{2}} qualquer. Pela definição de EH_{1}^{var}({K^{1}, K^{2}, I^{2}}) existem G_{1}, G_{2} ∈ EH_{0}^{var}({{K^{1}, K^{2}, I^{2}}) = {{K^{1}, K^{2}, I^{2}} e v ∈ V (G_{1}) tais que G = G_{1}(v → G_{2}). Observe que G_{1}, G_{2} ≠ K^{1}, pois caso contrário, teríamos G = K^{1}(v → G_{2}) = G_{2} ou G = G_{1}(v → K^{1}) = G_{1}. Observe que em ambos os casos teríamos ⊆ {K^{1}, K^{2}, I^{2}}, contrariando a escolha de G.

• Caso 2 (i > 1):

Suponha que a hipótese de indução valha para os valores menores que i e seja G ∈ EH_{i}^{var}({K^{1}, K^{2}, I^{2}})\{K^{1}, K^{2}, I^{2}}.

Observe que, pela definição de EH_{i}^{var}({K^{1}, K^{2}, I^{2}}), temos que existem G_{1}, G_{2} ∈ ⋃_{j<i} EH_{j}^{var}({{K^{1}, K^{2}, I^{2}}) e v ∈ V (G_{1}) tais que G = G_{1}(v → G_{2}). Se v(G_{1}), v(G_{2}) > 1 não há o que fazer. Caso contrário, temos G = K^{1}(v → G_{2}) = G_{2} ou G = G_{1}(v → K^{1}) = G_{1}. Como G ∉ {K^{1}, K^{2}, I^{2}} o resultado segue, em ambos os casos, pela hipótese de indução.

□

Lema 45. Se G ∈ EH^{var}({K^{1}, K^{2}, I^{2}}) com v(G) > 1 então existe uma partição própria {V_{1}, V_{2}} de V (G) tal que G[V_{1}], G[V_{2}] ∈ EH^{var}({K^{1}, K^{2}, I^{2}}) e G = K(G[V_{1}], G[V_{2}]) ou G = I(G[V_{1}], G[V_{2}]).

Demonstração: Vamos mostrar, por indução em v(G), que a afirmação do enunciado vale para todo G ∈ EH^{var}({K^{1}, K^{2}, I^{2}}) com v(G) > 1.

• Caso 1 (v(G) = 2): Decorre de G ∈ {K(K^{1}, K^{1}), I(K^{1}, K^{1})} e do fato de termos K^{1} ∈

EH^{var}({K^{1}, K^{2}, I^{2}}).

• Caso 2 (v(G) > 2): Suponha que a hipótese de indução valha para os valores menores que v(G). Observe que G ∉ {K^{1}, K^{2}, I^{2}} e, pelo Lema 44, temos que existem G_{1}, G_{2} ∈ EH^{var}({{K^{1}, K^{2}, I^{2}}) com v(G_{1}), v(G_{2}) > 1 e v ∈ V (G_{1}) tais que G = G_{1}(v → G_{2}). Como claramente 1 < v(G_{1}) < v(G) temos, pela hipótese de indução, que existe uma partição própria {V′_{1}, V′_{2}} de V (G_{1}) tal que G_{1}[V′_{1}], G_{1}[V′_{2}] ∈ EH^{var}({K^{1}, K^{2}, I^{2}}) e G_{1} = K(G_{1}[V′_{1}], G_{1}[V′_{2}]) ou G_{1} = I(G_{1}[V′_{1}], G_{1}[V′_{2}]).

Se v ∈ V′_{1}, faça G′ = G_{1}[V′_{1}](v → G_{2}) e G′′ = G_{1}[V′_{2}]; caso contrário, faça G′ = G_{1}[V′_{1}] e G′′ = G_{1}[V′_{2}](v → G_{2}). Observe que em ambos os casos o Lema 42 garante G′, G′′ ∈ EH^{var}({K^{1}, K^{2}, I^{2}}). Observe também que temos G = K(G′, G′′) ou G = I(G′, G′′). Ou seja, se tomarmos V_{1} = V (G′) e V_{2} = V (G′′) temos que {V_{1}, V_{2}} é uma partição própria de V (G) tal que G[V_{1}], G[V_{2}] ∈ EH^{var}({K^{1}, K^{2}, I^{2}}) e G = K(G[V_{1}], G[V_{2}]) ou G = I(G[V_{1}], G[V_{2}]).

□

Em posse dos lemas listados acima, podemos demonstrar o Lema 43.

Demonstração do Lema 43: Vamos mostrar, por indução em v(G), que se G ∈ EH^{var}({K^{1}, K^{2}, I^{2}}) então G ∈ EH({K^{1}}).

• Caso 1 (v(G) = 1): Neste caso, temos G = K^{1} ∈ EH_{0}(K^{1}) ⊆ EH({K^{1}}).

• Caso 2 (v(G) > 1): Suponha que a hipótese de indução valha para os valores menores que v(G). Pelo Lema 45 temos que existe uma partição própria {V_{1}, V_{2}} de V (G) tal que G[V_{1}], G[V_{2}] ∈ EH^{var}({K^{1}, K^{2}, I^{2}}) e G = K(G[V_{1}], G[V_{2}]) ou G = I(G[V_{1}], G[V_{2}]). Observe que v(G[V_{1}]) = |V_{1}| < v(G) e v(G[V_{2}]) = |V_{2}| < v(G). Pela hipótese de indução temos G[V_{1}], G[V_{2}] ∈ EH({K^{1}}) e, pelo Lema 42, temos

G ∈ {K(G[V_{1}], G[V_{2}]), I(G[V_{1}], G[V_{2}])} ⊆ EH({K^{1}}).

□

4. A prova do Teorema 40

Para demonstrarmos o Teorema 40 precisamos introduzir uma nova notação. Dados i ∈ ℕ e uma família de grafos G quaisquer, definimos

G_{i} G_{i} := {G ∈ G: v(G) ≤ i}. Agora considere os seguintes lemas auxiliares.

Lema 46. Sejam G um conjunto de grafos e k ∈ ℕ quaisquer. Então EH(G)_{k} ⊆ EH(G_{k}).

Demonstração: Sejam G e k nas condições do enunciado. Primeiramente vamos mostrar, por indução em i, que EH_{i}(G)_{k} ⊆ EH(G_{k}) para todo i ∈ ℕ.

• Caso 1 (i = 0): Temos claramente EH_{0}(G)_{k} = G_{k} = EH_{0}(G_{k}) ⊆ EH(G_{k}).

• Caso 2 (i > 0): Suponha que a hipótese de indução valha para os valores menores que i e seja G ∈ EH_{i}(G)_{k} qualquer — observe que v(G) ≤ k. Como EH_{i}(G)_{k} ⊆ EH_{i}(G) temos, pela definição de EH_{i}(G) com i > 0, que existe uma partição própria {V_{1}, V_{2}} de V (G) tal que G[V_{1}], G[V_{2}] ∈ ⋃_{j<i} EH_{j}(G) e G = K(G[V_{1}], G[V_{2}]) ou G = I(G[V_{1}], G[V_{2}]). Mas v(G[V_{1}]) = |V_{1}| < v(G) ≤ k e v(G[V_{2}]) = |V_{2}| < v(G) ≤ k. Portanto, pela hipótese de indução, temos G[V_{1}], G[V_{2}] ∈ ⋃_{j<i} EH_{j}(G)_{k} ⊆ EH(G_{k}). Pelo Lema 42 temos

G ∈ {K(G[V_{1}], G[V_{2}]), I(G[V_{1}], G[V_{2}])} ⊆ EH(G_{k}).

Como EH(G)_{k} é a menor família de grafos que contém EH_{i}(G)_{k} para todo i ∈ ℕ, segue que EH(G)_{k} ⊆ EH(G_{k}). □

Lema 47. Seja G um conjunto de grafos qualquer. Se G ∈ EH(G)\G então existe uma partição própria {V_{1}, V_{2}} de V (G) tal que G[V_{1}], G[V_{2}] ∈ EH(G) e G = K(G[V_{1}], G[V_{2}]) ou G = I(G[V_{1}], G[V_{2}]). Ademais, temos G ∈ EH(G_{v(G)−1}).

Demonstração: Seja G nas condições do enunciado e suponha G ∈ EH(G)\G qualquer. Como G ∈ EH(G) temos, pelo Lema 42, que existe i ∈ ℕ tal que G ∈ EH_{i}(G). Mas observe que G ∉ G = EH_{0}(G) e, portanto, temos i > 0. Pela definição de EH_{i}(G) com i > 0 temos que existe uma partição própria {V_{1}, V_{2}} de V (G) tal que G[V_{1}], G[V_{2}] ∈ ⋃_{j<i} EH_{j}(G) ⊆ EH(G) e G = K(G[V_{1}], G[V_{2}]) ou G = I(G[V_{1}], G[V_{2}]).

Como v(G[V_{1}]), v(G[V_{2}]) < v(G) temos, pelo Lema 46, que G[V_{1}], G[V_{2}] ∈ EH(G)_{v(G)−1} ⊆ EH(G_{v(G)−1}). Pelo Lema 42 segue

G ∈ {K(G[V_{1}], G[V_{2}]), I(G[V_{1}], G[V_{2}])} ⊆ EH(G_{v(G)−1}).
□

Lema 48. Seja G ∈ EH({K^{1}}) qualquer. Se V ⊆ V (G) com V ≠ ∅ então G[V] ∈ EH({K^{1}}).

Demonstração: Primeiramente vamos mostrar, por indução em i, que se G ∈ EH_{i}({K^{1}}) e V ⊆ V (G) com V ≠ ∅ então G[V] ∈ EH({K^{1}}), para todo i ∈ ℕ.

• Caso 1 (i = 0): Como EH_{0}({K^{1}}) = {K^{1}} temos que as únicas escolhas para G ∈ EH_{0}({K^{1}}) e V ⊆ V (G) com V ≠ ∅ são G = K^{1} e V = V (G). Neste caso temos G[V] = G ∈ EH({K^{1}}).

• Caso 2 (i > 0): Suponha que a hipótese de indução valha para os valores menores que i e sejam G ∈ EH_{i}({K^{1}}) e V ⊆ V (G) com V ≠ ∅ quaisquer. Vamos mostrar que G[V] ∈ EH({K^{1}}). Pela definição de EH_{i}({K^{1}}) com i > 0 temos que existe uma partição própria {V_{1}, V_{2}} de V (G) tal que G[V_{1}], G[V_{2}] ∈ ⋃_{j<i} EH_{j}({K^{1}}) e G = K(G[V_{1}], G[V_{2}]) ou G = I(G[V_{1}], G[V_{2}]). Temos dois casos possíveis:

– Caso 2.1 (V_{1} ∩ V = ∅ ou V_{2} ∩ V = ∅). Pela escolha de V e pelo fato de V_{1} e V_{2} formarem uma partição própria dos vértices de G temos que não pode ocorrer V_{1} ∩ V = ∅ e V_{2} ∩ V = ∅. Se V_{1} ∩ V = ∅ tome V′ = V_{2} e se V_{2} ∩ V = ∅ tome V′ = V_{1} — observe que temos V ⊆ V′ e V ≠ ∅. Como G[V′] ∈ ⋃_{j<i} EH_{j}({K^{1}}) temos, pela hipótese de indução, que G[V] = (G[V′])[V] ∈ EH({K^{1}}).

– Caso 2.2 (V_{1} ∩ V ≠ ∅ e V_{2} ∩ V ≠ ∅). Como G[V_{1}], G[V_{2}] ∈ ⋃_{j<i} EH_{j}({K^{1}}) temos, pela hipótese de indução, que G[V_{1} ∩ V], G[V_{2} ∩ V] ∈ EH({K^{1}}). Observando que G[V] ∈ {K(G[V_{1} ∩ V], G[V_{2} ∩ V]), I(G[V_{1} ∩ V], G[V_{2} ∩ V])} temos, pelo Lema 42, que G[V] ∈ EH({K^{1}}).

O resultado segue pelo fato de EH({K^{1}}) ser a menor família de grafos que contém EH_{i}({K^{1}}), para todo i ∈ ℕ. □

Em posse dos lemas listados acima podemos demonstrar o Teorema 40.

Demonstração do Teorema 40: Seja G nas condições do enunciado. Pelo Teorema 38 temos EH({K^{1}, G}) ⊆ EH^{var}({K^{1}, K^{2}, I^{2}, G}). Portanto, para mostrarmos que EH({K^{1}, G}) ⊂ EH^{var}({K^{1}, K^{2}, I^{2}, G}), basta provarmos que existe um grafo G′ ∈ EH^{var}({K^{1}, K^{2}, I^{2}, G})\EH({K^{1}, G}).

Considere v_{1}, v_{2} ∉ V (G) com v_{1} ≠ v_{2} e v ∈ V (G) quaisquer. Se d_{G}(v) = v(G) − 1 então defina H = ({v_{1}, v_{2}}, ∅); caso contrário faça H = ({v_{1}, v_{2}}, {{v_{1}, v_{2}}}). Tome G′ = G(v → H). Como G, H ∈ {K^{2}, I^{2}, G} ⊂ EH^{var}({K^{1}, K^{2}, I^{2}, G}) temos, pelo Lema 42, G′ ∈ EH^{var}({K^{1}, K^{2}, I^{2}, G}). Vamos mostrar que G′ ∉ EH({K^{1}, G}).

Suponha, por absurdo, que G′ ∈ EH({K^{1}, G}). Como claramente G′ ∉ {K^{1}, G} temos, pelo Lema 47, que existe uma partição própria {V_{1}, V_{2}} de V (G′) tal que G′[V_{1}], G′[V_{2}] ∈ EH({K^{1}, G}) e G′ = K(G′[V_{1}], G′[V_{2}]) ou G′ = I(G′[V_{1}], G′[V_{2}]).

Vamos mostrar primeiramente que G′[V_{1}], G′[V_{2}] ∈ EH({K^{1}}). Temos dois casos a considerar.

• Caso 1 (|V_{1}| = 1 ou |V_{2}| = 1): Suponha, sem perda de generalidade, |V_{1}| = 1 e seja v′ o único vértice pertencente a V_{1}. Observe que {v_{1}, v_{2}} ∩ V_{2} ≠ ∅ e suponha, sem perda de generalidade, que v_{2} ∈ V_{2}. Vamos mostrar que G′[V_{2}] não é isomorfo a G.

De fato, observe que G é isomorfo a G′[V (G′)\{v_{2}}] = G′[{v′}∪ V_{2}\{v_{2}}] e, portanto, temos

(51)  e(G) = e(G′[V_{2}]) + d_{G′}(v′) − d_{G′}(v_{2}).

Observe também que pela escolha de H temos

1 ≤ d_{G′}(v_{2}) ≤ v(G) − 1 = v(G′) − 2.

Como G′ = K(G′[{v′}], G′[V_{2}]) ou G′ = I(G′[{v′}], G′[V_{2}]) temos que d_{G′}(v′) = 0 ou d_{G′}(v′) = v(G′) − 1 e, portanto, vale

(52)  d_{G′}(v′) ≠ d_{G′}(v_{2}).

Aplicando (52) em (51), temos que e(G) ≠ e(G′[V_{2}]), o que prova que G e G′[V_{2}] não são isomorfos.

Agora, como |V_{2}| = v(G) > 1 temos G′[V_{2}] ∉ {K^{1}, G} e, pelo Lema 47, segue que G′[V_{2}] ∈ EH({K^{1}, G}_{v(G)−1}) = EH({K^{1}}). Observe que G′[V_{1}] é isomorfo a K^{1} ∈ EH({K^{1}}).

• Caso 2 (|V_{1}| > 1 e |V_{2}| > 1): Neste caso temos v(G′[V_{1}]), v(G′[V_{2}]) < v(G) e, pelo Lema 46, segue que G′[V_{1}], G′[V_{2}] ∈ EH({K^{1}, G})_{v(G)−1} ⊆ EH({K^{1}, G}_{v(G)−1}) = EH({K^{1}}).

Agora, como G′[V_{1}], G′[V_{2}] ∈ EH({K^{1}}) temos, pelo Lema 42, que

G′ ∈ {K(G′[V_{1}], G′[V_{2}]), I(G′[V_{1}], G′[V_{2})} ⊆ EH({K^{1}}).

Lembrando que G é isomorfo a G′[V (G′)\{v_{2}}] temos, pelo Lema 48, que G ∈ EH({K^{1}}), o que contraria a escolha de G. □

5. A prova do Teorema 41

Para demonstrarmos o Teorema 41 vamos precisar do seguinte resultado extraído de Seinsche [17].

Teorema 49. Considere um grafo G. As seguintes afirmativas são equivalentes:

(1) G não possui um subgrafo induzido isomorfo a P^{4}, o caminho com 4 vértices.

(2) Para todo X ⊆ V (G) com |X| ≥ 2 vale que G[X] não é conexo ou \overline{G}[X] não é conexo.

Na demonstração do Teorema 41 também utilizaremos o fato de que P^{4} ∉ EH({K^{1}}). De fato, como pode ser facilmente verificado, temos que o grafo P^{4} é o único grafo não pertencente a EH({K^{1}}) de ordem menor ou igual a 4.

Demonstração do Teorema 41: Primeiramente vamos provar, por indução em v(G), que se G não possui um subgrafo induzido isomorfo a P^{4} então G pertence a EH({K^{1}}).

• Caso 1 (v(G) = 1): Neste caso temos G = K^{1} ∈ EH_{0}({K^{1}}) ⊆ EH({K^{1}}).

• Caso 2 (v(G) > 1): Suponha que a hipótese de indução valha para os valores menores que v(G). Como, por hipótese, G não possui um subgrafo induzido isomorfo a P^{4} temos, pelo Teorema 49, que G ou \overline{G} não é conexo.

Se G não é conexo faça H = G, caso contrário faça H = \overline{G}. Como H não é conexo, temos que existe uma partição própria {V_{1}, V_{2}} de V (H) tal que H = I(H[V_{1}], H[V_{2}]).

Observe que G[V_{1}] e G[V_{2}] não possuem um subgrafo induzido isomorfo a P^{4} e |V_{1}|, |V_{2}| < v(G). Portanto, pela hipótese de indução temos G[V_{1}], G[V_{2}] ∈ EH({K^{1}}). Mas observe que pela escolha de H, V_{1} e V_{2} e pelo Lema 42 segue

G ∈ {K(G[V_{1}], G[V_{2}]), I(G[V_{1}], G[V_{2}])} ⊆ EH({K^{1}}).

O sentido inverso da demonstração decorre do Lema 48, juntamente com o fato de P^{4} ∉ EH({K^{1}}). □

Índice Remissivo

A_{f} (X), 45 B_{f} (X), 45 B_{f} (x), 45 C_{f} (X), 45 E(H), 7 G ⊆ H, 7 G(V → H), 15 G(v → H), 12 H[X], 8 I(G, H), 11 I^{n}, 8 J_{f} (x), 45 K(G, H), 11 K^{n}, 8 L ∩ L′, 37 P^{k}, 8 R(P, H, Π), 24 V (H), 7 [A]^{k}, 7 [A]_{i}^{j}, 7 Γ ⟶ (G, H), 8

Γ ⟶^{M} (G, H), 26

Γ ⟶^{ind} (G, H), 8

Γ ⟶^{s,i} (G, H), 8

Γ_{H}(X), 7 Γ_{H}(v), 7 r̂(G, H), 8 r̂(H), 8 r̂(n), 8 r̂_{ind}(G, H), 9 r̂_{sind}(G, H), 9 ⌈x⌉, 7 ⌊x⌋, 7 ℕ, 7 ℕ^{∗}, 7 R-satisfatível, 27 EH(G), 11 EH^{var}(G), 12 EH_{i}(G), 11 EH_{i}^{var}(G), 12 G_{i}, 53 L(P, H, X, Π), 24 ν(H), 7 \overline{G}, 7 \overline{ab}, 37 ρ_{R}(W), 18 |X|, 7 a ≪ b, 24 d_{H}(v), 7 e(H), 7 r(G, H), 8 r(H), 8 r(n), 8 r_{ind}(G, H), 9 r_{sind}(G, H), 9 v(H), 7 árvore pequena, 45 árvore, 8 adjacente, 7 arestas, 7 caminho, 8 emparelhamento, 7 folha, 8 grafo conexo, 8 grafo expansor, 45 grafo, 7 grau máximo de H, Δ(H), 7 grau mínimo de H, δ(H), 7 grau, 7 imersão, 45 isomorfismo, grafos isomorfos, 8 linhas de P, 37 ordem, 7 partição própria, 7 partição, 7 pontos de P, 37 propriedade P(P, H, ε̃, Π), 24 propriedade R(ε, ρ, G), 26 subgrafo induzido, 8 subgrafo, 7 vértices, 7 vizinhança, 7 vizinho, 7

Referências Bibliográficas

1. N. Alon, J. Pach, and J. Solymosi, Ramsey-type theorems with forbidden subgraphs, to appear.

2. V. Chvátal, Tree-complete graph ramsey numbers, Journal of Graph Theory 1 (1977), 93.

3. W. Deuber, A generalization of Ramsey’s theorem, Infinite and Finite Sets (Keszthely, 1973) (A. Hajnal, R. Rado, and V.T. Sós, eds.), Colloquia Mathematica Societatis János Bolyai, vol. 10, North-Holland, 1975, pp. 323–332.

4. R. Diestel, Graph theory, Graduate Texts in Mathematics, vol. 173, Springer-Verlag, 1996.

5. P. Erdős and A. Hajnal, Ramsey-type theorems, Discrete Applied Mathematics 25 (1989), no. 1–2, 37–52.

6. P. Erdős, A. Hajnal, and L. Pósa, Strong embeddings of graphs into colored graphs, Infinite and Finite Sets (Keszthely, 1973) (A. Hajnal, R. Rado, and V.T. Sós, eds.), Colloquia Mathematica Societatis János Bolyai, vol. 10, North-Holland, 1975, pp. 585– 595.

7. J. Friedman and N. Pippenger, Expanding graphs contain all small trees, Combinatorica 7 (1987), no. 1, 71–76.

8. R.L. Graham and V. Rödl, Numbers in Ramsey theory, Surveys in Combinatorics 1987 (C. Whitehead, ed.), London Mathematical Society Lecture Note Series, vol. 123, Cambridge University Press, Cambridge–New York, 1987, pp. 112–153.

9. Hoeffding W. J., Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (1963), 713–721.

10. X. Ke, The size Ramsey number of trees with bounded degree, Random Structures and Algorithms 4 (1993), 85–97.

11. Y. Kohayakawa, H.-J. Prömel, and V. Rödl, Induced Ramsey numbers, Combinatorica 18 (1998), no. 3, 373–404.

12. T. Łuczak and V. Rödl, On induced Ramsey numbers for graphs with bounded maximum degree, Journal of Combinatorial Theory, Series B 66 (1996), no. 2, 324–333.

13. J. Matoušek and J. Nešetřil, Invitation to discrete mathematics, Oxford.

14. C. McDiarmid, Concentration, Algorithms and Combinatorics (J. Ramirez-Alfonsin M. Habib, C. McDiarmid and B. Reed, eds.), vol. 16, Springer-Verlag, 1998, pp. 195– 248.

15. F.P. Ramsey, On a problem of formal logic, Proceedings of the London Mathematical Society 30 (1930), 264–286.

16. V. Rödl, The dimension of a graph and generalized Ramsey theorems, Master’s thesis, Charles University, 1973.

17. D. Seinsche, On a property of the class of n-colorable graphs, Journal of Combinatorial Theory, Series B 16 (1974), 191–193.