Cliques et stables

Pour ce genre de preuves, il faut procéder en deux temps :

1. exhiber une clique de taille 4
2. montrer que tout ensemble de 5 sommets n'est pas une clique.

Le sous ensemble des sommets bleus suivant est une clique :

Si on prend 5 éléments, cela revient à supprimer 1 élément du graphe et aucuns de ceux ci n'est une clique.

Il suffit de prendre un des deux sommets rouge à l'intersection de la clique de taille 4 et du triangle rouge.

Une clique et un stable ne peuvent partager qu'au plus 1 sommet donc $n - (\alpha(G) - 1) \geq \omega(G)$.

Si $S$ est un stable à $p$ sommets et Si $K_q$ la clique à $q$ sommets alors l$e graphe : $G = (V(S) \cup V(K_q), E(S) \cup E(K_q))$ est tel que : $\omega(G) = q$ et $\alpha(G) = p + 1$.

On utilise la réduction consistant à prendre en entrée de stable le graphe complémentaire de celui en entrée de clique. La construction de ce graphe est au pire de complexité $\mathcal{O}(n^2)$ avec $n$ le nombre de sommets du graphe (on peut être amené à ajouter de l'ordre de $\mathcal{O}(n^2)$ arêtes si le graphe initial est discret).

La solution du problème stable est aussi la solution de problème clique pour le graphe originel, il n'y a donc aucun ajustement à faire pour le retour.

On va le montrer par réduction depuis le problème SAT.

Soit l'ensemble de clauses suivantes formant une entrée du problème SAT, sur l'ensemble de variables $\{ x_1, \dots, x_n \}$ :

Avec pour tous $1\leq i \leq m$ et $1\leq j \leq k_i$, $l_i^j \in \{x_i \vert 1\leq i \leq n \} \cup \{\overline{x_i} \vert 1\leq i \leq n \}$.

On associe (polynomialement) à cette instance un graphe $G=(V, E)$ tel que :

• $V = \{ l_i^j \vert 1\leq i \leq m, 1\leq j \leq k_i \}$
• $l_i^jl_k^l$ est une arête si :
  • $i \neq k$
  • $l_i^j \neq \overline{l_k^l}$

Et on cherche s'il existe une clique de taille supérieure ou égale à $m$.

S'il existe une solution au problème SAT alors il existe un littéral $l_i^{u_i}$ qui est vrai pour toute clause $1\leq i \leq m$. L'ensemble $\mathcal{C} = \{ l_i^{u_i} \vert 1\leq i \leq m\}$ est une clique de taille $K$ de $G$.

Réciproquement toute clique de $G$ ne peut contenir qu'au plus un littéral de chaque clause, donc une clique de taille $K$ contient un littéral par clause que l'on peut positionner à vrai.

C'est vrai pour $n < 2$ et pour $n \geq 2$, s'il existait une couverture à strictement moins de $n-1$ éléments, il existerait $x$ et $y$, deux sommets différents qui n'y sont pas, ce qui n'est pas possible puisque $xy$ est une arête de $K_n$.

algorithme vérification_couverture(G: graphe<sommet>, A: {sommet}, K: entier) → booléen:
  si |A| > K:
    rendre Faux
  
  pour chaque x, y de E(G):
    si x ∉ A ET y ∉ A:
        rendre Faux
  
  rendre Vrai

C'est un stable !

L'exercice précédent montre que chercher une couverture de taille inférieure ou égale à $K$ est équivalent à trouver un stable de taille supérieure ou égale à $v(G) - K$.

On construit le graphe $G' = (V', E')$ tel que :

• $V' = V(G) \cup \{x_1, \dots, x_{v(G)} \}$
• $E' = E(G) \cup \{ x_iy \mid 1\leq i \leq v(G), y \in V(G) \in \in \}$

De là trouver une clique de taille au moins $K$ dans $G$ est équivalent à trouver une clique ou un stable de taille au moins $v(G) + K$ dans $G'$.

Toutes ces transformations étant polynomiales on a bien que le problème clique est plus simple que le problème clique ou stable.

On prouve le résultat par récurrence sur $r = p + q \geq 2$.

Comme on a clairement que $R(1, 1) = 1$ et $R(2, 1) = R(1, 2) = 2$ on a que le résultat est vrai pour tous $p, q\geq 1$ tels que $p +q = r = 2$. On suppose le résultat vrai pour $r\geq 2$ et soit $p, q\geq 1$ tels que $r+1 = p + q$.

Comme $R(p-1, q)$ et $R(p, q-1)$ existent par hypothèse de récurrence, soit $G$ un graphe à $n = R(p-1, q) + R(p, q-1)$ sommets et $v$ un de ses sommets.

De deux choses l'une :

• soit $\delta(v)\geq R(p-1, q)$. On a alors 2 cas :
  • $G$ restreint aux voisins de $v$ contient un stable de taille $q$, donc $G$ également
  • $G$ restreint aux voisins de $v$ contient une clique $C$ de taille $p-1$ : $C \cup \{v\}$ est une clique de taille $p$ dans $G$,
• soit $\delta(v)\leq R(p-1, q) - 1$ et $n-1-\delta(v) \geq R(p-1, q) + R(p, q-1) - 1 -(R(p-1, q) - 1) \geq R(p, q-1)$. De la même manière que précédemment soit :
  • il existe une clique de taille $p$ dans le graphe $G$ restreint aux non-voisins de $v$, donc dans $G$ également
  • il existe un stable $S$ de taille $q-1$ dans le graphe $G$ restreint aux non-voisins de $v$ : $S \cup \{v\}$ est un stable de taille $q$ dans $G$.

Une récurrence triviale en utilisant la formule du triangle de Pascal.

Soit $G$ un graphe à $R(p, q)$ sommets. Le graphe $\overline{G}$ à le même nombre de sommets que $G$ donc :

• il possède soit une clique de taille $p$ et $G$ possède un stable de taille $p$
• il possède soit un stable de taille $q$ et $G$ possède une clique de taille $q$

On en déduit que $R(p, q) \leq R(q, p)$ pour tous $p$ et $q$ ils sont donc égaux (car on a alors aussi $R(q, p) \leq R(p, q)$)

Tout d'abord $R(3)> 5$ puisque le cycle $C_5$ ne contient que des cliques et des stables de taille 2.

Soit alors un graphe $G$ à plus de 6 sommets et soit $v$ un de ses sommets. Si $\delta(v) \geq 3$ alors :

• soit le graphe $G$ restreint à $N(v)$ n'a pas d'arête et c'est un stable de taille au moins 3,
• soit le graphe $G$ restreint à $N(v)$ a une arête dont ses extrémités plus $v$ forment une clique de taille 3.

Enfin, si $\delta(v) < 3$ un raisonnement identique sur le complémentaire de $G$ donne que :

• soit $\overline{G}$ possède un stable de taille 3 et donc $G$ une clique de taille 3,
• soit $\overline{G}$ possède une clique de taille 3 et donc $G$ un stable de taille 3.

Le graphe de Wagner ne possède ni clique de taille 3 ni stable de taille 4.

L'exercice précédent montre $R(3, 4) \geq 9$. Notre minoration donne $R(3, 4) \leq R(2, 4) + R(3, 3) \leq 10$ mais on peut la raffiner pour notre cas. Soit $v$ un sommet d'un graphe à 9 sommets. Si $\delta(v) \geq R(2, 4)$ alors le même raisonnement que pour le théorème nous permet de conclure. On suppose alors que $\delta(v) < R(2, 4) = 4$. Mais si $\delta(v) = 3$, soit il n'y a pas d'arêtes dans le graphe restreint aux voisins de $v$ et il y a un stable de taille 3, soit il y a une arête et si on ajoute $v$ cela fait une clique de taille 3.

On peut alors supposer que $\delta(v) < 3$ et donc $9-\delta(v)> 6$ : le graphe restreint aux non-voisins de $G$ contient soit une clique de taille 3 soit un stable de taille 3 qui adjoint à $v$ fait un stable de taille 4.

On utilise la formule de Stirling : $\binom{2p}{p} \sim \frac{4^{n}}{\sqrt{\pi \cdot n}}$.

Il existe alors une fonction négligeable en 1 lorsque $n$ tend vers l'infini, notée $f(n)$, telle que : $\binom{2p}{p} = (1 + f(n)) \frac{4^{n}}{\sqrt{\pi \cdot n}}$. En utilisant la borne précédente appliquée à $R(n,n)$ on a : $R(n, n) \leq \binom{2(n-1)}{n-1} = (1 + f(n)) \frac{4^{n-1}}{\sqrt{\pi \cdot (n-1)}}$ et comme $\frac{1}{\sqrt{n}} \sim \frac{1}{\sqrt{n-1}}$ en $+\infty$ on en déduit bien l'inégalité demandée.

Prenons un graphe aléatoire à $n$ sommets dont la probabilité qu'une arête $xy$ donnée existe soit $1/2$. La probabilité que ce graphe soit le stable à $p$ sommet est la même que ce graphe soit le graphe complet à $p$ sommet et vaut : $(\frac{1}{2})^{n(n-1)/2}$. Ainsi, la probabilité que ce graphe soit soit un stable soit une clique vaut $(2 \cdot \frac{1}{2})^{n(n-1)/2} = 2^{1-n(n-1)/2}$

Si on a maintenant un graphe aléatoire$G$ à $K$ sommets. La probabilité $P_{n}(G)$ qu'il contienne soit un stable soit une clique à $n$ sommets est inférieure à la somme pour chaque sous-ensemble à $n$ sommets (il y en a $\binom{K}{n}$) de la probabilité qu'il soit une clique ou un stable (et qui vaut $2^{1-n(n-1)/2}$). On en déduit que :

$K = 2^{n/2}$, alors : $\binom{K}{n} < \frac{K^n}{n!} < \frac{2^{n^2/2}}{n!}$ et de là, comme $n! > 2^{n/2 + 1}$ (par une récurrence triviale) on a : $\binom{K}{n} < \frac{2^{n^2/2}}{2^{n/2 + 1}}$. On se retrouve dans les hypothèses de l'exercice, ce qui nous permet de conclure.

On va utiliser la méthode probabiliste mais de façon un peu plus subtile que dans l'exercice.

Soit $G$ un graphe aléatoire à $k$ sommets. Soit $X(G)$ la variable aléatoire qui compte le nombre de clique et de stables de taille $n$ de $G$. On a :

Si l'on supprime du graphe un sommet (on peut supprimer plusieurs fois le même sommet) pour chacune de ses cliques et stable de taille $n$, le nouveau graphe ne contient plus ni clique ni stable de taille $n$ et aura au moins $k - X(G)$ sommets puisque l'on peut supprimer le même sommet plusieurs fois.

De là, l'espérance du nombre de sommets du nouveau graphe est plus grande que $\mathbb{E}(N - X) = N - \mathbb{E}(X) = N - \binom{N}{n} \cdot {2^{1-n(n-1)/2}}$. Comme c'est une espérance il existe des graphes ayant ce nombre de sommets ou plus après suppression et donc : $R(n) \geq k - \binom{k}{n} \cdot {2^{1-n(n-1)/2}}$ pour tout $k$.

La proposition précédente étant vraie pour tout $k$. On peut alors prendre un $k$ qui nous arrange, par exemple : $k = \lfloor\frac{n}{e}\cdot 2^{n/2}\rfloor$. Ce $k$ est effectivement arrangeant car :

• $\binom{k}{n} = \frac{k (k-1) \dots (k-n-1)}{n!} < \frac{k^n}{n!}$
• $e^n \geq \frac{n^n}{n!}$, puisque $e^n = \sum_{i\geq 0}\frac{n^{i}}{i!}\geq \frac{n^n}{n!}$

Et donc : $\binom{k}{n} \cdot {2^{1-n(n-1)/2}} \leq \frac{k^n}{n^n/e^n} \cdot {2^{1-n(n-1)/2}}$

En remplaçant $k$ par sa valeur on obtient $R(n) > \lfloor\frac{n}{e}\cdot 2^{n/2}\rfloor - 2\cdot 2^{}n/2 \geq \frac{n}{e}\cdot 2^{n/2} - 1 - 2\cdot 2^{}n/2 = (1/e + o(1))\cdot n\cdot 2^{n/2}$ ce qui conclut la preuve.