Un limite inferiore costruttivo sui numeri di Ramsey
Il teorema di Ramsey lo afferma
Dato $s, t\in \mathbb{N}$, c'è $n\in \mathbb{N}$ tale che per ogni grafico con $n$ vertici, contiene un file $s$-clique o il suo complemento contiene a $t$-cricca.
Il più piccolo $n$ soddisfare l'affermazione è indicato da $R(s, t)$.
Ho trovato nell'articolo "The Probabilistic Method in Combinatorics, Lectures by Niranjan Balachandran" la seguente dichiarazione:
Un limite inferiore costruttivo su R (s, s), scoperto da Nagy, è il seguente: $$R(s, s)\ge \binom{s}{3}$$ (Esplicitamente, la sua costruzione è la seguente: prendi qualsiasi set $S$e trasforma la raccolta di tutti $3$-elemento sottoinsiemi di $S$ in un grafico collegando sottoinsiemi se e solo se la loro intersezione è dispari.)
Non sono stato in grado di dimostrare che questo grafico e il suo complemento non contengano $s$-cliques. Qualsiasi aiuto in questa materia sarebbe molto apprezzato.
Risposte
Prendiamo $S = \{1, 2, \dots, s\}$. Quello che possiamo effettivamente mostrare è che il grafico di Nagy ha
- cricche di dimensioni al massimo $\max\{7, \frac{s-1}{2}\}$, e
- insiemi di dimensioni indipendenti al massimo $s-1$ o meno quando $s \not\equiv 0 \pmod 4$, e al massimo $s$ quando $s \equiv 0 \pmod 4$.
Questo non lo dimostra $R(s,s) \ge \binom s3$ per tutti $s$, ma lo mostra $R(s,s) > \binom s3$, e anche quello $R(\frac{s}{2}, s) > \binom s3$, per infiniti valori di $s$.
Per prima cosa, troviamo la più grande cricca. Ci sono due casi:
- La cricca contiene $4$ vertici che si intersecano allo stesso elemento di $S$: dire, $\{1,2,3\}$, $\{1,4,5\}$, $\{1,6,7\}$, e $\{1,8,9\}$. Quindi ogni altro vertice deve contenere$1$: altrimenti, dovrebbe avere un elemento da ciascuno di $\{2,3\}$, $\{4,5\}$, $\{6,7\}$, e $\{8,9\}$, il che è impossibile. Una tale cricca può avere al massimo$\frac{s-1}{2}$ vertici.
- La cricca contiene al massimo $3$ vertici che si intersecano allo stesso elemento di $S$. Dire$\{1,2,3\}$è uno dei vertici. Allora ci possono essere al massimo$2$ altri vertici contenenti ciascuno di $1$, $2$, o $3$, quindi la cricca ha al massimo $7$ vertici.
Quindi, troviamo il più grande insieme indipendente. Qui, nota che se due vertici nell'insieme indipendente condividono$2$ elementi e terzo vertice nelle quote di insiemi indipendenti $2$ elementi con uno di essi, deve condividere almeno un elemento (e quindi $2$elementi) con l'altro. Quindi l'insieme indipendente deve essere costituito da cluster, dove condividono due vertici qualsiasi in un cluster$2$ elementi e due vertici qualsiasi all'esterno della condivisione del cluster $0$.
Ancora una volta, i cluster possono avere due forme diverse:
- Supponiamo che un cluster lo abbia $3$ vertici che condividono tutti lo stesso $2$ elementi: dire, $\{1,2,3\}$, $\{1,2,4\}$,e $\{1,2,5\}$. Un altro vertice nel cluster che conteneva solo uno di$\{1,2\}$ dovrebbe contenere ciascuno di $3$, $4$, e $5$, il che è impossibile. Quindi il cluster è composto da$k$ vertici della forma $\{1,2,x\}$, che "esaurisce" $k+2$ elementi di $S$.
- Supponiamo che un cluster abbia al massimo $2$ vertici che condividono qualsiasi file $2$elementi. Allora se$\{1,2,3\}$ è un vertice nel cluster, ogni altro vertice nel cluster deve contenere due di $\{1,2,3\}$, ma ce ne può essere al massimo uno di ogni tipo, per $4$vertici totali. Questi devono esaurirsi almeno$4$ elementi di $S$, come con $\{1,2,3\}, \{1,2,4\}, \{1,3,4\}, \{2,3,4\}$.
Vediamo che un cluster utilizza up $k$ elementi di $S$ può contenere al massimo $k$ vertici, quindi complessivamente i cluster possono contenere al massimo $S$vertici. Ma questo è possibile solo quando tutti i cluster sono del secondo tipo e coprono tutti gli elementi di$S$, che richiede $s \equiv 0 \pmod 4$.