Cote n° 87 · batch 1 · pages 1–20 · Transcription · Polyèdres convexes : notes manuscrites (s.d.)
Datation de l’inventaire : s.d. — le groupe « Géométrie et topologie combinatoire » (69 à 102) est daté 1976-[vers 1986]
Édition de démonstration

TEI P5 source — open the XML · download batch-01.fr.xml

Géométrie des convexes

2

le titre est de sa main, souligné, en tête de la page 2. Ses rubriques ouvertes par un astérisque sont rendues ici en liste sur cette page, puis en sous-sections à partir de la page 3

3

Facettes d'un convexe

\(R(x,y)\) : (\(x = y\) ou \(x\) et \(y\) sont intérieurs à \(D_{x,y} \cap C\)) est une relation d'équivalence. Une partie \(F\) de \(C\) est dite une facette si \(\forall x \in F\), on a \(F = \{ y \in C \mid R(x,y) \}\) — on exclut donc les \(F \neq \emptyset\) facettes — \(F\) est une classe suivant \(R\). Notations \(E_C\), \(E_F\)sous-espaces affines engendrés ; l'indice du premier \(E\) est un \(C\) appuyé. L'ensemble des facettes est noté par une abréviation lue \(\mathrm{Fac}(C)\) dans tout le lot.

Point extrémal \(x\) : facette réduite à \(\{x\}\) est facette \(\Leftrightarrow\) \(\forall D\) droite passant par \(x\), \(x\) n'est pas intérieur à \(D \cap C\) dans \(D\).

(1) Supposons \(C\) de dim finie \(d\). \(\exists !\) facette de dim \(d\), c'est \(\operatorname{int}_{E_C}(C)\).

(2) Soit \(F \in \mathrm{Fac}(C)\). Alors \(E_F \cap C\) est une réunion de facettes de \(C\), et […] les facettes de \(C\) contenues dans \(E_F \cap C\) sont les facettes de \(E_F \cap C\). Si \(E\) de dim finie, on a \(E_F \cap C = \overline{F} \cap C\) (\(= \overline{F}\) si \(C\) fermé), et \(F = \operatorname{int}_{E_F}(E_F \cap C)\), Pour deux

(3) Pour deux facettes \(F\), \(F'\), conditions équivalentes : \[\begin{array}{ll} E_{F'} \subset E_F & \\ E_{F'} \cap C \subset E_F \cap C & (\text{ou } E_{F'} \cap C \subset E_F) \\ F' \subset E_F \cap C & (\text{ou } F' \subset E_F) \\ F' \subset \overline{F} \cap C & (\text{ou } F' \subset \overline{F}) \\ \overline{F'} \subset \overline{F} & \end{array}\] une accolade réunit les deux dernières lignes, avec « si \(E\) de dim finie »

C'est là une relation d'ordre dans l'ens. \(\mathrm{Fac}(C)\) des facettes de \(C\). Si \(x, y \in C\), […] \[F_x \prec F_y \Leftrightarrow \bigl[ x = y \text{ ou } x \neq y \text{ et } y \in \operatorname{Int}_{D_{xy}} (D_{xy} \cap C) \bigr]\] un mot est noirci devant \(F_x\)

4

(4) Soient \((x_i)_{i \in I}\) une famille finie de pts de \(C\), \((\lambda_i)_{i \in I}\) avec \(\lambda_i > 0\), \(\sum \lambda_i = 1\), donc \(x = \sum \lambda_i x_i \in C\). Ceci dit, on a \[F_x = \sup F_{x_i}.\] (Par suite, dans \(\mathrm{Fac}(C)\) les sup finis existent — donc les sup quelconques aussi pourvu que \(\dim C < +\infty\)).

(5) Soit \(C' \subset C\) une partie de \(C\) réunion de facettes, et soit \(\Phi \subset \mathrm{Fac}(C)\) défini par \[\Phi = \{ F \in \mathrm{Fac}(C) \mid F \subset C' \}\] Pour que \(C'\) soit convexe, il faut et suffit que \(\Phi\) soit stable par sup finis ; pour que \(C'\) soit convexe et fermé relat. dans \(C\) (car dim \(E < \infty\)) il faut et suffit que \(\Phi\) soit stable par sup finis et qu'avec une facette il contienne celles qui sont majorées. (5) (Dim finie), (6) Pour que \(C'\) soit de la forme \(\overline{F} \cap C\) (\(F \in \mathrm{Fac}(C)\)) il faut et suffit que \(\Phi\) soit fermé, convexe et soit […] réunion de facettes. L'ens. des facettes relat. fermées de \(C\) […] est stable par intersections quelconques (donc il y a des inf quelconques dans l'ens. des facettes de \(C\)).

