LE MONDE EST-IL DISCRET ?

Discret est ici le contraire de continu. C’est à peu près tout
ce qu’on peut dire du terme lui-même. Avouons-le, ce mot ne
correspond à aucune notion mathématique précise. Les nombres réels
forment un ensemble « continu ». Les entiers, bien qu’infinis, sont
discrets, c’est à dire « loin » les uns des autres.

Et le monde, est-il discret ? Oui ! Depuis que l’on sait que la
matière est faite d’un nombre fini d’atomes (discrets)... Et
les mouvements continus peuvent être remplacés par de très petits
mouvements discrets...

N’est-il pas étonnant, quand on est écolier, que même l’eau soit
constituée d’un nombre fini d’atomes ? Et pourtant, la plupart des
théories mathématiques classiques traitent seulement « le continu »,
et sont souvent vues comme les sciences de l’infini. Les
mathématiques discrètes veulent traiter de ce qui est discret (fini ?), mais trop complexe pour être traité « à la main », sans outils
mathématiques.

On peut arriver au discret par l’approximation du continu d’une
part. Mais la science moderne, et en particulier l’industrie
automatisée, l’informatique, l’économie etc., produisent des
problèmes qui sont dès le départ « discrets ».

Les problèmes à caractère discret peuvent souvent se modéliser d’une
manière naturelle en terme de graphes. Mathématiques discrètes,
théorie des graphes, ou combinatoire sont des synonymes pour
certains, couvrent des notions différentes d’après d’autres, mais la
partie commune de ces domaines est certainement très grande :
peut-on rédiger un problème combinatoire qui ne peut pas être
reformulé en termes de graphes ? Il est vrai aussi qu’il existe des
méthodes plus « graphiques » que d’autres.

Rappelons tout d’abord qu’un graphe est une paire d’ensembles
$G=(V,E)$ où $V$ est un ensemble quelconque, et $E$ est un
sous-ensemble des paires d’éléments de $V$. Les éléments de $V$
s’appellent les sommets du graphe et les éléments de $E$
s’appellent arêtes. On dira aussi que $\{u,v\}\in E$ est une
arête entre $u$ et $v$ : on peut représenter les sommets d’un
graphe par des points et ses arêtes par des lignes qui les relient.
Deux sommets $u,v\in V$ sont voisins si $\{u,v\}\in E$.

Voyons maintenant, à titre d’exemple, un des problèmes les plus
classiques : le couplage. Il s’agit de marier (coupler) un nombre
maximum de filles et de garçons en respectant leurs sympathies
mutuelles, données à l’avance sous forme d’un graphe. Quelles
peuvent être les raisons pour lesquelles on ne peut pas marier plus
de $184$ filles lorsqu’il y en a $276$ en tout ? Autrement dit,
pourquoi peut-on être obligé de renoncer au mariage de $92$ filles ?
Une des raisons possibles : un sous-ensemble de filles rassemblant
par exemple $231$ d’entre elles, ne sympatisent en tout qu’avec
$139$ garçons. Déjà dans un tel sous-ensemble de filles, il y en
aura au moins $92$ qui ne seront pas mariées !

Appelons déficit d’un ensemble de filles la différence entre
le nombre de ses éléments et le nombre de ses sympatisants (92 dans
l’exemple) ; si ce nombre est négatif, le déficit est défini comme
étant $0$. Le déficit pourrait être considéré comme une mesure de
« difficulté » d’une communauté de filles à se marier.

A priori, on pourrait imaginer qu’il y a d’autres raisons que le
déficit pour empêcher le mariage des filles. La clef de ce problème
est l’un des premiers résultats de la théorie des graphes, et son
message est qu’il n’y a pas d’autre raison !

Grâce à ce théorème, on peut facilement certifier à quelqu’un qu’un
couplage est le plus grand possible : on lui montre un sous-ensemble
de filles dont le déficit est égal au nombre de filles non mariées.

