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

1. 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. [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} + …]

2. 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} .  (1)

(ii)

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

(iii) Para todo b > 0,

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

[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}.]

(iv) Prove a seguinte versão mais forte de (iii):

∑_{0≤j≤b} \binom{a}{j} ≤ (\frac{ea}{b})^{b} .  (4)

{Data de entrega: 28/8/2007} 3. (^{+}) [Kleitman] Seja B um espaço normado. (Se você não está famili-

Date: Versão de 14 de dezembro de 2007.

arizado com espaços normados, suponha que B é o ℝ^{d} para algum d.) Sejam x_{1}, …, x_{n} ∈ B. Considere as 2^{n} somas da forma

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

onde i_{1} < ⋯ < i_{k} e k ≥ 0. Dizemos que um conjunto S dessas somas é pequeno se quaisquer dois membros de S distam < 1.

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).

4. Sejam x_{1}, …, x_{n} ∈ ℝ^{d} e Δ ≥ 0. Considere as 2^{n} somas da forma

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

onde i_{1} < ⋯ < i_{k} e k ≥ 0. Dizemos que um conjunto S dessas somas é Δ-pequeno se quaisquer dois membros de S distam ≤ Δ.

Seja

m_{d}(n, Δ) = 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). Prove que existe uma constante c_{d} que depende apenas de d para o qual vale

m_{d}(n, Δ) ≤ c_{d}(⌊Δ⌋ + 1)\binom{n}{⌊n/2⌋}.  (5)

{Data de entrega: 28/8/2007}

5. Para inteiros t ≤ n, ponha

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

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}  (7)

para provar que

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

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: 30/8/2007}

6. [Caso de igualdade no Erdős–Ko–Rado] Sejam n e k inteiros positivos, com n > 2k. Seja F ⊂ \binom{[n]}{k} um sistema k-uniforme intersectante com

|F| = \binom{n − 1}{k − 1}.  (9)

Prove que existe x ∈ [n] para o qual temos

F = {F ⊂ [n]: |F | = k and x ∈ F }.  (10)

{Data de entrega: 30/8/2007}

7. [Erdős–Szekeres]

(i) Prove que, para todo n ≥ 1, existe N = N(n) tal que toda seqüência a_{0}, …, a_{N} de números contém uma subseqüência monótona com n + 1 elementos, isto é, uma subseqüência nãocrescente ou uma subseqüência não-decrescente com n+1 elementos. Mais formalmente, prove que existem 0 ≤ i_{0} < ⋯ < i_{n} ≤ N com a_{i_{0}} ≤ ⋯ ≤ a_{i_{n}} ou com a_{i_{0}} > ⋯ > a_{i_{n}}.

(ii) Prove que podemos tomar N(n) = n^{2} em (i) acima. {Data de entrega: 11/9/2007}

8. Para naturais n, a, e b, seja

f(n, a, b) = max |F|,  (11)

onde o máximo é tomado sobre todos os sistemas de conjuntos F ⊂ 2^{[n]} satisfazendo

|F | ≡ a (mod 2)  para todo F ∈ F  (12)

e

|F ∩ F′| ≡ b (mod 2) para todo F, F′ ∈ F com F ≠ F′. (13)

Determine ou estime f(n, a, b) para todos pares (a, b) ∈ {0, 1}×{0, 1} (os dois casos estudados em sala podem ser discutidos sucintamente). {Data de entrega: 11/9/2007}

9. Seja F ⊂ \binom{[4r]}{2r} um sistema 2-intersecting com |F| o maior possível. (i) Prove que

|F| = (\frac{1}{2} − ε(r)) \binom{4r}{2r},  (14)

onde lim_{r→∞} ε(r) = 0. (ii) [Desafio] Tente provar (14) para ε(r) ‘grande’. Você consegue

provar (14) para algum ε(r) tal que ε(r)\binom{4r}{2r} → ∞? {Data de entrega: 11/9/2007}

