EXERCÍCIOS DE MATEMÁTICA DISCRETA 2O. SEMESTRE DE 2002

1. [Erdős] Sejam x_{1}, …, x_{n} números reais. Considere as 2^{n} somas da

forma

x_{i_{1}} + ⋯ + x_{i_{k}},

onde i_{1} < ⋯ < i_{k} e k ≥ 0. Digamos que um conjunto S dessas somas seja pequeno se quaisquer dois membros de S distem < 1 (a diferença é menor que 1). Determine o tamanho máximo de um conjunto pequeno supondo que os x_{i} sejam todos tais que |x_{i}| ≥ 1. Isto é, determine f(n) para todo n ≥ 0, onde definimos f(n) como sendo

max_{x_{1},...,x_{n}} max{|S|: S é pequeno}

e o (primeiro) máximo é tomado sobre todas as seqüências x_{1}, …, x_{n} ∈ ℝ com |x_{i}| ≥ 1 para todo i. {Data de entrega: 22/8/2002}

2. (^{+}) [Kleitman] Seja B um espaço normado. (Se você não está familiarizado com espaços normados, suponha que B é o ℝ^{d} para algum d.) Determine f(n) para todo n ≥ 0, onde definimos f(n) como sendo

max_{x_{1},...,x_{n}} max{|S|: S é pequeno}

e o (primeiro) máximo é tomado sobre todas as seqüências x_{1}, …, x_{n} ∈ B com ||x_{i}|| ≥ 1 para todo i (isto é, todos os x_{i} têm norma pelo menos 1).

Naturalmente, este problema se reduz ao Ex. 1 se B é ℝ.

3. [Erdős–Szekeres] Prove que toda seqüência a_{0}, …, a_{n^{2}} contém uma subseqüência monótona com n+1 elementos, isto é, uma subseqüência não-crescente ou uma subseqüência não-decrescente com n+1 elementos. Mais precisamente, prove que existem 0 ≤ i_{0} < ⋯ < i_{n} ≤ n^{2} com a_{i_{0}} ≤ ⋯ ≤ a_{i_{n}} ou com a_{i_{0}} > ⋯ > a_{i_{n}}. {Data de entrega: 27/8/2002}

4. Seja P uma ordem parcial infinita que não contenha uma anticadeia com mais de m elementos (m ∈ ℕ). Deduza da versão finita do teorema de Dilworth que P pode ser coberta por uma família de m cadeias. [Sugestão. Considere o espaço topológico compacto [m]^{P} das funções de P em [m] = {1, …, m}. Caso você não tenha familiaridade com topologia (elementar), dê uma demonstração “puramente combinatória” para o caso em que P é enumerável.]

5. Fixe um inteiro positivo n e considere a ordem parcial P_{n} = ([n], ⪯) sobre [n] com x ⪯ y se e só se x divide y. Encontre uma anticadeia A em P_{n} e uma partição em cadeias C de P_{n} com |A| = |C|. Deduza que A é máximo e |C| é mínimo e assim determine o valor de α(P_{n}) = β(P_{n}). {Data de entrega: 29/8/2002}

Date: Versão de 11 de dezembro de 2002.

6. [Kövári, Sós, e Turán]

(i) Seja G = G^{n} um grafo r-regular (todos os vértices têm grau r), com r ≥ cn para alguma constante c > 0. Conte o número de cópias do grafo K^{2}(1, s) em G e, usando que

n\binom{r}{s} ≥ s\binom{n}{s} para n ≥ n_{0}(s, c),  (1)

deduza que se n é suficientemente grande, então G contém K^{2}(s, s). (Não deixe de provar (1).)

(ii) Use as idéias em (i) e a desigualdade

\frac{1}{n} ∑_{x∈V (G)} \binom{d(x)}{s} ≥ \binom{n^{−1} ∑_{x∈V (G)} d(x)}{s}  (2)

para provar que ex(n, H) = o(n^{2}) (isto é, lim_{n→∞} ex(n, H)/n^{2} = 0) para todo grafo bipartido H. (Você sabe provar (2)?)

(iii) Conclua que ex(n, H) = o(n^{2}) se e só se H é bipartido. {Data de entrega: 10/9/2002}

7. Seja G um grafo infinito. A densidade superior σ̄(G) de G é definida

como sendo

lim sup_{n→∞} σ_{n}(G),  (3)

onde

σ_{n}(G) = sup{σ(G[W]): W ⊂ V (G), |W | = n},  (4)

