O Número Cromático de Grafos-Distância sobre

os Inteiros

Pavlos B. Konstadinidis

DISSERTAÇÃO APRESENTADA

AO

INSTITUTO DE MATEMÁTICA E ESTATÍSTICA

DA

UNIVERSIDADE DE SÃO PAULO

PARA

OBTENÇÃO DO GRAU DE MESTRE

EM MATEMÁTICA

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

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

– São Paulo, 07 de março de 2005 –

O Número Cromático de Grafos-Distância sobre os Inteiros

Este exemplar corresponde à redação final da dissertação devidamente corrigida e defendida por Pavlos B. Konstadinidis e aprovada pela comissão julgadora.

São Paulo, 07 de março de 2005.

Banca examinadora:

Prof. Dr. Yoshiharu Kohayakawa IME - USP Prof. Dr. Daniel Victor Tausk IME - USP Prof. Dr. Carlos Gustavo Tamm de Araujo Moreira IMPA

Agradecimentos

Gostaria de registrar aqui os seguintes agradecimentos (a ordem foi escolhida de maneira aleatória).

Ao Professor Yoshi, que além de ter sido um excelente orientador nesse trabalho, mostrou possuir qualidades pessoais que estão à altura da sua brilhante pesquisa.

Ao grande amigo (e professor) Daniel Victor Tausk. Aos Professores Gugu, Cristina e Jair, por terem topado

participar das bancas.

Ao Professor Elói Medina Galego, por não ter “permitido” que eu me desviasse do meu caminho.

To Professor Alby Fisher, for the friendship, the mathematics and the valuable life tips.

Ao Professor A. Mandel, pelo incentivo à distância e pelo trabalho incansável nas redes do IME - USP.

Aos Professores I. Simon, D. Knuth e P. Erdős (in memoriam).

Aos Professores Barone, Mané, Sônia, Fichmann, Possani, Deborah, Toninho, Roseli, Agozzini, Clodoaldo, Pedro Salomão, Toscano, Eduardo, Vitor, Ofélia, Verderesi, Odilon, Chaim, Newton da Costa e Pascarelli (in memoriam).

À minha família, por tudo de bom (e.g., ter me trazido ao mundo) e de ruim (e.g., é, bom, deixa prá lá...).

Aos meus velhos amigos, por continuarem a me incentivar, seja com palavras, seja pelo modo pelo qual conduziram e continuam a conduzir as suas vidas.

Aos meus novos amigos, por me lembrarem sempre qual ordem de prioridade é a correta entre matemática, comida, música e amigos.

A Felipe Fritz Braga e Eduardo Tengan, por terem demonstrado várias vezes que amizades verdadeiras existem.

À A. C. M. B., a minha futura esposa, por todo amor, carinho e paciência.

Ao bom Deus, por tudo.

Resumo

Sejam ℤ o conjunto de todos os números inteiros e ℤ^{+} = {1, 2, 3, …} o conjunto de todos os números inteiros positivos. Dado um conjunto D ⊂ ℤ^{+}, o grafo-distância sobre ℤ definido por D é o grafo sobre ℤ cujo conjunto de arestas é {{a, b} ⊂ ℤ : |a − b| ∈ D}. Esse grafo é denotado por ℤ(D) e dizemos que D é o conjunto-distância do grafo ℤ(D). Agora, se G é um grafo e κ um cardinal, uma coloração (dos vértices) de G com κ cores é uma função γ : V (G) → K, onde K é qualquer conjunto satisfazendo |K| = κ. Ainda, uma tal coloração é apropriada se γ(x) ≠ γ(y) para todos x, y ∈ V (G) que são adjacentes em G. O número cromático de G é o menor cardinal χ(G) tal que existe uma coloração apropriada de G com χ(G) cores.

A maior parte dessa dissertação consiste em uma exposição dos resultados gerais mais importantes conhecidos atualmente que tratam do cálculo de χ (ℤ(D)) para diversos tipos de conjuntos D ⊂ ℤ^{+}. Nós mostraremos ainda o cálculo de outros tipos de números cromáticos no caso de grafos-distância sobre ℤ e também algumas das propriedades dos chamados Grafos de Rado, sendo uma delas a que diz que eles são grafos-distância sobre ℤ que têm número cromático infinito.

Abstract

Let ℤ be the set of all integers and ℤ^{+} = {1, 2, 3, …} the set of all positive integers. Given a set D ⊂ ℤ^{+}, the distance-graph on ℤ defined by D is the graph on ℤ whose edge-set is {{a, b} ⊂ ℤ : |a − b| ∈ D}. This graph is denoted by ℤ(D) and we say that D is the distance-set of the graph ℤ(D). Now, if G is a graph and κ a cardinal number, then a coloring of (the vertices of) G with κ colors is a function γ : V (G) → K, where K is any set satisfying |K| = κ. Moreover, such a coloring is appropriate if γ(x) ≠ γ(y) for all x, y ∈ V (G) which are adjacent in G. The chromatic number of G is the least cardinal number χ(G) such that there is an appropriate coloring of G with χ(G) colors.

The major part of this Master’s dissertation consists of an exposition of the most important general results known to date which deal with the computation of χ (ℤ(D)) for a variety of sets D ⊂ ℤ^{+}. Moreover, we will show the computation of other types of chromatic numbers in the case of distancegraphs on ℤ and also some properties of the so-called Rado’s Graphs, including the one that says that they are distance-graphs on ℤ with an infinite chromatic number.

Sumário

Introdução .................................................................................. vii Capítulo 1. Notações e Lemas Gerais....................................... 1

1.1. Notações e Definições ................................................... 1 1.2. Lemas Gerais................................................................ 3

Capítulo 2. Sequências Especiais ............................................. 7 2.1. Progressões Aritméticas................................................ 7 2.2. Cadeias de Divisão ....................................................... 8

Capítulo 3. Outros Números Cromáticos................................. 11

Capítulo 4. Os Grafos de Rado................................................ 14

Capítulo 5. Os Resultados de Katznelson ................................ 17 5.1. Conjuntos Não-Recorrentes .......................................... 17 5.2. Sequências Lacunárias .................................................. 18 5.3. Uma Sequência k−Universal ........................................ 19

Capítulo 6. O Critério de Weiss-Furstenberg-Weyl.................. 21 6.1. Conjuntos Sindéticos .................................................... 21 6.2. Sequências de Poincaré................................................. 22 6.3. Sequências de Fermat ................................................... 30

Capítulo 7. O Resultado de Ajtai, Havas e Komlós................. 33

Capítulo 8. Os Critérios de Ruzsa, Tuza e Voigt ..................... 41 8.1. Sequências Lacunárias .................................................. 41 8.2. Sequências Subexponenciais ......................................... 43

Capítulo 9. Comentários Finais ............................................... 46

Referências Bibliográficas ........................................................... 49

Introdução

Uma área de pesquisa recente trata dos chamados grafos-distância sobre os inteiros. Dado um conjunto (finito ou infinito) D ⊂ ℤ^{+} = {1, 2, 3, …}, seja ℤ(D) = (V, E) o grafo-distância sobre ℤ definido por D, i.e., V = ℤ e E = {{a, b} ⊂ ℤ : d(a, b) = |a − b| ∈ D}. Um dos parâmetros estudado por vários pesquisadores é o número cromático de ℤ(D) que, por simplicidade, denotaremos por χ(D). Gostaríamos de ressaltar que não é nada trivial dizer quanto vale χ(D), mesmo quando D tem poucos elementos. Por exemplo, o caso |D| = 3 (o primeiro caso não-trivial) já apresenta dificuldades consideráveis e só recentemente esse caso foi resolvido completamente, por Zhu [38]. Apesar de não apresentarmos a demonstração desse resultado (que é bastante técnica), alguns comentários relevantes acerca dele serão feitos no Capítulo 9.

Agora, para algumas classes naturais de D’s se conhece χ(D) exatamente. Por exemplo, Kemnitz e Marangio [22] calculam χ(D) quando D é uma progressão artimética e Chappell [6] mostra como se calcula χ(D) quando D é uma cadeia de divisão (o que inclui o caso de D ser uma progressão geométrica). Nós mostraremos esses resultados no Capítulo 2.

Um lema simples do Capítulo 1 nos diz que se D ⊂ ℤ^{+} é um conjunto finito, então χ(D) ≤ |D| + 1. Uma questão que surge naturalmente então é: para quais D’s infinitos temos χ(D) finito? Katznelson [21] e Ruzsa et al. [30] obtiveram os critérios mais gerais conhecidos que decidem se um dado D ⊂ ℤ^{+} com |D| = ∞ satisfaz χ(D) < ∞ ou χ(D) = ∞. Em particular, em ambos os casos os autores mostraram que se uma sequência D = {d_{i}} ⊂ ℤ^{+} é lacunária, i.e., se existe um real ϵ > 0 tal que inf_{i≥1}{d_{i+1}/d_{i}} ≥ 1+ϵ, então χ(D) < ∞. Entretanto, os métodos usados por eles diferem bastante. Katznelson reduz a questão ao estudo de sistemas dinâmicos em espaços métricos compactos, enquanto que Ruzsa et al. utilizam somente construções elementares. Não obstante isso, a prova de Ruzsa et al. nos fornece uma cota superior para χ(D) (em termos de inf_{i≥1}{d_{i+1}/d_{i}}), o que não ocorre com a de Katznelson (pelo menos não diretamente), como é usual em resultados dinâmicos desse tipo. Esses critérios serão vistos detalhadamente nos Capítulos 5 (Seções 5.1 e 5.2) e 8, respectivamente. Ainda, um problema em aberto bastante interessante nessa linha foi mencionado por Ruzsa et al. e será comentado no Capítulo 9.

Um outro critério de Ruzsa et al. nos diz que se ϵ_{i} é uma sequência não-crescente de reais positivos com ϵ_{i} → 0, então existe uma sequência D = {d_{i}} ⊂ ℤ^{+} com χ(D) = ∞ que é ϵ_{i}-subexponencial, i.e., que satisfaz d_{i+1}/d_{i} ≥ 1 + ϵ_{i}, para todo i. A demonstração que os autores dão para esse resultado é curta e completamente elementar (eles acabam na verdade por construir uma tal sequência). Uma pergunta natural que aparece então é: esse resultado continua valendo quando a sequência ϵ_{i} > 0 é qualquer, i.e., não necessariamente não-crescente? Na Seção 8.2, veremos que um colorário imediato do critério acima mostra que essa pergunta tem resposta afirmativa e elementar (veja o Corolário 8.2.2). Já nos Capítulos 6 (Seções 6.1 e 6.2) e 7, nós veremos uma série de resultados que fornecerão uma segunda prova disso. Entretanto, nesse caso a prova está bem longe de ser curta e elementar! Para que o leitor tenha uma idéia, ela envolve, entre outras coisas, o Princípio da Correspondência de Furstenberg e sequências de Poincaré, uma versão do Teorema Espectral, uma demonstração de uma versão do Teorema Ergódico devida a von Neumann, o Critério de Weyl sobre sequências uniformemente distribuídas módulo 1 (que está relacionado ao Teorema de Stone-Weierstrass) e uma bela construção probabilística devida a Ajtai et al. [1]. Esse “longo” caminho foi descrito por Weiss [35]. Como mencionamos, de fato não é necessário percorrer esse caminho todo para dar uma resposta afirmativa à pergunta acima. Entretanto, os teoremas do final do Capítulo 7 nos dizem que esse caminho não foi percorrido em vão. Aqueles resultados todos serão usados para mostrar que existe um grafo-distância sobre ℤ com número cromático infinito que não contém triângulos (ou, mais geralmente, que não contém circuitos de tamanho menor ou igual a l, qualquer que seja l ≥ 3 fixado).

Na Seção 6.3, nós trataremos brevemente das sequências de Fermat, ou seja, das sequências das m-ésimas potências F_{m} = (n^{m} : n ≥ 1), m = 1, 2, . . .. Nós mencionaremos um conhecido resultado de Bergelson e Leibman [3] que, em particular, diz que todas essas sequências têm número cromático infinito e forneceremos uma demonstração, devida a Walters [34], de como o caso particular χ(F_{2}) = ∞ já segue do famoso Teorema de Van der Waerden sobre progressões aritméticas em partições finitas dos inteiros.

No Capítulo 3, nós iremos calcular outros números cromáticos, a saber, o número-aresta-cromático, o número-total-cromático, o número-aresta-escolha e o número-total-escolha de grafos-distância sobre ℤ. Um fenômeno interessante que ocorre é que, apesar de esses outros números cromáticos terem definições bem mais complicadas do que o número cromático propriamente dito, obteremos o valor exato desses números cromáticos para absolutamente todos os grafos-distância sobre ℤ (o que ainda não está nem perto de acontecer para χ(D)). Além disso, esses cálculos mostram que os grafos-distância sobre ℤ são grafos que verificam três importantes conjecturas a respeito desses outros números cromáticos. Esses resultados são devidos a Kemnitz e Marangio [23].

No Capítulo 4, nós iremos expor algumas propriedades que os chamados Grafos de Rado possuem. Esses grafos surgiram do estudo de grafos aleatórios sobre conjuntos enumeráveis infinitos. O interesse para nós é que uma dessas propriedades diz que esses grafos são grafos-distância sobre ℤ com número cromático infinito. As propriedades que mostraremos são devidas a Cameron [5] e Rado [29].

No Capítulo 9, além de fazer uma série de comentários sobre alguns dos resultados mostrados, nós também iremos incluir alguns teoremas, conjecturas e problemas que não foram mencionados nos capítulos anteriores (mas que nem por isso deixam de ter a sua importância). Por exemplo, na Seção 5.3 do Capítulo 5, nós mostraremos que, para todo k ∈ ℤ^{+}, existe uma sequência com número cromático no máximo k^{2} que é k-universal, i.e., que contém (a menos de um múltiplo) todas as sequências finitas que têm número cromático no máximo k. Esse resultado é devido a Katznelson [21]. Agora, uma conjectura proposta por Chappell [6] é ligeiramente relacionada a esse resultado e será portanto mencionada no Capítulo 9.

Na Seção 1.1 do Capítulo 1, nós estabeleceremos as notações e definições gerais que serão usadas ao longo dessa dissertação. Esses conceitos são bastante conhecidos, de forma que o leitor pode, se assim o desejar, passar diretamente para os resultados de caráter geral da Seção 1.2.

Nós abreviaremos ‘se, e somente se’ por ‘sse’ e o símbolo □ indicará o término (ou ausência) de uma demonstração. Boa leitura!

OBS: Nós gostaríamos de observar que algumas vezes a referência a um resultado indica somente a fonte que utilizamos e não que ele é devido ao autor citado. Uma consulta à referência deverá tirar qualquer dúvida que o leitor possa vir a ter nesse sentido.

PS: Nós gostaríamos de registrar aqui um agradecimento especial aos membros da banca Gugu e Tausk por colaborações importantes que foram incorporadas a esse trabalho, especialmente no que diz respeito aos Corolários 7.5 e 8.2.2 e aos resultados do final do Capítulo 7. Durante a arguição, o Gugu observou que o Corolário 7.5 segue imediatamente como consequência do Teorema 8.2.1 (veja o Corolário 8.2.2, que diz exatamente a mesma coisa que o Corolário 7.5). Ainda durante a arguição, o Gugu sugeriu um tipo de resultado (Teorema 7.12) que fizesse uso então dos resultados da Seção 6.2 e do Capítulo 7, esboçando rapidamente um argumento. Logo após a defesa, o Tausk teve a gentileza de nos entregar um texto de sua autoria com todos os detalhes da demonstração feitos. Esse teorema nos dá então uma justificativa concreta para a exposição dos interessantes resultados da Seção 6.2 e do Capítulo 7.

CAPÍTULO 1 Notações e Lemas Gerais

1.1. Notações e Definições

Nessa seção, estabeleceremos algumas notações, definições e convenções gerais que serão usadas ao longo desse trabalho. Notações e definições mais específicas aparecerão nos capítulos pertinentes.

ℕ = {0, 1, 2, 3, …} representará o conjunto de todos os números inteiros não-negativos.

ℤ^{+} = {1, 2, 3, …} representará o conjunto de todos os números inteiros positivos.

ℤ = {…, −2, −1, 0, 1, 2, …} representará o conjunto de todos os números inteiros.

ℚ = {a/b : a, b ∈ ℤ, b ≠ 0} representará o conjunto de todos os números racionais.

ℝ representará o conjunto de todos os números reais e ℂ representará o conjunto de todos os números complexos.

Para todo N ∈ ℤ^{+}, [N] = {1, 2, …, N} representará o conjunto de todos os inteiros entre 1 e N. Mais geralmente, dados L e R em ℤ com L ≤ R, denotaremos por [L, R] o intervalo inteiro entre L e R, ou seja, [L, R] = {m ∈ ℤ : L ≤ m ≤ R}. Como é usual, se a, b ∈ ℝ, [a, b] também denotará um intervalo (fechado) em ℝ, i.e., [a, b] = {x ∈ ℝ : a ≤ x ≤ b}.

O tamanho de um conjunto X será denotado por |X| ou # X e diremos que X é enumerável se |X| ≤ |ℕ|. Ainda, dado k ∈ ℕ, diremos que Y é um k-subconjunto de X se Y ⊂ X e |Y | = k.

Por grafo entenderemos um grafo simples e não-orientado. Mais precisamente, um grafo G é um par ordenado (V, E), onde V é um conjunto (qualquer) e E é um subconjunto do conjunto de todos os 2-subconjuntos de V. Sem perda de generalidade, suporemos ainda que V ∩ E = ∅. Os elementos de V serão chamados de vértices (de G) e os elementos de E serão chamados de arestas (de G).

Dado um grafo G, o conjunto dos vértices de G será denotado por V (G) e o conjunto das arestas de G será denotado por E(G), ou seja, G = (V (G), E(G)). Se x, y ∈ V (G) são tais que e = {x, y} ∈ E(G), então diremos que os vértices x e y são adjacentes (em G) ou ainda que a aresta e liga os vértices x e y (em G). Ainda, diremos que duas arestas de G são adjacentes se elas têm exatamente um vértice em comum.

Fixado um conjunto V, diremos que um grafo G é um grafo sobre V se V (G) = V. Ainda, G será dito finito (infinito ) se G é um grafo sobre um conjunto finito (infinito).

Se G é um grafo e x é um vértice de G, então o grau de x (em G) é o # {y ∈ V (G) : y é adjacente a x em G}. Note que, por definição, um grafo não tem laços (vértices que são adjacentes a si mesmos).

Diremos que um grafo G é completo se quaisquer dois vértices de G são adjacentes. Mais geralmente, diremos que G é um grafo regular se todos os vértices de G têm o mesmo grau (em G).

Diremos que um grafo H é um subgrafo de um grafo G se V (H) ⊂ V (G) e E(H) ⊂ E(G). Ainda, dado W ⊂ V (G), o subgrafo de G induzido por W é o subgrafo de G que tem como conjunto de vértices W e como conjunto de arestas {{x, y} ∈ E(G) : x, y ∈ W }. Esse grafo será denotado por [W]_{G} (ou simplesmente por [W] se o grafo G estiver subentendido).

Dado um grafo G, um conjunto I ⊂ V (G) será dito independente se E([I]_{G}) = ∅, i.e., se quaisquer dois vértices em I não são adjacentes em G. Ainda, pomos α(G) = sup{|I| : I ⊂ V (G) é independente}. Diremos que α(G) é o número de independência de G.

Diremos que dois grafos G e G′ são isomorfos se existe uma função bijetora f : V (G) → V (G′) tal que x e y são adjacentes em G sse f(x) e f(y) são adjacentes em G′. Uma tal função será chamada de um isomorfismo entre os grafos G e G′. Em geral, grafos isomorfos serão considerados como sendo o mesmo grafo.

Dados um grafo G e x, y ∈ V (G), um passeio de x a y (em G) é uma sequência finita de vértices x_{1}, x_{2}, …, x_{k−1}, x_{k} (k ≥ 1) tal que x_{1} = x, x_{k} = y e, para todo i ∈ {1, 2, …, k − 1}, {x_{i}, x_{i+1}} ∈ E(G). Diremos que um grafo G é conexo se, para quaisquer dois vértices x e y de G, existe um passeio de x a y em G. Ainda, dado um vértice z de G, a componente conexa de G que contém z é o subgrafo de G induzido pelo conjunto dos vértices w para os quais existe um passeio de z a w (em G).

Dados um grafo G, um cardinal κ e um conjunto K com |K| = κ, uma função γ : V (G) → K será chamada de uma coloração (dos vértices) de G com κ cores ou simplesmente de uma κ-coloração de G. Ainda, diremos que uma tal coloração é apropriada se γ(x) ≠ γ(y) para todos x, y ∈ V (G) que são adjacentes em G. O número cromático de G é o menor cardinal χ tal que existe uma coloração apropriada de G com χ cores. Denotaremos o número cromático de G por χ(G). Nesse trabalho, só trataremos de grafos cujo número cromático é no máximo ℵ_{0} = |ℤ| e escreveremos χ(G) < ∞ ( χ(G) = ∞) para dizer que o número cromático de G é finito (infinito). Ainda, dado k ∈ ℕ, diremos que G é k-colorível se χ(G) ≤ k.

Dado x ∈ ℝ, denotaremos por ⌊x⌋ o piso de x e por ⌈x⌉ o teto de x, i.e., ⌊x⌋ = max{k ∈ ℤ : k ≤ x} e ⌈x⌉ = min{m ∈ ℤ : x ≤ m}. Ainda, {x} denotará a parte fracionária de x, i.e., {x} = x − ⌊x⌋.

Daremos agora a definição central desse trabalho.