5

(7) Supposons \(C\) de dim finie compact. Alors \(C\) est l'enveloppe convexe de l'ens. de ses pts extrémaux.

(8) Supposons \(C\) partie polyédrale dans \(E\) de dim finie (i.e. \(C\) réunion finie de simplexes \(\Leftrightarrow\) réunion finie d'enveloppes convexes de parties finies de \(E\)). Alors l'ens. des facettes de \(C\) est fini.

Cor. Polyèdres convexes : parties convexes compactes telles que \(\mathrm{Fac}(C)\) (ou \(\mathrm{Fac}_0(C)\), ens. des pts extrémaux) soit fini. Polaires

Polaires

\(E\), \(E'\) espaces vectoriels duals l'un de l'autre. Pour partie \(A\) de \(E\), on pose \[A^\circ = \{ x' \in E' \mid \langle x, x' \rangle \geq -1 \ \forall x \in A \} = \bigcap_{x \in A} H(x) \qquad (\text{où } H(x) = \{ x' \in E' \mid \langle x, x' \rangle \geq -1 \})\] De même on définit \(A'^\circ \subset E\) pour \(A' \subset E'\).

Th. 1 Pour \(A \subset E\), … \(A^{\circ\circ}\) = env. conv. fermée de \(A \cup \{0\}\).

Corollaire \(A \mapsto A^\circ\) et \(A' \mapsto A'^\circ\) sont des appl. bijectives inv. l'une de l'autre entre l'ens. des parties convexes fermées de \(E\) contenant \(0\), et l'ens. analogue

6

pour \(E'\). En De plus, pour de telles parties \[A_1 \subset A_2 \Longleftrightarrow A_2^\circ \subset A_1^\circ\] (i.e. la bijection précédente renverse l'ordre)

Cor \[\overline{\mathrm{Env}}(A_1, A_2) = A_1^\circ \cap A_2^\circ\] \[(A_1 \cap A_2)^\circ = \overline{\mathrm{Env}}(A_1, A_2)\] ainsi sur la page : aucun signe de polaire sur le membre de gauche de la première formule ni sur les arguments du second membre de la seconde

Cor \(A\) \(0 \in \operatorname{int}(A) \Longleftrightarrow A^\circ\) compact

\(A\) cpct \(\Longleftrightarrow 0 \in\) […] \(\operatorname{int}(A^\circ)\)

Le théorème est conséquence du théo. […] est équivalent :) la ligne est marquée à gauche d'un grand crochet

Théorème 1' Soit \(C\) une partie de \(E\). Pour que \(C\) soit convexe et fermé, il faut et suffit que \(C\) soit intersection de demi-espaces fermés.

Résulte du

Théorème 1'' (Hahn-Banach) Soit \(U\) une partie convexe ouverte de l'espace vectoriel réel \(E\) de dim finie, \(F \subsetneq E\) un sous-espace vectoriel de \(E\) tel que \(F \cap U = \emptyset\), alors \(\exists\) hyperplan \(H\) de \(E\) contenant \(F\), tel que \(H \cap U = \emptyset\).

7

Résultats Dém. […] : remplaçant \(U\) par \(\bigcup_{\lambda > 0} \lambda U\), OPS \(U\) un cône (i.e. stable par multiplication par \(\lambda > 0\)) Il suffit de prouver que si \(F\) n'est pas un hyperplan, \(\exists F' \supset F\), \(F\) de codim 1 dans \(F'\) i.e. \(\dim F' = \dim F + 1\). OPS \(\dim E = \dim F + 2\). […] : passant au quotient par \(F\), on se ramène au cas \(\dim E = 2\), \(F = 0\). OPS \(U \neq \emptyset\).le même mot, non lu, ouvre les deux phrases

On montre alors que ou bien \(U\) est un demi-espace ouvert, ou bien \(\exists\) base \(e_1, e_2\) telle que \[U = \{ \lambda_1 e_1 + \lambda_2 e_2 \mid \lambda_1, \lambda_2 > 0 \}\] dans la marge gauche, deux axes perpendiculaires issus d'un point

Dans les deux cas on gagne …

Secteurs polyédraux

Prop. Soit \(C\) partie de \(E\) (espace affine de dim finie) Conditions équivalentes :

8