e σ(G[W]) denota a densidade e(G[W])\binom{|W |}{2}^{−1} do grafo G[W] = (W, E(G)∩\binom{W}{2}) induzido por W em G. Deduza do teorema de Erdős e Stone que as únicas densidades superiores possíveis são

0, \frac{1}{2}, \frac{2}{3}, …, 1.

Isto é

\{σ̄(G): G grafo infinito\} = \{1 − \frac{1}{t}: t ∈ ℕ\} ∪ \{1\}.

8. [Erdős] Seja f^{(d)}(n) o número máximo de vezes que a distância 1 ocorre em uma configuração de n pontos em ℝ^{d}. Mostre que f^{(2)}(n) = O(n^{3/2}). [Sugestão. Prove que ex(n, K^{(2)}(2, 3)) = O(n^{3/2}) usando o método do Ex. 6 e use este resultado (K^{(2)}(2, 3) é o grafo bipartido completo com classes de vértices de cardinalidades 2 e 3).] {Data de entrega: 12/9/2002}

9. (^{+}) (Continuação do Ex. 8) Mostre que f^{(2)}(n) é superlinear, isto é,

lim_{n→∞} f^{(2)}(n)/n = ∞.

10. Seja H ⊂ \binom{[n]}{k} um hipergrafo k-uniforme. Para x = (x_{i})_{1≤i≤n} ∈ ℝ^{n}, seja

λ_{H}(x) = ∑_{H∈H} ∏_{i∈H} x_{i}.  (5)

Em palavras, para cada hiperaresta H de H, consideramos o monômio ∏_{i∈H} x_{i}, e consideramos a soma de todos estes monômios. Pomos

Δ = {x = (x_{i})_{1≤i≤n} ∈ ℝ^{n}:

∑_{1≤i≤n} x_{i} = 1 e x_{i} ≥ 0 para todo i} (6)

e

λ^{∗}(H) = sup{λ_{H}(x): x ∈ Δ}.  (7)

Para x = (x_{i})_{1≤i≤n} ∈ ℝ^{n}, seja

supp(x) = {i ∈ [n]: x_{i} ≠ 0}.  (8)

Segue da compacidade de Δ que λ^{∗}(H) = λ_{H}(x^{∗}) para algum x^{∗} = (x_{i}^{∗})_{1≤i≤n} ∈ Δ. Podemos, ademais, escolher x^{∗} de forma que a cardinalidade de supp(x^{∗}) seja a menor possível.

• [Frankl e Rödl] Prove que para todo i e j ∈ supp(x^{∗}), existe H ∈

H tal que {i, j} ⊂ H ⊂ supp(x^{∗}).

11. [Motzkin e Straus] (Continuação do Ex. 10)

(i) Mostre que λ^{∗}(H) ≥ |H|/n^{k}. (ii) Suponha agora que k = 2, isto é, estamos falando de grafos.

Seja ω(H) o número máximo de vértices mutuamente adjacentes em H, isto é, ω(H) = max{k: H contém K^{k}}. Mostre que

λ^{∗}(H) ≤ \frac{1}{2} (1 − \frac{1}{ω} ) .  (9)

(iii) Deduza o seguinte corolário do teorema de Turán: para todo t ≥ 1, temos

lim_{n→∞} ex(n, K^{t+1})\binom{n}{2}^{−1} = 1 − \frac{1}{t}.  (10)

{Data de entrega: 17/9/02}

12. Para inteiros t ≤ n, ponha

g(n, t) = max |F|  (11)

onde o máximo é tomado sobre todos os F ⊂ P([n]) = 2^{[n]} que são t-intersectantes, isto é, para todo F e F′ ∈ F, temos |F ∩ F′| ≥ t. (Note que, aqui, não estamos considerando r-grafos para algum r fixo, mas sistemas de conjuntos sem restrição de cardinalidade para seus membros).

(i) Mostre que g(n, 1) = 2^{n−1}.

(ii) Mostre que, para todo inteiro t ≥ 2, temos g(n, t) = (1+o(1))2^{n−1}. Isto é, prove que lim_{n→∞} g(n, t)2^{−n+1} = 1. [Sugestão. Use a fórmula de Stirling

n! = (1 + o(1)) (\frac{n}{e})^{n} \sqrt{2πn}  (12)

para provar que

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

para todo k ∈ ℤ fixo. Deduza que

∑_{k≥(n+t)/2} \binom{n}{k} = (1 + o(1))2^{n−1},

e use esse fato.] {Data de entrega: 19/9/2002}