D’après Edmonds, l’existence d’un certificat d’optimalité est un bon
indice pour que l’optimalité puisse être décidée d’une manière
efficace. Malgré ce pari — dont la formulation précise est
« $NP\cap coNP=P ?$ », similaire à la célèbre question « $P=NP ?$ » —, certains résultats laissent à penser que trouver
pourrait être plus difficile que certifier. Par exemple, écrire un
entier positif donné comme produit de deux entiers supérieurs à $1$
pourrait s’avérer plus difficile que certifier l’existence d’une
telle décomposition. En ce qui concerne les couplages max, on peut
décider s’ils existent ou non, et on peut même les trouver. Ce
théorème et l’algorithme efficace qui le montre (la « méthode
hongroise, en train de fêter son 50ème anniversaire [1] s’exécute en
temps « polynomial », voir [LL], [AS]) fournissent à la fois le couplage
optimal et un ensemble de filles de déficit maximum.

Le problème des mariages, ou couplages, est l’un des problèmes de
base de la théorie des graphes, dont les variantes, spécialisations
ou généralisations apparaissent partout en recherche opérationnelle
et dans de nombreuses autres disciplines. Voici par exemple comment
les couplages apparaissent dans un problème « d’ordonnancement de
tâches » classique :

Etant données $n$ tâches devant être exécutées sur deux machines
identiques, déterminer le temps d’exécution minimum, si

• l’exécution de chaque tâche demande une minute ;

• des « contraintes de précédence » sont données entre les
  tâches.

Est-ce que des chemins de précédence entre deux tâches forment le
seul obstacle, c’est-à-dire la seule raison de ne pas pouvoir
exécuter les tâches en moins de temps ?

On peut essayer de coupler le plus possible de tâches exécutables en
même temps. Autrement dit « marier » les tâches, mais c’est un peu
plus difficile, car on n’a pas une division naturelle en deux
ensembles, « garçons » et « filles ». Le maximum $k$ de paires de
tâches exécutables en même temps peut quand même être déterminé
(algorithme d’Edmonds). Comme on ne peut pas exécuter plus de $2$
tâches en même temps on peut être sûr qu’au moins $n-k$ minutes sont
nécessaires pour exécuter toutes les tâches. Miracle : il est vrai
aussi (montré par Fujii, Kasami, Ninomiya en 1969), que $n-k$
minutes suffisent ! Pour trois machines déjà, ce problème est
ouvert.

Encore quelques exemples — qui mènent d’une manière moins évidente
aux couplages — juste pour montrer comment l’abstraction
mathématique unifie des modèles qui ont l’air d’être très différents
à un plus bas niveau. Les lignes ($4$ lignes droites et une
circulaire) que vous voyez sur la Figure 1 peuvent représenter des
connexions électriques. Le dessin doit être réalisé avec des fils
électriques (en métal) en utilisant les deux côtés d’une plaque
(chaque point sur exactement un des deux côtés). On doit faire
attention à une et une seule chose : deux lignes ne peuvent pas se
toucher, c’est-à-dire que deux fils qui se croisent doivent être sur
des côtés différents de la plaque au point d’intersection.

Figure.1 VLSI, lignes aériennes, etc.

Pour bien arranger correctement les lignes, on peut creuser des
trous dans la plaque, et faire passer les fils d’un côté à l’autre,
mais bien sûr, pas dans les croisements, car ceci causerait des faux
contacts. Il est facile de voir, qu’on peut toujours réaliser un
plan de connexion sans croisements en faisant suffisamment de trous.
Mais les trous ne sont pas gratuits à faire, et rendent le système
plus compliqué $\ldots$ Comment trouver le nombre minimum de
trous ?

Les lignes peuvent aussi représenter des trajectoires d’avion qui
doivent toujours voler à l’un des niveaux possibles parmi deux,
leurs itinéraires ne pouvant pas se croiser (pas même à des temps
différents). On doit alors minimiser le nombre de changements de
niveaux (qui sont coûteux, inconfortables pour les passagers,
dangereux pour la marchandise $\ldots$)

Cette même Figure 1 peut encore être interprétée de multiples
façons. Toute discipline mathématique essaiera de trouver des
modèles généraux qui synthétisent les méthodes et regroupent les
problèmes autour de ces méthodes. Les deux interprétations de la
Figure 1 se rejoignent à un niveau plus général : ce sont des cas
particuliers du problème de coupe maximum (coupe max) dans un graphe
planaire, qui se résout avec des méthodes de la « théorie des
couplages ».

