Pagina 1 di 1

Coprire con catene

Inviato: ven mag 04, 2012 5: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).