se mbl e de so mmets V et d 'e nsembl e
d'arêtes E, et S est une partie de V, le bord
de S, noté ôS, est l'ensemb le des arêtes
co nn ec tant S à so n co mpl émenta ire
V - S. C'est donc l'ensemble des arêtes
qu' il fa ut enl ever pour déconnecter S
de V - S. Pour cette ra iso n, la paire
{S ; V - S} s'appell e une coupure du
graphe X.
La constante de Cheeger de X est :
* (X)= min
1
155
1
.
g:i~~1v1 1s1 x 1 v - SI
Le problème consistant à calculer *(X)
est connu sous le nom de problème de
la coupure de densité minimum (ou sparsest eut problem). C'est un prob lème
NP-di fficile, ce qui signifie que l'on ne
connaît essentiellement pas de meilleure
solution, pour calculer *(X), que d'énumérer les iv
1
- 2 parties S appara issant
dans la définiti on. D'où un temps de
calcul ex ponenti el en IVI.
On va se contenter d' une solution approximati ve, qui approcherait *(X) à une
constante multiplicati ve près. Une première solution a été fo urnie en 1995 par
les Israéliens Nati Linial, Eran London
et Yuri Rabinov itch. li s donnent d'abord
une réi nterprétation de <1> * en termes de
plongements de X (vu comme espace
métrique* , avec les arêtes de longueur
1) dans L
1 • Une distance* d surX est une
di stance- L
I s' il ex iste une appli cation
injective!: X-+ L
1 avec
d(x , y)= llflx) - f(y) II I' normalisé par :
I I d tEV \€v
Les tro is mathématiciens ont démontré
que
*( X)=
inf
L d(x,y) .
d d1~tancc-L
1 , urX (x,y)EE
Leur idée est de relaxer le probl ème en
oubli ant la cond iti on L
1
, c'est-à-dire en
travaillant avec toutes les métriques sur
X. On définit ainsi une constante PL(X),
dont le calcul est un problème de proPOUR LES MATHS
Petit glossaire des espaces de Banach
Espace de Banach : espace vectoriel sur Ill ou C muni d'une
norme* pour lequel il est complet*.
Norme sur un espace vectoriel : application qui, à
tout vecteur V, fait correspondre un nombre positif I IVI I
qui vérifie certaines propriétés, comme l lk.VI 1 = lkl x I IVI I
ou IIV+WII :s; IIVII + IIWIIEspace métrique : ensemble muni d'une distance d vérifiant certaines propriétés, en particulier l'inégalité triangulaire :
d(A, C) :S d(A, B) + d(B, C). Tout espace normé est un
espace métrique: on pose pour cela d(V, W) = I IW - VI 1 ,
mais il n'est pas forcément complet.
Espace métrique complet: dans un espace métrique complet, toute suite de Cauchy* est convergente. Ainsi, Ill ou Ill",
munis par exemple d'une norme euclidienne, sont des
espaces de Banach, mais pas ICI!, qui n'est pas complet.
Suite de Cauchy : suite (un)n pour laquelle la distance
11 u,,, - u,, 11 entre deux éléments tend vers o quand leurs indices
tendent vers l'infini. ICI! n'est pas complet car une suite de
Cauchy de a peut ne pas converger dans a mais dans Ill (par
exemple, la suite décimale de lt est une suite de Cauchy de
ICI! qui ne converge pas dans ICI!).
Espaces lJ' : on appelle IP(I) l'espace des fonctions dont
la puissance p est intégrable sur 1 (au sens de Lebesgue).
L co est l'espace des fonctions bornées.
gramm ation linéa ire, qui se résout en
temps po lynomi al avec une préc ision
arbitraire. On a clairement
PL(X) :5 *(X), mais un ri sque ex iste,
év idemment : fa ire une erreur gigantesque en remplaçant *(X) par PL(X).
C'est préc isément le rés ultat de Jean
Bourgain qui nous assure que PL(X) est
une bonne approximation de *(X) !
En effet, ce résultat implique
pL(X) :5 *(X) :5 C ln IX 1 rL(X)
Ce résultat remarquable a provoqué une
série d' interactions passionnantes impliquant info rmaticiens, analystes, théori c ie ns des graphes, th éo ri c ie ns des
groupes: une mani fes tati on de plus de
! ' unité des mathématiques !
A. V.
Hors-série n• 52. Mathématiques & informatique Tangente
8