13. Provamos que, para todo primo p, temos que o número cromático do ℝ^{n} satisfaz

c(4p − 1) ≥ \binom{4p − 1}{2p − 1}( ∑_{0≤j<p} \binom{4p − 1}{j})^{−1}.  (14)

(i) Prove que

∑_{0≤j<p} \binom{4p − 1}{j} ≤ (1 + \frac{1}{3} + \frac{1}{3^{2}} + …) \binom{4p − 1}{p − 1} ≤ \frac{3}{2}\binom{4p − 1}{p − 1}.

(ii) Use a fórmula de Stirling (12) para deduzir que

\binom{n}{αn} = (\frac{1}{α^{α}(1 − α)^{1−α}} )^{(1+o(1))n} ,

ou, equivalentemente,

lim_{n→∞} \frac{1}{n} log \binom{n}{αn} = H(α),

onde H(α) = α log(1/α)+(1−α) log(1/(1−α)) é a assim chamada função entropia.

(iii) Prove que o lado direito de (14) é pelo menos (1.139)^{4p−1} se p é

suficientemente grande. {Data de entrega: 24/9/2002}

14. O Exercício 13 mostra que c(4p − 1) ≥ (1.139)^{4p−1} para todo primo p suficientemente grande. Seja π(x) o número de números primos p ≤ x. O bem conhecido teorema dos números primos diz que

lim_{x→∞} π(x)\frac{log x}{x} = 1.

Use esse resultado para provar que c(n) ≥ (1.13)^{n} para todo n suficientemente grande.

15. Seja p um primo. Construa um conjunto X de \binom{4p}{2p} pontos em ℝ^{4p−1} com a seguinte propriedade: todo X′ ⊂ X que não contém dois elementos ortogonais é tal que

|X′| ≤ 2 ∑_{0≤j<p} \binom{4p}{j}.

[Sugestão. Considere vetores com coordenadas ±1 em ℝ^{4p} com o mesmo número de +1s e −1s.] Use esse conjunto X para construir conjuntos Y ⊂ ℝ^{d} que desprovam a conjectura de Borsuk, onde d = \binom{4p−1}{2}. [Sugestão. Considere a aplicação

g: (a_{ij})_{1≤i,j≤4p−1} ↦ (a_{ij})_{1≤i<j≤4p−1},

que leva matrizes (4p − 1) × (4p − 1) em matrizes triangulares superiores.] {Data de entrega: 26/9/2002}

16. [Problema de Witsenhausen; Frankl e Wilson] Seja S^{d} ⊂ ℝ^{d+1} a esfera unitária em ℝ^{d+1}:

S^{d} = {x ∈ ℝ^{d+1} : ∥x∥ = 1}.

Pomos

μ(d) = sup_{E} \frac{μ_{d}(E)}{μ_{d}(S^{d})},  (15)

onde o supremo é tomado sobre todos os conjuntos (mensuráveis) E ⊂ S^{d} que não contêm dois vetores ortogonais, e μ denota a medida de Lebesgue d-dimensional. Mostre que μ(d) ≤ (1 − ε)^{d} para alguma constante absoluta ε > 0. [Observação. A única dificuldade desse exercício está na teoria da medida envolvida, pois tudo se resume em uma aplicação do teorema de Fubini. Aqueles que não têm familiaridade suficiente com a teoria da medida podem dar um “argumento informal” para provar esse resultado.]

17. [Frankl e Wilson]

(i) Seja A ⊂ \binom{[n]}{k} um sistema de k-conjuntos e L um conjunto de s inteiros. Suponha que, para todo A e A′ ∈ A distintos, temos |A ∩ A′| ∈ L. Prove que

|A| ≤ ∑_{0≤j≤s} \binom{n}{j}.  (16)

(ii) Sejam p um primo e n um inteiro positivo, e considere o grafo completo K com conjunto de vértices

V = \binom{[n]}{p^{2} − 1}.  (17)

Pinte a aresta {A, B} de K de azul se

|A ∩ B| ≡ −1 (mod p)  (18)

e de vermelho caso contrário. Seja α(n, p) o número máximo de vértices em um subgrafo completo vermelho em K, e seja ω(n, p) o número máximo de vértices em um subgrafo completo azul em K. Prove que se p − 1 ≤ (n + 1)/3, então

α(n, p), ω(n, p) < 2\binom{n}{p − 1}.  (19)

{Data de entrega: 3/10/2002}