Dém. Si \(C = \emptyset\) les deux conditions sont satisfaites. Donc OPS \(C \neq \emptyset\). Soit \(x \in C\), on le prend comme origine OPS \(C\) convexe fermé, et OPS \(C = C^{\circ\circ}\), […] \(C' = C^\circ\) […] \(C\) engendre \(E\) (car on voit que les deux conditions sur \(C\) ne changent pas si on remplace \(E\) par \(E_C\)). Soit \(x \in \mathring{C}\), on le prend comme origine, on aura \[C = C'^\circ, \quad C' = C^\circ.\] D'où \(C'\) est compact.

[…]suit un long passage, encadré et barré de traits obliques, qui commence par « a) \(\Rightarrow\) b) » et où se lisent « convexe fermée d'un ens. fini de pts et de demi-droites fermées », « b) \(\Rightarrow\) a) », « enveloppe convexe », « d'un ens. fini de pts », « intersection d'un ens. fini de demi-espaces fermés » et « on gagne par polarité » ; il est remplacé par ce qui suit et par la page 9

b) \(\Rightarrow\) a) Si b) est vrai pour \(C\), alors par polarité \(C'\) est int. finie de \(\frac{1}{2}\)-espaces fermés, donc (lemme ci-dessous) étant compact, c'est un polyèdre convexe, i.e. env. conv. finie de d'un ens. fini de \(E'\), d'où a) par polarité.

9

a) \(\Rightarrow\) b) On sait (par polarité) que \(C'\) est […] env. conv. fermée d'un ens. fini de pts, donc d'après ce qui précède, […] il est intersection finie de demi-espaces fermés[…] donc par polarité on trouve b) pour \(E\), sous forme précisée. dans la marge gauche, un croquis : une bande entre deux droites parallèles, un point marqué sur l'une, et une ligne brisée en zigzag entre les deux

Lemme Soit \(C\) compact intersection finie de demi-espaces fermés. Alors \(C\) est un polyèdre convexe l'ens. des pts extrémaux de \(C\) est fini (donc \(C\) est un polyèdre convexe s'il est compact). En d'autres termes, \(C\) […] est […] fini de pts extrémaux.

Récurrence sur \(\dim E\) (trivial si \(\dim E = 0\)) puis sur le […] nb de demi-espaces qui entrent. Trivial si \(\nu = 0, 1\) ([…] \(n = 1\)) Supposonsle \(\nu\) renvoie à une ligne barrée, « sur \(\nu = n + \dim E\) » On est ramené au cas d'un convexe \(C_1\) n'ayant qu'un nb fini de pts extrémaux, et où on a \[C = C_1 \cap H \qquad (H \text{ demi-espace fermé, limité par l'hyperplan } H_0)\] Soit \(x \in C\) un pt extrémal. Si \(x \notin H_0\), alors \(x\) est pt extrémal de \(C\) ssi il est pt extrémal de \(C_1\). Si \(x \in H_0\), alors \(x\) est pt extrémal de \(C\), ssi il est pt extrémal de \(C_1\) […] \(H_0 \cap C\). On gagne.

10

Définition Secteur polyédral : partie satisfaisant aux conditions équivalentes précédentes.

