partizionare insieme mediante catene

[perplesso]

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.

[Martino]

Per ora vedo delle stime "stupide". Detto \( \displaystyle m(n) \) il numero minimo di elementi di una partizione di \( \displaystyle P(I_n) \) formata da catene, si ha \( \displaystyle \binom{n}{[n/2]} \leq m(n) \leq 2 \cdot m(n-1) \) (dove \( \displaystyle [x] \) indica la parte intera del numero reale \( \displaystyle x \) ).

La prima disuguaglianza è ottenuta considerando i sottoinsiemi di \( \displaystyle I_n \) formati da \( \displaystyle n/2 \) 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 \( \displaystyle P(I_n) \) in due parti: gli insiemi che contengono \( \displaystyle 1 \) e quelli che non contengono \( \displaystyle 1 \) , poi applico il caso \( \displaystyle n-1 \) .

[perplesso]

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$ ...

[hamming_burst]

Interessante questo calcolo.
Posso chiedere una piccola cosa: ma con "minimo ordine" si intende il numero minimo di catene possibili?

[perplesso]

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})$

[perplesso]

Anche se non è una dimostrazione il computer mi conferma la stima \( \displaystyle \binom{n}{[n/2]} \) 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.

[Martino]

Caso risolto.

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.

[perplesso]

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=$ \( \displaystyle \binom{12}{6} \) . Quindi ho il "forte sospetto" che questa formula \( \displaystyle \binom{n}{[n/2]} \) 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.

[maurer]

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...

[hamming_burst]

@perplesso: grazie del chiarimento