10. Seja V o espaço dos vetores (a_{1}, …, a_{n})^{T}, onde os a_{i} pertencem a um corpo F. Para a = (a_{1}, …, a_{n})^{T} e b = (b_{1}, …, b_{n})^{T}, defina o produto interno entre a e b como a^{T} b = a_{1}b_{1} +⋯+a_{n}b_{n}. Além disso, seja M um subespaço de V e A uma transformação linear de V em V. Decida se as seguintes afirmações são verdadeiras:

(a) Se A é não-singular, então A^{T} também é não-singular.

(b) Se A é não-singular, então A^{T} A é não-singular.

(c) A e A^{T} A têm o mesmo núcleo (kernel).

(d) M ∩ M^{⊥} = {0}, onde M^{⊥} é o subespaço ortogonal a M, isto é, M^{⊥} = {a: a^{T} b = 0 para todo b ∈ M}.

(e) O subespaço gerado por M ∪ M^{⊥} é igual a V.

(f) dim(M) + dim(M^{⊥}) = n.

(g) (M^{⊥})^{⊥} = M. {Data de entrega: 14/9/2007}

11. (a) Seja V um espaço n-dimensional sobre GF(2) = ℤ_{2}, e M um subespaço de V. Mostre que (1, …, 1)^{T} ∈ ⟨M ∪ M^{⊥}⟩, onde ⟨X⟩ indica o espaço gerado por X.

(b) Seja A uma matriz simétrica onde todas as entradas assumem valores em {0, 1}. Prove que a diagonal de A, considerada como um vetor linha, pertence ao espaço gerado pelas linhas de A sobre GF(2).

{Data de entrega: 18/9/2007}

12. Seja G um grafo.

(a) V (G) pode ser particionado em dois conjuntos V_{1} e V_{2} de modo que os subgrafos de G induzidos por esses conjuntos satisfazem que todos os vértices têm grau par (nos subgrafos induzidos).

(b) V (G) pode ser particionado em dois conjuntos V_{1} e V_{2} de modo que o subgrafo induzido por V_{1} satisfaz que todos os seus vértices têm grau par e o subgrafo induzido por V_{2} satisfaz que todos os seus vértices têm grau ímpar.

(c) Assuma que para todo vértice de um grafo há uma lâmpada e um botão. No começo todas as lâmpadas estão acesas. Apertar o botão de um vértice inverte a configuração de sua lâmpada e das lâmpadas dos seus vizinhos (as que estavam apagadas se acendem e as que estava acesas se apagam). Mostre que é possível apertar os botões de forma que todas as lâmpadas ficarão apagadas.

{Data de entrega: 18/9/2007}

13. Consideramos aqui o número cromático χ(ℝ^{n}) do ℝ^{n}, o menor número de cores com que podemos colorir os pontos de ℝ^{n} evitando dois pontos à distância 1 da mesma cor.

(i) Desenhe/descreva um grafo que prova que χ(ℝ^{2}) ≥ 4. Justifique sua resposta sucintamente.

(ii) Descreva um grafo que prova que χ(ℝ^{n}) ≥ 1.2^{n} para todo n com n ≥ n_{0} para algum n_{0}. Justifique sua resposta sucintamente. [Observação. Uma versão simplificada desse item é o Ex. 16. Se você preferir, você pode entregar Ex. 16 no lugar desse item.]

{Data de entrega: 25/9/2007}