Prop. \(E\), \(E'\) vectoriels de dim finie en dualité. Alors par \(A \mapsto A^\circ\), \(A' \mapsto A'^\circ\) on trouve des correspondances 1-1 inverses l'une de l'autre entre secteurs polyédraux de \(E\) contenant l'origine, et sect. pol. de \(E'\) contenant l'origine.

Polarité et facettes

\(E\), \(E'\) vectoriels de dim finie en dualité. Correspondance biunivoque entre sous-espaces affines \(F\) de \(E\) ne contenant pas l'origine, et sous-espaces affines \(F'\) de \(E'\) ne contenant pas l'origine, avec \[\dim F + \dim F^{0} = n - 1 \qquad (n = \dim E = \dim E')\] Notations \(F^{0}\),l'exposant de \(F^{0}\) est un petit rond ouvert, tracé autrement que le \(^\circ\) des polaires ; il est rendu \(^{0}\) ici et page 11

Correspondance caractérisée par les propriétés :

11

Terminologie Variété d'appui d'un convexe \(C\) = variété affine de la forme \(E_F\). Les variétés d'appui sont en corr. 1-1 avec les facettes, relation d'ordre et relation d'incidence

Th Soit \(C\), \(C'\) deux secteurs polyédraux polaires l'un de l'autre de \(E\), \(E'\) resp.t Alors il existe une unique […] application \(\varphi\) de l'ens. des facettes \(F\) de \(C\) telles que \(0 \notin \overline{F}\) (i.e. \(0 \in E_F\)) dans l'ens. des facettes \(F'\) de \(C'\) telles que \(0 \notin \overline{F'}\) (i.e. \(0' \in E_{F'}\)), caractérisée par la propriété que si \(F' = \varphi(F)\) \[E_{\varphi(F) = F'} = (E_F)^{0}\] les deux « i.e. » portent \(\in\) et non \(\notin\) sur la page. Devant la formule, un mot et un \(E\) sont barrés

Cette application est bijective, et renverse la relation d'ordre entre facettes

Cor. 1 L'ens. des facettes d'un secteur polyédral est fini (prendre l'origine intérieure au secteur polyédral, et appliquer dualité)

Cor. 2 Supposons \(C\), \(C'\) cpts […] i.e. \(E\) \(0_E\), \(0_{E'}\) intérieurs à \(C\), \(C'\) resp.t, i.e. \(C\), \(C'\) des polyèdres. Alors \(\varphi : \mathrm{Fac}(C) \simeq \mathrm{Fac}(C')\)

12

(antiisomorphisme d'ens. ordonnés).

Corollaire 3 Soit \(\Phi\) un polyèdre combinatoire strict. Alors

la notion de polyèdre combinatoire strict n'est pas définie sur ces feuillets

Dém. a) Résulte de Cor. 2. On sait que \(\Phi_{0,x}\) est un polyèdre combinatoire strict, (\(0\) plus petit élt) donc par dualité aussi \(\Phi_{x,1}\) (\(1\) plus grand él.) \(= (\Phi^\circ_{0,x})^\circ\). Appliquant ce dernier résultat à \(x \in \Phi_{0,y}\), on trouve que \(\Phi_{xy}\) est un polyèdre combinatoire strict.

Cor. 4 Soient \(x, y\) deux facettes

Cor. 4 Soit \(F\) une facette d'un p. \(C\) un polyèdre convexe, \(F\) une facette dudit, \(i \in \mathbf{Z}\) tel que \(-1 \leq i \leq d = \dim F\). Alors \(\exists\) facette de \(F'\) incidente à \(F\) telle que \(\dim F' =\)

13

Si \(d = -1\) ou \(d = 0\), c'est évident. Supposons \(d \geq 1\), i.e. \(F \neq \emptyset\), on sait que \(\overline{F}\) est l'enveloppe convexe de l'ens. de ses pts extrémaux, donc \(\exists F' \in \mathrm{Fac}(C)\) avec \(\dim F' = 0\), et \(F' \leq F\), […] \(F' < F\).ce passage et le corollaire barré de la page 12 sont encadrés et barrés de traits obliques ; l'énoncé revient page 14 comme Cor. 6

Application à la fonction dimension

Cor. 4 Soient \(C\) un polyèdre convexe, \(F_1, F_2 \in \mathrm{Fac}(C)\) avec \(F_1 < F_2\). Pour que \(F_2\) soit un successeur de \(F_1\) (i.e. qu'il n'existe pas \(F\) tel que \(F_1 < F < F_2\)) il faut et suffit qu'on ait \[\dim F_2 = \dim F_1 + 1\]

Comme \(\dim F\) est fonction strictement croissante sur \(\mathrm{Fac}(C)\), la suffisance est claire. Pour la nécessité, […] dans […] \(\dim F\) […] OPS (dualité) \(F_2 =\) \(\mathring{C}\) \(1\) (plus grande facette), et \(F_2\) puis en passant aux polaires (échangeant les rôles de \(F_1\) et \(F_2\)) que \(F_1 =\) \(\emptyset\) \(0\) (plus petite facette), et : à nouveau \(F_2 = 1\). Donc l'assertion devient maintenant : Pour qu'il n'existe aucune facette distincte de \(\mathring{C}\) et de la facette vide, il faut et suffit que \(\dim C \uncertain{=} 0\) ou \(-1\) i.e. que \(C\) vide réduit à un pt. […] (trivial, en effet, on prend pts extrémaux !)

Cor. 5 La fonction \(d : F \mapsto \dim F\) sur \(\mathrm{Fac}(C)\) (du cor. 4) est caractérisée par les conditions :

14

Cor. 6 Soit \(F \in \mathrm{Fac}(C)\) (\(C\) polyèdre convexe) Alors pour tout \(-1 \leq i \leq d = \dim F\), existe \(F' \leq F\) telle que \(\dim F' = i\).

Clair si \(d = -1\) ou \(0\), sinon […] Récurrence sur \(d\), clair si \(d = -1, 0\). Si \(d > 0\), \(\exists F'\) tel que \(F' \neq \emptyset, F\), \(\emptyset < F' < F\) (cor. 4) Donc \(\dim F' = d' < d\). Si \(i \leq d'\) on gagne par hyp. de récurrence appliquée à \(F'\) […] sinon on gagne par l'hyp. de récurrencebloc encadré et barré de traits obliques

Formel à partir du cor. 5, qui implique que si \(x \leq y\), \(x, y \in \mathrm{Fac}(C)\), alors \(\exists\) chaîne \(x_0 = x < x_1 < \cdots < x_n = y\), avec \(x_{i+1}\) succ. de \(x_i\) (\(0 \leq i \leq n-1\)), et qu'alors \(d(y) - d(x) = n\) […] \(d(x_i) - d(x_0) = i\) i.e. \(d(x_i) = d(x_0) + i\). [On prend \(y = F\), \(x = \emptyset\) …]

Cor. 7 Soit \(\Phi\) un polyèdre combinatoire strict, \(d\) une fonction dimension sur \(\Phi\) (cf cor. 5) Soient \(x, y \in \Phi\), \(x < y\), \(d(y) = d(x) + 2\). Alors l'ens. des \(z \in \Phi\) tels que \(x < z < y\) est de cardinal 2.

\(\Phi_{xy}\) est un polyèdre combinatoire strict de dim \((-1) + 2 = 1\), donc provient d'un polyèdre convexe de dim 1, i.e. d'un segment. Celui-ci a exactement 2 extrémités !

Cubes

« Cubes », à l'encre, est le seul mot de sa main sur la couverture de papier brun qu'est la page 15 ; elle porte aussi, au crayon et entourée, la mention « (13 p.) »

17

Caractérisation intrinsèque d'un \(n\)-cube, déterminée par un ens. \[\Phi \subset \mathrm{Espaff}(E)\] la notation est lue « \(\mathrm{Espaff}\) » avec doute de sous-espaces affines d'un espace affine sur \(k\) :

la fin de la page, écrite serrée et en partie en surcharge, n'est lue que par fragments

18

\(\operatorname{Inf}\) d'une partie de \(\Phi\) (dans \(\Phi\)) est \(\emptyset\), i.e. si son intersection ne contient pas d'él. de \(\Phi \setminus \{\emptyset\}\), que cette intersection soit vide. Ex : un quadrilatère qui n'est pas un parallélogrammesuit un petit croquis d'un quadrilatère dont deux côtés se coupent hors de lui. L'axiome qui suit assure qu'il en est pourtant ainsi …]

Dans l'espace des translations \(T\) de \(V\), les […] espaces directeurs \(\mathbb{H}_i\) (\(i \in I\)) des […] 2 sous-espaces […] hyperplans […] \(b \in B\) sont lin. indép., et correspondent donc à une décomposition \[T \simeq \prod T_i \qquad (T_i = T/\mathbb{H}_i)\] de \(T\) en produit de droites. La donnée du \(T\)-torseur \(E\) revient à la donnée d'une famille \((E_i)_{i \in I}\) de \(T_i\)-torseurs, \(E_i \simeq E/\mathbb{H}_i\). De plus, dans chaque \(E_i\) il y a une partie de deux pts distincts, […] \(B_i\), (isom. à la fibre de \(B/I\) en \(i \in I\)). Or on vérifie que la donnée d'une (pour \(i\)la lettre rendue \(\mathbb{H}\) est un \(H\) barré de traits verticaux

19

fixé) d'un \(T_i\), \(E_i\), \(B_i \subset E_i\) équivaut en fait à la donnée de \(B_i\) (comme torseur sous \(\pm 1\) !) en prenant \[T_i = \operatorname{Ker}(k^{B_i} \xrightarrow{\varepsilon} k), \quad E_i = \varepsilon^{-1}(1)\] Donc la donnée des d'une famille \((T_i, E_i, B_i)_{i \in I}\) (\(\operatorname{card} I = n\)) équivaut à la donnée d'une […] de \(n\)-cube. Montrons que cette donnée permet de reconstruire le \(n\)-cube, comme le produit de la famille (indexée par \(I\)) de 1-cubes …

On a aussi \[T = \operatorname{Ker}(k^B \xrightarrow{\mathrm{tr}} k^I), \qquad E = \mathrm{tr}^{-1}(1)\] « trace » est écrit au-dessus de la flèche, relié à « tr »

Si \(J \subset I\), on considère