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
Salve amici 
come promesso mi sono messo a studiare la teoria dei reticoli e dei poset, ed ho trovato che questo problema su cui stavamo riflettendo se lo è posto prima di noi il matematico Robert Dilworth che ha dimostrato che in un poset finito il numero minimo di catene in cui si può decomporre il poset stesso è uguale al massimo ordine di un'anticatena del poset. Nel nostro caso l''anticatena più grande di $P({1,...,n})$ ha ordine proprio $((n),([n/2]))$. Una dimostrazione sta in questo pdf (pagina 5 teorema 1.4) Saluti. 
come promesso mi sono messo a studiare la teoria dei reticoli e dei poset, ed ho trovato che questo problema su cui stavamo riflettendo se lo è posto prima di noi il matematico Robert Dilworth che ha dimostrato che in un poset finito il numero minimo di catene in cui si può decomporre il poset stesso è uguale al massimo ordine di un'anticatena del poset. Nel nostro caso l''anticatena più grande di $P({1,...,n})$ ha ordine proprio $((n),([n/2]))$. Una dimostrazione sta in questo pdf (pagina 5 teorema 1.4) Saluti.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo