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

[Os exercícios desta lista são reciclados de edições anteriores desta e disciplinas semelhantes. Alguns exercícios estão em sua versão original, em inglês. (Melhor assim do que demorar mais ainda para eu disponibilizá-los).]

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)

Date: Versão de 10 de outubro de 2003.

3. Considere a identidade

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

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

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

pois

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

onde ∑_{k}^{∗} indica soma sobre todos os k satisfazendo (6) 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 (5) está ‘exponencialmente concentrada’ nos termos com k satisfazendo

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

pois

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

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

(i) Prove que a condição de que ω → ∞ é necessária para que (7) valha. Para tanto, use a fórmula de Stirling (14). De fato, use (14) 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},  (10)

onde d = d(c) > 0 é uma constante que depende apenas de c. (ii) Seja 0 < α < 1 um real fixo. Ponha

H(α) = α log_{2} \frac{1}{α} + (1 − α) log_{2} \frac{1}{1 − α}.  (11)

Prove que

\binom{n}{⌊αn⌋} = 2^{(H(α)+o(1))n},  (12)

onde o(1) → 0 conforme n → ∞. [Sugestão. Stirling!] (iii) Prove (7). (iv) Prove (9). [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 (iii), aplique a desigualdade de Chebyshev (consulte suas notas de probabilidade!). Para (iv), use (ii).] 4. Para inteiros t ≤ n, ponha

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

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

para provar que

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

para todo k ∈ ℤ fixo. Deduza que

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

e use esse fato.]

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

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

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

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

e

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

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

6. [Equality case in Erdős–Ko–Rado] Let positive integers n and k be given, with n > 2k. Suppose F ⊂ \binom{[n]}{k} is an intersecting k-uniform hypergraph with

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

Prove that there is x ∈ [n] for which we have

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

7. Let F ⊂ \binom{[4r]}{2r} be a 2-intersecting family with |F| as large as possible. Prove that

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

where lim_{r→∞} ε(r) = 0.

[Extra credit] Try to prove (21) for a ‘large’ ε(r). Can you prove it for some ε(r) such that ε(r)\binom{4r}{2r} → ∞?

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

e

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

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

9. Suppose F ⊂ D ⊂ P([n]). Show that if F is intersecting and D is a down-set, then |F| ≤ (1/2)|D|.

10. [Kleitman] Let F_{1}, …, F_{k} ⊂ P([n]) be intersecting families. Show

that

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

For each n and k with 1 ≤ k ≤ n, exhibit F_{1}, …, F_{k} ⊂ P([n]) for which equality holds in (25).

11. [Kleitman] Let F ⊂ P([n]) be such that, for all F, F′ ∈ F, we have F ∩ F′ ≠ ∅ and F ∪ F′ ≠ [n]. Prove that |F| ≤ 2^{n−2}.

12. Fix an integer k ≥ 2 and let ε > 0 be a real number. Show that if n ≥ n_{0}(k, ε), then there is a system B ⊂ \binom{[n]}{k} with

|B| ≤ (1 + ε)\binom{n}{k − 1}\binom{k}{k − 1}^{−1}  (26)

covering all (k−1)-element subsets of n, that is, such that for any C ∈ \binom{[n]}{k−1}, there is some B ∈ B such that C ⊂ B. [Sugestão. Consider k-tuples x_{1}, …, x_{k} with ∑_{i} x_{i} ≡ 0 (mod n).]

13. Let integers 2 ≤ ℓ ≤ k ≤ n be fixed. Let C ⊂ \binom{[n]}{ℓ} be a system hitting all k-element subsets of [n], that is, such that for any B ∈ \binom{[n]}{k}, there is C ∈ C with C ⊂ B.

(i) Show that

|C| ≥ \binom{n}{ℓ}\binom{k}{ℓ}^{−1}.  (27)

(ii) Suppose now that ℓ = 2. How sharp do you think the lower bound in (27) is? [Sugestão. This is actually a graph theory question. Check your favourite graph theory book, if you don’t see what this question is about.]

14. Let us say that a chain C = {A_{1}, …, A_{k}}, with A_{1} ⊂ ⋯ ⊂ A_{k}, of elements of P([n]) is a symmetric chain if the following conditions hold:

(a) C is saturated, that is, |A_{i}| = |A_{i−1}| + 1 for all 1 < i ≤ k.

(b) |A_{1}| + |A_{k}| = n. Prove the following assertions:

(i) P([n]) may be partitioned into symmetric chains. [Sugestão. Use induction on n. Suppose n > 0 and that the result holds for smaller values of n. Let P([n−1]) = ⋃_{λ∈Λ} C_{λ} be a decomposition of P([n − 1]) into symmetric chains. Construct two chains from each C_{λ} as follows. Suppose C_{λ} is the chain A_{1} ⊂ ⋯ ⊂ A_{k}. Then consider A_{1} ⊂ ⋯ ⊂ A_{k} ⊂ A_{k} ∪ {n} and A_{1} ∪ {n} ⊂ ⋯ ⊂ A_{k−1} ∪ {n}.]

(ii) [Sperner] The maximal number of elements in an antichain in

P([n]) is \binom{n}{⌊n/2⌋}. (iii) The chains in the decomposition of P([n]) may be required to

satisfy the following extra condition. Suppose C_{λ} is a chain A_{1} ⊂ ⋯ ⊂ A_{k} in the decomposition of P([n]). Then, for any 1 < i < k, there is B ⊂ [n] such that

A_{i−1} ⊂ B ⊂ A_{i+1}  (28)

and, furthermore, the chain of the decomposition that contains B has cardinality less than k. [Sugestão. Check the hint for (i).]

15. [Hansel] Prove that the number of antichains in P([n]) is at most

3^{\binom{n}{⌊n/2⌋}},  (29)

following the steps below or otherwise.

(i) Observe that we need to give an upper bound for the number of functions f: P([n]) → {0, 1} that are decreasing (that is, such that f^{−1}(1) is a down-set).

(ii) Consider a decomposition Π of P([n]) into symmetric chains sa-

tisfying (iii) of the previews exercise. (iii) Check how many decreasing functions f one may produce by

defining f on each chain in Π in turn, considering smaller chains first. Suppose a function f is being constructed, and consider a chain C in Π with k elements (k ≥ 2) on which f is still undefined (f is already defined on all smaller chains in Π). Argue that f can only be extended in at most 3 ways on C. [Sugestão. This is clear for k = 2. For k > 2, use property (iii) of the previous exercise.]

16. Prove that there is a colouring of the natural numbers with red and blue such that no infinite arithmetic progression is monochromatic.

17. Prove that the infinite subsets of ℕ may be coloured with red and blue in such a way that no infinite subset S ⊂ ℕ has all its infinite subsets coloured with the same colour. [Sugestão. Write A ∼ B if the symmetric difference A △ B is finite; colour the sets so that, if A = B \ {b}, then A and B have different colours.]

18. Prove that there is a colouring of the pairs (2-element subsets) of ℝ with red and blue such that no uncountable subset S ⊂ ℝ has all its pairs of the same colour.

19. (i) Suppose a family of sets F ⊂ P(ℕ) = 2^{ℕ} is such that the symmetric difference F △ F′ is finite for all distinct F, F′ ∈ F. Prove that F is countable.

(ii) A family of sets F is called quasi-disjoint if the intersection F ∩ F′ is finite for all distinct F, F′ ∈ F. Prove that there is an uncountable quasi-disjoint family of sets F ⊂ P(ℕ) = 2^{ℕ}.