« L’univers discret » est structuré, et les mathématiciens ont bien
avancé dans la hiérarchie et les interrelations des classes de
problèmes. Les résultats théoriques peuvent devenir de bons
conseillers pratiques : ils arrivent souvent à cerner où se situent
de nouveaux problèmes dans cette jungle ; ce faisant ils orientent
les chercheurs vers des méthodes appropriées.

Notre pari est maintenant d’expliquer la solution complète d’un
problème difficile.

LA PLUIE

Que peut-on demander à des enveloppes mouillées ? Peut-on éviter,
sinon avec des parapluies, que l’information qu’elles contiennent ne
soit perdue ?

Il s’agit du problème de Shannon : trouver un code pour transmettre
des messages sans ambiguïté, bien que certaines paires de lettres
puissent être confondues.

Imaginez que vous deviez envoyer un message par l’intermédiaire d’un
médium qui connait seulement les lettres (« $a$ », « $c$ », « $u$ »,
« $v$ », « $w$ »). Quand les enveloppes sont mouillées, chaque lettre
peut être confondue avec son prédécesseur et successeur dans cet
ordre cyclique (le $a$ avec le $c$ et le $w$, le $c$ avec le $a$ et
le $u$, etc.). Que devraient faire les facteurs sous la pluie ?

Juste ouvrir leur parapluie !

Les paires de lettres qu’on peut confondre sont représentées par les
arêtes d’un graphe, qu’on va appeler graphe des
confusions.

Figure.2 Graphe de confusion $C_5$

On supposera qu’on envoie des messages ayant tous la même longueur
$k$ fixée (nombre de caractères). Si par exemple « a » est l’espace,
on peut toujours compléter à $k$ caractères les messages plus
courts. Deux messages peuvent être confondus, si toutes les paires
de lettres qui sont à la même position dans les deux se confondent.
On ne peut pas les confondre, s’il existe deux lettres aux
mêmes positions qui ne peuvent pas être confondues.

Si l’on pouvait confondre toutes les lettres les unes avec les
autres, alors on ne pourrait pas envoyer plus d’un seul message
quelle que soit sa longueur fixée. Ce ne serait même pas la peine de
l’envoyer ! La « capacité de Shannon » vaudra $0$. Quand on aura deux
lettres qu’on ne peut pas confondre elle vaudra $1$.

Dans un alphabet de 32 lettres (comme l’alphabet hongrois) si aucune
paire ne peut jamais être confondue (le graphe des confusions n’a
pas d’arêtes), la « capacité de Shannon » vaudra $5$. Ceci voudra dire
que cet alphabet a la même capacité que les mots binaires de
longueur $5$. Pour coder $n$ messages différents avec des mots
binaires de longueur $k$, il faut avoir $2^k\ge n$, c’est-à-dire
$k\ge\log_2 n$. En général, quand le graphe $G$ des confusions est
donné, la capacité de Shannon va mesurer le nombre de caractères
binaires (bits) équivalents à un de nos caractères ; autrement dit,
c’est la longueur du mot binaire équivalent, divisé par la longueur
de notre mot. La définition formelle :

Dans notre premier exemple (Figure 2) le nombre de messages différents de longueur $1$ parmi lesquels il n’y a pas de confusion est $2$. Comme si on avait
l’alphabet binaire à deux lettres, $0$ et $1$, sans confusion. Un
« bit utile » par lettre. Mais on peut faire mieux avec des mots de
deux lettres : en les représentant par un tableau $5\times 5$ (Figure 3) on peut
confondre deux mots si et seulement si leur représentation sur cet
échiquier torique $5\times 5$ est voisine par un côté ou par une
diagonale. (La première et la dernière lignes sont voisines, idem
pour les colonnes.)

Figure.3 Cinq mots de deux lettres qu’on ne peut pas confondre.

Peut-on faire encore mieux (en moyenne) en augmentant la longueur
des mots ? C’était la question posée par Shannon dans un article de
1956. Il a fallu attendre vingt deux ans, jusqu’en 1978 pour une
réponse. (Par Lovász, [RR]). La question a beaucoup contribué au
développement d’une portion très riche de la théorie des graphes.