Definição 1.1.1. Fixado D ⊂ ℤ^{+}, o grafo-distância sobre ℤ definido por D é o grafo cujo conjunto de vértices é ℤ e cujo conjunto de arestas é {{a, b} ⊂ ℤ : |a − b| ∈ D}. Esse grafo será denotado por ℤ(D) e diremos que D é o conjunto-distância do grafo-distância ℤ(D).

Note que dois vértices são ligados por uma aresta em ℤ(D) se, e somente se, a distância entre eles pertence a D. Se D = {d_{1}, d_{2}, d_{3}, …}, então às vezes escreveremos ℤ(d_{1}, d_{2}, d_{3}, …) ao invés de ℤ(D). Em geral, listaremos os elementos de D em ordem crescente. Ainda, iremos denotar o número cromático de ℤ(D) simplesmente por χ(D). Se D = {d_{1}, d_{2}, d_{3}, …}, então ocasionalmente escreveremos χ(d_{1}, d_{2}, d_{3}, …) no lugar de χ(D).

Dados D ⊂ ℤ^{+} e n ∈ ℤ^{+}, n ≥ 2, denotaremos por ℤ_{n}(D) o grafo circulante com n vértices 0, 1, …, n − 1 e conjunto-distância D, onde i é adjacente a j sse j − i ≡ ±d (mod n) para algum d ∈ D. Note que ℤ_{n}(D) é regular e que, se D contém algum múltiplo de n, então ℤ_{n}(D) contém laços, ou seja, temos que o grafo circulante ℤ_{n}(D) é um grafo propriamente dito sse D não contém múltiplos de n. Observe que grafos-distância sobre ℤ podem ser considerados como sendo grafos circulantes infinitos. Finalmente, fixado n ∈ ℤ^{+}, n ≥ 2, por ciclo de tamanho n entenderemos qualquer grafo isomorfo ao grafo (circulante) ℤ_{n}({1}).

1.2. Lemas Gerais

Nessa seção, provaremos alguns resultados gerais que serão usados ao longo desse trabalho.

Lema 1.2.1 ([22]). Se D = {d_{1}, d_{2}, d_{3}, …} ⊂ ℤ^{+} e n ∈ ℤ^{+} é tal que n divide d_{k} para todo k, então χ(d_{1}, d_{2}, d_{3}, …) = χ(d_{1}/n, d_{2}/n, d_{3}/n, …).

Demonstração. Para todo i = 0, 1, …, n − 1, considere o conjunto V_{i} = {a ∈ ℤ : a ≡ i (mod n)}. Agora, se a e b são vértices adjacentes em ℤ(D), então |a − b| ∈ D, de onde temos que n divide |a − b| e, portanto, que a e b pertencem a um mesmo V_{j}. Assim, nenhuma aresta de ℤ(D) liga vértices que estão em diferentes V_{i}’s. Claramente, cada [V_{i}] é isomorfo a [V_{0}], que por sua vez é isomorfo a ℤ(d_{1}/n, d_{2}/n, d_{3}/n, …). Concluímos então que χ(d_{1}, d_{2}, d_{3}, …) = χ(d_{1}/n, d_{2}/n, d_{3}/n, …). □

Corolário 1.2.2. Se d_{1}, d_{2}, d_{3}, … ∈ ℤ^{+} e d = mdc(d_{1}, d_{2}, d_{3}, …), então χ(d_{1}, d_{2}, d_{3}, …) = χ(d_{1}/d, d_{2}/d, d_{3}/d, …). □

Lema 1.2.3 ([6]). Se D = {d_{1}, d_{2}, d_{3}, …} ⊂ ℤ^{+} é não-vazio, então ℤ(D) é um grafo conexo sse d = mdc(d_{1}, d_{2}, d_{3}, …) = 1. Ainda, cada componente conexa de ℤ(d_{1}, d_{2}, d_{3}, …) é isomorfa a ℤ(d_{1}/d, d_{2}/d, d_{3}/d, …).

Demonstração. Existe um passeio de um vértice k ao vértice k + 1 sse existe uma combinação inteira finita ∑ n_{i}d_{i} = 1. Isso acontece exatamente quando d = 1. Agora, dℤ é o conjunto dos vértices de ℤ(D) que estão na componente conexa que contém o vértice 0. Um isomorfismo entre essa componente conexa e ℤ(d_{1}/d, d_{2}/d, d_{3}/d, …) é dk ↦ k. Finalmente, um isomorfismo entre a componente conexa que contém o vértice 0 e a componente conexa que contém o vértice m é l ↦ l + m. □

Lema 1.2.4 ([7]). Se D ⊂ ℤ^{+} e k ∈ ℤ^{+} são tais que D não contém nenhum múltiplo de k, então χ(D) ≤ k.

Demonstração. É claro que o resultado vale para k = 1. Se k ≥ 2, então basta colorir os vértices de Z(D) módulo k, i.e., temos que a coloração γ : ℤ → {0, 1, 2, …, k − 1} definida por γ(a) = a mod k é uma k-coloração apropriada de ℤ(D). □

Lema 1.2.5 ([7]). Se D ⊂ ℤ^{+} é finito, então χ(D) ≤ |D| + 1.

Demonstração. Ponha ψ(0) = 1. Se ψ já está definida em [−i, i], então ponha ψ(i + 1) = min(ℤ^{+} \ {ψ(j) : −i ≤ j ≤ i, i + 1 − j ∈ D}) e ψ(−i − 1) = min(ℤ^{+} \ {ψ(j) : −i ≤ j ≤ i + 1, j + i + 1 ∈ D}). Não é difícil ver que ψ é uma coloração apropriada de Z(D) com |D| + 1 cores. □

Lema 1.2.6 ([12]). Se D ⊂ ℤ^{+} é finito e ℤ(D) tem uma k-coloração apropriada, então ℤ(D) tem uma k-coloração apropriada que é periódica.

Demonstração. O resultado claramente vale se D = ∅. Suponha então que |D| ≥ 1 e seja φ : ℤ → {0, 1, …, k − 1} uma k-coloração apropriada de ℤ(D). Ponha q = max(D) ≥ 1. Agora, como o número total de blocos de tamanho q formados pelos k números 0, 1, …, k − 1 é k^{q} (e portanto finito), temos que na sequência bi-infinita …, φ(−1), φ(0), φ(1), … existem dois blocos de q termos consecutivos que são idênticos e disjuntos. Podemos supor então, sem perda de generalidade, que um bloco começa em φ(0) e que o outro começa em φ(a), para algum q ≤ a ≤ qk^{q}. Temos que φ(a + j) = φ(j), para todo 0 ≤ j < q. Seja agora φ̃ : ℤ → {0, 1, …, k − 1} a coloração definida por φ̃(i) = φ(res_{a}(i)), onde res_{a}(i) ∈ {0, 1, …, a−1} é tal que i ≡ res_{a}(i) (mod a). Note que φ̃ coincide com φ em {0, 1, …, a+q−1} e que a sequência bi-infinita …, φ̃(−1), φ̃(0), φ̃(1), … é periódica de período a. Não é difícil ver que φ̃ também é uma k-coloração apropriada de ℤ(D). □

Lema 1.2.7 ([6]). Se D ⊂ ℤ^{+}, então ℤ(D) não tem nenhuma coloração apropriada com um número finito de cores que seja periódica sse D contém um múltiplo de cada inteiro positivo.

Demonstração. Da prova do Lema 1.2.4 acima, vemos que se D não contém nenhum múltiplo de um determinado k ∈ ℤ^{+}, então ℤ(D) tem uma coloração apropriada com k cores que é periódica. Na outra direção, suponha que D contém um múltiplo de cada inteiro positivo e considere uma coloração de ℤ(D) que seja periódica, digamos de período k. Como D contém pelo menos um múltiplo de k, então essa coloração não é uma coloração apropriada de ℤ(D) (já que se a distância entre dois vértices de ℤ(D) é um múltiplo de k, então eles têm a mesma cor). □

Lema 1.2.8 ([22]). Sejam dados D ⊂ ℤ^{+} e n ∈ ℤ^{+}, n ≥ 2. Se ℤ_{n}(D) não tem laços, então χ(D) ≤ χ(ℤ_{n}(D)). Ainda, se D é finito, então temos que χ(D) = χ(ℤ_{p}(D)), onde p é o período de uma coloração apropriada periódica de ℤ(D) com χ(D) cores.

Demonstração. Para ver a primeira asserção, basta notar que, se ℤ_{n}(D) não tem laços, então qualquer coloração apropriada de ℤ_{n}(D) pode ser claramente estendida a uma coloração apropriada de ℤ(D) com o mesmo número de cores e que é periódica (de período n). Para ver a segunda asserção, note que, pelo Lema 1.2.6, ℤ(D) tem de fato uma χ(D)-coloração apropriada periódica. Fixe então uma tal χ(D)-coloração de ℤ(D). Se p é o período dessa coloração, então ℤ_{p}(D) não tem laços, de onde temos que essa coloração claramente induz uma χ(D)-coloração apropriada de ℤ_{p}(D). Portanto, temos que χ(ℤ_{p}(D)) ≤ χ(D) ≤ χ(ℤ_{p}(D)). □

Lema 1.2.9 ([10]). Para qualquer grafo G e qualquer k ∈ ℤ^{+}, temos que χ(G) ≤ k sse χ(H) ≤ k para todo subgrafo finito H de G.

Demonstração. Se G é um grafo finito, então o resultado é claro. Podemos assumir então que G é infinito. Em uma direção, o resultado é imediato. Na outra direção, suponha então que qualquer subgrafo finito H de G satisfaz χ(H) ≤ k. É claro que o resultado vale se k = 1. Suponha então que k ≥ 2. Considere uma coloração γ : G → [k] como sendo um elemento de [k]^{ℤ}. Agora, para cada aresta e = {x, y} de G, considere o conjunto C(e) = {γ ∈ [k]^{ℤ} : γ(x) ≠ γ(y)}. Colocando em [k]^{ℤ} a topologia produto (cada fator [k] tem a topologia discreta), vemos que cada C(e) é um subconjunto fechado não-vazio de [k]^{ℤ}. Portanto, temos que a coleção C = {C(e) : e ∈ E(G)} é uma coleção de subconjuntos fechados não-vazios de [k]^{ℤ} que tem a propriedade da intersecção finita, i.e., toda subcoleção finita de C tem intersecção não-vazia (pois estamos assumindo que todo subgrafo finito de G é k-colorível). Como [k]^{ℤ} é compacto, então temos que ⋂ C ≠ ∅. Seja então φ ∈ ⋂ C. Pela definição de C, vemos que φ é uma k-coloração apropriada de G, de onde concluímos que χ(G) ≤ k. □

Lema 1.2.10. Se G ≠ (∅, ∅) é um grafo finito, então χ(G) ≥ |V (G)|/α(G).

Demonstração. Seja φ : V (G) → {1, 2, …, χ(G)} uma coloração apropriada de G. Note que {φ^{−1}(c) : c ∈ χ(G)} é uma partição de V (G) em χ(G) subconjuntos independentes. Assim, necessariamente pelo menos um desses subconjuntos tem tamanho pelo menos |V (G)|/χ(G), de onde concluímos que α(G) ≥ |V (G)|/χ(G), ou seja, que χ(G) ≥ |V (G)|/α(G). □

Lema 1.2.11. Sejam G_{1} e G_{2} dois grafos tais que V (G_{1}) = V (G_{2}). Se G = G_{1} ∪ G_{2} é a união de G_{1} e G_{2}, i.e., V (G) = V (G_{1}) = V (G_{2}) e E(G) = E(G_{1}) ∪ E(G_{2}), então temos que χ(G) ≤ χ(G_{1})χ(G_{2}).

Demonstração. Para i = 1, 2, seja ψ_{i} : G_{i} → {1, 2, …, χ(G_{i})} uma coloração apropriada de G_{i} com χ(G_{i}) cores. Uma coloração apropriada de G com χ(G_{1})χ(G_{2}) cores é, por exemplo, a coloração que é definida por ψ(v) = (ψ_{1}(v), ψ_{2}(v)), para todo v ∈ G. □

CAPÍTULO 2 Sequências Especiais

2.1. Progressões Aritméticas

Nessa seção, iremos mostrar como se calcula χ(D) quando D é uma progressão aritmética qualquer.

Lema 2.1.1 ([22]). Sejam a, t ∈ ℤ^{+}, k ∈ ℕ e D = {a, a + 1, …, a + t}. Se ka < t ≤ (k + 1)a, então χ(D) = k + 3 = ⌈t/a⌉ + 2 = ⌈\frac{|D|−1}{a}⌉ + 2.

Demonstração. Sejam x_{1}, x_{2}, …, x_{(k+3)a} (k + 3)a vértices consecutivos de ℤ(D). Colora esses vértices com as cores {1, 2, …, k + 3} de forma que, para todo i ∈ {1, 2, …, k + 3}, os vértices x_{(i−1)a+1}, x_{(i−1)a+2}, …, x_{ia} tenham a cor i. Estenda essa coloração a todos os vértices de ℤ(D) de maneira periódica. Essa é uma coloração apropriada de ℤ(D) e, portanto, χ(D) ≤ k + 3. Agora, seja H = [{0, 1, …, 2a + t − 1}]. Dois vértices x e y de H são adjacentes sse |x − y| ∈ D, i.e., sse a ≤ |x − y| ≤ a + t. Um subconjunto independente I_{u} de H que contém um dado vértice u de H pode conter, além de u, somente elementos de V_{1} = {u + 1, u + 2, …, u + a − 1} e de V_{2} = {u − 1, u − 2, …, u − a + 1} (aqui os vértices são considerados módulo 2a + t). Cada u + k ∈ V_{1} (0 < k < a) é adjacente a u + k − a ∈ V_{2} (já que a distância entre eles é a ou a + t). Assim, |I_{u}| ≤ |V_{1}| + 1 = a. Logo, α(H) ≤ a e, portanto (Lema 1.2.10), χ(H) ≥ |V (H)|/α(H) ≥ (2a + t)/a. Concluímos então que χ(D) ≥ χ(H) ≥ (2a+t)/a > (2a+ka)/a = k +2. □

Teorema 2.1.2 ([22]). Se D = {a, a + d, a + 2d, …} ⊂ ℤ^{+} é uma progressão aritmética (finita ou infinita) com d ∈ ℕ e mdc(a, d) = 1, então (a) χ(D) = ⌈\frac{|D|−1}{a}⌉ + 2, se d = 1;

(b) χ(D) = 2, se d é par; e

(c) χ(D) = 3, em qualquer outro caso.

Demonstração. Nós temos os seguintes 5 casos a considerar.

(1) d = 0. Nesse caso, |D| = 1 e, portanto, χ(D) = 2.

(2) D é finito e d = 1. Nesse caso, podemos usar o Lema 2.1.1 acima para concluir que χ(D) = ⌈\frac{|D|−1}{a}⌉ + 2.

(3) D é infinito e d = 1. Nesse caso, χ(D) = ∞, já que ℤ(D) tem subgrafos (induzidos) completos de qualquer tamanho (por exemplo, os subgrafos [{0, a, 2a, …, ma}], m ∈ ℕ).

(4) |D| ≥ 2 e d ≥ 2 é par. Nesse caso, a é ímpar e, portanto, todos os elementos de D são ímpares, de onde χ(D) = 2 (Lema 1.2.4).

(5) |D| ≥ 2 e d ≥ 3 é ímpar. Nesse caso, temos que χ(D) ≥ 3, já que D contém elementos de paridades diferentes. Para concluirmos que χ(D) = 3, basta então mostrarmos que χ(D) ≤ 3. Para tanto, observe que, como temos a ≡ a + d ≡ a + 2d … (mod d) e mdc(a, d) = 1, então D não tem múltiplos de d. Assim, o grafo ℤ_{d}(D) não tem laços, e, portanto, χ(D) ≤ χ(ℤ_{d}(D)) (Lema 1.2.8). Agora, dois vértices u e v de ℤ_{d}(D) são adjacentes sse u − v ≡ ±a (mod d) (pois todos os elementos de D são equivalentes a a (mod d)). Como d é ímpar, então temos que cada vértice w de ℤ_{d}(D) é adjacente a exatamente 2 vértices de ℤ_{d}(D) (a saber, aos vértices w + a (mod d) e w − a (mod d)). Logo, temos que ℤ_{d}(D) é um ciclo de tamanho d (pois mdc(a, d) = 1) e, portanto, χ(D) ≤ χ(ℤ_{d}(D)) = 3. □

2.2. Cadeias de Divisão

Nessa seção, mostraremos como se calcula χ(D) quando D é uma cadeia de divisão qualquer.

Definição 2.2.1. Diremos que D = {d_{1}, d_{2}, d_{3}, …} ⊂ ℤ^{+} é uma cadeia de divisão se, para todo i, d_{i} divide d_{i+1}. As razões {r_{i}} ⊂ ℤ^{+} de uma tal cadeia de divisão são definidas por r_{i} = d_{i+1}/d_{i}, i = 1, 2, 3, . . ..

Note que, para calcularmos χ(D) quando D = {d_{i}} ⊂ ℤ^{+} é uma cadeia de divisão, podemos assumir (Corolário 1.2.2) que mdc(D) = 1, ou seja, que d_{1} = 1. Em outras palavras, χ(D) só depende das razões de D.

Definição 2.2.2. Diremos que α é uma palavra sobre {1, 2} (de tamanho l ∈ ℤ^{+}) se α = (α_{i})_{i=1}^{l} com α_{i} ∈ {1, 2} para i = 1, 2, …, l.

Teorema 2.2.3 ([6]). Se D = {d_{1}, d_{2}, d_{3}, …} ⊂ ℤ^{+} é uma cadeia de divisão, então χ(D) ≤ 4.

Demonstração. Como já observamos acima, podemos assumir que d_{1} = 1. Dados D′ ⊂ ℤ^{+} e k ∈ ℤ^{+}, k ≥ 2, diremos que uma palavra α sobre {1, 2} é k-compatível com D′ se existe uma coloração apropriada de ℤ(D′) com as cores {0, 1, …, k − 1} tal que as diferenças (módulo k) entre cores de vértices consecutivos formam uma concatenação de repetidas cópias de α. Assim, temos que α é k-compatível com {d} ⊂ ℤ^{+} sse a concatenação de repetidas cópias de α não contém d entradas consecutivas cuja soma é múltipla de k. Agora, iremos mostrar que, para todo n ∈ ℤ^{+}, existem palavras α^{n} e β^{n} sobre {1, 2} de tamanho d_{n} tais que vale a seguinte asserção.

(∗) α^{n} e β^{n} diferem somente nas suas primeiras entradas, com α_{1}^{n} = 1 e β_{1}^{n} = 2, e, se γ é uma palavra obtida pela concatenação de um número finito de cópias de α^{n} e/ou β^{n}, então γ é 4-compatível com {d_{1}, d_{2}, …, d_{n}}.

Note que se mostrarmos (∗) acima para todo n ∈ ℤ^{+}, então teremos, por exemplo, que α^{n} é 4-compatível com {d_{1}, d_{2}, …, d_{n}} para todo n ∈ ℤ^{+}. Como todo subgrafo finito de ℤ(D) é (isomorfo a) um subgrafo finito de ℤ(d_{1}, d_{2}, …, d_{m}) para algum m ∈ ℤ^{+}, então teremos mostrado que todo subgrafo finito de ℤ(D) tem uma 4-coloração apropriada. Logo, pelo Lema 1.2.9, χ(D) ≤ 4. Basta então mostrarmos que (∗) acima vale para todo n ∈ ℤ^{+}. Mostremos isso agora por indução em n.

(i) Para n = 1, ponha α^{1} = 1 e β^{1} = 2. Como d_{1} = 1, então (∗) acima vale nesse caso. (ii) Suponha que n ≥ 1 e que (∗) acima vale para n. Defina s e t por s = ∑_{i=1}^{d_{n}} α_{i}^{n} e t = ∑_{i=1}^{d_{n}} β_{i}^{n} = s + 1. Agora, [r_{n}s, r_{n}t] contém dois inteiros consecutivos, w e w + 1, tais que ambos não são múltiplos de 4 (se r_{n} > 2, isso vale, pois existem pelo menos 4 inteiros em [r_{n}s, r_{n}t], e, se r_{n} = 2, então 2s e 2t = 2s + 2 são ambos pares e exatamente um deles é múltiplo de 4 - se 2s é mútiplo de 4, ponha w = 2s+1, e se 2t é múltiplo de 4, ponha w = 2s). Agora, sejam a ≥ 1 e b ≥ 0 inteiros tais que a + b = r_{n} e as + bt = w (por exemplo, tome b = w − r_{n}s e a = r_{n} − b). Defina α^{n+1} como sendo a concatenação de a cópias de α^{n} com b cópias de β^{n}, e β^{n+1} como sendo a concatenação de β^{n} com a − 1 cópias de α^{n} com b cópias de β^{n} (equivalentemente, β^{n+1} é α^{n+1} com a primeira entrada substituída por 2). Note que α^{n+1} e β^{n+1} têm ambas comprimento d_{n+1} (pois a+b = r_{n} = d_{n+1}/d_{n}) e que elas diferem somente na primeira entrada (α_{1}^{n+1} = 1 e β_{1}^{n+1} = 2). Agora, se γ é uma concatenação de cópias de {α^{n+1}, β^{n+1}}, então γ é também uma concatenação de cópias de {α^{n}, β^{n}} e, portanto, γ é 4-compatível com {d_{1}, d_{2}, …, d_{n}}. Assim, para mostrarmos que (∗) acima vale para n + 1, bastra mostrarmos que γ é 4-compatível com {d_{n+1}}. Pelo que já observamos acima, isso vale sse uma concatenação de repetidas cópias de γ não contém d_{n+1} entradas consecutivas cuja soma é múltipla de 4. Como α^{n+1} e β^{n+1} têm ambas tamanho d_{n+1} e diferem somente em uma entrada (a primeira), então a soma de d_{n+1} entradas consecutivas em uma concatenação de repetidas cópias de γ é igual ou à soma das entradas de α^{n+1} ou à soma das entradas de β^{n+1}, ou seja, igual a as + bt = w ou a w + 1. Como ambos w e w + 1 não são múltiplos de 4, então temos o que queríamos, ou seja, que (∗) acima vale para n + 1. □

