Partizionare insieme mediante catene
Salve, oggi stavo riflettendo un pò sugli insiemi e mi è venuto in mente un questito a cui non ho saputo dare risposta. Magari è facile ma io sono un pò ottuso xD ... ecco la domanda:
Sia $I_n={1,2,..,n}$ l'insieme dei primi $n$ numeri naturali e sia $( P(I_n), \subset )$ l'insieme delle parti di $I_n$ ordinato mediante la relazione di inclusione. Qual'è il minimo ordine che può avere una partizione di $P(I_n)$ formata da catene (cioè da parti totalmente ordinate) ??
Esempio: l'insieme delle parti di ${1,2,3}$ è ${ \emptyset ,{1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}}$. Una sua partizione formata da catene potrebbe essere costituita dai tre insiemi:
${ \emptyset ,{1},{1,2},{1,2,3}}$
${{2},{2,3}}$
${{3},{1,3}}$
Non credo se ne possa costruire una con 2 elementi quindi la risposta è 3. Mi piacerebbe sapere qual è la risposta nel caso generale. Grazie.
Sia $I_n={1,2,..,n}$ l'insieme dei primi $n$ numeri naturali e sia $( P(I_n), \subset )$ l'insieme delle parti di $I_n$ ordinato mediante la relazione di inclusione. Qual'è il minimo ordine che può avere una partizione di $P(I_n)$ formata da catene (cioè da parti totalmente ordinate) ??
Esempio: l'insieme delle parti di ${1,2,3}$ è ${ \emptyset ,{1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}}$. Una sua partizione formata da catene potrebbe essere costituita dai tre insiemi:
${ \emptyset ,{1},{1,2},{1,2,3}}$
${{2},{2,3}}$
${{3},{1,3}}$
Non credo se ne possa costruire una con 2 elementi quindi la risposta è 3. Mi piacerebbe sapere qual è la risposta nel caso generale. Grazie.
Risposte
Per ora vedo delle stime "stupide". Detto [tex]m(n)[/tex] il numero minimo di elementi di una partizione di [tex]P(I_n)[/tex] formata da catene, si ha [tex]\binom{n}{[n/2]} \leq m(n) \leq 2 \cdot m(n-1)[/tex] (dove [tex][x][/tex] indica la parte intera del numero reale [tex]x[/tex]).
La prima disuguaglianza è ottenuta considerando i sottoinsiemi di [tex]I_n[/tex] formati da [tex]n/2[/tex] elementi. Osserva infatti che due sottoinsiemi con lo stesso numero di elementi non potranno mai stare in una stessa catena.
La seconda disuguaglianza è ottenuta per dicotomia: spezzo [tex]P(I_n)[/tex] in due parti: gli insiemi che contengono [tex]1[/tex] e quelli che non contengono [tex]1[/tex], poi applico il caso [tex]n-1[/tex].
La prima disuguaglianza è ottenuta considerando i sottoinsiemi di [tex]I_n[/tex] formati da [tex]n/2[/tex] elementi. Osserva infatti che due sottoinsiemi con lo stesso numero di elementi non potranno mai stare in una stessa catena.
La seconda disuguaglianza è ottenuta per dicotomia: spezzo [tex]P(I_n)[/tex] in due parti: gli insiemi che contengono [tex]1[/tex] e quelli che non contengono [tex]1[/tex], poi applico il caso [tex]n-1[/tex].
"Martino":
Per ora vedo delle stime "stupide"
Mica tanto "stupide".
Anzi secondo me con la prima stima $((n),([n/2]))$ ci hai preso... almeno per i primi valori di n perchè facendo un pò di conti a mano mi viene $3$ per $n=3$, $6$ per $n=4$ e $10$ per $n=5$ ...
Interessante questo calcolo.
Posso chiedere una piccola cosa: ma con "minimo ordine" si intende il numero minimo di catene possibili?
Posso chiedere una piccola cosa: ma con "minimo ordine" si intende il numero minimo di catene possibili?
Si intende il piu piccolo numero di catene disgiunte che coprono l'insieme $P(I_n)$. Tipo come ho fatto con l'esempio del primo post che con $3$ catene ho esaurito gli elementi di $P({1,2,3})$
Anche se non è una dimostrazione il computer mi conferma la stima [tex]\binom{n}{[n/2]}[/tex] per molti valori di $n$
3 per n = 3
6 per n = 4
10 per n = 5
20 per n = 6
35 per n = 7
70 per n = 8
126 per n = 9
252 per n = 10
462 per n = 11
924 per n = 12
1716 per n = 13
Caso risolto.
3 per n = 3
6 per n = 4
10 per n = 5
20 per n = 6
35 per n = 7
70 per n = 8
126 per n = 9
252 per n = 10
462 per n = 11
924 per n = 12
1716 per n = 13
Caso risolto.
"perplesso":Non sarei così d'accordo. Per dire che il caso è risolto bisognerebbe trovare una stima dall'alto buona, per dimostrare che il risultato è vero almeno asintoticamente. Ci stavo pensando giusto adesso, ma non sembra immediato.
Caso risolto.
Beh si, ho detto caso risolto nel senso che almeno fino a $n=13$ la stima è proprio esatta. Per esempio con $n=12$ si ha $924=$ [tex]\binom{12}{6}[/tex]. Quindi ho il "forte sospetto" che questa formula [tex]\binom{n}{[n/2]}[/tex] sia proprio valida per $n$ qualsiasi. Una dimostrazione chiaramente sarebbe ancora meglio rispetto all'approccio algoritmico che sto usando adesso... Se mi viene qualche idea vi aggiorno. 
Mi verrebbe da dire che in un'algebra di Boole due qualsiasi catene massimali hanno la stessa cardinalità. Credo che potrebbe essere utile per dimostrare quello che volete, ma non ho adesso il tempo di pensarci, quindi vi comunico solo l'abbozzo di idea...
@perplesso: grazie del chiarimento
Ok, l'ho dimostrato, per lo meno nel caso di tuo interesse.
Allora:
Lemma. Sia [tex]\{C_1,\ldots,C_m\}[/tex] una partizione minima di [tex]\mathcal P(I_n)[/tex] fatta di catene. Poniamo [tex]U_k = \bigcup C_k[/tex] (l'unione degli elementi di [tex]C_k[/tex]). Allora possiamo assumere che per ogni [tex]k = 1,\ldots,m[/tex], [tex]C_k[/tex] sia una catena massimale di [tex]\mathcal P(I_n) \setminus (U_1 \cup \ldots \cup U_{k-1})[/tex].
Dimostrazione. Supponiamo che [tex]C_k[/tex] non sia una catena massimale di [tex]\mathcal P(I_n) \setminus (U_1 \cup \ldots \cup U_{k-1})[/tex]; allora esiste una catena massimale [tex]C_k'[/tex] in [tex]\mathcal P(I_n) \setminus (U_1 \cup \ldots \cup U_{k-1})[/tex] tale che [tex]C_k \subset C_k'[/tex]. Questa nuova catena è ottenuta aggiungendo a [tex]C_k[/tex] elementi che si trovano in [tex]C_h[/tex] con [tex]h > k[/tex]; pertanto, togliendo questi elementi dalle rispettive catene, otteniamo una nuova partizione, e se [tex]m'[/tex] denota il nuovo numero di elementi che formano questa partizione, abbiamo [tex]m' \le m[/tex], sicché segue la tesi per minimalità di [tex]m[/tex]. []
A questo punto non dovrebbe essere difficile concludere. Di, nuovo però, non ho tempo immediato. Vi lascio a trarre le conclusioni da questo lemma.
Allora:
Lemma. Sia [tex]\{C_1,\ldots,C_m\}[/tex] una partizione minima di [tex]\mathcal P(I_n)[/tex] fatta di catene. Poniamo [tex]U_k = \bigcup C_k[/tex] (l'unione degli elementi di [tex]C_k[/tex]). Allora possiamo assumere che per ogni [tex]k = 1,\ldots,m[/tex], [tex]C_k[/tex] sia una catena massimale di [tex]\mathcal P(I_n) \setminus (U_1 \cup \ldots \cup U_{k-1})[/tex].
Dimostrazione. Supponiamo che [tex]C_k[/tex] non sia una catena massimale di [tex]\mathcal P(I_n) \setminus (U_1 \cup \ldots \cup U_{k-1})[/tex]; allora esiste una catena massimale [tex]C_k'[/tex] in [tex]\mathcal P(I_n) \setminus (U_1 \cup \ldots \cup U_{k-1})[/tex] tale che [tex]C_k \subset C_k'[/tex]. Questa nuova catena è ottenuta aggiungendo a [tex]C_k[/tex] elementi che si trovano in [tex]C_h[/tex] con [tex]h > k[/tex]; pertanto, togliendo questi elementi dalle rispettive catene, otteniamo una nuova partizione, e se [tex]m'[/tex] denota il nuovo numero di elementi che formano questa partizione, abbiamo [tex]m' \le m[/tex], sicché segue la tesi per minimalità di [tex]m[/tex]. []
A questo punto non dovrebbe essere difficile concludere. Di, nuovo però, non ho tempo immediato. Vi lascio a trarre le conclusioni da questo lemma.
Quindi, in virtù del tuo Lemma, per costruire una partizione minimale di $P(I_n)$ prendo una catena massimale di $P(I_n)$, poi costruisco una catena massimale con gli elementi rimasti e così via iterando il metodo. Allora per esaurire tutti gli elementi di $P(I_n)$ di ordine $k$ dovrò fare $((n),(k))$ iterazioni, questo implica in particolare che dopo $((n),([n/2]))$ iterazioni ho esaurito tutti gli elementi di $P(I_n)$ Vero?
Grazie maurer! Hai dato una giustificazione teorica al metodo da me bovinamente applicato!
Grazie maurer! Hai dato una giustificazione teorica al metodo da me bovinamente applicato!
Non c'è dubbio che le catene possano avere intersezione (per ottenere catene disgiunte basta togliere un po' di roba da una delle catene, dato che ogni sottoinsieme di una catena è ancora una catena).
In sostanza il problema di perplesso si può riformulare così: qual è il numero minimo di catene necessario a coprire [tex]P(I_n)[/tex]? Chiaro che esiste un ricoprimento minimale formato da catene massimali, cioè di lunghezza [tex]n[/tex].
Un modo utile per trovare stime dall'alto (sono queste che mancano!) è forse il seguente: un ordine dato agli [tex]n[/tex] numeri determina [tex]n[/tex] catene come segue: si parte da uno dei numeri e si va a destra ciclicamente. Per esempio la sequenza (ordinata!)
[tex]12345[/tex]
corrisponde (cioè, la facciamo corrispondere) alle catene
1 - 12 - 123 - 1234 - 12345
2 - 23 - 234 - 2345 - 23451
3 - 34 - 345 - 3451 - 34512
4 - 45 - 451 - 4512 - 45123
5 - 51 - 512 - 5123 - 51234
Naturalmente qui sopra ogni lista di numeri va intesa come l'insieme che li contiene, in altre parole l'ordine non conta.
Nel caso [tex]n=5[/tex] uno osserva che le sequenze 12345, 13524 determinano [tex]2 \cdot 5 = 10[/tex] catene che coprono tutto [tex]P(I_5)[/tex], e in modo "essenzialmente" disgiunto (gli unici elementi in comune sono quelli che lo devono essere: gli 1-insiemi, i 4-insiemi e il 5-insieme).
PS. Perplesso, non ho capito il tuo argomento. Come arrivi a ottenere un ricoprimento formato da [tex]\binom{n}{[n/2]}[/tex] elementi?
PPS. Maurer, sottintendi che il tuo lemma implica che il numero minimo cercato è [tex]\binom{n}{[n/2]}[/tex]? Sarà la giornata intensa, ma non vedo come.
In sostanza il problema di perplesso si può riformulare così: qual è il numero minimo di catene necessario a coprire [tex]P(I_n)[/tex]? Chiaro che esiste un ricoprimento minimale formato da catene massimali, cioè di lunghezza [tex]n[/tex].
Un modo utile per trovare stime dall'alto (sono queste che mancano!) è forse il seguente: un ordine dato agli [tex]n[/tex] numeri determina [tex]n[/tex] catene come segue: si parte da uno dei numeri e si va a destra ciclicamente. Per esempio la sequenza (ordinata!)
[tex]12345[/tex]
corrisponde (cioè, la facciamo corrispondere) alle catene
1 - 12 - 123 - 1234 - 12345
2 - 23 - 234 - 2345 - 23451
3 - 34 - 345 - 3451 - 34512
4 - 45 - 451 - 4512 - 45123
5 - 51 - 512 - 5123 - 51234
Naturalmente qui sopra ogni lista di numeri va intesa come l'insieme che li contiene, in altre parole l'ordine non conta.
Nel caso [tex]n=5[/tex] uno osserva che le sequenze 12345, 13524 determinano [tex]2 \cdot 5 = 10[/tex] catene che coprono tutto [tex]P(I_5)[/tex], e in modo "essenzialmente" disgiunto (gli unici elementi in comune sono quelli che lo devono essere: gli 1-insiemi, i 4-insiemi e il 5-insieme).
PS. Perplesso, non ho capito il tuo argomento. Come arrivi a ottenere un ricoprimento formato da [tex]\binom{n}{[n/2]}[/tex] elementi?
PPS. Maurer, sottintendi che il tuo lemma implica che il numero minimo cercato è [tex]\binom{n}{[n/2]}[/tex]? Sarà la giornata intensa, ma non vedo come.
La mia idea rozza era: si fissa una catena massimale e la si toglie. Il reticolo che rimane ha altezza [tex]n-1[/tex] ed ha precisamente [tex]n-1[/tex] elementi minimali e [tex]n-1[/tex] elementi massimali. Questo dovrebbe la possibilità di costruire [tex]n-1[/tex] catene massimali disgiunte; le tolgo tutte quante. Mi rimane un reticolo di altezza [tex]n-3[/tex] (e dovrebbe avere [tex]n-3[/tex] elementi minimali e [tex]n-3[/tex]massimali) ecc.
Immagino che si possa formulare in maniera decente questo modo di procedere. E dovrebbe realizzare il minimo teorico... Ma non ho controllato, quindi potrebbe non funzionare affatto!
Se può servire a farvi capire cosa intendo, sto visualizzando il reticolo delle parti come un rombo (che è il diagramma di Hasse associato al reticolo delle parti di un insieme finito).
Immagino che si possa formulare in maniera decente questo modo di procedere. E dovrebbe realizzare il minimo teorico... Ma non ho controllato, quindi potrebbe non funzionare affatto!
Se può servire a farvi capire cosa intendo, sto visualizzando il reticolo delle parti come un rombo (che è il diagramma di Hasse associato al reticolo delle parti di un insieme finito).
Spiego meglio quello che volevo dire prima. Grazie al lemma di maurer sappiamo che esiste un modo semplice per costruire una partizione minimale di $P(I_n)$. Cominciamo col prendere una catena massimale $C_0$ di $P(I_n)$, questo sarà il primo elemento della nostra partizione. Chiaramente $C_0$ conterrà un elemento di ogni ordine compreso fra $0$ e $n$. Fra gli elementi rimasti possiamo costruire un'altra catena massimale $C_1$ che sarà il secondo elemeno della partizione. Anche $C_1$ contiene un elemento per ogni ordine fra $1$ e $n-1$. Siccome in $P(I_n)$ ci sono $((n),(k))$ elementi di ordine $k$, dopo $i$ iterazioni con $((n),(k-1))=n-k$ sono gia esauriti . Fra i coefficienti binomiali che possiamo considerare il più grande è $((n),([n/2]))$ quindi dopo $((n),([n/2]))$ iterazioni abbiamo esaurito $P(I_n)$. Può essere giusto?
Ho aggiustato un pò il discorso del post precedente. Dovrebbe essere un pò più sensato... almeno credo... 
Allora, così dovrebbe funzionare. Sostanzialmente è una revisione di quello che ha detto perplesso.
Fissiamo una catena massimale [tex]C_0[/tex] e togliamo i suoi elementi da [tex]\mathcal P(I_n)[/tex]. Rimane un reticolo con [tex]n-1[/tex] elementi minimali e [tex]n-1[/tex] massimali. Questi danno origine a [tex]n-1[/tex] catene massimali distinte. Togliendole rimane un reticolo con [tex]r_2 := \binom{n}{2} - (1 + n - 1)[/tex] elementi minimali (e lo stesso numero di massimali). Se denotiamo con [tex]s_1 := 1 + (n-1)[/tex] il numero di catene costruite fino a questo momento, abbiamo che [tex]r_2 = \binom{n}{2} - s_1[/tex] ed inoltre a questo punto possiamo aggiungere [tex]r_2[/tex] catene massimali nel reticolo in cui lavoriamo attualmente. Quindi otteniamo la relazione
Fissiamo una catena massimale [tex]C_0[/tex] e togliamo i suoi elementi da [tex]\mathcal P(I_n)[/tex]. Rimane un reticolo con [tex]n-1[/tex] elementi minimali e [tex]n-1[/tex] massimali. Questi danno origine a [tex]n-1[/tex] catene massimali distinte. Togliendole rimane un reticolo con [tex]r_2 := \binom{n}{2} - (1 + n - 1)[/tex] elementi minimali (e lo stesso numero di massimali). Se denotiamo con [tex]s_1 := 1 + (n-1)[/tex] il numero di catene costruite fino a questo momento, abbiamo che [tex]r_2 = \binom{n}{2} - s_1[/tex] ed inoltre a questo punto possiamo aggiungere [tex]r_2[/tex] catene massimali nel reticolo in cui lavoriamo attualmente. Quindi otteniamo la relazione
- [tex]s_2 = s_1 + r_2 = \binom{n}{2}[/tex][/list:u:zk590bvr]
Più in generale al passo [tex]k+1[/tex] il reticolo [tex]L_{k+1}[/tex] con cui stiamo lavorando avrà [tex]r_{k+1} = \binom{n}{k+1} - s_k[/tex] elementi minimali ed altrettanti elementi massimali, quindi avremo [tex]r_{k+1}[/tex] nuove catene. Di conseguenza [tex]s_{k+1} = r_{k+1} + s_k = \binom{n}{k+1}[/tex].
Fino a che punto possiamo portare avanti il procedimento? Fino a [tex]k = \left\lfloor \frac{n}{2} \right\rfloor[/tex], quindi otteniamo [tex]\binom{n}{\lfloor n / 2 \rfloor}[/tex] catene, ossia il minimo teorico.
Ho visto che perplesso ha editato. Adesso leggo cos'ha scritto.
Ecco, ho letto. Sì, ma leggi quello che ho detto io. Ha più l'aria di una dimostrazione, anche se va riscritta in forma decente specificando per bene le notazioni.
"maurer":
Sì, ma leggi quello che ho detto io. Ha più l'aria di una dimostrazione, anche se va riscritta in forma decente specificando per bene le notazioni.
Si scusa Mauro. Putroppo ho poca dimestichezza con i reticoli, adesso me li studio un pò e poi rileggo tutto il discorso con calma. Grazie 100000
Non serve. In questo caso è solo un modo formale di trattare con l'insieme delle parti. Un reticolo è un insieme parzialmente ordinato in cui esistono sempre l'inf ed il sup di una coppia di elementi (in questo caso, unione ed intersezione). Ma non ho usato da nessuna parte le proprietà reticolari.
Il punto che mi disturba è questo:
"maurer":L'esistenza di queste catene è il punto cruciale della dimostrazione, e non mi sembra così ovvia. In generale non è vero che se un reticolo ha un certo numero [tex]m[/tex] di massimali e minimali allora da questi posso costruire [tex]m[/tex] catene massimali disgiunte. In questo caso mi sembra vero intuitivamente, ma non vedo un motivo formale.
Questi danno origine a [tex]n-1[/tex] catene massimali distinte.
No, ma infatti non è ancora a posto: il problema da formalizzare è proprio quello che dici tu. Bisogna andare ad usare esplicitamente il fatto che stiamo lavorando su un'algebra di Boole, ma non ho ancora avuto il tempo di pensare a come fare.
Forse mi sono espresso ambiguamente prima.
Forse mi sono espresso ambiguamente prima.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo