Lemme local de Lovász

Le lemme local de Lovász (parfois abrégé LLL[réf. nécessaire]) est un résultat de théorie des probabilités discrètes, dû à László Lovász et Paul Erdős. Il généralise le fait que la probabilité que des événements indépendants arrivent en même temps est égale au produit des probabilités de ces événements. Il existe plusieurs versions de ce résultat. Le lemme local est utilisé dans plusieurs domaines, notamment en combinatoire et en informatique théorique. Dans ces domaines il est parfois énoncé informellement de la manière suivante : étant donné un ensemble de mauvais événements, n'ayant pas de grande dépendances les uns avec les autres, il est possible d'éviter tous ces événements à la fois.

Introduction

Le lemme local peut être vu comme une version de la méthode probabiliste. Cette technique de combinatoire permet de montrer que certains objets existent en montrant que selon certaines constructions aléatoires la probabilité de créer un tel objet est non nul.

Par exemple, étant donné une famille d'événements indépendants, de probabilités strictement inférieures à 1, la probabilité qu'aucun d'eux n'apparaissent est non nulle. Le lemme local peut permettre d'obtenir le même résultat, si chaque événement n'est dépendant que d'un nombre borné d'autres événements.

Définitions

Dans la suite, on note les événements , dans un espace de probabilité quelconque.

Les dépendances entre ces événements peuvent être représentées par un graphe non orienté G=(V,E), appelé graphe des dépendances, défini par :

  • chaque nœud représente un événement,
  • une arête (u,v) appartient au graphe si et seulement si les événements et sont dépendants.

Énoncés

On donne d'abord l'énoncé général, puis la forme symétrique qui en est un corollaire, plus facilement utilisable[1].

Cas général

S'il existe une famille de réels de [0,1] tel que pour tout i :

Alors :

Cas symétrique

Si pour tout i, , si chaque événement ne dépend que d'au plus d autres événements, i.e si le graphe de dépendances est de degré maximum d, et si , où e est la base du logarithme naturel, alors .

Applications

Domaines d'application

Le lemme local a été utilisé dans de nombreux domaines de la combinatoire, notamment la théorie des graphes extrémaux, la théorie de Ramsey[2] et la théorie des graphes aléatoires[3], ainsi qu'en informatique théorique, notamment pour un cas particulier du problème SAT, pour des algorithmes de routage[4],[5] et pour des problèmes de coloration[6].

Exemple du problème k-SAT

Le problème SAT, consiste, étant donnée une formule logique sous forme normale conjonctive, de savoir s'il existe une assignation des variables telle que la formule est vraie, c'est-à-dire à décider la satisfiablilité de la formule. On fait deux hypothèses : il y a au plus k littéraux par clause (c'est le problème k-SAT) et chaque littéral n’apparaît que dans au plus clauses. Alors le lemme permet de dire que la formule est satisfiable[7]. En effet, si les valeurs des variables sont prises au hasard, alors les événements « la clause numéro i est satisfaite » satisfont les hypothèses du lemme symétrique avec et .

Historique

Le lemme local a été publié dans l'article Erdős et Lovász 1975 avec une hypothèse plus forte : . Il fut amélioré pour obtenir les bornes données ici. Les premières preuves du lemme étaient non-constructives, mais une preuve constructive a été trouvée autour de 2010, par Robin A. Moser et Gábor Tardos[8],[9]. Cette dernière preuve a aussi des conséquences algorithmiques, on parle d'ailleurs de lemme local de Lovász algorithmique (en). La méthode utilisée est appelée compression de l'entropie (en).

Notes et références
  1. Ces formes de l'énoncé sont issues de Motwani et Raghavan 1995 ; d'autres formes existent.
  2. L'un des premiers articles utilisant le lemme le fait pour donner une borne inférieure sur les nombres de Ramsey : Joel Spencer, « Asymptotic lower bounds for Ramsey functions », Discrete Mathematics, vol. 20,‎ , p. 69-76
  3. Cette liste d'applications est issue de Motwani et Raghavan 1995.
  4. Voir un exemple dans Regamey 2012, section 5.
  5. L'article original est : Frank Thomson Leighton, Bruce M. Maggs et Satish Rao, « Packet Routing and Job-Shop Scheduling in O(Congestion + Dilation) Steps », Combinatorica, vol. 14, no 2,‎ , p. 167-186.
  6. Par exemple l'article : Daniel Marx et Marcus Schaefer, « The complexity of nonrepetitive coloring », Discrete Applied Mathematics, vol. 157, no 1,‎ , p. 13-18.
  7. Motwani et Raghavan 1995
  8. Robin A. Moser et Gábor Tardos, « A constructive proof of the general lovász local lemma », Journal of the ACM, vol. 57, no 2,‎
  9. Un post sur cette preuve : (en) Terence Tao, « Moser’s entropy compression argument », sur terrytao.wordpress.com, (consulté le ).

Bibliographie
  • (en) Paul Erdős et László Lovász, « Problems and results on 3-chromatic hypergraphs and some related questions », dans Infinite and Finite Sets (to Paul Erdős on his 60th birthday), vol. II, (lire en ligne), p. 609–627
  • (en) Rajeev Motwani et Prabhakar Raghavan, Randomized Algorithms, Cambridge ; New York, Cambridge University Press (réimpr. 1997, 2000) (1re éd. 1995), 476 p. (ISBN 9780521474658), chap. 5.5 (« The Lovász local lemma »), p. 115-120
  • Samuel Regamey, Méthode probabiliste et Lemme local de Lovász (Rapport de projet), EPFL, (lire en ligne)
  • Portail des mathématiques
  • Portail de l'informatique théorique
  • Portail des probabilités et de la statistique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.