Corolário 2.2.4 ([6]). Se D = {d_{i}} ⊂ ℤ^{+} é uma cadeia de divisão e r_{i} ≠ 2, para todo i, então χ(D) ≤ 3.

Demonstração. Basta repetir a demonstração acima substituindo-se 4 por 3 (o único ponto onde isso não funcionaria na demonstração original seria na parte onde teríamos que encontrar dois inteiros consecutivos em [r_{n}s, r_{n}t] que não são múltiplos de 3 no caso r_{n} = 2, mas, como estamos assumindo que nenhum r_{i} é igual a 2, então sempre é possível encontrarmos dois inteiros consecutivos em [r_{n}s, r_{n}t] que não são múltiplos de 3). □

O último resultado desse capítulo irá classificar todas as cadeias de divisão de acordo com o seu número cromático. Como uma progressão geométrica é em particular uma cadeia de divisão, então como corolário obteremos o número cromático de todas as progressões geométricas.

Teorema 2.2.5 ([6]). Se D = {d_{1}, d_{2}, d_{3}, …} ⊂ ℤ^{+} uma cadeia de divisão (finita ou infinita) de razões r_{1} = d_{2}/d_{1}, r_{2} = d_{3}/d_{2}, …, então

(a) χ(D) ≤ 4;

(b) χ(D) ≤ 3 sse não existem i < j com r_{i} = 2 e r_{j} múltiplo de 3;

(c) χ(D) ≤ 2 sse todos os r_{i}’s são ímpares; e

(d) χ(D) = 1 sse D = ∅.

Demonstração. Pelo que já foi mostrado anteriormente, é claro que podemos assumir que d_{1} = 1 e que só nos resta mostrar a asserção (b) acima. Suponha então que i < j são tais que r_{i} = 2 e 3|r_{j}. Suponha ainda, por absurdo, que ℤ(D) tem uma 3-coloração apropriada. Temos que d_{i+1} = 2d_{i} e que 3d_{i}|d_{j}. Como χ(0, d_{i}, 2d_{i}) = χ(d_{i}, 2d_{i}, 3d_{i}) = 3, então 0 e 3d_{i} têm a mesma cor. Continuando dessa maneira, vemos que todos os múltiplos de d_{i} têm a mesma cor. Logo, 0 e d_{j+1} têm a mesma cor, o que é um absurdo. Na outra direção, suponha que não existem i < j com r_{i} = 2 e 3|r_{j}. Se existem infinitos r_{j}’s que são múltiplos de 3, então não existe r_{i} = 2 e, portanto χ(D) ≤ 3 (Corolário 2.2.4). Assuma então que só existe um número finito de r_{j}’s que são múltiplos de 3 e seja c o menor inteiro positivo tal que r_{i} não é múltiplo de 3 para todo i ≥ c. Pelo Corolário 2.2.4, temos que χ(d_{1}, d_{2}, …, d_{c}) ≤ 3. Pela prova do Corolário 2.2.4 acima, temos que existe uma palavra α^{c} sobre {1, 2} de tamanho d_{c} que é 3-compatível com {d_{1}, d_{2}, …, d_{c}}. Iremos mostrar agora que α^{c} é 3-compatível com D. Como α^{c} é 3-compatível com {d_{c}}, a soma das entrada de α^{c} não é múltipla de 3. Logo, se x e y diferem por um múltiplo de d_{c}, então, em qualquer coloração apropriada de ℤ(D) com as cores {0, 1, 2} onde as diferenças (módulo 3) entre cores de vértices consecutivos formam cópias repetidas de α^{c}, temos que x e y têm a mesma cor sse x e y diferem por um múltiplo de 3d_{c}. Note, porém, que nenhum d_{i} com i ≥ c é múltiplo de 3d_{c}. Logo, dois inteiros que diferem por d_{i} (i ≥ c) não recebem a mesma cor em uma tal coloração, de onde concluímos que α^{c} é 3-compatível com {d_{c}, d_{c+1}, d_{c+2}, …}. Como α^{c} já era 3-compatível com {d_{1}, d_{2}, …, d_{c}}, então temos que α^{c} é 3-compatível com D = {d_{1}, d_{2}, …, d_{c}} ∪ {d_{c}, d_{c+1}, d_{c+2}, …}. Assim, temos que ℤ(D) tem uma 3-coloração apropriada, de onde concluímos que χ(D) ≤ 3. □

Corolário 2.2.6 ([6]). Se D = {a, aq, aq^{2}, …} ⊂ ℤ^{+} é uma progressão geométrica (finita ou infinita), então χ(D) = 2, se q é ímpar, e χ(D) = 3, se q é par. □

CAPÍTULO 3 Outros Números Cromáticos

Nesse capítulo, iremos calcular o número-aresta-cromático, o númerototal-cromático, o número-aresta-escolha e o número-total-escolha (que serão definidos a seguir) de todos os grafos-distância sobre ℤ.

Diremos que um vértice x e uma aresta e de um dado grafo G são incidentes (em G) se e = {x, y} para algum y ∈ V (G).

Dados um grafo G e um cardinal λ, uma função ν : E(G) → λ será chamada de uma coloração apropriada das arestas de G com λ cores se arestas adjacentes (em G) têm cores distintas. O número-aresta-cromático de G é definido como sendo o menor cardinal χ′(G) tal que existe uma coloração apropriada das arestas de G com χ′(G) cores.

Dados um grafo G e um cardinal λ, uma função ν : V (G) ∪ E(G) → λ será chamada de uma coloração total apropriada dos vértices e arestas de G com λ cores se vértices adjacentes, arestas adjacentes e vértices e arestas incidentes (em G) têm cores distintas. O número-total-cromático de G é definido como sendo o menor cardinal χ′′(G) tal que existe uma coloração total apropriada dos vértices e arestas de G com χ′′(G) cores.

Dados um grafo G e a coleção L = {L(e) : e ∈ E(G)} de conjuntos, uma função ϕ : E(G) → ⋃ L será chamada de uma L-coloração apropriada das arestas de G se arestas adjacentes (em G) têm cores distintas e ϕ(e) ∈ L(e), para todo e ∈ E(G) (se e ∈ E(G), então L(e) é a lista de cores de e). Ainda, dado um cardinal κ, diremos que G é κ-aresta-escolhível se, para toda L = {L(e) : e ∈ E(G)} satisfazendo |L(e)| ≥ κ para todo e ∈ E(G), existe uma L-coloração apropriada das arestas de G. O númeroaresta-escolha de G é definido como sendo o menor cardinal ch′(G) tal que G é ch′(G)-aresta-escolhível.

Dados um grafo G e a coleção L = {L(h) : h ∈ V (G)∪E(G)} de conjuntos, uma função ϕ : V (G) ∪ E(G) → ⋃ L será chamada de uma L-coloração apropriada dos vértices e arestas de G se vértices adjacentes, arestas adjacentes e vértices e arestas incidentes (em G) têm cores distintas e ϕ(h) ∈ L(h), para todo h ∈ V (G) ∪ E(G) (se h ∈ V (G) ∪ E(G), então L(h) é a lista de cores de h). Ainda, dado um cardinal κ, diremos que G é κ-total-escolhível se, para toda L = {L(h) : h ∈ V (G) ∪ E(G)} satisfazendo |L(h)| ≥ κ para todo h ∈ V (G) ∪ E(G), existe uma L-coloração apropriada dos vértices e arestas de G. O número-total-escolha de G é definido como sendo o menor cardinal ch′′(G) tal que G é ch′′(G)-total-escolhível.

Teorema 3.1 ([23]). Se D ⊂ ℤ^{+}, então χ′(ℤ(D)) = 2|D| = ch′(ℤ(D)).

Demonstração. Para ver a primeira asserção, note que cada elemento d de D define um subgrafo de ℤ(D), a saber ℤ(d). Temos que ℤ(d) é a união disjunta de d caminhos infinitos, i.e., que cada componente conexa de ℤ(d) é isomorfa a ℤ(1). Portanto, colorindo as arestas de cada componenete conexa de ℤ(d) alternadamente com 2 cores, vemos que χ′(ℤ(d)) ≤ 2, de onde temos que χ′(ℤ(D)) ≤ 2|D|. Agora, como cada vértice de ℤ(D) tem grau 2|D|, temos que χ′(ℤ(D)) ≥ 2|D|. Mostremos agora a segunda asserção. É claro que o resultado vale se D é vazio ou infinito. Podemos supor então que |D| = t ∈ ℤ^{+}. Ponha D = {d_{1} < d_{2} < … < d_{t}}. Suponha ainda que a cada aresta e de ℤ(D) esteja associada uma lista L(e) com 2t cores. Iremos agora colorir as arestas de ℤ(D) sucessivamente, de forma que cada aresta a ser colorida é adjacente a no máximo 2t−1 arestas já coloridas (e, portanto, poderemos atribuir a essa aresta uma cor da sua lista de forma que a coloração resultante seja uma L = {L(e) : e ∈ E(ℤ(D)}-coloração apropriada das arestas de ℤ(D)). Note que se mostrarmos que de fato isso é possível, então teremos mostrado que ch′(ℤ(D)) ≤ 2t = 2|D|. Primeiramente, pinte L-apropriadamente as 2t arestas adjacentes ao vértice 0 (de uma maneira arbitrária). Suponha então que já colorimos L-apropriadamente as arestas incidentes aos vértices 0, 1, −1, 2, −2, …, k, −k, para algum k ≥ 0. Iremos mostrar agora como podemos colorir L-apropriadamente as arestas incidentes aos vértices k+1 e −k−1. Primeiramente, colorimos L-apropriadamente as arestas {k + 1, k + 1 − d_{i}}, i = 1, 2, …, t, em uma ordem arbitrária (note que isso é possível, pois cada aresta {k+1, k+1−d_{i}} é adjacente a no máximo 2t − 2 arestas já coloridas, a saber, a no máximo t − 1 arestas incidentes a k + 1 e a no máximo t − 1 arestas incidentes a k + 1 − d_{i}). Em seguida, iremos colorir as arestas {k +1, k +1+d_{i}} na ordem i = 1, 2, …, t. A aresta {k+1, k+1+d_{i}} é adjacente a no máximo 2t−1 arestas já coloridas (a saber, a t + i − 1 arestas incidentes a k + 1 e a no máximo t − i arestas que ligam o vértice k+1+d_{i} aos vértices k+1+d_{i} −d_{j}, j = i+1, i+2, …, t). Assim, podemos colorir L-apropriadamente as arestas {k+1, k+1+d_{i}}, i = 1, 2, …, t. Finalmente, argumentos completamente análogos aos dados acima mostram que podemos colorir L-apropriadamente as arestas {−k − 1, −k − 1 + d_{i}}, na ordem i = 1, 2, …, t, e as arestas {−k − 1 − d_{i}}, na ordem i = 1, 2, …, t (ou seja, temos que cada uma dessa arestas será adjacente a no máximo 2t − 1 arestas já coloridas). Concluímos então que ch′(ℤ(D)) ≤ 2t = 2|D|. Como cada vértice de ℤ(D) tem grau 2t, temos que ch′(ℤ(D)) ≥ 2t = 2|D|. □

Teorema 3.2 ([23]). Se D ⊂ ℤ^{+}, então χ′′(ℤ(D)) = ch′′(ℤ(D)) = = 2|D| + 1.

Demonstração. A prova é quase totalmente análoga à prova do Teorema 3.1 acima. Primeiramente, mostremos que ch′′(G) ≤ 2|D| + 1. É claro que isso vale se D é vazio ou infinito. Podemos supor então que |D| = t ∈ ℤ^{+}. Ponha D = {d_{1} < d_{2} < … < d_{t}}. Suponha ainda que a cada vértice ou aresta h de ℤ(D) esteja associada uma lista L(h) com 2t + 1 cores. Iremos agora colorir os vértices e arestas de ℤ(D) sucessivamente, de forma que cada vértice ou aresta a ser colorida é adjacente ou incidente a no máximo 2t vértices ou arestas já coloridos (e, portanto, poderemos atribuir a esse vértice ou aresta a ser colorida uma cor da sua lista, de forma que a coloração resultante seja uma L = {L(h) : h ∈ ℤ ∪ E(ℤ(D))}-coloração apropriada dos vértices e arestas de ℤ(D)). Note que se de fato mostrarmos que isso é possível, então teremos mostrado que ch′′(G) ≤ 2t + 1 = 2|D| + 1. Primeiramente, pinte L-apropriadamente o vértice 0 e as 2t arestas incidentes ao vértice 0 (de uma maneira arbitrária). Suponha então que já colorimos L-apropriadamente os vértices 0, 1, −1, 2, −1, …, k, −k e todas as arestas incidentes a esses vértices, para algum k ≥ 0. Iremos mostrar agora como podemos colorir L-apropriadamente o vértice k + 1, as arestas incidentes ao vértice k + 1, o vértice −k − 1 e, finalmente, as arestas incidentes ao vértice −k − 1. O vértice k + 1 é incidente a no máximo t arestas já coloridas e adjacente a no máximo t vértices já coloridos. Assim, podemos atribuir ao vértice k +1 uma cor da sua lista. Cada aresta {k +1, k +1−d_{i}} (i = 1, 2, …, t) é adjacente a no máximo 2t − 2 arestas já coloridas, e, portanto, podemos colorir L-apropriadamente essas arestas (em uma ordem arbitrária). Cada aresta {k + 1, k + 1 + d_{i}} (i = 1, 2, …, t) é adjacente a no máximo 2t − 1 arestas já coloridas (veja a prova do Teorema 3.1 acima). Como o vértice k + 1 + d_{i} ainda não foi colorido, então também podemos colorir L-apropriadamente todas essas arestas. Finalmente, assim como foi indicado na prova do Teorema 3.1 acima, colorimos L-apropriadamente o vértice −k − 1 e as arestas incidentes ao vértice −k − 1. Concluímos então que ch′′(ℤ(D)) ≤ 2t + 1 = 2|D| + 1. Como cada vértice de ℤ(D)) tem grau 2t, temos que χ′′(ℤ(D)) ≥ 2t + 1. Agora, note que claramente temos ch′′(ℤ(D)) ≥ χ′′(ℤ(D)). Assim, ch′′(ℤ(D)) ≥ χ′′(ℤ(D)) ≥ 2t + 1 = 2|D| + 1, de onde a asserção do teorema segue. □

Observação 3.3 ([23]). Os resultados acima mostram que os grafosdistância verificam três importantes conjecturas. A primeira conjectura diz que, para qualquer grafo G, temos que χ′(G) = ch′(G). A segunda conjectura postula que todos os grafos G satisfazem Δ(G)+1 ≤ χ′′(G) ≤ Δ(G)+2, onde Δ(G) denota o grau máximo de (um vértice de) G. Finalmente, a terceira conjectura diz que, para qualquer grafo G, temos que χ′′(G) = ch′′(G).

CAPÍTULO 4 Os Grafos de Rado

Nesse capítulo, iremos expor algumas propriedades dos Grafos de Rado (que serão definidos a seguir). Em particular, mostraremos que esses grafos são grafos-distância sobre ℤ que têm número cromático infinito.

Definição 4.1. Diremos que um grafo Γ sobre um conjunto enumerável infinito S é escolhido ao acaso se cada elemento do conjunto de todos os 2-subconjuntos de S é selecionado para ser uma aresta de Γ independentemente com probabilidade 1/2.

Teorema 4.2 ([5]). Existe um grafo R que possui a seguinte propriedade. Se um grafo sobre um conjunto enumerável infinito é escolhido ao acaso, então com probabilidade 1 o grafo resultante é isomorfo a R.

Definição 4.3. Se um grafo Γ é isomorfo ao grafo R do teorema acima, então diremos que Γ é um Grafo de Rado.

O Teorema 4.2 acima seguirá dos dois lemas seguintes. Ambos tratam da seguinte propriedade de grafos.

Definição 4.4. Diremos que um grafo G tem a Propriedade Chave (P.C.) se, para quaisquer m, n ∈ ℕ e vértices distintos u_{1}, …, u_{m}, v_{1}, …, v_{n}, existe um vértice z ∉ {u_{i}, v_{j}} que é adjacente a u_{1}, …, u_{m} e que não é adjacente a v_{1}, …, v_{n}. Diremos que um tal vértice z está corretamente ligado a {u_{i}, v_{j}} (em G).

Observe que se um grafo tem a P.C., então ele é necessariamente infinito. Lema 4.5 ([5]). Se um grafo sobre um conjunto enumerável infinito é

escolhido ao acaso, então com probabilidade 1 ele tem a P.C..

Demonstração. Seja então Γ um grafo sobre um conjunto enumerável infinito S escolhido ao acaso. Nós precisamos mostrar que o evento “Γ não tem a P.C.” tem probabilidade 0. Para isso, é suficiente mostrarmos que, fixados vértices distintos u_{1}, …, u_{m}, v_{1}, …, v_{n}, o conjunto dos grafos sobre S escolhidos ao acaso para os quais a P.C. falha para os vértices u_{i}, v_{j} tem probabilidade 0. Considere então vértices z_{1}, …, z_{N} ∉ {u_{i}, v_{j}}. A probabilidade de que um dado z_{k} não esteja corretamente ligado a {u_{i}, v_{j}} é 1 − (1/2)^{m+n}. Assim, a probabilidade de que nenhum desses N vértices esteja corretamente ligado a {u_{i}, v_{j}} é (1−(1/2)^{m+n})^{N}, que tende a 0 quando N → +∞. Assim, a probabilidade de que nenhum vértice de S esteja corretamente ligado a {u_{i}, v_{j}} é 0, de onde temos que, com probabilidade 1, Γ tem a P.C.. □

Observe que já podemos concluir do Lema 4.5 acima que existem grafos sobre conjuntos enumeráveis infinitos que têm a P.C..

Lema 4.6 ([5]). Se dois grafos sobre conjuntos enumeráveis infinitos têm a P.C., então eles são isomorfos.

Demonstração. Sejam então Γ_{1} e Γ_{2} dois grafos sobre conjuntos enumeráveis infinitos que têm a P.C.. Suponha que g : [{x_{1}, …, x_{n}}] → [{y_{1}, …, y_{n}}] seja um isomorfismo de subgrafos induzidos ({x_{i}} ⊂ V (Γ_{1}) e {y_{i}} ⊂ V (Γ_{2})). Agora, seja x_{n+1} ∈ V (Γ_{1}) \ {x_{i}}. Iremos mostrar que g pode ser estendido a x_{n+1}. Seja U o conjunto dos vértices em {x_{i}} que são adjacentes a x_{n+1} e ponha V = {x_{i}} \ U. A imagem de x_{n+1} por uma extensão de g pode ser qualquer vértice de Γ_{2} que seja adjacente a todo vértice em g(U) e que não seja adjacente a nenhum vértice em g(V). Como Γ_{2} tem a P.C., então um tal vértice existe. Essa observação nos permite construir um isomorfismo entre Γ_{1} e Γ_{2} da seguinte maneira. Ponha V_{1} = V (Γ_{1}) = {x_{1}, x_{2}, …}, V_{2} = V (Γ_{2}) = {y_{1}, y_{2}, …} e f_{0} = ∅. Suponha que f_{n} já esteja construído para algum n ≥ 0. Se n é par, seja m o menor índice de um vértice em V_{1} que não esteja no domínio de f_{n}. Defina f_{n+1} como sendo a extensão de f_{n} a x_{m} conforme observamos acima. Se n é ímpar, seja m o menor índice de um vértice em V_{2} que não esteja na imagem de f_{n}. Usando agora o fato que Γ_{1} tem a P.C., estenda f_{n} a um isomorfismo f_{n+1} com y_{m} na sua imagem (i.e., aplique a observação acima a f_{n}^{−1}). Agora, ponha f = ⋃_{n} f_{n}. Não é difícil ver que f é um isomorfismo entre Γ_{1} e Γ_{2}, de onde concluímos que Γ_{1} e Γ_{2} são de fato isomorfos. □

Dos Lemas 4.5 e 4.6 acima, fica claro que Grafos de Rado existem (na verdade, mostramos que quase todos os grafos sobre um conjunto enumerável infinito são de Rado). Em outras palavras, o Teorema 4.2 acima é verdadeiro. Iremos dar agora algumas construções explícitas de Grafos de Rado (uma dessas construções será um grafo-distância sobre ℤ cujo número cromático é infinito). Note que mostrar que um dado grafo (sobre um conjunto enumerável infinito) é de Rado é equivalente a mostrar que ele tem a P.C..

Proposição 4.7 ([5]). Seja 𝕄 um modelo enumerável da Teoria dos Conjuntos. Defina o grafo M sobre 𝕄 ligando x a y sse x ∈ y ou y ∈ x. Assim, temos que M é um Grafo de Rado.

Demonstração. Sejam u_{1}, …, u_{m}, v_{1}, …, v_{n} vértices distintos de M. Ponha w = {v_{1}, …, v_{n}} e z = {u_{1}, …, u_{m}, w}. Não é difícil ver que z está corretamente ligado a {u_{i}, v_{j}} em M (o Axioma da Regularidade garante que z não é adjacente a nenhum v_{j}). □

