Pagina 1 di 1

Coprire con catene

Inviato: ven mag 04, 2012 6:18 pm
da Tino
Ciao!

Qual è il numero minimo di catene che occorre per coprire $P(\{1,\dots,n\})$?

Mi spiego meglio.

Fissiamo un intero $n \geq 1$ e definiamo $I_n := \{1,\dots,n\}$. Chiamiamo $P(I_n)$ l'insieme delle parti di $I_n$, cioè l'insieme dei sottoinsiemi di $I_n$, e lo pensiamo ordinato tramite la relazione di inclusione.

Una "catena" di $P(I_n)$ è un sottoinsieme totalmente ordinato di $P(I_n)$. In altre parole $C \subseteq P(I_n)$ si dice catena se per ogni $a,b \in C$ si ha $a \subseteq b$ oppure $b \subseteq a$. Un esempio di catena è questo: $\{\emptyset,\{1\},\{1,2\},\dots,\{1,\dots,n\}\}$.

Qual è il numero minimo di catene necessario a coprire tutto $P(I_n)$?

In altre parole: un insieme $\{C_1,\dots,C_m\}$ di catene di $P(I_n)$ si dice ricoprimento di $P(I_n)$ se vale $C_1 \cup \dots \cup C_m = P(I_n)$. Un ricoprimento si dice minimale se ha cardinalità minima. Qual è il valore di questa cardinalità minima?

Se n'è parlato qui (dove potete constatare i progressi fatti), e volevo sapere cosa ne pensate voi. Lì si parla di partizione tramite catene, ma il concetto è lo stesso: un ricoprimento tramite catene induce una partizione (basta togliere la roba in più: infatti un sottoinsieme di una catena è ancora una catena).