14. (i) Seja G um grafo com conjunto de vértices V (G) = ℕ^{∗} = {1, 2, … } e com χ(G) = q < ∞. Prove que existe um subgrafo G′ de G com um número finito de vértices e χ(G′) = q. Isto é, se todos os subgrafos finitos de um grafo infinito G são (q − 1)-coloríveis, então G é (q − 1)-colorível. [Sugestão. Seja G_{i} o subgrafo de G induzido por [i] (i ≥ 1). Suponha que χ(G_{i}) < q para todo i. Fixe uma (q − 1)-coloração própria de G_{i} para todo i. Para infinitos i (digamos, i_{1} < i_{2} < …), o vértice 1 de G recebe uma mesma cor nas (q − 1)-colorações dos G_{i_{1}}, G_{i_{2}}, …, digamos c_{1}. Pinte o vértice 1 de G da cor c_{1}. Passamos a considerar os grafos G_{i_{1}}, G_{i_{2}}, … no resto da prova. Ponha G_{1}^{(1)} = G_{i_{1}}, G_{2}^{(1)} = G_{i_{2}}, etc. Para infinitos i (digamos, i_{1}^{(1)} < i_{2}^{(1)} < …), o vértice 2 de G recebe uma mesma cor nas (q − 1)-colorações dos G_{i_{1}}^{(1)}, G_{i_{2}}^{(1)}, …, digamos c_{2}. Pinte o vértice 2 de G da cor c_{2}. Basta agora completar esta prova.] {Data de entrega: 25/9/2007}

(ii) [Para meditar] Considere agora o caso em que G acima tem conjunto de vértices ℝ (e não mais ℕ^{∗}). Como seria o resultado análogo? Como seria a prova?

15. Para x ∈ ℝ, seja π(x) o número de números primos p ≤ x. O teorema dos números primos nos diz que

π(x) = (1 + o(1))\frac{x}{log x},  (15)

onde o(1) → 0 conforme x → ∞. Seja p_{k} o k-ésimo primo (assim, p_{1} = 2, p_{2} = 3, e p_{10} = 29).

(i) Prove que p_{k}/p_{k−1} = 1 + o(1) conforme k → ∞. (ii) Prove que p_{k} = (1 + o(1))k log k conforme k → ∞. {Data de entrega: 27/9/2007}

16. Seja c(n) = χ(ℝ^{n}) o número cromático do ℝ^{n}.

(i) Seja p um primo. Prove que

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

(ii) 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}.

(iii) Use a fórmula de Stirling (7) 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.

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

suficientemente grande. {Data de entrega: 27/9/2007} [Observação. Esta é uma versão levemente simplificada do Ex. 13(ii). Você pode entregar esse exercício em vez de entregar o Ex. 13(ii)]

17. O Exercício 16 mostra que c(4p − 1) ≥ (1.139)^{4p−1} para todo primo p suficientemente grande. Use o resultado do Ex. 15 para deduzir que c(n) ≥ (1.13)^{n} para todo n suficientemente grande. {Data de entrega: 27/9/2007}

18. (i) 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.]

(ii) Use o conjunto X de (i) para construir um conjunto Y ⊂ ℝ^{d} que desprova a conjectura de Borsuk (em dimensão suficientemente alta), 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.]

(iii) Seja f(d) o menor k tal que todo S ⊂ ℝ^{d} admite uma particão de Borsuk em k partes, isto é, uma partição em k partes de diâmetro menor que diam(S). Use (ii) para provar uma cota inferior exponencial para f(d) para todo d suficientemente grande.

{Data de entrega: 2/10/2007}

19. (i) 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).]

(ii) Deduza do Ex. 14(ii) que B(d, ε) (com d e ε apropriados) contém

subgrafos finitos G com χ(G) ≥ k e og(G) ≥ 2ℓ + 1. {Data de entrega: 2/10/2007}

20. (Continuação do Ex. 19) 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). {Data de entrega: 2/10/2007}

(ii) Mostre que se G tem a propriedade P (1/2), então χ(G) ≤ 2.

{Data de entrega: 2/10/2007} (iii) [Para meditar] 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 é (basicamente) um tal grafo. Use Ex. 19(ii).]

{Data de entrega: 2/10/2007}

21. Fixe um corpo F e um conjunto U de polinômios com coeficientes em F nas indeterminadas X = (X_{1}, …, X_{n}): U ⊂ F [X]. Para A ⊂ U, pomos V (A) = {x ∈ F^{n}: a(x) = 0 para todo a ∈ A}. Claramente, V (A) = ⋂_{a∈A} V (a), onde escrevemos V (a) para V ({a}). Dado X ⊂ F^{n}, seja I(X) = {a ∈ U: a(x) = 0 para todo x ∈ X}. Prove que o par (V, I) constitui uma conexão de Galois entre as partes de U e as partes de F^{n}, isto é, prove as seguintes afirmações:

(i) Tanto V quanto I invertem a ordem: para todo A ⊂ B, temos V (A) ⊃ V (B) e analogamente para I.

(ii) Para todo A ⊂ U temos I(V (A)) ⊃ A e para todo X ⊂ F^{n}

temos V (I(X)) ⊃ X. Deduza de (i) e (ii) que vale o seguinte. (iii) Sejam im V = {V (A): A ⊂ U} e im I = {I(X): X ⊂ F^{n}}. Prove

que V é uma bijeção de im I em im V. Qual é a inversa de V : im I → im V? {Data de entrega: 16/10/2007}

22. (Continuação do Ex. 21) Dizemos que b ∈ U depende de A se V (b) ⊃ V (A). O fecho de A em U é Ā = {b ∈ U: b depende de A}. Um conjunto A é fechado em U se Ā = A. Prove as seguintes asserções:

(i) A operação A ↦ Ā é uma operação de fecho, isto é, (a) A ⊂ Ā para todo A, (b) para quaisquer A e B com A ⊂ B, temos Ā ⊂ B̄, e (c) ¯ Ā = Ā.

(ii) Seja (A_{λ})_{λ∈Λ} uma família de fechados em U. Então ⋂_{λ∈Λ} A_{λ} é

um fechado. Identifique os fechados de U em termos das aplicações V e I (veja Ex. 21). {Data de entrega: 16/10/2007}

23. Considere os padrões de zeros δ(f(x)) ∈ {0, ∗}^{m} (x ∈ F^{n}) de uma seqüência de polinômios f = (f_{1}, …, f_{m}) sobre um corpo F nas indeterminadas X = (X_{1}, …, X_{n}). Seja Z_{F} (f) o conjunto de tais padrões e Z_{F} (f) = |Z_{F} (f)|.

(i) Seja U = {f_{1}, …, f_{m}}. Exiba uma injeção de Z_{F} (f) nos fechados de U.

(ii) Dizemos que A gera um fechado B de U se Ā = B. Suponha agora que os f_{i} em U são todos lineares, isto é, são da forma f_{i}(X) = ⟨a_{i}, X⟩ + b_{i} = a_{i1}X_{1} + ⋯ + a_{in}X_{n} + b_{i}. Prove que todo fechado B ⊂ U com B ≠ U admite um conjunto gerador A com |A| ≤ n.

(iii) Conclua que, no caso em que os f_{i} são lineares, temos

Z_{F} (f) ≤ 1 + ∑_{j=0}^{n} \binom{m}{j}.  (17)

(iv) Altere levemente o argumento acima para provar que (17) pode ser melhorado para

Z_{F} (f) ≤ ∑_{j=0}^{n} \binom{m}{j}.  (18)

{Data de entrega: 16/10/2007}

24. Prove que a vasta maioria das funções booleanas de n variáveis exige circuitos booleanos com Ω(2^{n}/n) portas para sua representação (isto é, existe c > 0 tal que, para n ≥ n_{0}, o número necessário de portas é maior que c2^{n}/n). {Data de entrega: 23/10/2007}

25. Seja M(x_{1}, …, x_{n}) a função booleana ‘da maioria’, dada por

M(x_{1}, …, x_{n}) = \begin{cases}0 & se ∑_{1≤i≤n} x_{i} < n/2 \\ 1 & se ∑_{1≤i≤n} x_{i} ≥ n/2. \end{cases}  (19)

(i) Prove que existe um circuito com O(n^{2}) portas que calcula M. {Data de entrega: 23/10/2007}

(ii) Prove que existe um circuito com O(n log n) portas que cal-

cula M. {Data de entrega: 23/10/2007} (ii) [Desafio] Prove que existe um circuito com O(n) portas que cal-

cula M.

