Exercice 105

On note $\mathcal{E}_{X}$ l'ensemble des arêtes dont les deux extrémités appartiennent à $X$, de sorte que $Y = |\mathcal{E}_{X}|$, et, pour une arête $e$, $\mu(e)$ son extrémité de plus grand numéro. La partie retirée est $D = \mu(\mathcal{E}_{X}) \subset X$, et $U = X \setminus D$.

1. Si une arête $e$ était contenue dans $U$, elle le serait dans $X$, donc $e \in \mathcal{E}_{X}$, et l'extrémité $\mu(e)$ appartiendrait à $D$, donc pas à $U$ : c'est absurde. Ainsi $\boxed{U \text{ est indépendante}}$. L'ensemble $D$ est l'image de $\mathcal{E}_{X}$ par $\mu$, donc $|D| \leqslant |\mathcal{E}_{X}| = Y$ (chapitre 2), et, comme $D \subset X$, $$\boxed{|U| = |X| - |D| \geqslant |X| - Y}$$ L'inégalité peut être stricte : un même sommet peut être retiré à cause de plusieurs arêtes.

2. On a $|X| = \sum_{s \in S} B_{s}$ et $Y = \sum_{\{s, s'\} \in \mathcal{E}} B_{s}B_{s'}$, et, pour $s \neq s'$, $\mathrm{E}(B_{s}B_{s'}) = p^{2}$ par l'indépendance et la proposition 20. Par croissance et linéarité de l'espérance (théorème 9), $$\mathrm{E}\big(|U|\big) \geqslant \mathrm{E}\big(|X|\big) - \mathrm{E}(Y) = np - |\mathcal{E}|\,p^{2}, \qquad\text{d'où}\qquad \boxed{\mathrm{E}\big(|U|\big) \geqslant np - \frac{p^{2}nd}{2}}$$ C'est la méthode des indicatrices (section 21.6.3), qui ne demande pas la loi de $|U|$.

3. La fonction $f : p \mapsto np - \frac{p^{2}nd}{2}$ est un trinôme du second degré, de coefficient dominant négatif, maximal en $p = \frac{1}{d}$, qui appartient à $\left]0\,,1\right]$ puisque $d \geqslant 1$ : $$f\Big(\frac{1}{d}\Big) = \frac{n}{d} - \frac{n}{2d} = \frac{n}{2d}, \qquad \mathrm{E}\big(|U|\big) \geqslant \frac{n}{2d} \ \text{ pour } p = \frac{1}{d}.$$ Par le principe de la moyenne (théorème 9 (v)), $\mathrm{P}\big(|U| \geqslant \mathrm{E}(|U|)\big) > 0$ : l'événement n'est pas vide, et il existe une issue $\omega$ telle que $|U(\omega)| \geqslant \mathrm{E}(|U|) \geqslant \frac{n}{2d}$. La partie $U(\omega)$ est indépendante, d'où $$\boxed{\alpha(\Gamma) \geqslant \frac{n}{2d}}$$ Pour l'hexagone, $n = 6$ et $d = 2$ : la minoration donne $\alpha \geqslant \frac{3}{2}$, donc $\alpha \geqslant 2$, et l'on a en fait $\alpha = 3$ ; le calcul exact donne $\mathrm{E}(|U|) = \frac{13}{8}$ pour $p = \frac{1}{2}$ ✓. Le réel $d = \frac{2|\mathcal{E}|}{n}$ est le degré moyen d'un sommet. La minoration a le bon ordre de grandeur : pour la réunion disjointe de $\frac{n}{d + 1}$ graphes complets à $d + 1$ sommets, on a $\frac{nd}{2}$ arêtes et $\alpha = \frac{n}{d + 1}$, puisqu'une partie indépendante contient au plus un sommet de chaque graphe complet.

À retenir. On a démontré l'existence d'une grande partie indépendante sans en construire aucune, en calculant une espérance : c'est la méthode probabiliste, déjà rencontrée avec les tournois de l'exercice 54 et avec l'exercice 50 de la feuille du chapitre 19. Le choix du paramètre $p$ est un réglage : trop grand, il crée trop d'arêtes internes ; trop petit, la partie $X$ est trop petite.