18. (Continuação do Ex. 17) Use o teorema dos números primos (veja Ex. 14) e umas estimativas simples para coeficientes binomiais para mostrar que, escolhendo n = p^{3}, a coloração definida acima prova (construtivamente!) o seguinte: para todo ε > 0, se t ≥ t_{0}(ε), o número de Ramsey R(t) satisfaz

R(t) ≥ exp \{(\frac{1}{4} − ε) \frac{(log t)^{2}}{log log t}\} .  (20)

A cota inferior para R(t) em (20) é a melhor que se sabe provar de forma construtiva.

19. Fixe um inteiro positivo n. Nesta questão, escrevemos {x < y} para um par de inteiros {x, y} com x < y. Considere o grafo Γ = Γ_{n} cujos vértices são os pares {x, y} ⊂ [n] e cujas arestas são todos os pares de vértices da forma

{{x < y}, {y < z}}.

(Γ = Γ_{n} tem \binom{n}{2} vértices e \binom{n}{3} arestas.) Observe que Γ não tem triângulos. Mostre que, dado qualquer inteiro k, existe n_{0} tal que se n ≥ n_{0}, então o número cromático de Γ = Γ_{n} é pelo menos k. {Data de entrega: 15/10/2002}

20. [de Bruijn e Erdős] Seja G = (V, E) um grafo e k um inteiro. Suponha que χ(G) ≥ k. Prove que G contém um subgrafo finito H com χ(H) ≥ k. Equivalentemente, mostre que existe W ⊂ V finito com o grafo G[W] induzido por W em G tal que χ(G[W]) ≥ k. O grafo G[W] tem, por definição, conjunto de vértices W e conjunto de arestas

\binom{W}{2} ∩ E.

21. [Erdős e Hajnal] Fixe um inteiro d e um real ε > 0. O grafo de Borsuk B(d, ε) tem como conjunto de vértices

S^{d} = {x ∈ ℝ^{d+1} : ∥x∥ = 1}

e {x, y} ⊂ S^{d} é uma aresta de B(d, ε) se

∥x − y∥ ≥ 2 − ε.

Prove que para todo k e ℓ inteiros, existem d e ε > 0 tais que B(d, ε) tem número cromático ≥ k e cintura ímpar ≥ 2ℓ + 1. A cintura ímpar og(G) de um grafo G é o comprimento mínimo de um circuito de comprimento ímpar em G:

og(G) = min{2r + 1: ∃x_{0}, …, x_{2r} ∈ V (G) distintos com {x_{i−1}, x_{i}} ∈ E(G) para todo i (índices mod 2r + 1)}

[Sugestão. Use o teorema de Borsuk: se cobrimos a esfera S^{d} com d+1 fechados (respectivamente, abertos), sempre há um par de pontos antípodas em um dos fechados (respectivamente, abertos).]

Deduza do Ex. 20 que B(d, ε) (com d e ε apropriados) contém subgrafos finitos G com χ(G) ≥ k e og(G) ≥ 2ℓ + 1.

22. (Continuação do Ex. 21) Nesta questão, dizemos que um grafo G tem a propriedade P (c) se todo subgrafo H de G é tal que α(H) ≥ c|V (H)|.

(i) Mostre que se G é tal que χ(G) = k, então G tem a propriedade P (1/k).

(ii) Mostre que se G tem a propriedade P (1/2), então χ(G) ≤ 2. (iii) Mostre que para todo inteiro k e 0 < c < 1/2, existe um grafo G

que tem a propriedade P (c) mas χ(G) ≥ k. [Sugestão. Mostre que B(d, ε) com d e ε apropriados é um tal grafo.]

23. Suponha que

p = p(n) = \frac{log n + f}{n} ,  (21)

onde f = f(n), e considere o grafo aleatório G(n, p). Prove que as seguintes asserções valem para quase todo G = G(n, p).

(i) Se f = f(n) → ∞, então G não tem vértices isolados. (ii) Se f = f(n) → −∞ e |f| ≤ log n, então G tem vértices isolados.

De fato, o número de vértices isolados X = X(G) em G satisfaz

X ∼ exp{−f}.

(iii) O que você consegue dizer sobre o caso em que f = f(n) → f_{0}

para alguma contante f_{0}? {Data de entrega: 17/10/2002}

24. Considere [n] = {1, …, n} e suponha que sorteamos um subconjunto aleatório R de [n] colocando x ∈ [n] em R com probabilidade p, independentemente para cada x. Considere a propriedade PA_{k} de R conter uma progressão aritmética de k elementos, onde k ≥ 3 é um inteiro fixo, independente de n. Mostre que p^{∗} = p^{∗}(n) = n^{−2/k} é uma função limiar para a propriedade PA_{k}. {Data de entrega: 22/10/2002}.