26. Neste problema, o termo Δ-sistema significa um Δ-sistema com 3 membros (isto é, um girassol com três pétalas). Seja φ(n) o menor inteiro tal que toda família F de n-conjuntos (conjuntos com n elementos) com |F| > φ(n) contém um Δ-sistema. Ademais, seja γ(n) o menor inteiro tal que toda família intersectante de n-conjuntos com |F| > γ(n) contém um Δ-sistema.

(i) Prove que

φ(n) ≤ nφ(n − 1) + γ(n)  (20)

para todo n > 1. (ii) Seja E um sistema intersectante de n-conjuntos com γ = γ(n)

membros que não contém um Δ-sistema. Seja

t = Ave{|E ∩ E′|: E, E′ ∈ E, E ≠ E′}

= \binom{γ}{2}^{−1} ∑\{|E ∩ E′|: E, E′ ∈ E, E ≠ E′\} (21)

a média das cardinalidades das interseções de pares de membros distintos de E. Prove que

γ ≤ \frac{n}{t}φ(n − 1).  (22)

[Sugestão. Prove por um argumento de média que existe E_{0} ∈ E para o qual Ave_{E≠E_{0}} |E_{0} ∩ E| ≥ t. Também por um argumento de média, prove que existe x ∈ E_{0} tal que deg(x) ≥ tγ/n.]

(iii) Prove que

γ(n) ≤ tφ(n − 1) + (n − 1)^{2}φ(n − 2).  (23)

[Sugestão. Seja E como em (ii) acima. Mostre por um argumento de média que existem E_{1} e E_{2} ∈ E tais que |E_{1} ∩ E_{2}| ≤ t. Considere os F em E \{E_{1}, E_{2}}. Para limitar o número de F que são disjuntos de I = E_{1} ∩ E_{2}, observe que F ∩ (E_{i} \ I) ≠ ∅.]

(iv) Deduza que, para uma certa constante C, temos

φ(n) ≤ Cn! (\frac{5}{3})^{n} .  (24)

[Observação. Refinando este argumento, podemos provar que para todo ε > 0, existe C para o qual temos φ(n) ≤ Cn!(1 + ε)^{n}, isto é, φ(n) ≤ n!(1 + o(1))^{n}.]

{Data de entrega: 1/11/2007}

27. 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: 4/12/2007}

28. Suponha que

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

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}. [Inicialmente, reescreva (*) de forma mais explícita.]

(iii) O que você consegue dizer sobre o caso em que f = f(n) → f_{0} para alguma contante f_{0}? [Aqui você pode apenas conjecturar o resultado; não é necessário provar sua conjectura.]

{Data de entrega: 4/12/2007}

29. Prove que p_{0} = p_{0}(n) = n^{−2/3} é a função limiar para a existência de K^{4} em G(n, p). {Data de entrega: 4/12/2007}

30. Desenvolva um PTAS para o MaxCut restrito a grafos densos (isto é, suponha que temos uma constante c > 0 fixa e restringimos as entradas de MaxCut a grafos G = G^{n} com ≥ cn^{2} arestas). {Data de entrega: 4/12/2007}

31. [Desafio] Para cada n ≥ 1, defina o grafo G_{n} com conjunto de vértices V_{n} = P([n]) = 2^{[n]} e com conjunto de arestas E_{n} dado por {x, y} ∈ E_{n} se e só se |x ∩ y| é ímpar. Mostre que, para todo S ⊂ V_{n}, temos

|E(G[S])| = \frac{1}{2}\binom{|S|}{2} + o(N^{2}),  (26)

onde N = 2^{n} = |V_{n}|.

32. Prove que, para todo ε > 0, existe ℓ(ε) para o qual vale a seguinte afirmação. Suponha que G = G^{n} seja tal que χ(G − F) ≥ 3 para todo F ⊂ E(G) com |F | ≤ ε\binom{n}{2}. Então G contém um circuito ímpar de comprimento ≤ ℓ(ε). {Data de entrega: 4/12/2007}