partizionare insieme mediante catene

[maurer]

Ok, l'ho dimostrato, per lo meno nel caso di tuo interesse.

Allora:

Lemma. Sia \( \displaystyle \{C_1,\ldots,C_m\} \) una partizione minima di \( \displaystyle \mathcal P(I_n) \) fatta di catene. Poniamo \( \displaystyle U_k = \bigcup C_k \) (l'unione degli elementi di \( \displaystyle C_k \) ). Allora possiamo assumere che per ogni \( \displaystyle k = 1,\ldots,m \) , \( \displaystyle C_k \) sia una catena massimale di \( \displaystyle \mathcal P(I_n) \setminus (U_1 \cup \ldots \cup U_{k-1}) \) .
Dimostrazione. Supponiamo che \( \displaystyle C_k \) non sia una catena massimale di \( \displaystyle \mathcal P(I_n) \setminus (U_1 \cup \ldots \cup U_{k-1}) \) ; allora esiste una catena massimale \( \displaystyle C_k' \) in \( \displaystyle \mathcal P(I_n) \setminus (U_1 \cup \ldots \cup U_{k-1}) \) tale che \( \displaystyle C_k \subset C_k' \) . Questa nuova catena è ottenuta aggiungendo a \( \displaystyle C_k \) elementi che si trovano in \( \displaystyle C_h \) con \( \displaystyle h > k \) ; pertanto, togliendo questi elementi dalle rispettive catene, otteniamo una nuova partizione, e se \( \displaystyle m' \) denota il nuovo numero di elementi che formano questa partizione, abbiamo \( \displaystyle m' \le m \) , sicché segue la tesi per minimalità di \( \displaystyle m \) . []

A questo punto non dovrebbe essere difficile concludere. Di, nuovo però, non ho tempo immediato. Vi lascio a trarre le conclusioni da questo lemma.

[perplesso]

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!

[Martino]

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 \( \displaystyle P(I_n) \) ? Chiaro che esiste un ricoprimento minimale formato da catene massimali, cioè di lunghezza \( \displaystyle n \) .

Un modo utile per trovare stime dall'alto (sono queste che mancano!) è forse il seguente: un ordine dato agli \( \displaystyle n \) numeri determina \( \displaystyle n \) catene come segue: si parte da uno dei numeri e si va a destra ciclicamente. Per esempio la sequenza (ordinata!)

\( \displaystyle 12345 \)

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 \( \displaystyle n=5 \) uno osserva che le sequenze 12345, 13524 determinano \( \displaystyle 2 \cdot 5 = 10 \) catene che coprono tutto \( \displaystyle P(I_5) \) , 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 \( \displaystyle \binom{n}{[n/2]} \) elementi?

PPS. Maurer, sottintendi che il tuo lemma implica che il numero minimo cercato è \( \displaystyle \binom{n}{[n/2]} \) ? Sarà la giornata intensa, ma non vedo come.

[maurer]

La mia idea rozza era: si fissa una catena massimale e la si toglie. Il reticolo che rimane ha altezza \( \displaystyle n-1 \) ed ha precisamente \( \displaystyle n-1 \) elementi minimali e \( \displaystyle n-1 \) elementi massimali. Questo dovrebbe la possibilità di costruire \( \displaystyle n-1 \) catene massimali disgiunte; le tolgo tutte quante. Mi rimane un reticolo di altezza \( \displaystyle n-3 \) (e dovrebbe avere \( \displaystyle n-3 \) elementi minimali e \( \displaystyle n-3 \) 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).

[perplesso]

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))<i < ((n),(k))$ otteniamo una catena $C_i$ che contiene un elemento di ogni ordine fra $k$ ed $n-k$. Inoltre gli elementi di ordine $<=k$ oppure $>=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?

[perplesso]

Ho aggiustato un pò il discorso del post precedente. Dovrebbe essere un pò più sensato... almeno credo...

[maurer]

Allora, così dovrebbe funzionare. Sostanzialmente è una revisione di quello che ha detto perplesso.

Fissiamo una catena massimale \( \displaystyle C_0 \) e togliamo i suoi elementi da \( \displaystyle \mathcal P(I_n) \) . Rimane un reticolo con \( \displaystyle n-1 \) elementi minimali e \( \displaystyle n-1 \) massimali. Questi danno origine a \( \displaystyle n-1 \) catene massimali distinte. Togliendole rimane un reticolo con \( \displaystyle r_2 := \binom{n}{2} - (1 + n - 1) \) elementi minimali (e lo stesso numero di massimali). Se denotiamo con \( \displaystyle s_1 := 1 + (n-1) \) il numero di catene costruite fino a questo momento, abbiamo che \( \displaystyle r_2 = \binom{n}{2} - s_1 \) ed inoltre a questo punto possiamo aggiungere \( \displaystyle r_2 \) catene massimali nel reticolo in cui lavoriamo attualmente. Quindi otteniamo la relazione

\( \displaystyle s_2 = s_1 + r_2 = \binom{n}{2} \)

Più in generale al passo \( \displaystyle k+1 \) il reticolo \( \displaystyle L_{k+1} \) con cui stiamo lavorando avrà \( \displaystyle r_{k+1} = \binom{n}{k+1} - s_k \) elementi minimali ed altrettanti elementi massimali, quindi avremo \( \displaystyle r_{k+1} \) nuove catene. Di conseguenza \( \displaystyle s_{k+1} = r_{k+1} + s_k = \binom{n}{k+1} \) .

Fino a che punto possiamo portare avanti il procedimento? Fino a \( \displaystyle k = \left\lfloor \frac{n}{2} \right\rfloor \) , quindi otteniamo \( \displaystyle \binom{n}{\lfloor n / 2 \rfloor} \) 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.

[perplesso]

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

[maurer]

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.

[Martino]

Il punto che mi disturba è questo:

Questi danno origine a \( \displaystyle n-1 \) catene massimali distinte.

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 \( \displaystyle m \) di massimali e minimali allora da questi posso costruire \( \displaystyle m \) catene massimali disgiunte. In questo caso mi sembra vero intuitivamente, ma non vedo un motivo formale.