25. Considere a identidade

∑_{0≤k≤n} \binom{n}{k} = 2^{n},  (22)

e seja ω = ω(n) uma função com ω → ∞ conforme n → ∞. Podemos dizer que a soma em (22) está ‘concentrada’ nos termos com k satisfazendo

|k − \frac{n}{2}| ≤ ω\sqrt{n},  (23)

pois

∑_{k}^{∗} \binom{n}{k} ∼ 2^{n},  (24)

onde ∑_{k}^{∗} indica soma sobre todos os k satisfazendo (23) e escrevemos f(n) ∼ g(n) se lim_{n} f(n)/g(n) = 1.

Suponha agora que ε > 0 é um número real fixo. Podemos dizer que a soma em (22) está ‘exponencialmente concentrada’ nos termos com k satisfazendo

|k − \frac{n}{2}| ≤ εn,  (25)

pois

∑′_{k} \binom{n}{k} ≤ 2^{n} exp\{−c_{ε}n\},  (26)

onde ∑′_{k} indica soma sobre todos os k para os quais (25) não vale, c_{ε} > 0 é uma constante que depende apenas de ε, e supomos n ≥ n_{0}(ε).

(i) Prove (24). (ii) Prove que a condição de que ω → ∞ é necessária para que (24)

valha. Para tanto, use a fórmula de Stirling (12). De fato, use (12) para provar que se k = k(n) = n/2+c_{n}\sqrt{n}, onde c_{n} → c (n → ∞) e c é uma constante, então

\binom{n}{k} = \frac{n!}{k!(n − k)!} ∼ \frac{d}{\sqrt{n}}2^{n},  (27)

onde d = d(c) > 0 é uma constante que depende apenas de c. (iii) Prove (26). Qual é o maior valor de c_{ε} com o qual você consegue

provar (26)? [Sugestão. Considere um variável aleatória binomial X de parâmetros n e 1/2, de forma que ℙ(X = k) = \binom{n}{k}2^{−n}. Para (i), aplique a desigualdade de Chebyshev. Para (iii), use uma desigualdade para grandes desvios.] {Data de entrega: 24/10/2002}

26. Prove as seguintes estimativas. Nesta questão, escrevemos O(f(x)) para qualquer termo y tal que |y| ≤ C|f(x)| para todo x satisfazendo |x| ≤ x_{0}, onde C e x_{0} > 0 são constantes absolutas. (Observe que, nestas estimativas, estamos intessados em uma vizinhança de 0.)

(i) 1 + x ≤ e^{x} para todo x ∈ ℝ. (ii) 1 + x > exp {x − x^{2}/2} para todo 0 < x ≤ 1. (iii) 1−x > exp {−x−x^{2}} para todo 0 < x < x_{0}, para algum x_{0} > 0.

De fato, podemos tomar, por exemplo, x_{0} = 0.68. (iv) Prove que 1 + x ≥ exp{x/(1 + x)} para todo x > −1. (Este item

substituiu dois itens que constavam nesta lista anteriormente.)

[Sugestão. Lembre que 1/(1 − x) = 1 + x + x^{2} + … uniformemente se |x| ≤ x_{0} e x_{0} < 1. Integre ambos os lados para obter

− log(1 − x) = x + \frac{1}{2}x^{2} + \frac{1}{3}x^{3} + …]

27. Prove as seguintes estimativas para \binom{a}{b}, onde a e b são inteiros nãonegativos.

(i) Se a ≥ b, então

\binom{a}{b} ≥ (\frac{a}{b})^{b} .  (28)

(ii)

\binom{a}{b} ≤ \frac{a^{b}}{b!} .  (29)

(iii) Para todo b > 0,

\binom{a}{b} ≤ (\frac{ea}{b})^{b} .  (30)

[Sugestão para (iii ). Avalie (1+x)^{a} por cima e por baixo para x = b/a. Use, para tanto, 1 + x ≤ e^{x} e o binômio de Newton: (1 + x)^{a} ≥ \binom{a}{b}x^{b}.]

28. [Shamir–Spencer] Considere o grafo aleatório G = G(n, 1/2), ou, equivalentemente, seja G um grafo escolhido uniformemente ao acaso dentre todos os grafos com n vértices fixos, digamos [n]. Defina

A_{i} = {{i, j}: i < j ≤ n}  (31)

e

Γ_{i} = 2^{A_{i}} = P(A_{i})  (32)