Proposição 4.8 ([29]). Seja B o grafo cujo conjunto de vértices é ℕ e no qual s é adjacente a t sse o s-ésimo dígito na expansão binária de t for 1 ou se o t-ésimo dígito na expansão binária de s for 1. Assim, temos que B é um Grafo de Rado.

Demonstração. Dados u_{1}, …, u_{m}, v_{1}, …, v_{n} inteiros positivos distintos, não é difícil construir um inteiro positivo z que seja corretamente ligado a {u_{i}, v_{j}} em B (e.g., z = 2^{u_{1}} + ⋯ + 2^{u_{n}} + 2^{U}, onde U é um inteiro grande o suficiente para garantir que z não seja adjacente a nenhum v_{j}). □

Proposição 4.9 ([5]). Seja ℙ_{1} o conjunto de todos os números primos congruentes a 1 módulo 4. Defina o grafo P_{1} sobre ℙ_{1} ligando p a q sse p for um resíduo quadrático módulo q (pelo Teorema da Reciprocidade Quadrática, P_{1} é um grafo). Assim, temos que P_{1} é um Grafo de Rado.

Demonstração. Sejam u_{1}, …, u_{m}, v_{1}, …, v_{n} primos distintos em ℙ_{1}. Fixe resíduos quadráticos a_{i} módulo u_{i} (por exemplo, a_{i} = 1) e resíduos não-quadráticos b_{j} módulo v_{j}. Pelo Teorema Chinês do Resto, as seguintes congruências x ≡ 1 (mod 4), x ≡ a_{i} (mod u_{i}) e x ≡ b_{j} (mod v_{j}) têm uma (única) solução comum x ≡ x_{0} (mod 4u_{1} … u_{m}v_{1} … v_{n}). Pelo Teorema de Dirichlet, existe um primo z que satisfaz essa congruência. Portanto, vemos que z ∈ ℙ_{1} e que z está corretamente ligado a {u_{i}, v_{j}} em P_{1}. □

Definição 4.10. Um conjunto D ⊂ ℤ^{+} será chamado de universal se, para quaisquer k ∈ ℤ^{+} e T ⊂ [k], existe um inteiro K tal que, para todo a ∈ [k], a + K ∈ D sse a ∈ T.

Proposição 4.11 ([5]). Se D ⊂ ℤ^{+} é um conjunto universal, então ℤ(D) é um Grafo de Rado.

Demonstração. Sejam então u_{1}, …, u_{m}, v_{1}, …, v_{n} inteiros distintos. Ponha l = min{u_{i}, v_{j}}, L = max{u_{i}, v_{j}}, k = L − l + 1 e T = {u_{i} − l + 1 : i = 1, 2, …, m}. Como D é universal, existe um inteiro K tal que, para todo a ∈ [k], a + K ∈ D sse a ∈ T. Não é difícil ver que z = l − 1 − K está corretamente ligado a {u_{i}, v_{j}} em ℤ(D). □

Observação 4.12 ([5]). Uma maneira de se construir conjuntos D ⊂ ℤ^{+} universais é a seguinte. Primeiro, identifique subconjuntos de ℤ^{+} com sequências infinitas de 0’s e 1’s. Uma tal sequência é universal sse ela contém toda sequência finita de 0’s e 1’s como uma subsequência de termos consecutivos. Assim, um exemplo simples de sequência universal é a sequência F formada pela concatenação de todas as sequências finitas de 0’s e 1’s na ordem lexicográfica. Da Proposição 4.11 acima, vemos que ℤ(F) é um Grafo de Rado. Ainda, como ℤ(F) tem subgrafos (induzidos) completos arbitrariamente grandes, temos que χ(F) = ∞. Não é difícil mostrar que, na verdade, quase toda sequência infinita de 0’s e 1’s é universal.

CAPÍTULO 5 Os Resultados de Katznelson

5.1. Conjuntos Não-Recorrentes

Nessa seção, iremos apresentar o critério mais geral conhecido que decide se um dado D ⊂ ℤ^{+} infinito tem número cromático finito ou não. Esse critério é de certa forma inesperado, pois ele traduz a finitude de χ(D) em termos de propriedades de sistemas dinâmicos em espaços métricos compactos. Entretanto, esse mesmo tema é encontrado, por exemplo, na demonstração dinâmica do famoso Teorema de Van der Waerden sobre progressões aritméticas em partições finitas dos inteiros ([19]) .

Definição 5.1.1. Para nós, um sistema dinâmico é um par ((X, ρ), T), onde (X, ρ) é um espaço métrico compacto não-vazio e T : X → X é um homeomorfismo. Quando a função-distância ρ estiver subentendida, escreveremos simplesmente (X, T) ao invés de ((X, ρ), T).

Definição 5.1.2. Sejam dados D ⊂ ℤ^{+} infinito e um sistema dinâmico ((X, ρ), T). Diremos que D é não-recorrente para ((X, ρ), T) se existe b ∈ ℝ, b > 0, tal que, para quaisquer x ∈ X e d ∈ D, temos que ρ(x, T^{d}x) ≥ b.

Definição 5.1.3. Diremos que um conjunto D ⊂ ℤ^{+} é não-recorrente se existe um sistema dinâmico (X, T) para o qual D é não-recorrente.

Podemos dar agora o critério mencionado acima.

Teorema 5.1.4 ([21]). Para qualquer D ⊂ ℤ^{+} infinito, temos que χ(D) < ∞ sse D é não-recorrente.

Demonstração. Seja γ : ℤ → C uma coloração apropriada de ℤ(D), onde C é um conjunto finito de cores. Considere γ como elemento de C^{ℤ} e denote por T o shift à esquerda em C^{ℤ}, i.e., T (α_{n}) = (α_{n+1}), para todo (α_{n}) ∈ C^{ℤ}. Como ℤ(D) é invariante por translação, temos que T^{m}γ também é uma coloração apropriada de Z(D), para todo m ∈ ℤ. Mais ainda, se colocamos em C^{ℤ} a topologia produto (onde cada fator C tem a topologia discreta) e (γ^{k}) ⊂ C^{ℤ} é uma sequência de colorações apropriadas de ℤ(D) com γ^{k} → γ′ ∈ C^{ℤ}, então γ′ é também uma coloração apropriada de ℤ(D) (isso na verdade vale para qualquer grafo sobre ℤ). Agora, uma funçãodistância ρ em C^{ℤ} que induz a topologia produto é a função definida por

ρ(\{σ_{n}\}, \{τ_{n}\}) = \frac{1}{1 + max\{k : |j| ≤ k ⇒ σ_{j} = τ_{j}\}},

para todos {σ_{n}} ≠ {τ_{n}} ∈ C^{ℤ} (e, é claro, ρ(σ, σ) = 0, ∀ σ ∈ C^{ℤ}). Ponha O(γ) = \{T^{n}γ : n ∈ ℤ\}. Como C^{ℤ} é compacto, segue que (\overline{O(γ)}, T) é um sistema dinâmico para o qual D é um conjunto não-recorrente (pois \overline{O(γ)} é compacto não-vazio com T \overline{O(γ)} = \overline{O(γ)} e, para quaisquer γ̃ ∈ \overline{O(γ)} e d ∈ D, ρ(γ̃, T^{d}γ̃) = 1, já que γ̃_{d} = (T^{d}γ̃)_{0} ≠ γ̃_{0}). Como γ̃ é uma coloração apropriada de ℤ(D) (pois γ̃ ∈ \overline{O(γ)}), concluímos que D é não-recorrente. Na outra direção, sejam ((Y, ρ), T) um sistema dinâmico para o qual D é não-recorrente e b ∈ ℝ uma constante positiva que atesta esse fato. Seja ainda {U_{i} : i = 1, 2, …, a} uma partição finita de Y tal que diam(U_{i}) < b, para todo i ∈ [a]. Agora, fixe y_{0} ∈ Y (qualquer) e seja γ ∈ [a]^{ℤ} a coloração definida por γ(m) = i sse T^{m}(y_{0}) ∈ U_{i}. Resta mostrarmos então que γ é uma coloração apropriada de ℤ(D). Suponha que existem m, n ∈ ℤ e d ∈ D tais que n − m = d e γ(m) = γ(n) = j ∈ [a]. Assim, temos que T^{m}y_{0}, T^{n}y_{0} ∈ U_{j}, de onde ρ(T^{m}y_{0}, T^{n}y_{0}) = ρ(T^{m}y_{0}, T^{d}(T^{m}y_{0})) < b, o que é uma contradição (já que ρ(y, T^{d}y) ≥ b qualquer que seja y ∈ Y). Assim, γ é de fato uma a-coloração apropriada de ℤ(D), de onde χ(D) < ∞. □

5.2. Sequências Lacunárias

Nessa seção, iremos aplicar o critério acima (Teorema 5.1.4) para concluir que toda sequência lacunária tem número cromático finito.

Definição 5.2.1. Dado D = {d_{i}} ⊂ ℤ^{+} infinito, diremos que D é uma sequência lacunária se inf_{i≥1}{d_{i+1}/d_{i}} > 1.

Definição 5.2.2. Considere a relacão de equivalência em ℝ definida por x ∼ y sse x − y ∈ ℤ e ponha 𝕋 = ℝ /∼ (𝕋 também pode ser considerado como sendo o círculo unitário no plano complexo). Ainda, dados z, w ∈ 𝕋, a distância de z a w (em 𝕋) será denotada por ∥z − w∥.

Teorema 5.2.3 ([21]). Se D ⊂ ℤ^{+} é uma sequência lacunária qualquer, então χ(D) < ∞.

Demonstração. Seja então D ⊂ ℤ^{+} uma sequência lacunária e ponha δ = inf_{i≥1}{d_{i+1}/d_{i}} > 1. Ainda, seja s ∈ ℤ^{+} tal que δ^{s} ≥ 5 e ponha D_{k} = {d_{k+js}}_{j=0}^{∞}, k = 1, 2, …, s. Cada D_{k} = {d_{i}^{k}} é uma sequência lacunária satisfazendo inf_{i≥1}{d_{i+1}^{k}/d_{i}^{k}} ≥ 5. Como D = ⋃_{k=1}^{s} D_{k}, é suficiente mostrarmos o resultado no caso em que δ ≥ 5 (Lema 1.2.11). Agora, para todo j ≥ 1, ponha A_{j} = {α ∈ 𝕋 : ∥d_{j}α∥ ≥ 1/4}. Note que cada A_{j} é a união de d_{j} arcos de comprimento 1/(2d_{j}). Como d_{j+1} ≥ 5d_{j} para todo j, cada componente conexa de A_{j} contém pelo menos duas componentes conexas de A_{j+1}. Portanto, ⋂_{j=1}^{∞} A_{j} ≠ ∅. Logo, existe α ∈ 𝕋 tal que ∥dα∥ ≥ 1/4 para todo d ∈ D. Note que isso na verdade significa que D é não-recorrente para o sistema dinâmico ((𝕋, ∥.∥), R_{α}), onde R_{α} : 𝕋 → 𝕋 é a rotação de ângulo α no sentido anti-horário. Assim, D é não-recorrente e, portanto, podemos usar o Teorema 5.1.4 acima para concluir que χ(D) < ∞. □

5.3. UMA SEQUÊNCIA k−UNIVERSAL 19

5.3. Uma Sequência k−Universal

Nessa seção, iremos mostrar que, para todo k ∈ ℤ^{+}, existe uma sequência cujo número cromático é no máximo k^{2} e que “contém” (i.e., contém a menos de um múltiplo) todas as sequências finitas com número cromático no máximo k.

Lema 5.3.1 ([21]). Para todo D ⊂ ℤ^{+}, χ(D) = sup_{N→∞} χ(D ∩ [N]).

Demonstração. Claramente, χ(D) ≥ sup_{N→∞} χ(D ∩ [N]). Assuma agora que sup_{N→∞} χ(D ∩ [N]) = k ∈ ℤ^{+}. Assim, para todo N ∈ ℤ^{+}, temos que χ(D ∩ [N]) ≤ k. Para cada N ∈ ℤ^{+}, seja então c_{N} ∈ [k]^{ℤ} uma coloração apropriada de ℤ(D ∩[N]). Como [k]^{ℤ} (com a topologia produto) é compacto, vemos que {c_{N}} tem um ponto limite c ∈ [k]^{ℤ}, de onde concluímos que χ(D) ≤ k (já que c também é uma coloração apropriada de ℤ(D)). □

Definição 5.3.2 ([21]). Dadas D e D′ sequências em ℤ^{+}, diremos que D contém D′ a menos de um múltiplo se existe m ∈ ℤ^{+} tal que mD′ ⊂ D.

Teorema 5.3.3 ([21]). Seja {D_{j} : j ≥ 1} ⊂ [L_{j}] uma sequência de sequências finitas, todas de número cromático no máximo k. Ainda, sejam m_{j} ≥ 5L_{j} e M_{j} = ∏_{t<j} m_{t}. Assim, se D = ⋃_{j=1}^{∞} M_{j}D_{j}, então χ(D) ≤ k^{2}.

Demonstração. Para N = 1, 2, 3, …, ponha D(N) = ⋃_{j=1}^{N} M_{j}D_{j}. Pelo Lema 5.3.1 acima, é suficiente mostrarmos que, para todo N ∈ ℤ^{+}, χ (D(N)) ≤ k^{2}. No que segue, as colorações tomarão valores em ℤ_{k} = ℤ/kℤ. Agora, assim como no caso das expansões decimais, não é difícil ver que todo n ∈ ℤ se escreve de maneira única como n = ∑_{j=1}^{N+1} a_{j}M_{j}, onde 0 ≤ a_{j} < m_{j}, para todo j ∈ [N], e a_{N+1} ∈ ℤ (os a_{j}’s serão chamados de dígitos de n). Ainda, para cada j, seja c_{j} ∈ ℤ_{k}^{ℤ} uma k-coloração apropriada de ℤ(D_{j}) e ponha C̃(n) = ∑_{j=1}^{N} c_{j}(a_{j}). Agora, se n_{1} < n_{2} ∈ ℤ são tais que os seus N primeiros dígitos correspondentes, exceto os s-ésimos, são iguais e n_{2} − n_{1} ∈ M_{s}D_{s}, então C̃(n_{1}) ≠ C̃(n_{2}) (já que c_{s} assume valores distintos nos s-ésimos dígitos de n_{1} e n_{2} e as outras colorações assumem valores iguais nos outros dígitos entre 1 e N correspondentes). Mais ainda, observe que se d ∈ D_{r} e o dígito a_{r} de n satisfaz a_{r} < 4m_{r}/5, então a_{r} + d < m_{r} (já que d ≤ L_{r} ≤ m_{r}/5), de onde temos que os N primeiros dígitos de n e n + M_{r}d correspondentes, exceto os r-ésimos, são iguais e, portanto, C̃(n) ≠ C̃(n + M_{r}d). Pondo I_{N} = ∑_{j=1}^{N} ⌊m_{j}/2⌋M_{j}, não é difícil ver que, para todo n ∈ ℤ e todo λ ∈ D(N), a observação anterior se aplica a pelo menos um dos dois pares n, n + λ e n + I_{N}, n + I_{N} + λ, de onde segue que a coloração definida por C(n) = (C̃(n), C̃(n + I_{N})) é uma coloração apropriada de ℤ (D(N)). Assim, χ(D(N)) ≤ k^{2} e, portanto, concluímos que de fato temos χ(D) ≤ k^{2}. □

Corolário 5.3.4 ([21]). Para todo k ∈ ℤ^{+}, existe D = D(k) ⊂ ℤ^{+} com χ(D) ≤ k^{2} que contém a menos de um múltiplo todas as sequências finitas que têm número cromático no máximo k. □

Demonstração. Basta tomar {D_{j}} como sendo a sequência de todas as sequências finitas de número cromático no máximo k (em alguma ordem) no enunciado do Teorema 5.3.3 acima. □

CAPÍTULO 6 O Critério de Weiss-Furstenberg-Weyl

6.1. Conjuntos Sindéticos

Nessa seção, iremos estabelecer uma conexão entre D’s infinitos tais que χ(D) = ∞ e subconjuntos sindéticos de ℤ (que serão definidos a seguir). Lembramos que alguns conceitos usados aqui foram estabelecidos na Seção 5.1 do Capítulo 5.

Definição 6.1.1. Diremos que um conjunto infinito A = {a_{i}} ⊂ ℤ é sindético se existe M ∈ ℤ^{+} tal que |a_{i+1} − a_{i}| ≤ M para todo i.

Definição 6.1.2. Diremos que uma coleção P de subconjuntos de ℤ é invariante por translação se, para quaisquer P ∈ P e t ∈ ℤ, temos que P + t = {p + t : p ∈ P } ∈ P.

Definição 6.1.3. Dados um sistema dinâmico (X, T) e X_{0} ⊂ X, diremos que (X_{0}, T) é um subsistema de (X, T) se X_{0} é fechado, não-vazio e invariante por T (i.e., T (X_{0}) ⊂ X_{0}). Ainda, diremos que (X, T) é minimal se o único subsistema de (X, T) é o próprio (X, T). Note que se (X_{0}, T) é um subsistema minimal de (X, T), então (X_{0}, T |X_{0}) é um sistema dinâmico.

Lema 6.1.4. Todo sistema dinâmico (X, T) tem um subsistema minimal.

Demonstração. Considere a famíla I = {E ⊂ X : ∅ ≠ E é fechado e invariante por T }. Como X ∈ I, temos que I é não-vazia e, portanto, o Lema de Zorn nos diz que I tem de fato um elemento minimal. □

Lema 6.1.5 ([35]). Se (X_{0}, T) é um sistema dinâmico minimal e x_{0} pertence a X_{0}, então, para todo aberto não-vazio U ⊂ X_{0}, temos que o conjunto {n ∈ ℤ : T^{n}x_{0} ∈ U} é sindético.

Demonstração. Sejam então x_{0} ∈ X_{0} e U ⊂ X_{0} aberto não-vazio. Primeiramente, note que O(x) = {T^{n}x : n ∈ ℤ} é densa em X_{0} para todo x ∈ X_{0} (pois \overline{O(x)} é não-vazio, fechado e invariante por T). Assim, temos que ⋃_{−∞}^{+∞} T^{i}(U) = X_{0}. Como T é um homeomorfismo e X_{0} é compacto, existe N ∈ ℕ tal que ⋃_{−N}^{N} T^{i}(U) = X_{0}, i.e., ⋃_{0}^{2N} T^{i}(U) = X_{0}. Portanto, {n ∈ ℤ : T^{n}x_{0} ∈ U} é de fato um conjunto sindético. □

Teorema 6.1.6 ([35]). Se P é uma coleção de subconjuntos finitos de ℤ que é invariante por translação, então temos que em qualquer partição finita {C_{1}, C_{2}, …, C_{J}} de ℤ sempre existe um C_{j} que contém algum elemento de P sse todo subconjunto sindético de ℤ contém um elemento de P.

Demonstração. Seja então A um subconjunto sindético de ℤ. Assim, temos que existe J ∈ ℤ^{+} tal que ℤ = A ∪ (A + 1) ∪ … ∪ (A + J − 1). Seja agora c : ℤ → {0, 1, …, J − 1} a coloração (i.e., partição) de ℤ definida por c(m) = min{j ∈ {0, 1, …, J − 1} : m ∈ A + j}. Temos que existem P_{0} ∈ P e j_{0} ∈ {0, 1, …, J − 1} tais que, para todo p ∈ P_{0}, c(p) = j_{0}. Portanto, para todo p ∈ P_{0}, temos que p ∈ A + j_{0}, i.e., que p − j_{0} ∈ A. Em outras palavras, P_{0} − j_{0} ⊂ A. Como P é invariante por translação, P_{0} − j_{0} ∈ P. Concluímos então que A contém um elemento de P. Na outra direção, seja então {C_{1}, C_{2}, …, C_{J}} uma partição finita de ℤ. Defina γ ∈ [J]^{ℤ} por γ(m) = j ∈ [J] sse m ∈ C_{j}, e ponha X = \overline{\{T^{k}γ\}} ⊂ [J]^{ℤ} (onde [J]^{ℤ} tem a topologia produto e T denota o shift à esquerda em [J]^{ℤ}). Pelo Lema 6.1.4 acima, o sistema dinâmico (X, T) tem um subsistema (X_{0}, T) que é minimal (e, portanto, (X_{0}, T |X_{0}) é um sistema dinâmico). Fixe x_{0} = (x_{0}(n)) ∈ X_{0} e seja j_{0} = x_{0}(0). Como a topologia em [J]^{ℤ} é a topologia produto, vemos que o conjunto A = {n ∈ ℤ : x_{0}(n) = j_{0}} é sindético (Lema 6.1.5 acima). Assim, temos que existe P_{0} ∈ P tal que P_{0} ⊂ A. Agora, fixe N ∈ ℤ^{+} tal que P_{0} ⊂ [−N, N] e seja ρ a função-distância em [J]^{ℤ} definida como na demonstração do Teorema 5.1.4 (ρ induz a topologia produto em [J]^{ℤ}). Como x_{0} ∈ \overline{\{T^{k}γ\}}, existe M ∈ ℤ tal que ρ(T^{M}γ, x_{0}) ≤ (N + 1)^{−1}. Assim, para todo n ∈ [−N, N], γ(n + M) = x_{0}(n) e, portanto, P_{0} + M ⊂ C_{j_{0}} (pois, para todo p ∈ P_{0}, γ(p + M) = x_{0}(p) = j_{0}). Agora, como P é invariante por translação, P_{0} + M ∈ P, e, portanto, C_{j_{0}} contém um elemento de P. □

