COMBINATORIA

Claudia Malvenuto – Daniele A. Gewurz Scheda di esercizi n. 9

1. Data una qualsiasi famiglia F di sottoinsiemi di [n], è possibile trovare una sottofamiglia di F che sia di Sperner?

2. Dato un grafo G, sia F(G) la famiglia delle clique massimali di G. Provare che F(G) ha la proprietà di Sperner.

È vero che per ogni famiglia di Sperner F esiste un grafo G tale che F = F(G), ovvero che F sia composta dalle clique massimali di G?

3. Individuare le catene massimali e le anticatene massimali dell’insieme parzialmente ordinato descritto dal seguente diagramma di Hasse.

A  B C  D E  F G  H

4. Dare un esempio di famiglia di sottoinsiemi di [n] che, pur verificando la disuguaglianza LYM, non sia un’anticatena (cioè non sia di Sperner).

5. Una famiglia F di sottoinsiemi di [n] si dice intersecante se {A, B} ∈ \binom{F}{2} ⇒ A ∩ B ≠ ∅.

Dimostrare che per ogni famiglia intersecante F di sottoinsiemi di [n] si ha |F| ≤ 2^{n−1}. Esistono famiglie intersecanti di cardinalità massima? È possibile darne una descrizione esaustiva?

6. Si consideri la famiglia R di sottoinsiemi di [7]:

R = {{1, 2, 3}, {1, 4, 5}, {1, 6, 7}, {2, 4, 6}, {2, 5, 7}, {3, 4, 7}, {3, 5, 6}}.

Sia F = {A ⊆ [7] : A ⊇ R per qualche R ∈ R}. Dimostrare che:

(a) R è una famiglia intersecante (nota come piano di Fano);

(b) F è una famiglia intersecante;

(c) |F| = 2^{6} (cioè di cardinalità massima).

7. Dimostrare che nel grafo G, in cui V (G) = 2^{[n]} e in cui {A, B} ∈ E(G) se e solo se A ⊆ B oppure B ⊆ A, si ha χ(G) = ω(G).