para todo 1 ≤ i < n. Note que os A_{i} (1 ≤ i < n) particionam \binom{[n]}{2}. Assim, podemos identificar G com um vetor (X_{1}, …, X_{n−1}), onde X_{i} ∈ Γ_{i} para todo i. Note que os X_{i} (1 ≤ i < n) são independentes. Como de usual, seja χ(G) o número cromático de G.

(i) Prove que χ: ∏_{1≤i<n} Γ_{i} → ℝ é 1-Lipschitz; note que isso equivale a dizer que para quaisquer dois grafos G e G′ com conjunto de vértices [n], se E(G)△E(G′) = (E(G) ∪ E(G′)) \ (E(G) ∩ E(G′)) ⊂ A_{i} para algum i, então |χ(G) − χ(G′)| ≤ 1.

(ii) Seja λ = λ(n) uma função arbitrária com λ → ∞. Mostre que χ(G) está concentrada em uma faixa de largura 2λ\sqrt{n} em torno de 𝔼(χ), isto é, mostre que a probabilidade de termos

|χ(G) − 𝔼(χ)| ≤ λ\sqrt{n}

é 1 − o(1). (iii) Como de usual, seja ω(G) o número de clique de G, isto é, ω(G) é

a cardinalidade máxima de um conjunto de vértices mutuamente adjacentes em G. Mostre que ω(G) < 2 log_{2} n com probabilidade 1 − o(1), e conclua que χ(G) > n/2 log_{2} n com probabilidade 1 − o(1). [Sugestão. Estime o valor esperado do número de U ⊂ [n], |U| = ⌈2 log_{2} n⌉, com \binom{U}{2} ⊂ E(G) (isto é, U induz um clique). Para tanto, use Ex. 27(iii).]

(iv) Observe que segue de (ii) e (iii) que χ(G) ∼ 𝔼(χ) com probabi-

lidade 1 − o(1). {Data de entrega: 31/10/2002}

29. Chamemos uma cópia de K^{3} (um triângulo) em um grafo G de isolado se ele não tem aresta comum com nenhum outro triângulo. Seja Y o número conjuntos U ∈ \binom{[n]}{3} que induzem um triângulo isolado no grafo aleatório G(n, p). Mostre que 𝔼(Y) ≥ (1/6 − o(1))n^{3}p^{3} se p = λn^{−2/3} com λ = λ(n) → ∞, mas, digamos, λ ≪ n^{1/6}. [Sugestão. Seja X o número de U ∈ \binom{[n]}{3} que induzem um triângulo em G(n, p) e seja Z o número de W ∈ \binom{[n]}{4} que induzem pelo menos 5 arestas. Note que Y ≥ X − 4Z.]^{1}

30. Considere o grafo aleatório G(n, p) com p = λn^{−2/3}, com λ = λ(n) → ∞ e λ ≪ n^{1/6}, e sejam X e Y como no Ex. 29. Prove que

ℙ(X = 0) ≤ ℙ(Y = 0) ≤ exp {−cλ^{6}}  (33)

para uma constante c > 0. [Sugestão. Observe que Y é 1-Lipschitz.] Observação. Infelizmente, a sugestão não está correta (você vê o motivo?). Chamemos uma família de triângulos de independente se quaisquer dois triângulos nesta família não têm aresta comum. Seja Y′ a cardinalidade máxima de uma família independente de triângulos. Mostre que Y′ é 1-Lipschitz. Use esse fato para provar que

ℙ(X = 0) ≤ exp {−cλ^{6}}  (34)

para alguma constante c > 0. {Data de entrega: 5/11/2002}

31. [Łuczak] (Continuação do Ex. 30) A cota superior para ℙ(X = 0) do Ex. 30 pode ser melhorada para

ℙ(X = 0) ≤ exp {−cn^{3}p^{3}}  (35)

para alguma constante c > 0, desde que, digamos, p ≪ 1/\sqrt{n}. Eis um roteiro da prova^{2}: inicialmente, fixe uma coloração γ: \binom{[n]}{2} → [f] de \binom{[n]}{2} com f cores, onde f ∼ Cn^{3}p^{3} e C é uma constante convenientemente grande, e |γ^{−1}(i)| ≤ n^{2}/f para todo i (isto é, cada cor é usada no máximo n^{2}/f vezes).

Defina uma cópia H de K^{3} em G(n, p) como γ-isolada se as cores que ocorrem nas três arestas de H não ocorrem em nenhuma outra cópia H′ de K^{3} em G(n, p) com E(H′)∩E(H) = ∅. Seja Y_{γ} o número de cópias isoladas de K^{3} em G(n, p).

