Une borne inférieure constructive sur les nombres de Ramsey
Le théorème de Ramsey déclare que
Donné $s, t\in \mathbb{N}$, il y a $n\in \mathbb{N}$ tel que pour chaque graphe avec $n$ sommets, il contient un $s$-clique ou son complément contient un $t$-clique.
Le plus petit $n$ la satisfaction de l'instruction est désignée par $R(s, t)$.
J'ai trouvé dans l'article "La méthode probabiliste en combinatoire, conférences de Niranjan Balachandran" la déclaration suivante:
Une borne inférieure constructive sur R (s, s), découverte par Nagy, est la suivante: $$R(s, s)\ge \binom{s}{3}$$ (Explicitement, sa construction est la suivante: prenez n'importe quel ensemble $S$, et tournez la collection de tous $3$-élément sous-ensembles de $S$ dans un graphe en connectant des sous-ensembles ssi leur intersection est étrange.)
Je n'ai pas pu prouver que ce graphe et son complément ne contiennent pas $s$-cliques. Toute aide dans ce domaine serait grandement appréciée.
Réponses
Prenons $S = \{1, 2, \dots, s\}$. Ce que nous pouvons en fait montrer, c'est que le graphique de Nagy a
- cliques de taille au plus $\max\{7, \frac{s-1}{2}\}$, et
- ensembles indépendants de taille au plus $s-1$ ou moins quand $s \not\equiv 0 \pmod 4$, et au plus $s$ quand $s \equiv 0 \pmod 4$.
Cela ne montre pas que $R(s,s) \ge \binom s3$ pour tous $s$, mais cela montre que $R(s,s) > \binom s3$, et même ça $R(\frac{s}{2}, s) > \binom s3$, pour une infinité de valeurs de $s$.
Tout d'abord, trouvons la plus grande clique. Il y a deux cas:
- La clique contient $4$ sommets se croisant au même élément de $S$: dire, $\{1,2,3\}$, $\{1,4,5\}$, $\{1,6,7\}$, et $\{1,8,9\}$. Ensuite, chaque autre sommet doit contenir$1$: sinon, il devrait avoir un élément de chacun des $\{2,3\}$, $\{4,5\}$, $\{6,7\}$, et $\{8,9\}$, ce qui est impossible. Une telle clique peut avoir au plus$\frac{s-1}{2}$ sommets.
- La clique contient au plus $3$ sommets se croisant au même élément de $S$. Dire$\{1,2,3\}$est l'un des sommets. Alors il peut y avoir au plus$2$ d'autres sommets contenant chacun des $1$, $2$, ou $3$, donc la clique a au plus $7$ sommets.
Ensuite, trouvons le plus grand ensemble indépendant. Ici, notez que si deux sommets de l'ensemble indépendant partagent$2$ éléments et troisième sommet dans les partages d'ensemble indépendants $2$ éléments avec l'un d'entre eux, il doit partager au moins un élément (et donc $2$éléments) avec l'autre. Ainsi, l'ensemble indépendant doit être composé de clusters, où deux sommets d'un cluster se partagent$2$ éléments et deux sommets en dehors du partage de cluster $0$.
Encore une fois, les clusters peuvent avoir deux formes différentes:
- Supposons qu'un cluster a $3$ des sommets qui partagent tous le même $2$ éléments: dire, $\{1,2,3\}$, $\{1,2,4\}$,et $\{1,2,5\}$. Un autre sommet du cluster qui ne contenait qu'un seul des$\{1,2\}$ devrait contenir chacun des $3$, $4$, et $5$, ce qui est impossible. Le cluster se compose donc de$k$ sommets de la forme $\{1,2,x\}$, qui «utilisent» $k+2$ des éléments de $S$.
- Supposons qu'un cluster ait au plus $2$ sommets partageant $2$éléments. Puis si$\{1,2,3\}$ est un sommet du cluster, chaque autre sommet du cluster doit contenir deux des $\{1,2,3\}$, mais il peut y en avoir au plus un de chaque type, car $4$sommets au total. Ceux-ci doivent utiliser au moins$4$ des éléments de $S$, comme avec $\{1,2,3\}, \{1,2,4\}, \{1,3,4\}, \{2,3,4\}$.
On voit qu'un cluster s'épuise $k$ des éléments de $S$ peut contenir au plus $k$ sommets, de sorte que les clusters peuvent contenir au plus $S$sommets. Mais cela n'est possible que lorsque tous les clusters sont du second type et couvrent tous les éléments de$S$, ce qui nécessite $s \equiv 0 \pmod 4$.