Teoria di Ramsey

[fields1]

Eccovi un esercizietto che ho appena inventato:

Siano $S$ un insieme finito, $P(S)$ l'insieme dei sottinsiemi di $S$ e $X\sube P(S)$. Dimostrare che se $|X|>|P(S)|/2$, allora esistono $A,B\in X$ tali che $A\sub B$.

[vl4dster]

molto molto intuitivamente (e anche con qualche dubbio... Ramsey e' ancora nella lista delle cose da fare),
consideriamo il reticolo $(P(S), \subseteq)$ come un grafo, e coloriamo
di rosso gli archi. Coloriamo di blu gli archi complementari, in modo da avere un grafo completo.
Ora cerchiamo un insieme massimale di vertici tali che ci sia un cammino hamiltoniano blu, e tali che
siano mutuamente non connessi da archi rossi. Si nota che gli elementi di tale insieme devono essere tutti
sottoinsiemi di $S$ di cardinalita' $[|S|/2]$ (l'intero piu' vicino), perche' se cosi' non fosse, potremmo sempre
prendere gli insiemi contenuti o contenenti l'insieme di cardinalita' diversa da $[|S|/2]$,
e ne troveremmo necessariamente almeno uno in piu', contro l'ipotesi di massimalita'.
Da $((|S|),([|S|/2])) < 2^{|S|-1}$ si ha la tesi...

(Quante cazzate dico?)

[fields1]

Il risultato è "stile Ramsey", ma non serve nessuna conoscenza della teoria di Ramsey per risolverlo, è elementare.

Per quanto riguarda la tua soluzione, ti chiederei di spiegare meglio i dettagli, perché sinceramente non ti seguo...

EDIT: In particolare è questa affermazione

Si nota che gli elementi di tale insieme devono essere tutti
sottoinsiemi di $S$ di cardinalita' $[|S|/2]$ (l'intero piu' vicino), perche' se cosi' non fosse, potremmo sempre
prendere gli insiemi contenuti o contenenti l'insieme di cardinalita' diversa da $[|S|/2]$,
e ne troveremmo necessariamente almeno uno in piu', contro l'ipotesi di massimalita'.

che andrebbe giustificata con cura (se vera).

[vl4dster]

Lascia stare, convince poco anche me... vedo di cercare una strada diversa

[TomSawyer1]

Si dovrebbe poter abbassare il bound di $|P(S)|/2$ a $((|S|),([|S|/2]))$, perché si può vedere $P(S)$ come l'unione dei sottoinsiemi di $S$ con $1$ elemento, con $2$ elementi, ..., con $|S|$ elementi. La massima cardinalità di $X$ per cui non vale la tesi è $((|S|),([|S|/2]))$, cioè $\max((|S|),(k))$, con $k \in [1,|S|]$, perché se $X$ contiene solo sottoinsiemi con cardinalità uguali, allora nessuno contiene l'altro. Ma aggiungendone un altro qualsiasi, si avrà subito la tesi.

[fields1]

"TomSawyer":Si dovrebbe poter abbassare il bound di $|P(S)|/2$ a $((|S|),([|S|/2]))$

Eh già, si dovrebbe poter abbassare il bound in quel modo, ottendo quindi un vero risultato alla Ramsey. Il problema è dimostrarlo! Ho postato il bound $|P(S)|/2$ perché è più facile. Comunque ora sono incuriosito, proverò a pensarci

[TomSawyer1]

Non avevo visto che vl4d ha detto la stessa cosa . Si potrebbe provare per induzione, ma non mi sembra molto fattibile; poi non sarebbe neanche bello.

[TomSawyer1]

Intanto dò la soluzione del problema iniziale. Si consideri l'ordine lessicografico per definire una biezione degli elementi di $P(S)$ con ${1,2,...,|P(S)|-2}$, tralasciando $\emptyset$ ed $S$ stesso. Usando questo ordine, comunque si scelgano tre insiemi consecutivi, ci sarà sempre uno che è sottoinsieme proprio di un altro. Quindi ora basta provare che, comunque si prendano $2^{|S|-1}+1$ numeri interi compresi in $[1,2^{|S}-2], ce ne saranno sempre tre consecutivi.
Siano $1\le a_1 < a_2 < ... < a_{2^{|S|-1}+1}\le 2^{|S|}-2$ i numeri scelti. Si avrà anche $4 \le a_1+3 < a_2+3 <...

Cita

Segnala

[fields1]

Idea carina Questa affermazione però non è vera:

"TomSawyer": Quindi ora basta provare che, comunque si prendano $2^{|S|-1}+1$ numeri interi compresi in $[1,2^{|S}-2]$, ce ne saranno sempre tre consecutivi.

Poniamo $|S|=4$

Nell'intervallo $[1,14]$ possiamo scegliere più di $2^3$ elementi senza averne tre consecutivi

$1,2,4,5,7,8,10,11,13,14$

[TomSawyer1]

Vero , ho dimostrato un'altra cosa.

Lemma: se si scelgono $n+2$ interi dall'insieme ${1,...,2n}$, allora ci sarà sempre una coppia di interi consecutivi, di cui il primo pari.
Dim.Si consideri la divisione dell'insieme in $n+1$ sottoinsiemi: ${1},{2,3},{4,5},...,{2n-2,2n-1},{2n}$. Siccome abbiamo a disposizione $n+2$ elementi, allora almeno un insieme di cardinalità 2 sarà coperto.

Allora consideriamo di nuovo la biezione di prima $f: P(S) \to {1,2,...,2^{|S|}-2}$. Nell'ordine lessicografico, si ha che $f^{-1}(n) \sub f^{-1}(n+1)$, se $n$ è pari. Quindi, basta usare il lemma per vedere che comunque si scelgano $2^{|S|-1}+1$ interi diversi compresi in $[1,2^{|S|}-2]$, ce ne saranno due di consecutivi, di cui il primo pari. E' ok questa?

ps: progressi con l'altro problema?

[fields1]

In queste dimostrazioni non si possono saltare i dettagli, altrimenti si sbaglia. Se dimostri anche questo, allora la tua prova è ok.

"TomSawyer": Nell'ordine lessicografico, si ha che $f^{-1}(n) \sub f^{-1}(n+1)$, se $n$ è pari.

Per quanto riguarda l'altro problema, devo ancora capire se ho fatto progressi o no . In sostanza ho ridotto il problema nel trovare una funzione iniettiva $f$ dall'insieme $S_k$ dei sottinsiemi di $S$ con $k$ elementi nell'insieme $S_(k+1)$ dei sottinsiemi di $S$ con $k+1$ elementi (ovviamente quanto $|S_k|<|S_(k+1)|$) tale che $A sub f(A)$ per ogni $A\in S_k$. Però anche dimostrare questo non è così facile.

[TomSawyer1]

Ok, è che mi sembra così per definizione. L'ordine lessicografico a cui faccio riferimento (ci sono almeno tre ordini in giro con questo nome) è questo. Esempio per $S={1,2,3}$: ${1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}$. Ogni due elementi si introduce uno nuovo, facendo seguire poi

Tesi: $f^{-1}(n) \sub f^{-1}(n+1)$, se $n$ è pari. Per $n=2$ è vera. Supponiamo sia vera per $n-1$. Allora per $n$ abbiamo già metà dei sottoinsiemi ordinati (per ipotesi induttiva), cioè tutti quelli senza $n$. I prossimi $2^{n-1}$ sottoinsiemi, sono esattamente quelli della prima metà, con aggiunto ${n}$ ad ognuno, non cambiando assolutamente nulla.

Ora veniamo alla tua dimostrazione di una riga .

[fields1]

"TomSawyer":L'ordine lessicografico a cui faccio riferimento (ci sono almeno tre ordini in giro con questo nome) è questo.

E quando pensavi di specificare quale dei tre era il tuo ordinamento lessicografico? Io stavo pensando a tutt'altro ordinamento!

Comunque, ordinamento carino e prova carina.

Io avevo fatto cosi. Fissiamo $s\in S$. Consideriamo la funzione $f: X to P(S\\{s})$ cosi' definita: $f(A)=A\\{s}$. Il codominio di $f$ ha cardinalita' $2^(|S|-1)$, mentre il dominio di $f$ ha cardinalita' maggiore di $2^(|S|-1)$ per ipotesi. Per il pigeonhole principle, esistono due distinti $A,B\in X$ tali che $f(A)=f(B)$; dunque $A\\{s}=B\\{s}$. Chiaramente $s$ non puo' appartenere o non appartenere a entrambi $A$ e $B$, altrimenti $A=B$. WLOG, $s\in B$ e $s\notin A$ e dunque $A=A\\{s}=B\\{s}$ e dunque $A\sub B$.

Ora al lavoro sul problema più difficile!

[vl4dster]

Io ho provato un po' sia per induzione sia ragionando sul grafo del reticolo d'ordine... ma o
ero rincitrullito, o la prova non e' molto agevole in quei modi...

[fields1]

EDIT: Ragazzi, ma quello che cercavamo di dimostrare è il teorema di Sperner!

http://www.math.cmu.edu/~af1p/Combinato ... es/Ch6.pdf

http://www.cut-the-knot.org/pigeonhole/sperner.shtml