1Os enunciados dos Ex. 29–32 ainda podem sofrer certa revisão.

2Eu ficaria contente se alguém pudesse verificar este roteiro.

(i) Prove que

𝔼(Y_{γ}) ≥ c_{1}n^{3}p^{3}  (36)

para alguma constante c_{1} > 0 desde que C seja suficientemente grande. [Sugestão. Sejam X e Z como no Ex. 29. Como 𝔼(Z) ≪ 𝔼(X), podemos ignorar cópias de K^{3} que não são isoladas (no sentido do Ex. 29). Seja agora Z_{γ} o número de pares (H, H′) de cópias de K^{3} em G(n, p), com E(H) ∩ E(H′) = ∅ e com alguma aresta em H e alguma aresta em H′ da mesma cor (isto é, ambos H e H′ encontram um mesmo γ^{−1}(i) para algum i). Você pode estimar 𝔼(Z_{γ}) por

O (f\binom{n^{2}/f}{2}n^{2}p^{4}) = O (n^{3}p^{3}/C) .

Conclua (36).] (ii) Ponha agora Γ_{i} = 2^{γ^{−1}(i)} = P(γ^{−1}(i)) (1 ≤ i ≤ f). Observe

que G(n, p) pode ser identificado com um vetor (X_{1}, …, X_{f}) com os X_{i} ∈ Γ_{i} para todo i e com os X_{i} independentes. Prove que Y_{γ} é 1-Lipschitz, no sentido que se temos dois grafos G e G′ com E(G)△E(G′) = (E(G) ∪ E(G′)) \ (E(G) ∩ E(G′)) ⊂ γ^{−1}(i) para algum i, então |Y_{γ}(G) − Y_{γ}(G′)| ≤ 1.

(iii) Conclua (35).

32. Dado um grafo G, seja χ_{3}(G) o número mínimo de partes em que podemos particionar o conjunto de vértices de G de forma que cada uma das partes não induza triângulos. Equivalentemente, χ_{3}(G) = k se podemos colorir os vértices de G com k cores de forma que nenhum triângulo fique monocromático (tenha seus 3 vértices da mesma cor), mas k − 1 cores não bastam.^{3} Prove que, para todo inteiro k, existe um grafo G que não contém K^{4}, mas temos χ_{3}(G) ≥ k. [Sugestão. Considere G(n, p) com p = λn^{−2/3} com λ = λ(n) apropriado. Use (35) para mostrar que, com probabilidade 1 − o(1), conjuntos que não induzem K^{3} em G(n, p) são de cardinalidade o(n). Altere G(n, p) de forma apropriada para obter G como no enunciado.] {Data de entrega: 5/11/2002}

33. Seja G = G^{n} um grafo com n vértices e grau máximo

Δ = Δ(G) = max{deg(x): x ∈ V (G)}.

Seja m = |E(G)| o número de arestas em G. Seja 0 < p = p(n) < 1 e suponha que escolhemos um conjunto aleatório W ⊂ V (G) pondo ℙ(x ∈ W) = p, independetemente para todo x ∈ V (G). Seja Y o número de arestas induzidas por W, isto é,

Y = |E(G) ∩ \binom{W}{2}| .

Ponha μ = 𝔼(Y).

3Definindo χ_{2}(G) de forma análoga, χ_{2}(G) = χ(G), o número cromático usual de G.

(i) Observe que μ = p^{2}m. Observe também que Y é Δ-Lipschitz, isto é, se W △W′ = (W \W′)∪(W′\W) é unitário, então |Y (W)− Y (W′)| ≤ Δ.

(ii) Deduza que, para todo t ≥ 0, temos

ℙ(|Y − μ| ≥ t) ≤ 2 exp{−t^{2}/2Δ^{2}n}.  (37)

(iii) Prove que, para alguma constante universal c > 0,

ℙ(|Y − μ| ≥ t) ≤ 4 exp{−ct^{2}/Δ^{2}(μ + t)}  (38)

para todo t ≥ 0. [Sugestão. Note que, para todo inteiro r ≥ 1, a desigualdade Y ≥ r pode ser justificada por um certificado de “tamanho” no máximo 2rΔ^{2}; isto é, tome ψ(r) = 2rΔ^{2}.]

(iv) Suponha agora que G é d-regular, isto é, todos os seus vértices têm grau d. Deduza de (37) e (38) que se

