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

1. [Desafio] Decida se P = NP. {Data de entrega: até o final do semestre}

2. [Desafio] Sejam G_{1}, …, G_{M} grafos distintos sobre [n] = {1, …, n}. Suponha que a interseção G_{i} ∩ G_{j} contém um triângulo para todo i e j.

(i) Exiba uma tal coleção de grafos com M = 2^{\binom{n}{2}−3}. (ii) Dê uma cota superior para M.

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

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

Date: Versão de 19 de novembro de 2008.

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

5. Para inteiros t ≤ n, ponha

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

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

para provar que

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

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: 5/11/2008}

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

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

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

{Data de entrega: 5/11/2008}

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

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

onde lim_{r→∞} ε(r) = 0. {Data de entrega: 17/11/2008} 8. Seja H = H^{n} um grafo r-partido de ordem n. Prove que H tem no

máximo

\binom{n}{2} − ∑_{0≤i<r} \binom{⌊(n + i)/r⌋}{2}  (11)

arestas. Mostre que, a menos de isomorfismo, existe um único tal H com o número de arestas dado por (11) (tais grafos são às vezes chamados de grafos de Turán e são denotados por T_{r}(n)).

9. Deduza o Teorema de Turán do Teorema de Erdős: o número máximo de arestas em um grafo G de ordem n que não contém K^{r+1} como subgrafo é dado por (11). Ademais, se um tal grafo G tem o número de arestas dado em (11), então G é isomorfo a T_{r}(n) (veja o Exercício 8). {Data de entrega: 17/11/2008}

10. Considere o plano projetivo PG(2, q). Seja G o grafo cujos vértices são os pontos de PG(2, q), e o vértice (x, y, z) é adjacente (x′, y′, z′) se e só se xx′ + yy′ + zz′ = 0. Use G para mostrar que

lim_{n→∞} ex(n, C^{4})n^{−3/2} = 1/2.  (12)

{Data de entrega: 8/12/2008}