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).
Coprire con catene
Moderatori: Gianfranco, Bruno
Questo forum è una sezione del PORTALE DI BASE CINQUE
Coprire con catene
"Oh! But I have been blind- blind. Complex, I have said?
Complicated? Mais non. Of a simplicity extreme - extreme.
And miserable one that I am, I saw nothing - nothing."
(Peril At End House)
Complicated? Mais non. Of a simplicity extreme - extreme.
And miserable one that I am, I saw nothing - nothing."
(Peril At End House)