LE PARAPLUIE

En d’autre termes, les deux lettres — par exemple $a$ et $v$ —
qu’on ne peut pas confondre nous donnent $2^k$ mots de longueur $k$
sans aucun risque de confusion, ce qui nous offre seulement $1$ bit
utile par lettre. D’après la Figure 3 on a mieux : $5^k$ mots de
longueur $2k$ (à la place de $4^k$). En effet, pour $k=1$ on a $5$
mots (de longueur $2k$), et avec $k$ répétitions on aura $5^k$ mots
de longueur $2k$, ce qui équivaut à un message binaire de longueur
$k\log_2 5$. En moyenne une de nos lettres équivaudra donc à $1/2 \log_2 5 > 1$ lettres binaires (bits) ! Si on démontre qu’on ne
peut pas faire mieux on aura :

La méthode utilisée par Lovász a été à l’origine de méthodes
fondamentales en optimisation combinatoire, et a eu des
rebondissements récents. C’était la première application importante
de la « programmation semidéfinie » en combinatoire :

La représentation orthonormale des sommets d’un graphe $G$,
est une affectation de vecteurs unité de dimension $d$ ($d$
arbitraire) aux sommets, de façon à ce que pour
toute paire de sommets non-adjacents de $G$, les vecteurs
correspondants aux deux sommets soient perpendiculaires (produit
scalaire égal à $0$). On dit d’un sous-ensemble $S\subseteq V(G)$
des sommets d’un graphe qu’il est stable, si aucune paire
d’éléments de $S$ n’est une arête ; $\alpha (G)$ est la cardinalité
d’un stable maximum de $G$.

En effet, les vecteurs associés aux sommets de $S$ sont
orthonormaux, donc on peut les compléter en une base orthonormale.
Dans cette base orthonormale, la somme des carrés des $i$-ièmes
coordonnées des vecteurs pour tout $i=1,\ldots, d$
est égal à $1$ (la transposée d’une
matrice orthonormale est aussi orthonormale). Si on restreint la
somme à $S$ on a l’inégalité voulue.

La Figure 4 montre la représentation $3$-dimensionnelle de $C_5$ qui
s’avérera optimale pour le Lemme.

Figure 4. Le parapluie magique de Lovász

Le parapluie du dessin est ouvert de façon à ce que les paires de
baleines non-voisines soient perpendiculaires. Le lecteur se
convaincra facilement que ceci est possible. On choisit la longueur
des cinq arêtes égale à $1$ chacun. Il est clair, que les 5 vecteurs
oc, ou, ov, ow, oa fournissent une représentation orthonormale de
$C_5$.

En substituant le résultat de l’encadré dans le lemme, on obtient
que la somme sur un stable quelconque de $C_5$ de la fonction
constante $1/\sqrt{5}$ est inférieure ou égale à $1$, et par
conséquent, $\alpha(C_5) \le \sqrt{5}.$

Pourquoi avoir travaillé tant pour aussi peu ? On sait très bien,
que dans cette inégalité là, on pourrait remplacer $\sqrt{5}$ par
$2$ ! Parce ce que cette borne, même si inexacte pour $2$, s’étendra
facilement à des messages arbitrairement longs, et il se
trouve qu’elle donnera la meilleure borne supérieure pour la
moyenne du nombre de bits !

Calcul pour le parapluie

Calculons la représentation orthonormale de $C_5$ (Figure 4), pour
la substituer dans le Lemme, afin d’obtenir la borne supérieure de
la capacité de Shannon d’une manière élémentaire.

On fait ce calcul de lycée (il y a plus court, mais y a-t-il plus
élémentaire) pour aller au bout de l’expérience : un calcul élémentaire avec un
petit peu d’algèbre linéaire et de réflexion combinatoire peuvent
collaborer d’une manière originale dans la solution d’un problème
difficile ! Faites vérifier les calculs par vos enfants lycéens !

On effectue d’abord des calculs sur le pentagone régulier dont le
côté est de longueur $1$.