Corolário 6.1.7 ([35]). Se D ⊂ ℤ^{+} é infinito, então χ(D) = ∞ sse todo conjunto sindético A ⊂ ℤ contém uma aresta de ℤ(D).

Demonstração. Basta observar que E(ℤ(D)) é uma coleção de subconjuntos finitos de ℤ invariante por translação e que dizer que χ(D) = ∞ é o mesmo que dizer que, em toda partição finita {C_{1}, C_{2}, …, C_{J}} de ℤ, sempre existe um C_{j} que contém uma aresta de ℤ(D). □

6.2. Sequências de Poincaré

Nessa seção, iremos provar que determinadas sequências têm número cromático infinito mostrando que elas são sequências de Poincaré. Para tanto, seguiremos o caminho indicado por Weiss, que usa o Corolário 6.1.7 acima, o chamado Princípio da Correspondência de Furstenberg (que estabelece uma conexão entre subconjuntos substanciais de ℤ e sistemas que preservam medida de probabilidade, conceitos esses que serão definidos a seguir) e, finalmente, uma demonstração de uma versão do Teorema Ergódico devida a von Neumann que está relacionada ao conhecido Critério de Weyl sobre sequências uniformemente distribuídas módulo 1.

Definição 6.2.1. Diremos que um conjunto A ⊂ ℤ tem densidade superior positiva ou que ele é substancial se existem uma sequência de inteiros positivos k_{i} ↗ ∞ e uma sequência {n_{i}} ⊂ ℤ tais que o limite lim_{i→∞} k_{i}^{−1} # (A ∩ [n_{i} + 1, n_{i} + k_{i}]) existe e é positivo.

Lema 6.2.2. Se A ⊂ ℤ é sindético, então A é substancial.

Demonstração. Imediata. □

Definição 6.2.3. Diremos que (X, B, μ, T) é um sistema que preserva medida de probabilidade se (X, B, μ) é um espaço de probabilidade (i.e., (X, B, μ) é um espaço de medida com μ(X) = 1) e T : X → X é um isomorfismo de medida, ou seja, T é uma bijeção mensurável que preserva medida e cuja inversa também é mensurável (e automaticamente também preserva medida).

O lema seguinte (cuja prova será esboçada mais adiante) é o chamado Princípio da Correspondência de Furstenberg. Esse lema foi o primeiro passo na demostração ergódica que Furstenberg deu para o Teorema de Szemerédi (que por sua vez é uma generalização do Teorema de Van der Waerden).

Lema 6.2.4 ([18]). Seja P uma coleção de subconjuntos finitos de ℤ que é invariante por translação. Assim, temos que todo subconjunto substancial de ℤ necessariamente contém algum elemento de P sse, para qualquer sistema que preserva medida de probabilidade (X, B, μ, T) e qualquer B ∈ B com μ(B) > 0, existe P = {u_{1}, …, u_{k}} ∈ P tal que μ (⋂_{i=1}^{k} T^{−u_{i}}B) > 0. □

Definição 6.2.5. Uma sequência {d_{n}} ⊂ ℤ^{+} será chamada de sequência de Poincaré se, para qualquer sistema que preserva medida de probabilidade (X, B, μ, T) e qualquer B ∈ B com μ(B) > 0, temos que existe algum d_{j} tal que μ (T^{d_{j}}B ∩ B) > 0.

Lema 6.2.6 ([35]). Se D = {d_{n}} ⊂ ℤ^{+} é uma sequência de Poincaré, então χ(D) = ∞.

Demonstração. Basta aplicar o Corolário 6.1.7 e os Lemas 6.2.2 e 6.2.4 acima. □

A recíproca do Lema 6.2.6 acima não vale. Um contra-exemplo foi construído por Kříž ([25]) (usando os grafos de Kneser de maneira nãotrivial). O próximo teorema nos fornece uma condição suficiente para que uma sequência seja de Poincaré.

Teorema 6.2.7 ([35]). Se {d_{n}} ⊂ ℤ^{+} é uma sequência tal que, para todo 0 < α < 1 temos que lim_{N→∞} N^{−1} ∑_{n=1}^{N} e^{2πiαd_{n}} = 0, então {d_{n}} é uma sequência de Poincaré.

A condição no enunciado do Teorema 6.2.7 acima não é necessária. Para ver isso, basta considerar a sequência dos quadrados perfeitos (voltaremos à essa sequência na próxima seção). Mostaremos a seguir uma série de definições e resultados que culminarão nas demonstrações do Lema 6.2.4 e do Teorema 6.2.7 acima. Em seguida, mostraremos a relação que existe entre a condição no enunciado do Teorema 6.2.7 e o Critério de Weyl sobre sequências uniformemente distribuídas módulo 1 (que, por sua vez, tem relação com o Teorema de Stone-Weierstrass).

Sejam H_{1}, H_{2} espaços de Hilbert complexos (o produto interno de ambos será denotado por ⟨·, ·⟩). Dada uma aplicação linear limitada L : H_{1} → H_{2}, a adjunta de L é a única aplicação L^{∗} : H_{2} → H_{1} (automaticamente linear limitada) tal que

⟨Lx, y⟩ = ⟨x, L^{∗}y⟩,

para todos x ∈ H_{1}, y ∈ H_{2}. Diremos que a aplicação L é unitária se L é um isomorfismo e L^{∗} = L^{−1}. Equivalentemente, L é unitária quando L é um isomorfismo e ⟨Lx, Ly⟩ = ⟨x, y⟩, para todos x, y ∈ H_{1}. Se H é um espaço de Hilbert complexo, então um operador linear limitado L : H → H é dito normal se LL^{∗} = L^{∗}L. Claramente, todo operador unitário L : H → H é normal.

Exemplo 6.2.8. Seja (X, A, μ) um espaço de medida. Considere o espaço vetorial

(6.2.1)  {f : X → ℂ mensurável : ∫_{X} |f|^{2} dμ < +∞}.

Denotaremos por L^{2}(X, A, μ) o quociente do espaço (6.2.1) pelo subespaço formado pelas funções f : X → ℂ que são nulas quase sempre. Temos que L^{2}(X, A, μ) é um espaço de Hilbert complexo munido do produto interno

⟨f, g⟩ = ∫_{X} fḡ dμ,

onde identificamos cada f em (6.2.1) com a sua classe de equivalência (i.e., com a classe das funções iguais a f quase sempre). Se ϕ : X → ℂ é uma função mensurável limitada, então considere o operador linear limitado M_{ϕ} em L^{2}(X, A, μ) definido por

M_{ϕ}(f) = ϕf,

para toda f ∈ L^{2}(X, A, μ). O adjunto de M_{ϕ} é claramente Mϕ̄ e, portanto, M_{ϕ} é normal. Como M_{ϕ}Mϕ̄ = M_{|ϕ|^{2}}, segue que M_{ϕ} é unitário sse |ϕ| = 1 quase sempre. Os operadores da forma M_{ϕ} serão chamados de operadores de multiplicação.

O Teorema Espectral enunciado a seguir nos diz que todo operador normal limitado é unitariamente equivalente a um operador de multiplicação.

Teorema 6.2.9 (Teorema Espectral). Sejam H um espaço de Hilbert complexo e L : H → H um operador normal limitado. Assim, existem um espaço de medida (X, A, μ), uma aplicação unitária σ : H → L^{2}(X, A, μ) e uma função mensurável limitada ϕ : X → ℂ tal que o diagrama

(6.2.2)  \xymatrix{H \ar[r]^{L} \ar[d]_{σ}^{≅} & H \ar[d]^{σ}_{≅} \\ L^{2}(X, A, μ) \ar[r]_{M_{ϕ}} & L^{2}(X, A, μ)}

comuta. □

Note que se o operador L no enunciado do Teorema Espectral é unitário, então o operador de multiplicação M_{ϕ} também é unitário e, portanto, |ϕ| = 1 quase sempre.

Se (X, A, μ) é um espaço de medida e A ∈ A é um subconjunto mensurável de X, então denotaremos por L^{2}(A) o subespaço de L^{2}(X, A, μ) formado pelas funções que são nulas quase sempre no complementar de A. Não é difícil ver que, para todo A ∈ A, o complemento ortogonal de L^{2}(A) é L^{2}(X \A). De fato, é claro que os subespaços L^{2}(A) e L^{2}(X \A) são ortogonais. Além disso, se f ∈ L^{2}(X, A, μ) é ortogonal a L^{2}(A), então, denotando por χ_{A} a função característica de A, temos que

0 = ⟨f, fχ_{A}⟩ = ∫_{A} |f|^{2} dμ,

de onde f ∈ L^{2}(X \ A).

Observe que se ϕ : X → ℂ é uma função mensurável limitada, então, para todo λ ∈ ℂ, vale que

Ker(M_{ϕ} − λ1) = L^{2}(ϕ^{−1}(λ)),

onde 1 denota o operador identidade em L^{2}(X, A, μ).

Agora, seja p : ℂ \ {0} → ℂ um polinômio de Laurent com coeficientes complexos, i.e., uma aplicação da forma

p(z) = ∑_{k=−n}^{n} a_{k}z^{k}, z ∈ ℂ \ {0},

onde a_{k} ∈ ℂ, ∀ k ∈ [−n, n]. Ainda, se H é um espaço de Hilbert complexo e L : H → H é um isomorfismo, então pomos

p(L) = ∑_{k=−n}^{n} a_{k}L^{k},

onde L^{0} = 1 é o operador identidade em H.

O lema a seguir é uma consequência do Teorema Espectral e das considerações acima.

Lema 6.2.10. Sejam H um espaço de Hilbert complexo, L : H → H um operador unitário, λ um número complexo, v ∈ H um vetor ortogonal ao subespaço Ker(L − λ1) e (p_{n})_{n≥1} uma sequência de polinômios de Laurent com coeficientes complexos. Suponha ainda que

• lim_{n→∞} p_{n}(z) = 0, para todo z ∈ ℂ com |z| = 1 e z ≠ λ; e que • existe c ≥ 0 tal que |p_{n}(z)| ≤ c, para todos n ≥ 1 e todos z ∈ ℂ

com |z| = 1 e z ≠ λ.

Assim, temos que lim_{n→∞} p_{n}(L)v = 0 em H.

Demonstração. O Teorema Espectral nos dá um espaço de medida (X, A, μ), uma aplicação unitária σ : H → L^{2}(X, A, μ) e uma função mensurável limitada ϕ : X → ℂ tal que o diagrama (6.2.2) comuta. Além disso, como L é unitário, temos que |ϕ| = 1 quase sempre. Verifica-se diretamente que o diagrama

\xymatrix{H \ar[r]^{p_{n}(L)} \ar[d]^{≅}_{σ} & H \ar[d]_{≅}^{σ} \\ L^{2}(X, A, μ) \ar[r]_{M_{pn∘ϕ}} & L^{2}(X, A, μ)}

comuta, para todo n ≥ 1. Pondo f = σ(v) ∈ L^{2}(X, A, μ), vemos que

(6.2.3)  ∥p_{n}(L)v∥^{2} = ∫_{X} |p_{n}(ϕ(x))f(x)|^{2} dμ,

para todo n ≥ 1. Além disso, f é ortogonal a Ker(M_{ϕ} − λ1) e, portanto,

f ∈ L^{2}(X \ ϕ^{−1}(λ)),

ou seja, f(x) = 0 para quase todo x com ϕ(x) = λ. Afirmamos que

lim_{n→∞} p_{n}(ϕ(x))f(x) = 0,

para quase todo x ∈ X. De fato, para quase todo x com ϕ(x) ≠ λ, temos que lim_{n→∞} p_{n}(ϕ(x)) = 0 e, para quase todo x com ϕ(x) = λ, f(x) = 0.

Claramente, temos que

|p_{n}(ϕ(x))f(x)|^{2} ≤ c^{2}|f(x)|^{2},

para quase todo x ∈ X. Usando agora o Teorema da Convergência Dominada, vemos que

lim_{n→∞} ∫_{X} |p_{n}(ϕ(x))f(x)|^{2} dμ = 0.

O resultado segue então da equação (6.2.3) acima. □

Lema 6.2.11 ([31, 35]). Se {s_{n}} ⊂ ℤ é tal que, para todo 0 < α < 1, lim_{N→∞} N^{−1} ∑_{n=1}^{N} e^{2πiαs_{n}} = 0, então, para qualquer sistema que preserva medida de probabilidade (X, B, μ, T), temos que, se I_{0} ⊂ L^{2}(X, B, μ) denota o subespaço fechado das funções T -invariantes e π_{0} a projeção ortogonal em I_{0}, então, para toda f ∈ L^{2}(X, B, μ),

lim_{N→∞} ∥\frac{1}{N} ∑_{n=1}^{N} (f ∘ T^{s_{n}}) − π_{0}f∥_{L^{2}} = 0.

Demonstração. Considere o operador U no espaço de Hilbert complexo L^{2}(X, B, μ) definido por

U(f) = f ∘ T,

para toda f ∈ L^{2}(X, B, μ). Como T é um isomorfismo de medida, temos que U é unitário. Agora, fixe f ∈ L^{2}(X, B, μ) e ponha g = π_{0}f, i.e., g é a projeção ortogonal de f no subespaço fechado I_{0} = Ker(U − 1). Temos que f − g é ortogonal a todo elemento de Ker(U − 1). Agora, para cada inteiro N ≥ 1, seja p_{N} o polinômio de Laurent definido por

p_{N}(z) = \frac{1}{N} ∑_{n=1}^{N} z^{s_{n}}.

Da hipótese, segue que

lim_{N→∞} p_{N}(z) = 0,

para todo z ∈ ℂ com |z| = 1 e z ≠ 1. Claramente, temos que

|p_{N}(z)| ≤ 1,

para todo N ≥ 1 e todo z ∈ ℂ com |z| = 1. Como v = f − g é ortogonal a Ker(U − 1), podemos usar o Lema 6.2.10 acima para ver que

lim_{N→∞} \frac{1}{N} ∑_{n=1}^{N} U^{s_{n}}(f − g) = 0

em L^{2}(X, B, μ). Como Ug = g, concluímos que

(6.2.4)  lim_{N→∞} \frac{1}{N} ∑_{n=1}^{N} f ∘ T^{s_{n}} = lim_{N→∞} \frac{1}{N} ∑_{n=1}^{N} U^{s_{n}}f = g = π_{0}f

em L^{2}(X, B, μ). □

Podemos dar agora um esboço da prova do Lema 6.2.4 acima.

DEMONSTRAÇÃO do Lema 6.2.4 ([31]). Sejam então (X, B, μ, T) um sistema que preserva medida de probabilidade e B ∈ B com μ(B) > 0. Considere o operador unitário U no espaço de Hilbert complexo L^{2}(X, B, μ) definido como na prova do Lema 6.2.11 acima e seja g a projeção ortogonal da função χ_{B} no subespaço fechado Ker(U −1). Como a sequência (s_{n} = n) claramente satisfaz as hipóteses do Lema 6.2.11, vemos que

lim_{N→∞} ∥\frac{1}{N} ∑_{n=1}^{N} (χ_{B} ∘ T^{n}) − g ∥_{L^{2}} = 0.

Temos então que existe uma subsequência N_{k} tal que

lim_{k→∞} \frac{1}{N_{k}} ∑_{n=1}^{N_{k}} χ_{B}(T^{n}x) = g(x), para quase todo x ∈ X.

Agora, não é difícil ver que g ≥ 0 e que μ ({x ∈ X : g(x) > 0}) > 0. Logo, temos que o conjunto

{x ∈ X : {n ≥ 0 : T^{n}x ∈ B} é substancial}}

tem medida positiva. Assim, o conjunto

{x ∈ X : existe P (x) ∈ P tal que, ∀ u ∈ P (x), T^{u}x ∈ B}

também tem medida positiva. Como P é enumerável, vemos que de fato existe P ∈ P tal que o conjunto {x ∈ X : P (x) = P } tem medida positiva. Na outra direção, seja então A ⊂ ℤ um conjunto substancial. Considere as medidas de probabilidade discretas μ_{i} em {0, 1}^{ℤ} definidas por

μ_{i} = \frac{1}{k_{i}} ∑_{j=n_{i}+1}^{n_{i}+k_{i}} δ_{T^{j}a},

onde T : {0, 1}^{ℤ} → {0, 1}^{ℤ} denota o shift à esquerda, δ_{y} a medida que é concentrada em y, a = χ_{A} ∈ {0, 1}^{ℤ} e as sequências k_{i} e n_{i} vêm da definição da propriedade de A ser substancial. Agora, seja μ um ponto aderente à sequência {μ_{i}} (no espaço das medidas de probabilidade em {0, 1}^{ℤ} com a topologia induzida pela topologia fraca-∗ no dual de C({0, 1}^{ℤ})). Como μ é invariante por T (já que k_{i} ↗ ∞), temos que T é um isomorfismo de medida. Portanto, ({0, 1}^{ℤ}, B, μ, T) é um sistema que preserva medida de probabilidade (B denota a σ-álgebra de Borel). Ponha agora B = {x ∈ {0, 1}^{ℤ} : x_{0} = 1} ∈ B e note que μ(B) > 0 (já que o conjunto A é substancial). Aplicando então a hipótese ao sistema ({0, 1}^{ℤ}, B, μ, T) e B, não é difícil ver que o fato de P ser invariante por translação nos permite concluir que A necessariamente contém algum elemento de P. □

Daremos a seguir uma demonstração do Teorema 6.2.7 acima.

DEMONSTRAÇÃO do Teorema 6.2.7 ([31]). Sejam então (X, B, μ, T) um sistema que preserva medida de probabilidade e B ∈ B com μ(B) > 0. Considere o operador unitário U no espaço de Hilbert complexo L^{2}(X, B, μ) definido como na prova do Lema 6.2.11 acima e seja g a projeção ortogonal da função χ_{B} no subespaço fechado Ker(U − 1). Temos que χ_{B} − g é ortogonal a todo elemento de Ker(U − 1). Em particular, χ_{B} − g é ortogonal à função que é constantemente igual a 1. Isso nos dá

∫_{X} (χ_{B} − g) dμ = 0,

de onde ∫_{X} g dμ = μ(B) > 0. Portanto, g ≠ 0. Do Lema 6.2.11 acima, temos que

(6.2.5)  lim_{N→∞} \frac{1}{N} ∑_{n=1}^{N} U^{d_{n}}χ_{B} = g

em L^{2}(X, B, μ). Agora, note que

U^{d}χ_{B} = χ_{T^{−d}(B)},

para todo d ∈ ℤ. Multiplicando-se (6.2.5) escalarmente por χ_{B}, vem que

lim_{N→∞} \frac{1}{N} ∑_{n=1}^{N} μ(T^{−d_{n}}(B) ∩ B) = ⟨g, χ_{B}⟩.

Como χ_{B} − g é ortogonal a g, ⟨g, χ_{B}⟩ = ⟨g, χ_{B} − g + g⟩ = ⟨g, g⟩ > 0. Em particular, temos que existe j ≥ 1 tal que

μ(T^{−d_{j}}(B) ∩ B) = μ(B ∩ T^{d_{j}}(B)) > 0,

como queríamos. □

Terminaremos essa seção relacionando a condição no enunciado do Teorema 6.2.7 acima com o Critério de Weyl sobre sequências uniformemente distribuídas módulo 1 (veja também [28]).

Definição 6.2.12. Fixados um espaço de medida (X, A, μ) e uma sequência x = (x_{n}) ⊂ X, ponha

F(x, X) = \{f ∈ L^{1}(X) : lim_{N→∞} \frac{1}{N} ∑_{n=1}^{N} f(x_{n}) = ∫_{X} f dμ\}.

É claro que F(x, X) é um subespaço vetorial de L^{1}(X) e que F(x, X) é fechado por conjugação (no caso complexo). Mais ainda, também não é difícil mostrar os seguintes três resultados gerais sobre F(x, X).

Lema 6.2.13. Sejam f, φ_{k}, ψ_{k} ∈ L^{1}(X) satisfazendo φ_{k} ≤ f ≤ ψ_{k}. Se φ_{k}, ψ_{k} ∈ F(x, X), ∫ φ_{k} → ∫ f e ∫ ψ_{k} → ∫ f, então f ∈ F(x, X). □

Teorema 6.2.14. Se X satisfaz μ(X) < ∞ e f_{k} ∈ F(x, X) é tal que f_{k} → f uniformemente, então f ∈ F(x, X). □

Corolário 6.2.15. Se X = [0, 1] e μ é a medida de Lebesgue em [0, 1], então as três condições seguintes são equivalentes.

• As funções características χ_{[a,b)} de intervalos semi-fechados pertencem (todas) a F(x, [0, 1]).

• As funções de [0, 1] em ℂ que são contínuas e iguais nos extremos pertencem a F(x, [0, 1]).

• As funções de [0, 1] em ℂ que são Riemann-integráveis pertencem a F(x, [0, 1]). □

O Teorema de Stone-Weierstrass diz o seguinte.

Teorema 6.2.16 (Stone-Weierstrass). Sejam X um espaço compacto (Hausdorff) e C(X) a álgebra das funções contínuas de X em ℂ (o produto em C(X) é definido ponto a ponto) com a topologia da convergência uniforme (i.e., com a norma do sup). Se A ⊂ C(X) é uma subálgebra que contém as funções constantes, separa pontos (ou seja, para todos x ≠ y ∈ X, existe f ∈ A com f(x) ≠ f(y)) e é fechada por conjugação (i.e., se f ∈ A, então f̄ ∈ A), então A é densa em C(X). □

Definição 6.2.17. Diremos que uma sequência x = (x_{n}) ⊂ [0, 1] é uniformemente distribuída em [0, 1] se as funções características de intervalos semi-fechados estão todas em F(x, [0, 1]), i.e., se para todos a < b ∈ [0, 1], temos que lim_{N→∞} N^{−1} # {n ∈ [N] : a ≤ x_{n} < b} = ∫ χ_{[a,b)} dμ = b − a.

