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

Instruções. Esta prova é individual, mas naturalmente você pode consultar suas anotações, livros, etc. Entregue suas soluções até as 14:00 do dia 12/12/2003, na secretaria do MAC.

1. Para inteiros t ≤ n, ponha

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

onde o máximo é tomado sobre todos os F ⊂ P([n]) = 2^{[n]} que são tintersectantes, isto é, para todo F e F′ ∈ F, temos |F ∩F′| ≥ t. (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}  (2)

para provar que

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

para todo k ∈ ℤ fixo. Deduza que

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

e use esse fato.]

2. [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|,  (4)
|H ∩ I| ≥ 2^{−n}|H||I|,  (5)

e

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

Date: Versão de 3 de março de 2004.

[Sugestão. É suficiente provar, por exemplo, (6). 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|.]

3. Use o Lema de Kleitman, dado na Questão 2, para provar os resultados abaixo.

(i) Seja F ⊂ D ⊂ P([n]). Mostre que se F é intersectante e D é fechado por se tomar subconjuntos, então |F| ≤ (1/2)|D|.

(ii) Seja F ⊂ P([n]) tal que, para todo F e F′ ∈ F, temos F ∩F′ ≠ ∅ e F ∪ F′ ≠ [n]. Prove que |F| ≤ 2^{n−2}. Mostre um exemplo em que ocorre a igualdade.

(iii) Sejam F_{1}, …, F_{k} ⊂ P([n]) famílias intersectantes. Prove que

|F_{1} ∪ ⋯ ∪ F_{k}| ≤ 2^{n} − 2^{n−k}.  (7)

Para todo n e k com 1 ≤ k ≤ n, exiba F_{1}, …, F_{k} ⊂ P([n]) para os quais vale a igualdade em (7).

4. Prove que os subconjuntos infinitos de ℕ podem ser coloridos de vermelho e azul de forma que nenhum subconjunto infinito S de ℕ tem todos os seus subconjuntos infinitos da mesma cor. [Sugestão. Ponha A ∼ B se a diferença simétrica A △ B é finita; pinte os conjuntos de forma que, se A = B \ {b}, então A e B têm cores distintas.]

5. Seja A = {A_{λ}: λ ∈ Λ} uma família de subconjuntos de um conjunto finito V. Considere os subconjuntos Λ′ ⊂ Λ tais que o sistema de conjuntos A_{λ} (λ ∈ Λ′) admite uma transversal (isto é, um sistema de representantes distintos: uma coleção de elementos dois a dois distintos a_{λ} ∈ A_{λ} (λ ∈ Λ′). Mostre que quaisquer dois tais conjuntos Λ′ ⊂ Λ têm a mesma cardinalidade. Defina um matróide sobre Λ a partir desta observação.

6. [Edmonds] Sejam M = M(S) e N = N(S) dois matróides sobre S. Prove que

max{|I|: I ∈ I(M) ∩ I(N)}
= min{r_{M}(A) + r_{N}(S \ A): A ⊂ S}. (8)

[Sugestão. Considere o matróide M ∨ N^{∗}, onde N^{∗} é o dual de N.]

7. Seja G um grafo conexo, e suponha que as arestas de G estão coloridas de forma arbitrária. Prove que G contém uma árvore geradora com todas as suas arestas de cores distintas se e só se, para todo subgrafo H de G, o número de cores que ocorrem em E(G) \ E(H) é pelo menos c(H) − 1, onde c(H) é o número de componentes conexas em H. [Sugestão. Lembre-se do matróide uniforme U_{n,m}. Para cada cor, considere os conjuntos de arestas daquela cor e m = 1 (isto dá um matróide para cada cor). Aplique o teorema de Edmonds dado na Questão 6. Alternativamente, dê uma prova elementar.]