partizionare insieme mediante catene

Messaggioda perplesso » 02/05/2012, 17:06

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.
Avatar utente
perplesso
Average Member
Average Member
 
Messaggio: 428 di 985
Iscritto il: 09/12/2009, 19:52

Re: partizionare insieme mediante catene

Messaggioda Martino » 02/05/2012, 17:28

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 \) .
Le persone che le persone che le persone amano amano amano.
Avatar utente
Martino
Moderatore globale
Moderatore globale
 
Messaggio: 5153 di 7368
Iscritto il: 21/07/2007, 11:48
Località: Brasilia

Re: partizionare insieme mediante catene

Messaggioda perplesso » 02/05/2012, 22:02

Martino ha scritto:Per ora vedo delle stime "stupide"

Mica tanto "stupide". :D 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$ ...
Avatar utente
perplesso
Average Member
Average Member
 
Messaggio: 429 di 985
Iscritto il: 09/12/2009, 19:52

Re: partizionare insieme mediante catene

Messaggioda hamming_burst » 02/05/2012, 22:12

Interessante questo calcolo.
Posso chiedere una piccola cosa: ma con "minimo ordine" si intende il numero minimo di catene possibili?
hamming_burst
Cannot live without
Cannot live without
 
Messaggio: 1941 di 4280
Iscritto il: 04/07/2009, 11:53

Re: partizionare insieme mediante catene

Messaggioda perplesso » 02/05/2012, 22:18

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})$
Avatar utente
perplesso
Average Member
Average Member
 
Messaggio: 430 di 985
Iscritto il: 09/12/2009, 19:52

Re: partizionare insieme mediante catene

Messaggioda perplesso » 03/05/2012, 12:23

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. :-)
Avatar utente
perplesso
Average Member
Average Member
 
Messaggio: 431 di 985
Iscritto il: 09/12/2009, 19:52

Re: partizionare insieme mediante catene

Messaggioda Martino » 03/05/2012, 12:42

perplesso ha scritto: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.
Le persone che le persone che le persone amano amano amano.
Avatar utente
Martino
Moderatore globale
Moderatore globale
 
Messaggio: 5154 di 7368
Iscritto il: 21/07/2007, 11:48
Località: Brasilia

Re: partizionare insieme mediante catene

Messaggioda perplesso » 03/05/2012, 13:01

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. :wink:
Avatar utente
perplesso
Average Member
Average Member
 
Messaggio: 432 di 985
Iscritto il: 09/12/2009, 19:52

Re: partizionare insieme mediante catene

Messaggioda maurer » 03/05/2012, 19:21

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...
I believe in the axiom of choice, and in particular that every proper ideal in a ring is contained in a maximal ideal!
maurer
Senior Member
Senior Member
 
Messaggio: 1600 di 1866
Iscritto il: 31/07/2008, 13:11
Località: Milano!

Re: partizionare insieme mediante catene

Messaggioda hamming_burst » 03/05/2012, 22:36

@perplesso: grazie del chiarimento :-)
hamming_burst
Cannot live without
Cannot live without
 
Messaggio: 1944 di 4280
Iscritto il: 04/07/2009, 11:53

Prossimo

Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 5 ospiti