PROVA DE MATEMÁTICA DISCRETA 2O. SEMESTRE DE 2002

Instruções. Esta prova é individual, mas naturalmente você pode consultar suas anotações, livros, etc. Entregue suas soluções até as 12:00 do dia 16/12/2002, na secretaria do MAC. Faça quantas questões quanto você conseguir; minha expectativa é que você consiga basicamente fazer todas as 6 questões. Após a entrega, farei uma pequena entrevista com cada aluno que fizer a prova.

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

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

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

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

e

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

Determine ou estime f(n, a, b) para todos pares (a, b) ∈ {0, 1}×{0, 1}.

2. Para todo natural n > 1, seja

Ω(n) = ∑_{i} e_{i},  (4)

onde n = p_{1}^{e_{1}} … p_{k}^{e_{k}} é a fatoração de n em primos distintos. Isto é, Ω(n) é o número de primos que dividem n, contados com multiplicidade. Prove que

Ω(n) = (1 + o(1)) log log N  (5)

para quase todo n escolhido uniformemente ao acaso em [N].

3. Sejam dados um natural n e um real ε > 0. Seja

g_{ε}(n) = sup |S|,  (6)

onde o supremo é tomado sobre todos os S ⊂ ℝ^{n} tais que para todo x ∈ S, temos ∥x∥ = 1, e para todo x e y ∈ S com x ≠ y temos |⟨x, y⟩| ≤ ε.

(i) Prove que g_{ε}(n) < ∞ para todo n ≥ 1 e ε < 1. (ii) Mais ainda, prove que lim sup_{n→∞} g_{ε}(n)^{1/n} < ∞ se ε < 1.

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

(iii) Prove que para qualquer ε > 0 existem n_{0} e δ > 0 tais que

g_{ε}(n) ≥ (1 + δ)^{n}  (7)

para todo n ≥ n_{0}.

4. Prove que quase todo grafo G^{n} é conexo.

5. Dizemos que um grafo é k-universal se ele contém todos os grafos com k vértices como subgrafos induzidos. Ademais, dizemos que um grafo G satisfaz a propriedade P (a, b) se, para toda a-upla x_{1}, …, x_{a} ∈ V (G) e toda b-upla y_{1}, …, y_{b} ∈ V (G) de vértices distintos de G, existe um vértice z em G, diferente de todos os x_{i} e y_{j}, tal que z é adjacente a todos os x_{i} (1 ≤ i ≤ a) e não é adjacente a nenhum y_{j} (1 ≤ j ≤ b).

(i) Prove que se G satisfaz P (k − 1, k − 1), então G é k-universal. (ii) Prove que quase todo grafo G^{n} é k-universal para todo k fixo.

6. 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 ||,

é ‘grande’, onde η = |A|/N. (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.