Corrigé ENS Ulm 2025 Maths D MP — Partie 2.3 (Q25 à Q28) : Complexes de polytopes : facettes, cône sur le bord, subdivision barycentrique, caractéristique d'un complexe convexe

On utilise les lemmes L1--L4 (partie 2.1) et L5--L7 (partie 2.2) ; $J(x)$ désigne l'ensemble des contraintes saturées en $x$ et $F(x)=F_{J(x)}$ la plus petite face contenant $x$. Une face de dimension $\dim P-1$ est appelée facette.

Deux lemmes.

Lemme L8 (facettes). Soit $P$ de dimension $k\ge 1$ et $E_P$ comme en L6. Soit $J\subset I\setminus S_P$ minimal (pour l'inclusion) tel que $P=E_P\cap \{x:{\ell }_j(x)\le a_j,j\in J\}$ (il en existe : $J=I\setminus S_P$ convient, et $I$ est fini). Alors (i) pour tout $j\in J$, $F_{\{j\}}$ est une facette ; (ii) $P\setminus P^{\circ }\subset {\bigcup }_{j\in J}{F}_{\{j\}}$.

(i) $J\ne \varnothing$, sinon $P=E_P$ serait un sous-espace affine de dimension $k\ge 1$ (L6(c)), non borné. Soit $j\in J$. Par minimalité, il existe $y\in E_P$ avec ${\ell }_m(y)\le a_m$ pour $m\in J\setminus \{j\}$ et ${\ell }_j(y)>a_j$. Soit $x\in P^{\circ }$ (L6(a)) : ${\ell }_j(x)<a_j$. Pour $t^{\ast }=\frac{a_j-{\ell }_j(x)}{{\ell }_j(y)-{\ell }_j(x)}\in ]0,1[$, le point $z=x+t^{\ast }(y-x)\in E_P$ vérifie ${\ell }_j(z)=a_j$ et, pour $m\in J\setminus \{j\}$, ${\ell }_m(z)=(1-t^{\ast }){\ell }_m(x)+t^{\ast }{\ell }_m(y)<a_m$. Le sous-espace affine $H_j=E_P\cap \{{\ell }_j=a_j\}$ est de dimension $k-1$ (${\ell }_j$ n'est pas constante sur $E_P$ puisque ${\ell }_j(x)\ne {\ell }_j(y)$), et les points de $H_j$ assez proches de $z$ vérifient encore les inégalités strictes, donc sont dans $P$, donc dans $F_{\{j\}}$. Ainsi ${\overrightarrow{F}}_{\{j\}}\supset {\overrightarrow{H}}_j$ et $\dim F_{\{j\}}\ge k-1$ ; comme $F_{\{j\}}\ne P$ ($x\notin F_{\{j\}}$), Q12 donne $\dim F_{\{j\}}=k-1$.

(ii) Soit $x\in P$ tel que ${\ell }_j(x)<a_j$ pour tout $j\in J$. Alors un voisinage de $x$ dans $E_P$ est contenu dans $P$. Si $i\notin S_P$ vérifiait ${\ell }_i(x)=a_i$, ${\ell }_i$ ne serait pas constante sur $E_P$ (elle ne l'est pas sur $P\subset E_P$), et en déplaçant $x$ dans $E_P$ dans une direction où ${\ell }_i$ augmente, on resterait dans $P$ en violant ${\ell }_i\le a_i$ : absurde. Donc $J(x)=S_P$ et $x\in P^{\circ }$. Par contraposée, tout point de $P\setminus P^{\circ }$ sature un $j\in J$.

Lemme L9 (rayons issus d'un point de l'intérieur relatif). Soient $x\in P^{\circ }$ et $y\in P\setminus \{x\}$. La demi-droite $\{x+t(y-x),t\ge 0\}$ rencontre $P\setminus P^{\circ }$ en exactement un point $z=x+t_1(y-x)$, avec $t_1\ge 1$ ; les points de paramètre $t\in [0,t_1[$ sont dans $P^{\circ }$, ceux de paramètre $t>t_1$ hors de $P$. En particulier $y=x+s(z-x)$ avec $s=1/t_1\in ]0,1]$.

Par L2, les $t\ge 0$ tels que $x+t(y-x)\in P$ forment un segment $[0,t_1]$, $t_1\ge 1$, et un indice $i$ vérifie ${\ell }_i(z)=a_i$ et ${\ell }_i(y-x)>0$ ; comme $x,y\in P$, ${\ell }_i$ n'est pas constante sur $P$, donc $i\notin S_P$ et $z\notin P^{\circ }$. Pour $0\le t<t_1$, le point est $(1-\frac{t}{t_1})x+\frac{t}{t_1}z$ avec un poids $>0$ sur $x$ : les contraintes $i\notin S_P$ y sont strictes (car ${\ell }_i(x)<a_i$, ${\ell }_i(z)\le a_i$) et celles de $S_P$ saturées, donc il est dans $P^{\circ }$.

Q25. Soit ${\mathcal{C}}_P$ l'ensemble des facettes de $P$. Il est fini (Q13), non vide (L8(i)), formé de polytopes (Q12). Pour $F,G\in {\mathcal{C}}_P$, si $F\cap G\ne \varnothing$, alors $F\cap G=F_{S_F}\cap F_{S_G}=F_{S_F\cup S_G}$ est une face de $P$, contenue dans $F$ et dans $G$ ; par L3, c'est une face de $F$ et une face de $G$. Donc ${\mathcal{C}}_P$ est un complexe. (Le même argument montre que tout ensemble fini non vide de faces de $P$ est un complexe.)