Le losange en gras de la Figure 5 a. nous permet de trouver la
longueur de la diagonale qui vaut $1+x$ où $x$ vérifie l’équation en
dessous de la figure, d’où $x=\frac{-1+ \sqrt{5}}{2}$ ; la longueur
de la diagonale est donc $\frac{1+ \sqrt{5}}{2}$, et on va noter la
longueur de la demi-diagonale par $d=\frac{1+ \sqrt{5}}{4}$. La
Figure 5b.) montre que le rayon $r$ peut aussi être calculé en
appliquant à nouveau le théorème de Pythagore :
$$m=\sqrt{1-d^2}=1/4\sqrt{10-2\sqrt{5}}$.
Donc
\[r=1/(2m)=\frac{2}{\sqrt{10-2\sqrt{5}}}=\frac{\sqrt{2}}{\sqrt{\sqrt{5}}\sqrt{\sqrt{5}-1} }.\]

Et maintenant passons au parapluie dont les baleines sont de
longueur $1$, et qui est ouvert de façon à ce que chaque paire
de baleines non-voisines forment un angle droit. Ces deux baleines
forment alors un triangle rectangle isocèle dont les deux côtés
perpendiculaires sont de longueur $1$. La longueur de la diagonale
du pentagone régulier formé par les extrémités des arêtes à
l’ouverture appropriée du parapluie est donc de $\sqrt{2}$ au lieu
de $2d$ et le rayon du cercle circonscrit de ce pentagone régulier
est de $\sqrt{2}/(2d)$ fois la valeur
$\frac{\sqrt{2}}{\sqrt{\sqrt{5}}\sqrt{\sqrt{5}-1} }$ du rayon
calculé pour le pentagone régulier de la Figure 5 a.) :
$\frac{\sqrt{\sqrt{5}-1}}{\sqrt{\sqrt{5}}}$.

On obtient donc, par une application de plus du théorème de
Pythagore, que la projection orthogonale des baleines du parapluie
sur le manche est de longueur $1/\sqrt{\sqrt{5}}$. Si on choisit
alors cet axe comme « axe $x$ », la première coordonnée de toutes les
arêtes est $1/\sqrt{\sqrt{5}}$.

Figure 5. Calculs sur $C_5$

Définissons le graphe $G^k$ dont les sommets sont les mots de
longueur $k$ construits à partir des sommets du graphe des
confusions $G$, et avec une arête entre deux mots si on peut les
confondre. Les stables de ce graphe sont donc les ensembles de
$k$-tuples qui ne peuvent pas être confondus. On va utiliser le
lemme pour démontrer que
\[\begin{equation}\alpha(C_5^{2k})\le 5^{k} \label{equation_1}\end{equation}\]
et ceci finit évidemment la preuve du théorème.
On va définir une représentation orthonormale de $C_5^k$ pour tout
$k$. On en a déjà une pour $C_5$, et pour passer de $C_5^{k}$ à
$C_5^{k+1}$, on va appliquer la méthode suivante :

Si on a déjà une représentation de $G^{r}$ et $G^{s}$, on
représentera l’ensemble de leurs concaténations (les mots qu’on
obtient en mettant l’un à côté de l’autre) — exactement $G^{r+s}$ —, par le produit tensoriel des vecteurs associés. Le produit tensoriel $x\otimes y$ de $x\in\mathbb{R}^r$, $y\in\mathbb{R}^s$ n’est rien d’autre qu’une table de multiplication $r\times s$ : une matrice
$r\times s$ dont l’élément $ij$ est $x_iy_j$, et que l’on regarde
comme un vecteur, pour que par exemple le produit scalaire de deux
produits tensoriels soit bien défini (comme la somme des produits
des éléments correspondants).

Alors l’équation élémentaire
[(x\otimes y)^T(w\otimes z)=(x^Tw)(y^Tz).]
est vraie pour tout $x,w\in\mathbb{R}^r$, $y,z\in\mathbb{R}^s$. En effet, les
deux côtés somment tous les termes de la forme $x_iy_jw_iz_j$
$i=1,\ldots, r$, $j=1,\ldots, s$.