Definição 6.2.18. Diremos que uma sequência (x_{n}) ⊂ ℝ é uniformemente distribuída módulo 1 se a sequência ({x_{n}}) (das partes fracionárias) é uniformemente distribuída em [0, 1].

Podemos agora enunciar e mostrar o Critério de Weyl.

Teorema 6.2.19 (Weyl). Uma sequência (x_{n}) ∈ ℝ é uniformemente distribuída módulo 1 sse lim_{N→∞} N^{−1} ∑_{n=1}^{N} e^{2πihx_{n}} = 0, ∀ h ∈ ℤ \ {0}.

Demonstração. Ponha S^{1} = {z ∈ ℂ : |z| = 1}. Pelo Teorema de Stone-Weierstrass (Teorema 6.2.16 acima), o conjunto dos polinômios de Laurent (restritos a S^{1}) com coeficientes complexos é denso em C(S^{1}). Assim, temos que o subespaço gerado pelo conjunto {e^{2πih} : [0, 1] → ℂ : h ∈ ℤ} é denso no espaço das funções de [0, 1] em ℂ que são contínuas e iguais nos extremos. Podemos então usar o Teorema 6.2.14 e o Corolário 6.2.15 acima para concluir o resultado. □

Definição 6.2.20. Dado m ∈ ℤ^{+}, m ≥ 2, diremos que uma sequência {s_{n}} ⊂ ℤ é uniformemente distribuída módulo m se

lim_{N→∞} N^{−1} #\{n ∈ [N] : s_{n} ≡ j (mod m)\} = \frac{1}{m},

para todo j ∈ {0, 1, …, m − 1}.

Definição 6.2.21. Diremos que uma sequência {s_{n}} ⊂ ℤ é uniformemente distribuída em ℤ se {s_{n}} é uniformemente distribuída módulo m para todo m ≥ 2.

Lema 6.2.22. Temos que uma sequência {s_{n}} ⊂ ℤ é uniformemente distribuída em ℤ sse lim_{N→∞} N^{−1} ∑_{n=1}^{N} e^{2πirs_{n}} = 0 para todo r ∈ ℚ \ ℤ.

Demonstração. Imediata. □

Teorema 6.2.23. Uma dada sequência {d_{n}} ⊂ ℤ^{+} satisfaz

lim_{N→∞} \frac{1}{N} ∑_{n=1}^{N} e^{2πiαd_{n}} = 0

para todo 0 < α < 1 sse {d_{n}} é uniformemente distribuída em ℤ e {βd_{n}} é uniformemente distribuída módulo 1 para todo 0 < β < 1 irracional.

Demonstração. Aplique o Teorema 6.2.19 e o Lema 6.2.22 acima. □

6.3. Sequências de Fermat

Definição 6.3.1. As sequências F_{m} = {i^{m} : i = 1, 2, …}, m = 1, 2, …, ou seja, as sequências das m-ésimas potências (perfeitas) serão chamadas de sequências de Fermat.

A seguinte extensão do Teorema de Van der Waerden foi mostrada por Bergelson e Leibman (esse resultado é conhecido também como o Teorema de Van de Waerden Polinomial).

Teorema 6.3.2 ([3]). Se p_{1}, …, p_{l} são polinômios em ℤ[X] sem termos constantes, então, para qualquer partição finita {C_{1}, …, C_{J}} de ℤ, existem j ∈ [J] e inteiros a e d ≠ 0 tais que a, a+p_{k}(d) ∈ C_{j}, para k = 1, …, l. □

O Teorema de Van der Waerden original pode ser recuperado colocandose p_{k}(x) = kx, para todo k ∈ [l], no enunciado do Teorema 6.3.2 acima. Ainda, temos que χ(F_{m}) = ∞, para todo m ∈ ℤ^{+} (colocando-se l = 1 e p_{1}(x) = x^{m} no enunciado do Teorema 6.3.2). Em particular, temos que a sequência F_{2} (a sequência dos quadrados perfeitos) tem número cromático infinito. Ao invés de mostrar o Teorema 6.3.2 acima em toda a sua generalidade, nós terminaremos esse capítulo mostrando a seguir como o caso particular χ(F_{2}) = ∞ já segue do Teorema de Van der Waerden “linear”.

Teorema 6.3.3 ([34]). Se colorirmos ℤ^{+} com um número finito de cores, então existem a e d em ℤ^{+} tais que a e a + d^{2} têm a mesma cor.

Demonstração. Nós diremos que a_{i} ∈ ℤ^{+} está focado em a ∈ ℤ^{+} se existe d_{i} ∈ ℤ^{+} tal que a_{i} − a = d_{i}^{2}. Mais geralmente, diremos que a_{1}, a_{2}, …, a_{r} estão focados em a se cada a_{i} está focado em a e todos os a_{i}’s têm cores distintas. Agora, se o seguinte resultado valer para todo k fixado, então a asserção do teorema segue.

(∗) Para todo r ≤ k, existe N ∈ ℤ^{+} tal que se pintarmos [N] com k cores, então ou existem a, a_{1}, a_{2}, …, a_{r} ∈ [N] tais que a_{1}, a_{2}, …, a_{r} estão focados em a ou existem a, a + d^{2} ∈ [N], com d ≠ 0, que têm a mesma cor.

De fato, pondo r = k, vemos que ou a tem a mesma cor que algum a_{i} focado em a ou a e a + d^{2} (d ≠ 0) têm a mesma cor . Assim, é suficiente mostrar que (∗) acima vale. Faremos isso por indução em r. Suponha então que N ∈ ℤ^{+} satisfaz (∗) para r − 1. Precisamos mostrar que existe N′ ∈ ℤ^{+} satisfazendo (∗) para r. Nós não iremos computar o valor de N′ explicitamente - basta que N′ seja grande o suficiente para que o que segue valha. Primeiramente, note que podemos assumir que [N′] não contém a e a + d^{2} (d ≠ 0) da mesma cor. Agora, divida [N′] em blocos de tamanho N e ponha B_{s} = \{(s − 1)N + 1, (s − 1)N + 2, …, sN\} e l = ⌊2\sqrt{N}⌋. Como só existe um número finito de maneiras de se colorir um desses blocos com k cores, podemos aplicar o Teorema de Van der Waerden aos blocos e concluir que existe uma progressão aritmética B_{s}, B_{s+t}, …, B_{s+lt} de blocos identicamente coloridos. Agora, pela escolha de N e pelo que assumimos sobre [N′], temos que existem a, a_{1}, a_{2}, …, a_{r−1} ∈ B_{s} tais que a_{1}, a_{2}, …, a_{r−1} estão focados em a (já que [N] ⊂ [N′]). Observe que as cores dos a_{i}’s são distintas e que existem d_{i}’s inteiros não-nulos tais que a_{i} = a + d_{i}^{2}. Para terminar a prova, é suficiente então mostrarmos que vale o seguinte.

(∗∗) Temos que a e a_{i} + 2d_{i}Nt (i = 1, 2, …, r − 1) estão focados em a − (Nt)^{2}.

Primeiramente, note que

a + 2d_{i}Nt − (a − (Nt)^{2})) = d_{i}^{2} + 2d_{i}Nt + (Nt)^{2} = (d_{i} + Nt)^{2}

e que

a − (a − (Nt)^{2}) = (Nt)^{2}.

Agora, observe que a_{i} + 2d_{i}Nt e a_{i} têm a mesma cor, pois a_{i} − a = d_{i}^{2} ≤ N, de onde 2d_{i} ≤ l, e, portanto, temos que o bloco B_{s+2d_{i}t} está colorido da mesma forma que o bloco B_{s}. Assim, a_{i} + 2d_{i}Nt, i = 1, 2, …, r − 1, têm cores distintas (já que a_{1}, a_{2}, …, a_{r−1} têm cores distintas). Ainda, vemos que a cor de a é diferente da cor de a_{i} + 2d_{i}Nt, para i = 1, 2, …, r − 1 (pois senão a e a_{i} têm a mesma cor, o que contraria o que assumimos sobre [N′], já que a_{i} está focado em a e ambos pertencem a [N′]). Concluímos portanto que a e a_{i} + 2d_{i}Nt, i = 1, 2, …, r − 1, estão de fato focados em a − (Nt)^{2}, ou seja, que (∗∗) acima vale (observe que a − (Nt)^{2} pode ser negativo, mas como estamos tratando de propriedades que são invariantes por translação, bastaria então somar uma mesma constante a todos os blocos de forma a garantir que a − (Nt)^{2} fique positivo). □

CAPÍTULO 7 O Resultado de Ajtai, Havas e Komlós

Nesse capítulo, iremos expor um resultado de Ajtai, Havas e Komlós que, quando combinado com o Lema 6.2.6 e o Teorema 6.2.7, nos permitirá concluir que, para qualquer sequência infinita {q_{i}} de reais estritamente maiores do que 1 com q_{i} → 1, existe uma sequência infinita D = {d_{i}} ⊂ ℤ^{+} que satisfaz χ(D) = ∞ e d_{i+1}/d_{i} ≥ q_{i}, para todo i.

Lema 7.1 (Markov). Sejam Y uma variável aleatória real não-negativa e x ∈ ℝ com x > 0. Assim, temos que ℙ(Y > x) ≤ 𝔼(Y)/x.

Demonstração. Imediata. □

Lema 7.2 ([1]). Suponha que X_{1}, X_{2}, …, X_{N} são N variáveis aleatórias complexas independentes satisfazendo |X_{n}| ≤ 1, para n = 1, 2, …, N, e ponha S_{N} = X_{1} + X_{2} + ⋯ + X_{N}. Para cada real 0 < ϵ < 1 fixado, temos que se |𝔼(S_{N})| ≤ (ϵ/4)N, então ℙ(|S_{N}| > ϵN) < 4 exp\{−\frac{ϵ^{2}}{100}N\}.

Demonstração. Como |S_{N}| ≤ |ℜ S_{N}| + |ℑ S_{N}|, temos que

ℙ (|S_{N}| > ϵN) ≤ ℙ (|ℜ S_{N}| > \frac{ϵ}{2}N) + ℙ (|ℑ S_{N}| > \frac{ϵ}{2}N) .

Assim, é suficiente mostrarmos que, para variáveis aleatórias reais independentes X_{1}, X_{2}, …, X_{N}, as condições |X_{n}| ≤ 1, para n = 1, 2, …, N, e |𝔼(S_{N})| ≤ (ϵ/2)N implicam

ℙ (|S_{N}| > ϵN) < 2 exp \{−\frac{4ϵ^{2}}{100}N\} .

Usando o Lema 7.1 acima, vemos que, para todo 0 < t < 1,

ℙ (S_{N} > ϵN) = ℙ (exp(tS_{N}) > exp(tϵN)) ≤ exp{−tϵN} 𝔼 (exp(tS_{N})) =

= exp{−tϵN} ∏_{n=1}^{N} 𝔼 (exp(tX_{n})) < exp{−tϵN} ∏_{n=1}^{N} 𝔼(1 + tX_{n} + t^{2}) <

< exp\{−tϵN\} exp\{t 𝔼(S_{N}) + Nt^{2}\} ≤ exp \{−t \frac{ϵ}{2}N + Nt^{2}\} .

Agora, tomando t = ϵ/4 na desigualdade acima, nós vemos que

ℙ(S_{N} > ϵN) < exp \{−\frac{ϵ^{2}}{16}N\} < exp \{−\frac{4ϵ^{2}}{100}N\} .

Trabalhando com −S_{N} no lugar de S_{N} no argumento acima, nós temos que ℙ(−S_{N} < −ϵN) também satisfaz a mesma desigualdade. □

Lema 7.3 (Borel-Cantelli). Sejam A_{1}, A_{2}, … uma sequência de eventos em um espaço de probabilidade e ponha B = lim sup_{n→∞} A_{n} = ⋂_{k=1}^{∞} ⋃_{k}^{∞} A_{n}. Assim, se ∑ ℙ(A_{n}) < ∞, então ℙ(B) = 0.

Demonstração. Para cada k ∈ ℤ^{+}, temos que

ℙ(B) ≤ ℙ ( ⋃_{n=k}^{∞} A_{n}) ≤ ∑_{n=k}^{∞} ℙ(A_{n}).

Como ∑ ℙ(A_{n}) < ∞, vemos que ∑_{n=k}^{∞} ℙ(A_{n}) → 0 quando k → ∞. □

Note que o conjunto B acima é o conjunto dos pontos do espaço de probabilidade que pertencem a infinitos A_{n}’s. Assim, a interpretação de ℙ(B) = 0 é que, com probabilidade 1, só um número finito de A_{n}’s ocorrem.

Teorema 7.4 ([1]). Seja {ϵ_{n}} uma sequência de reais com ϵ_{n} > 0 e ϵ_{n} → 0. Assim, existe uma sequência {d_{n}} ⊂ ℤ^{+} com d_{n+1}/d_{n} ≥ 1+ϵ_{n}, para todo n, que satisfaz lim_{N→∞} N^{−1} ∑_{n=1}^{N} e^{2πiαd_{n}} = 0, para todo 0 < α < 1.

Demonstração. Seja I_{n} = [u_{n}, v_{n}] ⊂ ℤ^{+} uma sequência de intervalos (inteiros) satisfazendo as seguintes três condições.

(a) v_{n} = exp\{o(n)\}, i.e., lim_{n→∞} \frac{log v(n)}{n} = 0;

(b) lim_{N→∞} N^{−1} ∑_{n=1}^{N} 1/|I_{n}| = 0 (e.g., |I_{n}| → ∞); e

(c) u_{n+1}/v_{n} ≥ 1 + ϵ_{n}, para todo n.

Agora, para todo n, escolha d_{n} em I_{n} com probabilidade uniforme e de maneira independente para diferentes valores de n. Não é difícil ver (usando, e.g., , o Lema 6.2.22 e o Teorema 6.2.23) que é suficiente mostrarmos que, com probabilidade 1, a sequência {d_{n}} assim escolhida satisfaz

(+)  lim_{N→∞} \frac{1}{N} ∑_{n=1}^{N} exp\{2πimαd_{n}\} = 0,

para todo 0 < α < 1 irracional e todo m ∈ ℤ^{+}, e também para todo 0 < α = p/q < 1, com mdc(p, q) = 1, e m = 1, 2, …, q − 1.

Agora, fixe m e considere as variáveis aleatórias

X_{n} = exp{2πimαd_{n}}, n = 1, …, N.

Observe que

|𝔼(X_{n})| = |\frac{1 − exp\{2πimα|I_{n}|\}}{1 − exp\{2πimα\}}| · \frac{1}{|I_{n}|} ≤ \frac{2}{|I_{n}|} \frac{1}{|1 − exp\{2πimα\}|} ≤ \frac{1}{2γ|I_{n}|},

se ρ_{m}(α), a distância de α ao racional da forma j/m mais próximo, satisfaz ρ_{m}(α) ≥ γ > 0 (note que, na última desigualdade acima, foi usado o fato de que, para ângulos 0 < θ ≤ π, temos que a maior razão entre o comprimento do arco e o comprimento da corda subentendidos por θ é π/2). Para um dado δ > 0, temos portanto que

|𝔼(S_{N})| ≤ \frac{1}{2ρ_{m}(α)} ∑_{n=1}^{N} \frac{1}{|I_{n}|} < \frac{δ}{4}N,

se tivermos que α satisfaz

ρ_{m}(α) > \frac{2}{δ} \frac{1}{N} ∑_{n=1}^{N} \frac{1}{|I_{n}|}.

Ponha então

q_{N} = \frac{2}{δ} \frac{1}{N} ∑_{n=1}^{N} \frac{1}{|I_{n}|}.

Assim, para um α satisfazendo ρ_{m}(α) > q_{N}, temos (Lema 7.2 acima) que

ℙ (|∑_{n=1}^{N} exp\{2πimαd_{n}\}| > δN) < 4 exp \{−\frac{δ^{2}}{100}N\} .

Consequentemente,

ℙ( |∑_{n=1}^{N} exp\{2πimαd_{n}\}| > δN para algum α da forma k exp \{−\frac{δ^{2}}{200}N\},

k ∈ ℤ^{+}, 0 < α < 1, ρ_{m}(α) > q_{N}) < 4 exp \{−\frac{δ^{2}}{200}N\}.

Dado 0 < α′ < 1 com ρ_{m}(α′) > q_{N}, não é difícil ver que podemos achar um α da forma k exp\{−\frac{δ^{2}}{200}N\}, com k ∈ ℤ^{+}, 0 < α < 1 e ρ_{m}(α) > q_{N}, tal que

|α′ − α| < exp\{−\frac{δ^{2}}{200}N\},

desde que N seja suficientemente grande para termos

(∗)  exp\{−\frac{δ^{2}}{200}N\} < 1/m − 2q_{N}.

Note que temos 1/(2m) ≥ ρ_{m}(α′) > q_{N}, e, portanto, que 1/m − 2q_{N} > 0. Ainda, observe que

|∑_{n=1}^{N} exp{2πimα′d_{n}}| ≤ |∑_{n=1}^{N} exp{2πimαd_{n}}| +

+ ∑_{n=1}^{N} |exp{2πimα′d_{n}} − exp{2πimαd_{n}}|.

A última soma acima é no máximo

2πm|α′ − α| ∑_{n=1}^{N} d_{n} < 2πm exp \{−\frac{δ^{2}}{200}N\} Nd_{N} < δN,

desde que valha

d_{N} < \frac{δ}{2πm} exp \{\frac{δ^{2}}{200}N\} ,

que vale se

(∗∗)  v_{N} < \frac{δ}{2πm} exp \{\frac{δ^{2}}{200}N\} .

Assim, se N satisfaz as desigualdades (∗) e (∗∗) acima, para o evento

A_{N}(δ, m) = {|∑_{n=1}^{N} exp{2πimαd_{n}}| < 2δN, ∀ α, 0 < α < 1, ρ_{m}(α) > q_{N}} ,

nós temos que, se Ā_{N} denota o evento complementar de A_{N}, então

ℙ(Ā_{N}) < 4 exp \{−\frac{δ^{2}}{200}N\} .

Usando (a) e (b) acima, vemos que existe N_{0} = N_{0}(δ, m) ∈ ℤ^{+} tal que

∑_{N>N_{0}} ℙ(Ā_{N}) < ∑_{N>N_{0}} 4 exp \{−\frac{δ^{2}}{200}N\} < ∞.

Portanto, o Lema de Borel-Cantelli (Lema 7.3 acima) nos diz que, com probabilidade 1, existe N_{1} > N_{0} tal que A_{N}(δ, m) vale para todo N > N_{1}. Assim, com probabilidade 1, temos que para todo 0 < α < 1, α não da forma j/m,

lim sup_{N→∞} |\frac{1}{N} ∑_{n=1}^{N} exp\{2πimαd_{n}\}| ≤ 2δ.

Como δ é um número positivo arbitrário, segue que, com probabilidade 1,

lim_{N→∞} \frac{1}{N} ∑_{n=1}^{N} exp\{2πimαd_{n}\} = 0,

para todo α, 0 < α < 1, α não da forma j/m. Agora, como todo α em (+) acima não é da forma j/m (mesmo quando α é racional), temos que, com probabilidade 1, (+) vale. Como não é difícil ver que de fato existem intervalos I_{n} satisfazendo as condições (a), (b) e (c) acima, para terminar a prova basta notar que (c) garante que d_{n+1}/d_{n} ≥ 1 + ϵ_{n}, para todo n. □

Corolário 7.5 ([35]). Se {q_{i}} é uma sequência de reais estritamente maiores do que 1 com q_{i} → 1, então existe uma sequência D = {d_{i}} ⊂ ℤ^{+} que satisfaz χ(D) = ∞ e d_{i+1}/d_{i} ≥ q_{i}, para todo i. □

Demonstração. Basta combinar o Teorema 7.4 acima com o Lema 6.2.6 e o Teorema 6.2.7. □

Observação 7.6. Conforme veremos no Capítulo 8, o Corolário 7.5 acima pode ser obtido muito mais facilmente como corolário do Teorema 8.2.1. Em outras palavras, os resultados da Seção 6.2 e desse capítulo não são necessários para se mostrar o Corolário 7.5 acima. Concluiremos esse capítulo mostrando então dois teoremas interessantes que fazem uso daqueles resultados todos. Esses teoremas têm relação direta com um dos mais importantes resultados de teoria dos grafos obtido por Erdős [17] através do método probabilístico.