p ≫ min\{n^{−1/4}, \sqrt{d/n}\},

então Y ∼ μ com probabilidade 1 − o(1); isto é, para alguma função g(n) → 0, temos

lim_{n→∞} ℙ(|Y/μ − 1| ≤ g(n)) = 1.

{Data de entrega: 19/11/2002}

34. [Janson] Este exercício ilustra uma forma alternativa de se provar o resultado no Ex. 31.

(i) Prove (35) usando a desigualdade de Janson. Mais explicitamente, mostre que existe uma constante absoluta c > 0 tal que se p ≪ 1/\sqrt{n}, então (35) vale.

(ii) Suponha agora que p ≫ 1/\sqrt{n}. Mostre que a desigualdade (35) não vale. Mostre, entretanto, que

ℙ(X = 0) ≤ exp{−cpn^{2}}

para alguma constante c > 0. Prove ainda que

ℙ(X = 0) ≥ exp{−c′pn^{2}}

para alguma constante c′ > 0. {Data de entrega: 19/11/2002}

35. [Kleitman] Suponha que F, G, H, e I são sistemas de conjuntos sobre o conjunto X = [n], isto é, F, G, H, e I ⊂ 2^{X} = P(X). Suponha ainda que F e G são “fechados por se tomar subconjuntos” e H e I são “fechado por se tomar superconjuntos”. Isto é, se F ⊂ F′ ∈ F, então F ∈ F e analogamente para G; enquanto que se H ⊂ H′ e H ∈ H, então H′ ∈ H e analogamente para I. Prove que

|F ∩ G| ≥ 2^{−n}|F||G|,  (39)
|H ∩ I| ≥ 2^{−n}|H||I|,  (40)

e

|F ∩ H| ≤ 2^{−n}|F||H|.  (41)

[Sugestão. É suficiente provar, por exemplo, (41). Para tanto, fixe um x ∈ X e considere os membros de F e H que contêm x e os membros de F e H que não contêm x separadamente, e use indução em n = |X|.]

36. [Janson, Łuczak, e Ruciński] Sejam S ⊂ P([n]) = 2^{[n]},

X_{S} = [S ⊂ Γ_{p_{1},...,p_{n}}],

e X = ∑_{S∈S} X_{S}, como em sala. Seja ainda Δ = ∑_{A,B} 𝔼(X_{A}X_{B}), onde a soma é sobre os pares ordenados (A, B) ∈ S × S com A ≠ B e A ∩ B ≠ ∅.

(i) Ponha Ψ(s) = 𝔼(e^{−sX}), para todo s ≥ 0. Prove que

log ℙ(X = 0) = ∫_{0}^{∞}(log Ψ(s))′ ds.  (42)

(ii) Seja Y_{A} = ∑_{B} X_{B}, onde a soma é sobre todos os B ∈ S com A ∩ B ≠ ∅. Prove que

∫_{0}^{∞} 𝔼(e^{−sY_{A}} | X_{A} = 1) ds = 𝔼(1/Y_{A} | X_{A} = 1).  (43)

(iii) Seja Y′_{A} = Y_{A} − X_{A}. Use que 1/(1 + y′) ≥ 1 − y′/2 para y′ ≥ 1 para deduzir que

∑_{A∈S} ℙ(X_{A} = 1) 𝔼(1/Y_{A} | X_{A} = 1) ≥ μ − Δ,  (44)

onde μ = 𝔼(X). (iv) Finalmente, lembre que provamos que

−(log Ψ(s))′ ≥ ∑_{A∈S} ℙ(X_{A} = 1) 𝔼(e^{−sY_{A}} | X_{A} = 1).  (45)

Deduza de (42)–(45) que

ℙ(X = 0) ≤ e^{−μ+Δ}.  (46)

{Data de entrega: 21/11/2002}

37. Vimos dois teoremas de Roth. A grosso modo, estes resultados podem ser enunciados da seguinte forma: (i) Para qualquer A ⊂ [N], existe uma progressão aritmética P ⊂ [N] para o qual a discrepância

||A ∩ P | − η|P ||,

onde η = |A|/N, é ‘grande’. (ii) Para qualquer conjunto A ⊂ [N] com |A|/N ≥ η, onde η > 0 é uma constante positiva, se N ≥ N_{0}(η), então A contém uma progressão aritmética com três elementos. Escreva a prova destes dois resultados em um único texto, de forma organizada, destacando os princípios comuns e as tecnicalidades específicas de cada uma das demonstrações. {Data de entrega: 10/12/2002}