Teoria di Ramsey

[fields]

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

[vl4d]

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?)

[fields]

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

[vl4d]

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

[TomSawyer]

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.

[fields]

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

[TomSawyer]

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.

[TomSawyer]

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 <...<a_{2^{|S|-1}+1}+3 \le 2^{|S|}+1$. Tra i $2^{|S|}+2$ numeri $a_1,a_2,...,a_{2^{|S|-1}+1}, a_1+3,...,a_{2^{|S|-1}+1}+3$ ce ne saranno due di uguali; cioè ci sono due indici $i,j$ tali che $a_i=a_j+3$, e segue facilmente la tesi.

[fields]

Idea carina Questa affermazione però non è vera:

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$

[TomSawyer]

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?