Lema 7.7. Se (ε_{n})_{n≥1} é uma sequência em ]0, 1[ tal que a série ∑_{1}^{∞} ε_{n} converge, então

∏_{n=1}^{∞}(1 − ε_{n}) = lim_{n→∞} ∏_{k=1}^{n}(1 − ε_{k}) > 0.

Demonstração. Como

lim_{x→0^{+}} \frac{| ln(1 − x)|}{x} = 1,

temos que a série ∑_{1}^{∞} | ln(1 − ε_{n})| é convergente. Assim, o limite

lim_{n→∞} ∑_{k=1}^{n} ln(1 − ε_{k})

existe em ℝ. Exponenciando, obtemos que

lim_{n→∞} ∏_{k=1}^{n}(1 − ε_{k}) = exp ( lim_{n→∞} ∑_{k=1}^{n} ln(1 − ε_{k})) > 0.  □

Lema 7.8. Se (x_{n})_{n≥1} é uma sequência de escalares que tende a zero, então lim_{n→∞} \frac{1}{n} ∑_{1}^{n} x_{k} = 0.

Demonstração. Dado ε > 0, seja n_{0} ≥ 1 tal que |x_{n}| < \frac{ε}{2}, para todo n > n_{0}. Ainda, seja n_{1} > n_{0} tal que \frac{1}{n_{1}} ∑_{1}^{n_{0}} |x_{k}| < \frac{ε}{2}. Agora, para todo n ≥ n_{1}, temos que

|\frac{1}{n} ∑_{k=1}^{n} x_{k}| ≤ \frac{1}{n} ∑_{k=1}^{n} |x_{k}| = \frac{1}{n} ∑_{k=1}^{n_{0}} |x_{k}| + \frac{1}{n} ∑_{k=n_{0}+1}^{n} |x_{k}| ≤

≤ \frac{1}{n_{1}} ∑_{k=1}^{n_{0}} |x_{k}| + \frac{1}{n − n_{0}} ∑_{k=n_{0}+1}^{n} |x_{k}| < \frac{ε}{2} + \frac{ε}{2} = ε. □

Corolário 7.9. Se (v_{n})_{n≥1} é uma sequência de reais positivos tal que lim_{n→∞} \frac{v_{n+1}}{v_{n}} = 1, então lim_{n→∞} \frac{ln(v_{n})}{n} = 0.

Demonstração. Para todo n ≥ 1, escreva α_{n} = \frac{v_{n+1}}{v_{n}}. Temos que

v_{n} = v_{1} ∏_{k=1}^{n−1} α_{k}

e, portanto, que

\frac{ln(v_{n})}{n} = \frac{1}{n} ln(v_{1}) + \frac{1}{n} ∑_{k=1}^{n−1} ln(α_{k}),

para todo n ≥ 1. Como α_{n} → 1, temos que ln(α_{n}) → 0 e a conclusão segue então do Lema 7.8 acima. □

Lema 7.10 ([27, 31]). Se (ε_{n})_{n≥1} é uma sequência de reais positivos com ε_{n} → 0, então existem sequências (u_{n})_{n≥1} e (v_{n})_{n≥1} de inteiros positivos tais que

(a) u_{n} ≤ v_{n} < u_{n+1}, para todo n ≥ 1;
(b) |I_{n+1}| > n^{2}, para todo n ≥ 1, onde I_{n} = [u_{n}, v_{n}];
(c) a série ∑_{1}^{∞} \frac{n^{2}}{|I_{n}|} é convergente;
(d) lim_{n→∞} \frac{ln(v_{n})}{n} = 0;
(e) u_{n+1} ≥ (1 + ε_{n})v_{n}, para todo n ≥ 1.
Note que a condição (c) acima implica lim_{n→∞} \frac{1}{n} ∑_{1}^{n} \frac{1}{|I_{k}|} = 0.

Demonstração. As sequências (u_{n})_{n≥1} e (v_{n})_{n≥1} serão definidas recursivamente da seguinte forma. Tome u_{1} = 1. Supondo que u_{n} foi definido para um dado n ≥ 1, ponha v_{n} = u_{n}+n^{4} e u_{n+1} como sendo o menor inteiro tal que u_{n+1} ≥ (1 + ε̃_{n})v_{n}, onde ε̃_{n} é definido por

ε̃_{n} = max \{ε_{n}, (\frac{n+1}{n})^{5} − 1\} > 0.

Temos então que |I_{n}| > n^{4}, de modo que as condições (b) e (c) do enunciado estão satisfeitas. Além disso, não é difícil ver que as condições (a) e (e) do enunciado também estão satisfeitas. Falta somente verificarmos então a condição (d). Em virtude do Corolário 7.9 acima, é suficiente verificar que lim_{n→∞} \frac{v_{n+1}}{v_{n}} = 1. Temos

v_{n} < v_{n+1} = u_{n+1} + (n + 1)^{4} ≤ (1 + ε̃_{n})v_{n} + 1 + (n + 1)^{4},

e, portanto,

(i)  1 < \frac{v_{n+1}}{v_{n}} ≤ 1 + ε̃_{n} + \frac{1 + (n + 1)^{4}}{v_{n}} ,

para todo n ≥ 1. Agora, note que

v_{n+1} ≥ u_{n+1} ≥ (1 + ε̃_{n})v_{n} ≥ \frac{(n + 1)^{5}}{n^{5}} v_{n},

para todo n ≥ 1. Segue então por indução em n que

(ii)  v_{n} ≥ n^{5},

para todo n ≥ 1. Agora basta fazer n → ∞ em (i) acima, levando-se em conta (ii) acima e o fato que ε̃_{n} → 0. □

Agora, considere o produto cartesiano Ω = ∏_{1}^{∞} I_{n}, munido da medida de probabilidade produto, onde em cada I_{n} colocamos a medida de probabilidade uniforme. Para cada n ≥ 1, considere a aplicação

π_{n} : Ω ⟶ I_{1} × I_{2} × ⋯ × I_{n}

e o conjunto

T_{n} = {(d_{1}, …, d_{n}) ∈ I_{1} × ⋯ × I_{n} : ℤ(d_{1}, …, d_{n}) não contém triângulos}.

Note que se (d_{1}, …, d_{n}) ∈ I_{1} × ⋯ × I_{n}, então d_{1} < ⋯ < d_{n}. Temos que (π_{n}^{−1}(T_{n}))_{n≥1} é uma sequência decrescente de eventos no espaço de probabilidade Ω e que a intersecção T = ⋂_{n=1}^{∞} π_{n}^{−1}(T_{n}) é o evento

T = {(d_{n})_{n≥1} ∈ Ω : ℤ(d_{1}, d_{2}, …) não contém triângulos}.

Assim,

(iii)  ℙ(T) = lim_{n→∞} ℙ(π_{n}^{−1}(T_{n})),

onde ℙ denota a medida de probabilidade em Ω.

Lema 7.11 ([27, 31]). Nas condições e notações acima, assuma que a série

(iv)  ∑_{n=1}^{∞} \frac{n^{2}}{|I_{n}|}

converge e que existe n_{0} ≥ 1 tal que T_{n_{0}} ≠ ∅ e |I_{n+1}| > n^{2}, para todo n > n_{0}. Podemos concluir então que ℙ(T) > 0.

Demonstração. Seja n ≥ 1 fixado. Para d = (d_{1}, …, d_{n}) em T_{n}, considere o conjunto

A^{d} = {d_{n+1} ∈ I_{n+1} : (d_{1}, …, d_{n}, d_{n+1}) ∈ T_{n+1}} ⊂ I_{n+1}.

Note que

I_{n+1} \ A^{d} ⊂ {d_{i} + d_{j} : i, j = 1, …, n}

e, portanto, temos que |A^{d}| ≥ |I_{n+1}| − n^{2}. Logo,

ℙ[π_{n+1}^{−1}(\{d_{1}\} × ⋯ × \{d_{n}\} × A^{d})] ≥ \frac{1}{|I_{1}| ⋯ |I_{n}|}(1 − \frac{n^{2}}{|I_{n+1}|}).

Agora, como T_{n+1} é a união disjunta dos conjuntos {d_{1}} × ⋯ × {d_{n}} × A^{d}, d = (d_{1}, …, d_{n}) ∈ T_{n}, segue que

ℙ(π_{n+1}^{−1}(T_{n+1})) ≥ \frac{|T_{n}|}{|I_{1}| ⋯ |I_{n}|}(1 − \frac{n^{2}}{|I_{n+1}|}) = ℙ(π_{n}^{−1}(T_{n}))(1 − \frac{n^{2}}{|I_{n+1}|}).

Usando indução em n e a desigualdade acima, vem que

ℙ(π_{n}^{−1}(T_{n})) ≥ ℙ(π_{n_{0}}^{−1}(T_{n_{0}})) ∏_{k=n_{0}}^{n−1} (1 − \frac{k^{2}}{|I_{k+1}|}),

para todo n > n_{0}. Como T_{n_{0}} ≠ ∅, temos que ℙ(π_{n_{0}}^{−1}(T_{n_{0}})) > 0. Além do mais, segue das hipóteses que a série ∑_{1}^{∞} \frac{n^{2}}{|I_{n+1}|} converge. A conclusão vem então da igualdade (iii) e do Lema 7.7 acima. □

Note que T_{1} = I_{1} ≠ ∅. Assim, se a série (iv) acima converge e se |I_{n+1}| > n^{2}, para todo n > 1, então as hipóteses do lema acima estão satisfeitas. Em outras palavras, as condições (b) e (c) do Lema 7.10 acima implicam a conclusão do Lema 7.11 acima. Temos então os ingredientes para mostrar o seguinte resultado.

Teorema 7.12 ([27, 31]). Existe uma sequência D = {d_{i}} ⊂ ℤ^{+} com χ(D) = ∞ tal que ℤ(D) não contém triângulos.

Demonstração. Basta combinar os Lemas 7.11 e 7.10 com o Teorema 7.4 acima. □

Não é difícil ver que basta fazer pequenas modificações nos lemas acima para concluir que na verdade podemos mostrar um pouco mais. Mais precisamente, vale a seguinte generalização do Teorema 7.12 acima.

Teorema 7.13 ([24]). Dado um inteiro l ≥ 3, temos que existe uma sequência D = {d_{i}} ⊂ ℤ^{+} com χ(D) = ∞ tal que ℤ(D) não contém circuitos de tamanho menor ou igual a l. □

Finalmente, enunciamos a seguir o resultado clássico devido a Erdős que tem forte ligação com os teoremas acima e que na época foi considerado um exemplo surpreendente da aplicação do chamado método probabilístico à teoria dos grafos (veja também [2, 26]).

Teorema 7.14 ([17]). Dados inteiros positivos k e l ≥ 3, existe um grafo finito com número cromático maior do que k que não contém circuitos de tamanho menor ou igual a l. □

CAPÍTULO 8 Os Critérios de Ruzsa, Tuza e Voigt

8.1. Sequências Lacunárias

No Capítulo 5, nós vimos um critério geral que nos permite decidir se χ(D) é finito ou não. Em particular, esse critério foi usado para mostrar que se D = {d_{i}} é uma sequência lacunária, i.e., se inf_{i≥1}{d_{i+1}/d_{i}} > 1, então χ(D) < ∞. Observe, porém, que a demonstração não nos deu nenhuma cota superior para χ(D). Nessa seção, iremos fornecer uma outra prova desse fato que, em particular, dá uma cota superior para χ(D) (em termos de inf_{i≥1}{d_{i+1}/d_{i}}). Dado x ∈ ℝ, ⟨x⟩ denotará a distância de x ao inteiro mais próximo de x, ou seja, ⟨x⟩ = min{x − ⌊x⌋, ⌈x⌉ − x}. Nesse capítulo, trataremos somente de D’s infinitos.

Lema 8.1.1 ([30]). Se D = {d_{1}, d_{2}, d_{3}, …} ⊂ ℤ^{+} é infinito e r ≥ 3 é um inteiro tais que d_{i+1}/d_{i} ≥ (2r − 2)/(r − 2) para todo i, então χ(D) ≤ r.

Demonstração. Iremos primeiramente encontrar um x ∈ ℝ que satisfaz ⟨xd_{i}⟩ ≥ 1/r, para todo i. Para achar um tal x, nós definiremos uma sequência encaixante (I_{i} : i ∈ ℤ^{+}) de intervalos fechados não-vazios de ℝ. Essa sequência será definida de forma recursiva. Ponha

I_{1} = [\frac{1}{rd_{1}} , \frac{r − 1}{rd_{1}}] .

Note que o comprimento de I_{1} é l(I_{1}) = (r − 2)/(rd_{1}). Agora, suponha que o intervalo I_{i} de comprimento l(I_{i}) = (r − 2)/(rd_{i}) já esteja definido. Afirmamos que existe z_{i} ∈ ℤ tal que

I_{i+1} = [\frac{z_{i}}{d_{i+1}} + \frac{1}{rd_{i+1}} , \frac{z_{i}}{d_{i+1}} + \frac{r − 1}{rd_{i+1}} ] ⊂ I_{i}.

De fato, note que l(I_{i}) = (r−2)/(rd_{i}) ≥ (2r−2)/(rd_{i+1}) > 1/d_{i+1}. Portanto, existe z_{i} ∈ ℤ tal que z_{i}/d_{i+1} ∈ I_{i}. Agora, se z_{i}/d_{i+1} pertence à primeira metade de I_{i}, então

[\frac{z_{i}}{d_{i+1}} + \frac{1}{rd_{i+1}} , \frac{z_{i}}{d_{i+1}} + \frac{r − 1}{rd_{i+1}} ] ⊂ I_{i},

e, se z_{i}/d_{i+1} pertence à segunda metade de I_{i}, então

[\frac{z_{i} − 1}{d_{i+1}} + \frac{1}{rd_{i+1}} , \frac{z_{i} − 1}{d_{i+1}} + \frac{r − 1}{rd_{i+1}} ] ⊂ I_{i}.

Observe que l(I_{i}) = (r−2)/(rd_{i}) > 0, que l(I_{i}) → 0 e que I_{1} ⊃ I_{2} ⊃ I_{3} ⊃ . . .. Assim, existe um (único) x ∈ ℝ tal que {x} = ⋂_{i=1}^{∞} I_{i}. Pondo z_{0} = 0, vemos que xd_{i} ∈ [z_{i−1} + 1/r, z_{i−1} + (r − 1)/r], para todo i. Portanto, temos que ⟨xd_{i}⟩ ≥ 1/r para todo i, como queríamos. Iremos agora utilizar x para colorir ℝ com r cores e mostrar que essa coloração, quando restrita a ℤ, é uma r-coloração apropriada de ℤ(D). Dado v ∈ ℝ, seja j = j(v) o único número em {0, 1, …, r − 1} tal que {xv} = xv − ⌊xv⌋ ∈ [j/r, (j + 1)/r). Defina φ : ℝ → {0, 1, …, r − 1} por φ(v) = j(v). Note que ℝ é particionado em intervalos semi-fechados sucessivos de comprimento 1/(xr) e que cada um desses intervalos recebe uma cor de forma que [0, xr) recebe a cor 0 e a sequência de cores é …, 0, 1, …, r − 1, 0, 1, …, r − 1, … (periodicamente). Resta mostrarmos então que φ|ℤ é uma r-coloração apropriada de ℤ(D). Suponha, por absurdo, que v > w são dois vértices adjacentes em ℤ(D) tais que φ(w) = φ(v) = j ∈ {0, 1, …, r − 1}. Assim, existem d_{k} ∈ D com v − w = d_{k} e inteiros z_{v} e z_{w} (a saber, z_{v} = ⌊xv⌋ e z_{w} = ⌊xw⌋) tais que z_{v} + j/r ≤ xv < z_{v} + (j + 1)/r e z_{w} + j/r ≤ xw < z_{w} + (j + 1)/r, de onde z_{v}−z_{w}−1/r < xv−xw < z_{v}−z_{w}+1/r, o que nos dá ⟨xd_{k}⟩ = ⟨xv−xw⟩ < 1/r, o que é uma contradição (já que ⟨xd_{i}⟩ ≥ 1/r, para todo i). Logo, vértices adjacentes em ℤ(D) nunca têm a mesma cor e, portanto, φ|ℤ é de fato uma r-coloração apropriada de ℤ(D), de onde concluímos que χ(D) ≤ r. □

Lema 8.1.2 ([30]). Sejam dados k ∈ ℤ^{+} e D = {d_{i}} ⊂ ℤ^{+} infinito. Temos que, se d_{i+1} ≥ 4^{1/k}d_{i} para todo i, então χ(D) ≤ 3^{k} e, se d_{i+1} ≥ 3^{1/k}d_{i} para todo i, então χ(D) ≤ 4^{k}.

Demonstração. Para cada j ∈ {0, 1, …, k − 1}, considere o conjunto D_{j} = {d_{i} : i ≡ j (mod k)}. Note que {D_{j} : j = 0, 1, …, k − 1} é uma partição de D em k subconjuntos. Agora, se d_{i+1} ≥ 4^{1/k}d_{i}, para todo i, então d_{i+k} ≥ 4d_{i}, para todo i, de onde χ(D_{j}) ≤ 3, para todo j (Lema 8.1.1 acima, com r = 3). Ainda, se d_{i+1} ≥ 3^{1/k}d_{i}, para todo i, então d_{i+k} ≥ 3d_{i}, para todo i, de onde χ(D_{j}) ≤ 4, para todo j (Lema 8.1.1, com r = 4). Como ℤ(D) = ⋃_{j=o}^{k−1} ℤ(D_{j}), o resultado segue do Lema 1.2.11. □

Corolário 8.1.3 ([30]). Se D = {d_{i}} é um subconjunto de ℤ^{+} que satisfaz inf_{i≥1}{d_{i+1}/d_{i}} > 1, então χ(D) < ∞. Mais geralmente, se k ∈ ℤ^{+} é tal que inf_{i≥1}{d_{i+k}/d_{i}} > 1, então χ(D) < ∞.

Demonstração. Ponha q = inf_{i≥1}{d_{i+1}/d_{i}}. Agora, fixe um inteiro positivo m ≥ ⌈log 4/ log q⌉. Temos que d_{i+1}/d_{i} ≥ q ≥ 4^{1/m}, para todo i. Do Lema 8.1.2 acima segue portanto que χ(D) ≤ 3^{m}. A segunda asserção também vale, pois, assim como fizemos na prova do Lema 8.1.2, escrevemos ℤ(D) = ⋃_{j=0}^{k−1} ℤ(D_{j}) e podemos então aplicar a primeira asserção a cada um dos D_{j}’s (e, é claro, usar o Lema 1.2.11) para concluir que χ(D) < ∞. □

Observação 8.1.4 ([30]). As melhores escolhas para m satisfazendo q ≥ 4^{1/m} ou q ≥ 3^{1/m} são m_{1} = ⌈log 4/ log q⌉ e m_{2} = ⌈log 3/ log q⌉, respectivamente. Assim, χ(D) ≤ ⌈4(exp{log 3 log 4})^{1/ log q}⌉. Escrevendo q = 1 + ϵ e usando o fato que log(1 + ϵ)/ϵ → 1 quando ϵ → 0, vemos que χ(D) ≤ 4(4,586)^{1/ϵ}, ou seja, que χ(D) ≤ 4(4,586)^{1/(q−1)} (para q suficientemente perto de 1).

8.2. Sequências Subexponenciais

No Capítulo 7, nós mostramos que se uma sequência {q_{i}} de reais estritamente maiores do que 1 satisfaz q_{i} → 1 (não importa quão devagar), então existe uma sequência D = {d_{i}} ⊂ ℤ^{+} que satisfaz χ(D) = ∞ e d_{i+1}/d_{i} ≥ q_{i} para todo i (Corolário 7.5). Note, porém, que a demonstração foi de natureza probabilística, i.e., nós mostramos que uma tal sequência existe sem exibir nenhuma em particular. Nessa seção, iremos construir uma tal sequência (primeiramente no caso de {q_{i}} ser não-crescente e em seguida no caso geral). Mais precisamente, temos o seguinte tipo de “volta” do Corolário 8.1.3 acima.

Teorema 8.2.1 ([30]). Se {ϵ_{i} : i ∈ ℤ^{+}} é uma sequência não-crescente de reais positivos com ϵ_{i} → 0, então temos que existe um conjunto infinito D = {d_{i}} ⊂ ℤ^{+} que satisfaz χ(D) = ∞ e d_{i+1}/d_{i} ≥ 1 + ϵ_{i}, para todo i.

Demonstração. Iremos definir D = {d_{i}} ⊂ ℤ^{+} recursivamente. Seja d_{1} ∈ ℤ^{+} arbitrário. Se d_{i} já está definido, para algum i ≥ 1, então ponha d_{i+j} = jd_{i+1}, para todo j ∈ {1, 2, …, ⌈1/ϵ_{i}⌉ + 1}. Isso define o bloco de distâncias {d_{i+1}, …, d_{i+⌈1/ϵ_{i}⌉+1}}. Entre blocos consecutivos, a condição d_{i+1}/d_{i} ≥ (1 + ϵ_{i})d_{i} é satisfeita automaticamente (pois d_{i+1} = ⌈(1 + ϵ_{i})⌉d_{i}). Já dentro de um determinado bloco, as distâncias formam uma progresão aritmética, e, portanto, a menor razão entre distâncias consecutivas ocorre para as duas últimas distâncias do bloco. Claramente, temos que essa menor razão é 1+1/⌈1/ϵ_{i}⌉ ≥ 1+ϵ_{i+j}, para todo j ≥ 0 (pois a sequência {ϵ_{i}} é nãocrescente). Agora, se considerarmos os elementos de um dado bloco como vértices de ℤ(D), então vemos que eles induzem um subgrafo completo de ℤ(D). Como 1/ϵ_{i} → ∞, então ℤ(D) tem subgrafos (induzidos) completos arbitrariamente grandes, de onde concluímos que χ(D) = ∞. □

Corolário 8.2.2 ([27]). Se {ϵ_{i} : i ∈ ℤ^{+}} é uma sequência de reais positivos com ϵ_{i} → 0, então existe um conjunto infinito D = {d_{i}} ⊂ ℤ^{+} que satisfaz χ(D) = ∞ e d_{i+1}/d_{i} ≥ 1 + ϵ_{i}, para todo i.

Demonstração. Para todo i, ponha ϵ̃_{i} = max{ϵ_{j} : j ≥ i}. Note que, como ϵ_{i} → 0, a sequência ϵ̃_{i} está bem definida e satisfaz as hipóteses do Teorema 8.2.1 acima. Logo, existe um conjunto infinito D = {d_{i}} ⊂ ℤ^{+} que satisfaz χ(D) = ∞ e d_{i+1}/d_{i} ≥ 1 + ϵ̃_{i} ≥ 1 + ϵ_{i}, para todo i. □

O último resultado desse capítulo será uma espécie de generalização do Teorema 8.2.1 acima. Observe, porém, que esse resultado não é uma caracterização da finitude ou não de χ(D) em termos do conjunto D em si (como na Seção 5.1 do Capítulo 5), mas sim em termos do tipo de crescimento de D. Mais precisamente, ele nos permite decidir se numa certa classe de D’s (a saber, aqueles com um crescimento previamente postulado) existe um D que tem número cromático infinito, ou se todos os D’s nessa classe têm número cromático finito (nesse caso, vale um pouco mais - os números cromáticos desses D’s são na verdade uniformemente limitados superiormente).

Teorema 8.2.3 ([30]). Sejam q = (q_{1}, q_{2}, q_{3}, …) uma sequência de reais estritamente maiores do que 1, D(q) = {D = {d_{i}} ⊂ ℤ^{+} : d_{i+1}/d_{i} ≥ q_{i}, ∀ i } e χ(q) = sup{χ(D) : D ∈ D(q)}. Ainda, para todo k inteiro positivo, ponha α_{k} = inf_{i≥1} ∏_{j=0}^{k−1} q_{i+j}. Assim, temos que χ(q) = ∞ sse α_{k} = 1, ∀ k ∈ ℤ^{+}.

Demonstração. Seja k ∈ ℤ^{+} tal que α_{k} > 1. Assim, temos que todo D = {d_{i}} ∈ D(q) satisfaz inf_{i≥1}{d_{i+k}/d_{i}} ≥ α_{k} > 1. Logo, se m ∈ ℤ^{+} é tal que α_{k} ≥ 4^{1/m}, então, para todo D ∈ D(q), χ(D) ≤ 3^{mk} (Lemas 8.1.2 e 1.2.11). Assim, temos que χ(q) < ∞. Na outra direção, suponha que α_{k} = 1 para todo k ∈ ℤ^{+}. Uma forma de mostrarmos que χ(q) = ∞ é construir um D ∈ D(q) tal que χ(D) = ∞. Para tanto, primeiramente definiremos (de forma recursiva) uma sequência de índices (i_{k})_{k=0}^{∞} ⊂ ℤ^{+}. Ponha i_{0} = 1. Se i_{k−1} já está definido para algum k ≥ 1, seja i_{k} o menor inteiro positivo que satisfaz i_{k} ≥ i_{k−1} + k e ∏_{j=0}^{k−1} q_{i_{k}+j} ≤ 1 + 1/k. Pelas hipóteses, é claro que essa sequência de índices está bem definida. Usando essa sequência de índices, iremos construir D bloco a bloco. Os blocos serão os conjuntos {d_{i_{k}}, d_{i_{k}+1}, …, d_{i_{k}+k}} (que têm tamanho k + 1), para todo k ≥ 0, e também os restantes {d_{j}} como blocos unitários (ou seja, sempre que j ∈ ℤ^{+} não for um índice da forma i_{k}, i_{k} + 1, …, i_{k} + k, {d_{j}} é um bloco). Escolha d_{i_{0}} = d_{1} ∈ ℤ^{+} de maneira arbitrária. Agora, se as distâncias {d_{1}, d_{2}, …, d_{i}} já estiverem definidas para algum i ≥ 1, ponha d_{i+1} = ⌈q_{i}d_{i}⌉. Todas as distâncias do bloco que estamos construindo são escolhidas de forma que elas formam uma progressão aritmética de razão d_{i+1}, i.e., pomos d_{i+j} = jd_{i+1}, para j = 1, 2, …, k + 1 (dentro desse bloco). Entre blocos consecutivos, a condição d_{i+1} ≥ q_{i}d_{i} é satisfeita automaticamente. Já dentro de um determinado bloco, a menor razão entre distâncias consecutivas ocorre para as duas últimas distâncias do bloco (já que as distâncias dentro de um mesmo bloco formam uma progressão aritmética). Claramente, essa menor razão é 1 + 1/k ≥ q_{i_{k}+j}, para j = 0, 1, …, k − 1. Assim, temos que D ∈ D(q). Ainda, pelos mesmos argumentos apresentados na prova do Teorema 8.2.1 acima, vemos que ℤ(D) tem subgrafos (induzidos) completos arbitrariamente grandes. Logo, χ(D) = ∞ e, portanto, χ(q) = ∞. □

Observação 8.2.4. Na Seção 6.3 do Capítulo 6, nós vimos que todas as sequências de Fermat F_{m} = (i^{m} : i ∈ ℤ^{+}), m = 1, 2, 3, …, têm número cromático infinito. Gostaríamos de observar que não podemos usar o Teorema 8.2.3 acima (diretamente) para decidir se o número cromático de uma dada sequência de Fermat F_{m} é finito ou não. De fato, se para todo i ∈ ℤ^{+} colocarmos

q_{i} = \frac{(i + 1)^{m}}{i^{m}} ,

então temos que α_{k} = inf_{i≥1} ∏_{j=0}^{k−1} q_{i+j} = inf_{i≥1}(1 + k/i)^{m} = 1, para todo k ∈ ℤ^{+}. Assim, pondo q = (q_{i}), vemos que F_{m} ∈ D(q) e que χ(q) = ∞. Da demonstração do Teorema 8.2.3 acima, concluímos que existe alguma sequência em D(q) que tem número cromático infinito (mas isso claramente não diz nada sobre a (in)finitude de χ(F_{m})).

CAPÍTULO 9 Comentários Finais

No Capítulo 2, os números cromáticos de todas as progressões aritméticas e de todas as cadeias de divisão (que incluem as progressões geométricas) foram calculados (exatamente). Na Seção 1.2 do Capítulo 1, nós vimos que se D ⊂ ℤ^{+} é finito, então χ(D) ≤ |D| + 1 (Lema 1.2.5). Uma pergunta natural portanto é: dado D ⊂ ℤ^{+} finito, quanto vale χ(D)? Surpreendentemente, ainda não se conhecem teoremas do tipo “se, e somente se” que classificam todos os D’s de tamanho n de acordo com o valor de χ(D) (i.e., teoremas do tipo χ(D) = m sse D satisfaz…) para nenhum n ≥ 4. Para o caso n = 3 (o primeiro caso não trivial), só recentemente um teorema assim foi obtido, por Zhu [38] (esse teorema resolve uma conjectura proposta independentemente por Chen at al. [7] e por Voigt [32]). Os dois teoremas a seguir são então os únicos resultados gerais conhecidos que classificam D’s finitos de acordo com o valor de χ(D).

Teorema 9.1 ([7]). Seja D ⊂ ℤ^{+}. Se D = ∅, então χ(D) = 1. Se D = {d}, então χ(D) = 2. Finalmente, se D = {a, b}, com mdc(a, b) = 1, então χ(D) = 2, se a e b são ambos ímpares; e χ(D) = 3, caso contrário.

Demonstração. As duas primeiras asserções são claras. Para ver a última asserção, note que, se a e b são ambos ímpares, então D não tem múltiplos de 2 e, portanto, podemos usar o Lema 1.2.4 para concluir que χ(D) = 2. Finalmente, suponha que a é ímpar e b é par. Note que ℤ(D) contém o circuito 0, a, 2a, …, (b − 1)a, ba, (a − 1)b, (a − 2)b, …, 2b, b, cujo tamanho é a + b. Logo, ℤ(D) contém um circuito de tamanho ímpar, de onde concluímos que χ(D) > 2 e, portanto, que χ(D) = 3 (Lema 1.2.5). □

Teorema 9.2 ([38]). Seja D = {a < b < c} ⊂ ℤ^{+}, com mdc(a, b, c) = 1. Temos que χ(D) = 2 sse os inteiros a, b e c são ímpares; χ(D) = 4 sse a = 1, b = 2 e c ≡ 0 (mod 3) ou a + b = c e a ≢ b (mod 3); e χ(D) = 3, em qualquer outro caso. □

Uma pergunta relacionada a dizer qual é o valor de χ(D) para um dado D ⊂ ℤ^{+} com |D| = n ∈ ℕ nos ocorreu. Se n ≥ 1, então temos que 2 ≤ χ(D) ≤ n+1. Apesar de não sabermos dizer quanto vale χ(D) em geral, será pelo menos verdade que, para todo 2 ≤ m ≤ n + 1, existe D ⊂ ℤ^{+} tal que |D| = n e χ(D) = m? O próximo resultado que apresentaremos é um resultado simples nosso que diz que essa pergunta tem resposta afirmativa, i.e., temos que toda tabela de classificação dos D’s de tamanho n de acordo com o valor de χ(D) é necessariamente completa, qualquer que seja n ∈ ℤ^{+}.

Teorema 9.3. Para todos n ∈ ℤ^{+} e m ∈ {2, 3, …, n+1}, existe D ⊂ ℤ^{+} tal que |D| = n e χ(D) = m.

Demonstração. Seja a ∈ ℤ^{+} tal que mdc(a, m) = 1. Coloque em D os m−1 inteiros a, 2a, …, (m−1) a e também quaisquer outros n−m+1 inteiros positivos que (também) não são múltiplos de m. Note que |D| = n, que χ(D) ≤ m, pois D não contém múltiplos de m (Lema 1.2.4), e que χ(D) ≥ m (pois o subgrafo de ℤ(D) induzido por V = {0, a, 2a, …, (m − 1) a} é um grafo completo com m vértices, de onde temos que χ(D) ≥ χ([V]) = m). □

Voltaremos a esse resultado logo adiante. Agora, uma área de pesquisa mais específica nessa linha foi iniciada por Eggleton et al. [12] - o objetivo é estudar χ(D) quando D ⊂ ℙ, onde ℙ denota o conjunto de todos os números primos. Não é difícil ver que χ(ℙ) = 4 (de fato, basta colorir ℤ módulo 4 e notar que o subgrafo induzido por {0, 1, …, 6} tem número cromático 4). Entretanto, classificar todos os subconjuntos D ⊂ ℙ de acordo com o valor de χ(D) também está em aberto (veja, e.g., [11, 13, 15, 16, 33]).

Na Seção 5.3 do Capítulo 5, nós vimos que, para todo k ∈ ℤ^{+}, existe uma sequência (de número cromático no máximo k^{2}) que é k-universal, i.e., que contém (a menos de um múltiplo) todas as sequências finitas que têm número cromático no máximo k. Agora, usando o Lema 1.2.6, não é difícil ver que, dado D ⊂ ℤ^{+} finito, existe um algoritmo que calcula χ(D). Uma questão natural que surge então é saber se existe um algoritmo eficiente que calcula χ(D) para D’s finitos. Para cada inteiro k ≥ 3 fixado, sabe-se que dizer se um grafo finito G satisfaz χ(G) ≤ k é um problema NP-completo [20]. A conjectura a seguir, proposta por Chappell [6], diz que o mesmo deve ocorrer para grafos-distância com conjuntos-distância finitos (note que segue do Teorema 9.3 acima que existem conjuntos-distância arbitrariamente grandes com número cromático igual a k).

Conjectura 9.4 ([6]). Para cada inteiro k ≥ 3 fixado, determinar se χ(D) ≤ k para conjuntos finitos D ⊂ ℤ^{+} é um problema NP-completo.

Na Seção 6.2 do Capítulo 6, nós mencionamos que a sequência F_{2} (a sequência dos quadrados perfeitos) não satisfaz a hipótese do Teorema 6.2.7. Não é difícil ver que a única sequência de Fermat que satisfaz a hipótese do Teorema 6.2.7 é a sequência F_{1}. Já na Seção 6.3 do Capítulo 6, nós notamos que uma das consequências do Teorema 6.3.2 é que as sequências de Fermat têm número cromático infinito. Uma dúvida que aparece então é: as sequências de Fermat são sequências de Poincaré? Bergelson e Leibman mostraram que sim. Mais precisamente, eles provaram a seguinte generalização do Teorema 6.3.2.

Teorema 9.5 ([3]). Se p_{1}, …, p_{l} são polinômios em ℤ[X] sem termos constantes, então, para qualquer conjunto substancial A ⊂ ℤ, temos que existem inteiros a e d ≠ 0 tais que a, a+p_{k}(d) ∈ A, para k = 1, 2, …, l. □

Na Seção 8.1 do Capítulo 8, nós demos uma cota superior para χ(D) quando D é uma sequência lacunária. Não obstante, o seguinte problema foi mencionado por Ruzsa et al. [30] e continua sem solução.

Problema 9.6 ([30]). Para todo número real ϵ > 0 fixado, considere a coleção D(ϵ) = {D = {d_{i}} ⊂ ℤ^{+} : d_{i+1}/d_{i} ≥ 1 + ϵ, ∀ i} e determine o valor de M(ϵ) = sup{χ(D) : D ∈ D(ϵ)}.

Lembramos que o Corolário 8.1.3 nos diz que M(ϵ) < ∞ para todo ϵ > 0. Mais ainda, nós vimos (Observação 8.1.4) que M(ϵ) ≤ 4(4,586)^{1/ϵ} (para ϵ suficientemente perto de 0). Um outro problema interessante é tentar resolver a seguinte conjectura, devida a Wills [37] (veja também, e.g., [4, 8, 9]).

Conjectura 9.7 ([37]). Para toda sequência finita d_{1}, d_{2}, …, d_{n} de inteiros positivos, existe x ∈ ℝ tal que ⟨xd_{i}⟩ ≥ 1/(n + 1), para i = 1, 2, …, n.

Daremos a seguir uma prova de um resultado (mencionado em [30]) que mostra a relação que existe entre a Conjectura 9.7 acima e certos tipos de colorações apropriadas de grafos-distância com conjuntos-distância finitos.

Definição 9.8 ([39]). Dados α ∈ ℝ com α > 0 e k ∈ ℤ^{+}, a coloração (periódica) de ℝ que atribui a cor i (mod k) ∈ {0, 1, …, k − 1} ao intervalo semi-fechado [iα, (i + 1)α) será chamada de coloração regular de ℝ com k cores e parâmetro α.

Teorema 9.9 ([30]). Para todo D = {d_{1}, d_{2}, …, d_{n}} ⊂ ℤ^{+}, temos que existe uma coloração regular de ℝ com n + 1 cores que induz uma coloração apropriada de ℤ(D) sse a Conjectura 9.7 acima é verdadeira.

Demonstração. Em uma direção, o argumento é essencialmente o mesmo que o apresentado na segunda parte da prova do Lema 8.1.1 (note que a coloração φ ali definida é uma coloração regular de ℝ com r cores e parâmetro 1/(xr)). Na outra direção, se a coloração regular de ℝ com as cores 0, 1, …, n tem parâmetro α, então ponha x = 1/(α(n + 1)). Temos que a cor de v ∈ ℝ é o único número j ∈ {0, 1, …, n} tal que {xv} ∈ [j/(n+1), (j+1)/(n+1)). Agora, como o vértice 0 tem cor 0, nenhum ±d_{i} tem cor 0. Ainda, se algum d_{i} tem cor n, então {xd_{i}} ∈ [n/(n + 1), 1), de onde {−xd_{i}} ∈ (0, 1/(n + 1)]. Temos então que {−xd_{i}} = 1/(n + 1) (pois senão −d_{i} tem cor 0, o que é absurdo). Portanto, {xd_{i}} = n/(n+1). Assim, para todo i ∈ [n], vemos que ou a cor de d_{i} pertence a {1, 2, …, n − 1} ou {xd_{i}} = n/(n + 1). Em qualquer caso, temos que ⟨xd_{i}⟩ ≥ 1/(n + 1). □

Por fim, e a título de curiosidade, nós observamos que o Lema 1.2.7 mais o Teorema 2.2.3 nos dizem que ℤ({k! : k ≥ 1}) (o grafo fatorial ) é um grafo com número cromático finito (na verdade, com número cromático 4) para o qual não existe nenhuma coloração apropriada com um número finito de cores que seja periódica, e que nós podemos usar o Teorema 6.3.2 mais o Último Teorema de Fermat [36] para concluir que os grafos ℤ(F_{m}), m ≥ 3, são exemplos de grafos-distância sobre ℤ com número cromático infinito que não contêm triângulos (veja o Teorema 7.12).

Referências Bibliográficas

[1] Ajtai, H.; Havas, I.; Komlós, J. Every group admits a bad topology. Studies in Pure Math.: to the memory of P. Turán. Edited by P. Erdős, Birkhäuser, 1983, 21–34.

[2] Alon, N.; Spencer, J. H.; Erdős, P. The probabilistic method. John Wiley & Sons, New York, 1992.

[3] Bergelson, V.; Leibman, A. Polynomial extensions of Van der Waerden’s and Szemerédi’s theorems. J. Amer. Math. Soc. 9 (1996), 725–753.

[4] Bienia, W.; Goddyn, L.; Gvozdjak P.; Sebő, A.; Tarsi, M. Flows, view obstructions, and the lonely runner. J. Combin. Theory Ser. B 72 (1998), 1–9.

[5] Cameron, P. The random graph. In The Mathematics of Paul Erdős. II. Edited by R. Graham and J. Nešetřil, Springer-Verlag, Berlin, 1997, 333–351.

[6] Chappell, G. Coloring distance graphs on the integers. preprint, ar-Xiv:math.CO/9805084 (1998).

[7] Chen, J-J.; Chang, G.; Huang, K-C. Integral distance graphs. J. Graph Theory 25 (1997), no. 4, 287–294.

[8] Chen, Y-G. On a conjecture in Diophantine approximations. II. J. Number Theory 37 (1991), 181–198.

[9] Chen, Y-G.; Cusick, T. The view-obstruction problem for n-dimensional cubes. J. Number Theory 74 (1999), 126–133.

[10] de Bruijn, N; Erdős, P. A colour problem for infinite graphs and a problem in the theory of relations. Nederl. Akad. Wetensch. Proc. Ser. A 54 = Indagationes Math. 13 (1951), 369–373.

[11] Eggleton, R. New results on 3-chromatic prime distance graphs. Ars Combinatoria 26B (1988), 153–180.

[12] Eggleton, R.; Erdős, P.; Skilton, D. Colouring prime distance graphs. Graphs and Combinatorics 6 (1990), 17–32.

[13] Eggleton, R.; Erdős, P.; Skilton, D. Colouring the real line. J. Combin. Theory Ser. B 39 (1985), 86–100.

[14] Eggleton, R.; Erdős, P.; Skilton, D. Erratum to Colouring the real line. J. Combin. Theory Ser. B 41 (1986), 139.

[15] Eggleton, R.; Erdős, P.; Skilton, D. Research problem 77. Discrete Math. 58 (1986), 323.

[16] Eggleton, R.; Erdős, P.; Skilton, D. Update on research problem 77. Discrete Math. 69 (1988), 105–106.

[17] Erdős, P. Graph thory and probability. Canadian J. of Math. 11 (1959), 34–38.

[18] Furstenberg, H. Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions. Journal D’Analyse Mathématique 31 (1977), 204–256.

[19] Furstenberg, H; Weiss, B. Topological dynamics and combinatorial number theory. Journal D’Analyse Mathématique 34 (1978), 61–85.

[20] Garey, M.; Johnson, D. Computers and intractability: a guide to the theory of NPcompleteness. Freeman, New York, 1979.

[21] Katznelson, Y. Chromatic numbers of integer distance graphs on ℤ and recurrence. Combinatorica 21 (2001), 211–219.

[22] Kemnitz, A.; Marangio, M. Chromatic numbers of integer distance graphs. Discrete Math. 233 (2001), no. 1-3, 239–246.

[23] Kemnitz, A.; Marangio, M. Edge colorings and total colorings of integer distance graphs. Discussiones Mathematicae. Graph Theory 22 (2002), no. 1, 149–158.

[24] Kohayakawa, Yoshiharu: personal communication.

[25] Kříž, I. Large independent sets in shift-invariant graphs: solution of Bergelson’s problem. Graphs and Combinatorics 3 (1987), 145–158.

[26] Molloy, M.; Reed, B. Graph colouring and the probabilistic method. Springer-Verlag, 2002.

[27] Moreira, Carlos Gustavo Tamm de Araujo: personal communication.

[28] Niederreiter, H.; Kuipers, L. Uniform distribution of sequences. John Wiley & Sons, New York, 1974.

[29] Rado, R. Universal graphs and universal functions. Acta Arith. 9 (1964), 331–340.

[30] Ruzsa, I.Z.; Tuza, Zs.; Voigt, M. Distance graphs with finite chromatic number. J. Combin. Theory Ser. B 85 (2002), 181–187.

[31] Tausk, Daniel Victor: personal communication.

[32] Voigt, M. Colouring of distance graphs. Ars Combinatoria 52 (1999), 3–12.

[33] Voigt, M.; Walther, W. Chromatic number of prime distance graphs. Discrete Applied Math. 51 (1994), 197–209.

[34] Walters, M. Combinatorial proofs of the polynomial Van der Waerden theorem and the polynomial Hales-Jewett theorem. J. London Math. Soc. 2 (2000), no. 61, 1–12.

[35] Weiss, B. Single orbit dynamics. CBMS Regional Conference Series in Math. 95 (1991).

[36] Wiles, A. Modular elliptic curves and Fermat’s last theorem. Ann. of Math. (2) 141 (1995), 443–551.

[37] Wills, J. Zwei Sätze über inhomogene diophantische Approximation von Irrationalzahlen. (In German) Monatsch. Math. 71 (1967), 263–269.

[38] Zhu, X. Circular chromatic number of distance graphs with distance sets of cardinality three. J. Graph Theory 41 (2002), no. 3, 195–207.

[39] Zhu, X. Pattern periodic coloring of distance graphs. J. Combin Theory Ser. B 73 (1998), 195–206.