Cette équation exprime exactement ce qui nous manque : si on a
une représentation orthonormale de $G^r$ et de $G^s$ et qu’on
représente la concaténation de deux vecteurs par le produit
tensoriel de leur représentation, alors on obtient une
représentation orthonormale de $G^{r+s}$ !

Nous avons vu (encadré) une représentation orthonormale de $C_5$, où
la première coordonnée de chaque représentant est $1/ \sqrt{\sqrt{5}}$.

Donc pour tous les vecteurs de la représentation de $G=C_5^{k}$
obtenue par produit tensoriel on a $r_1^2=(1/\sqrt{5})^k$. En
substituant ce résultat dans le lemme, on obtient que le nombre
maximum de mots de longueur $k$ qu’on ne peut pas confondre est
inférieur ou égal à $(\sqrt{5})^k$, c’est à dire pour $2k$ la borne
est $5^k$, d’où $\ref{equation_1}$. Le théorème qui a été une cible bien connue
des chercheurs pendant 22 ans, est démontré !

LA PERFECTION ET AU-DELA

Bien avant que la capacité de Shannon de $C_5$ ait pu être
calculée, le problème posé par Shannon a stimulé un chapitre de la
théorie des graphes qui a été pendant longtemps l’un de ses moteurs
et a eu un rayonnement bien au-delà. Ce chapitre est celui des
graphes parfaits, définis par Claude Berge, qui a aussi énoncé deux
conjectures devenues célèbres les concernant, sous les noms de
conjecture faible et forte des graphes parfaits. (Voir les notes
historiques de Berge, dans son dernier article [RR].)

Un ensemble de sommets mutuellement non-voisins d’un graphe est dit
stable ; un ensemble de sommets mutuellement voisins est un
graphe complet. Nous avons vu que $\alpha(G^k)\ge (\alpha (G))^k$. Rappelons la source de difficulté exprimée par $\alpha (C_5)=2$, $\alpha (C_5^2)=5>2^2$.

Quels sont les graphes pour lesquels ce phénomène ne se présente
pas, c’est-à-dire $\alpha (G^k)=(\alpha (G) )^k ?$ Pour ceux-là la
capacité de Shannon est égal au nombre de stabilité. Nous laissons
au lecteur le plaisir de montrer que $\alpha (G)=\chi(\bar G)$ est
une condition suffisante pour avoir cette propriété. On note par
$\bar G$ le complémentaire d’un graphe $G$, c’est-à-dire le
graphe dont les sommets $u$ et $v$ sont voisins si et seulement si
ils ne sont pas voisins dans le graphe original ; $\chi(G)$ est le
nombre chromatique de $G$, c’est à dire le nombre minimum de
classes d’une partition des sommets en stables.

On a vu que $C_5$ n’a pas cette propriété. Il est facile de voir,
que les graphes « cycles impairs » et leurs complémentaires ne l’ont
pas non plus. La conjecture célèbre de Berge [LL], [RR], [AS]
énonce :

Une variante plus faible a été démontré par Lovász en 1972, et cette conjecture
« forte » par Chudnovsky, Robertson, Seymour et Thomas en 2002.
Colorier les sommets d’un graphe, ou reconnaître une sous-classe
par un algorithme efficace (polynomial) reste un problème
utile et intéressant : les recherches sur les graphes parfaits et
leurs sous-classes gardent encore beaucoup de secrets [RR], dont
Chudnovsky et Seymour ou Maffray et Trotignon continuent à révéler
certains, même après la grande percée que représente le théorème
fort. Un grand problème reste ouvert : pour les graphes parfaits le
stable max, le nombre chromatique (et par conséquent la capacité de
Shannon) se laissent calculer en temps polynomial en utilisant la
programmation semidéfinie (faisant appel à la méthode des
ellipsoïdes) mais il n’y a pas d’algorithme combinatoire !

Et qu’y a-t-il au-delà de la perfection ? L’imperfection ! Les
graphes imparfaits ont été étudiés en grande partie pour résoudre la
conjecture de Berge [RR], mais la preuve utilise peu ces résultats.

