Journées MAS 2010

Optimisation combinatoire (pdf)

Session organisée par Charles Bordenave (CNRS, Université de Toulouse)

La méthode de la cavité en physique statistique a donné un nouvel élan à toute une classe de probèmes sur des structures combinatoires aléatoires. Les premiers succès remontent aux travaux G. Parisi et M. Mézard dans la deuxième moitié des années 80. Il a fallu attendre le début les années 2000, avec notamment les travaux de D. Aldous et M. Talagrand pour avoir les premières confirmations mathématiques de leurs résultats. Depuis, la recherche s'est portée vers des problèmes sur des structures combinatoires plus diluées, comme des graphes avec degrés bornés. Comme en témoigne l'ouvrage de M. Mézard et A. Montanari, les prédictions non-rigoureuses ont avancé plus vite que les arguments rigoureux. La compréhension mathématique de la méthode de la cavité est aujourd'hui encore insuffisante et il y a de nombreuses questions à résoudre pour le mathématicien.

Exposé de 40 minutes Guilhem Semerjian (ENS) Problèmes aléatoires de satisfaction de contraintes : approches et résultats de la physique statistique transparents

Dans les années 90 des simulations numériques ont révélées des propriétés intéressantes dans les ensembles aléatoires d'instances de problèmes de satisfaction de contraintes (satisfiabilité, coloriage de graphes notamment). Quand un paramètre définissant l'ensemble aléatoire (le nombre de clauses par variables) augmente la probabilité de trouver une formule satisfiable chute abruptement de 1 à 0 dans la limite des grandes tailles de formule. Ce phénomène de seuil a été l'objet d'actives recherches en informatique et en probabilités. Par ailleurs des outils (non-rigoureux) de physique statistique ont pu être appliqués à ces problèmes. Un certain nombre de résultats ont émergé de ces études, par exemple des conjectures quantitatives sur la valeur du seuil de satisfiabilité, et une image plus précise de la structure de l'ensemble des solutions des formules satisfiables. D'autres résultats de physique statistique ont un aspect plus algorithmique, que ce soit l'analyse d'algorithmes déjà existants ou la suggestion de nouvelles stratégies pour résoudre ces formules aléatoires. Dans cet exposé j'essaierai de présenter, sans rentrer dans les détails techniques, le cadre général de ces études et certains de ces résultats.

Exposé de 20 minutes Raphaël Rossignol (Université Paris Sud) en collaboration avec Nadia Creignou, Hervé Daudé et Uwe Egly Le seuil d'(1,2)-QSAT transparents

QSAT est la version quantifiée du problème SAT. On montre l'existence d'un effet de seuil pour la transition de phase associée à la satisfaisabilité des formules aléatoires quantifiées de type (1,2)-CNF. Plus précisément, on considère un modèle aléatoire de formules booléennes de la forme "pour tout X, il existe Y tel que \psi(X,Y), où X est un vecteur de m variables booléennes, Y un vecteur de n variables booléennes et \psi une conjonction de 3-clauses telle que chaque clause contienne un littéral venant de X et deux de Y. Pour de telles formules, on prouve que le phénomène de seuil est contrôlé par le rapport nombre de clauses sur nombre de variables, et on donne la valeur exacte du rapport critique, qui est une fonction de la limite de m/\log(n).

Exposé de 20 minutes Nicolas Broutin (INRIA Rocquencourt) Les distances dans les arbres couvrants minimaux transparents

Les propriétés locales des arbres couvrant minimaux de graphes pondérés de façon aléatoire on fait l'objet de nombreuses recherches. En revanche, en dépit de leur importance pour les applications, les paramètres globaux reliés aux distances comme l'index de Wiener ou encore le diamètre ont quant à eux été très peu étudiés. Nous verrons comment décrire la distribution des distances dans l'arbre couvrant minimal d'un graphe pondéré aléatoirement en utilisant un couplage naturel avec le modèle des graphes aléatoires.

Exposé de 20 minutes Justin Salez (ENS et INRIA) en collaboration avec Charles Bordenave et Marc Lelarge The weak limit of Boltzmann random matchings on diluted graphs transparents

A matching on a finite graph G=(V,E) is a collection of pairwise non-adjacent edges M\subseteq E. The Boltzmann random matching at temperature z>0 on G is distributed as follows : for any matching M on G,
\mathbb P({\cal M}^z_G=M)=\frac{z^{|V|-2|M|}}{P_G(z)}, with P_G(z)=\sum_{M}z^{|V|-2|M|}.
We are interested in the asymptotic behavior of {\cal M}^z_G as |G|\to\infty. Specifically, we establish that for any graph sequence (G_n)_{n\geq 1} converging to an infinite tree {\cal T} with finite Hausdorff dimension, {\cal M}^z_{G_n} converges in distribution to a properly defined random matching {\cal M}^z_{\cal T} on {\cal T} with determinantal marginals. Moreover, the zero-temperature limit {\cal M}^0_{\cal T}=\lim_{z\to 0}{\cal M}^z_{\cal T} exists in some sense, and under an extra condition on {\cal T} it is precisely the weak limit of a the uniform maximum matching on G_n. When the (G_n)_{n\geq 1} are random and converge weakly to a Galton-Watson tree, the limit turns out to be characterized by a recursive distributional equation, which we solve. We thus obtain an explicit formula for the asymptotic size of a maximum matching on G_n, generalizing that of Karp and Sipser for Erdös-Rényi graphs.