Cependant le monde discret n’est pas toujours complètement lisse, et
il faut faire avec. On peut souvent remédier à l’imperfection — dans
un sens plus général avec des méthodes non moins profondes :

Le problème du partitionnement des sommets d’un graphe en deux
parties, $A$ et $B$, de façon à maximiser le nombre, ou plus
généralement la somme des poids, des arêtes qui sont « à cheval »
entre les deux parties, est un des problèmes les plus utilisés de la
théorie des graphes. On l’appelle coupe max. C’est un
problème difficile (NP-difficile) et donc on ne peut pas espérer le
résoudre « parfaitement ». Par une idée extrêmement originale de
Goemans et Williamson, ce problème admet une solution « imparfaite »,
mais intéressante, et similaire aux parapluies. Nous allons
l’esquisser pour montrer comment des idées similaires apparaissent
dans des situations différentes :

Etant donnés des poids $w_{ij}$ $(i,j=1,\ldots, n)$ sur les paires
de sommets d’un graphe (qu’on peut supposer être complet,
c’est-à-dire toutes les paires de sommets sont des arêtes) on peut
résoudre le problème de représenter les points sur la sphère de
dimension $n$ et maximiser

\[\begin{equation}\sum_{i

où $x_i,x_j$ représentent les sommets $i,j$, et
dist$(a,b)$ est la distance euclidienne entre $a$ et $b$.

Ceci est un « programme semidéfini ». Le lecteur intéressé par
l’algèbre linéaire pourra facilement démontrer que ce problème
d’optimisation est équivalent à déterminer la matrice symétrique
semidéfinie $X_{n\times n}$ dont les entrées sur la diagonale sont
égales à $1$, et pour laquelle

$\sum_{i

Un programme semidéfini est traitable (par des algorithmes
polynomiaux) et ceci découle du fait que « la contrainte qu’une
matrice soit semidéfinie » est une contrainte qui peut être traitée
similairement à la non-négativité de la programmation linéaire.

Si nous choisissons la sphère de diamètre $1$, le maximum $S$
de la somme dans $\ref{equation_2}$ nous donnera une borne supérieure à la valeur
maximum $M$ d’une coupe, (on peut placer les sommets dans deux
points antipodaux de la sphère), d’autre part, si dans $\ref{equation_2}$ on
remplace dist$(i,j)$ par l’angle $x_iOx_j$ où $x_i,y_j$
représentent les sommets $i$ et $j$, $O$ est le centre de la sphère,
et on mesure les angles en demi-tours (la mesure de l’angle de 180°
est $1$ et les autres angles ont une mesure proportionnelle) — on
notera cette quantité angle$(x_i,x_j)$ —, alors $S$ devient $S'$ et
il se trouve qu’on peut trouver une coupe de taille $S'$, de plus,
$S'$ n’est pas beaucoup plus petit que $S$, que nous prouvons :

Un hyperplan aléatoire qui passe par l’origine sépare les sommets en
deux, définissant une partition. (La probabilité d’avoir des sommets
sur l’hyperplan, est $0$.) Cette partition sépare $x_i$ et $x_j$
avec probabilité égale à angle$(x_i,x_j)$ . Et donc l’espérance
mathématique de la contribution de l’arc $ij$ est
angle$(x_i,x_j)w_{ij}$. Par conséquent l’espérance mathématique de
la coupe est juste $S'$, donc il existe une coupe de taille au moins
$S'$ qu’on peut déterminer en temps polynomial avec la technique de
la dérandomisation ! Il ne reste plus qu’à vérifier $0,878 S\le S'\le S,$ où on sait déjà $S'\le S$, et le lecteur pourra à nouveau
vérifier ceci avec le théorème de Pythagore et de la trigonométrie
de lycée : on est de nouveau dans le plan de dimension $2$ — défini
par le centre de la sphère et $x_i,x_j$ —, et on peut calculer
dist$(i,j)$ en fonction du sinus et cosinus de l’angle. Il est
surprenant mais vrai que l’angle divisé par la distance au
carré reste toujours supérieur ou égal à 0,878, vérifiez le avec
votre calculette !

UNE PLACE (TROP) DISCRÈTE ?

La méthode des représentations géométriques similaires et
l’application de la programmation semidéfinie sont maintenant choses
courantes en optimisation combinatoire voir [RR]. D’autres idées
géométriques ou algébriques ont montré leur puissance en théorie des
graphes. Par exemple le nombre de Colin de Verdière — la
multiplicité de la plus petite valeur propre positive d’une certaine
matrice associée à un graphe — qui permet d’exprimer des
représentations importantes et profondes (dans le plan ou d’une
manière avantageuse en trois dimension) du graphe. La méthode
utilise de l’algèbre linéaire et des arguments analytiques. Encore
un autre des multiples exemples : Lovász, Bárány, Matoušek
et récemment un jeune étudiant grenoblois Frédéric Meunier,
utilisent des résultats de la topologie pour démontrer des théorèmes
combinatoires qui ne se laissent pas aborder d’une manière
élémentaire, (voir une introduction à ce sujet dans le joli livre de
Matoušek).

A l’inverse, on voit de plus en plus que les autres domaines des
mathématiques utilisent des méthodes ou des résultats combinatoires.
Quelques exemples : la topologie (la théorie des nœuds utilise la
théorie des graphes et des résultats de la combinatoire polyédrale),
la géométrie algébrique (relations proches avec la programmation en
nombres entiers), et les statistiques mathématiques (qui utilisent
la théorie des structures régulières comme les « bloc design »), etc.
Les relations tissent les liens entre mathématiques discrètes et les
autres domaines des mathématiques. Beaucoup de jolis problèmes
viennent aussi de l’informatique, d’autres sciences, de l’industrie,
ou de l’économie (recherche opérationnelle), etc. Le domaine reste
proche de ses applications, qui demeurent une ressource importante
de problèmes.

Un autre domaine d’application mérite d’être mentionné :
l’enseignement des mathématiques. Le discret est ludique, et fait
bien travailler le cerveau même à un niveau de débutant : on y
trouve des mini-théories prêtes a être enseignées dans le
secondaire ; elles pourraient remplacer ou compléter certains
enseignements classiques. Des collègues y travaillent (« maths à
modeler », « math-en-jeans », etc), et avec beaucoup de succès
auprès des élèves. Espérons que ce bruit d’enfants joyeux qui aiment
les maths sans être nécessairement « matheux » arrivera bientôt aux
adultes qui déterminent le programme des écoles.

Quelle est la place des mathématiques discrètes dans le paysage
scientifique ? En Allemagne
 [2], en Hongrie
 [3], ou encore dans de nombreuses universités
d’Amérique du Nord (par exemple [4]), elles ont une place
consolidée, leur importance dans les formations universitaires
modernes a été reconnue. En France cette place reste encore
discrète. Le besoin de son enseignement — pour les informaticiens,
ingénieurs, économistes, biologistes, etc. — est identifié, mais la
nécessité d’une expertise importante n’est pas partout réalisée.
Pourtant plusieurs équipes font une recherche appréciée au niveau
international avec un nombre croissant de jeunes, dans le cadre de
collaborations florissantes (exemple : le projet européen « Marie
Curie training network » [5], et pourraient fournir des enseignants spécialisés.

Il y a un quart de siècle, Lovász [LL] a écrit : « ... It is often
forcefully stated that Combinatorics is a collection of problems,
which may be interesting in themselves but are not linked and do not
constitute a theory ... In my opinion, Combinatorics is growing out
of this early stage. There are techniques to learn ... There are
branches which consist of theorems forming a hierarchy and which
contain central structure theorems forming the backbone of study ...
There are notions abstracted to many non-trivial results, which
unify large parts of the theory ... » Ceci s’est confirmé depuis,
le domaine est devenu adulte, bien que toujours jeune et dynamique ;
nous espérons que cette mini-photo condensée en donne une image
déchiffrable.

Références

[LL] L. Lovász, Combinatorial problems and exercises,
North Holland and Akadémiai Kiadó, 1979.

[RR] Perfect Graphs, recueil d’articles édité par
J. Ramirez-Alfonsin, B. Reed, Springer (2001).

[AS] A Schrijver, Combinatorial Optimization 1-3, Springer
(2003)