Lovasz Laszlo

En 1963, encore adolescent, László Lovász remporte une première médaille d'or aux Olympiades internationales de mathématiques. Le jeune Hongrois, né à Budapest en 1948, obtient ensuite deux autres médailles d'or en 1964 et 1965.

Son parcours relie des problèmes faits de sommets, d'arêtes et de choix discrets à des outils venus d'autres domaines. En 1978, il emploie ainsi la topologie pour démontrer la conjecture de Kneser. Cette manière de franchir les frontières des disciplines marque ses contributions à la combinatoire et aux fondements de l'informatique.

László Lovász est un mathématicien hongrois, né en 1948 à Budapest, dont les travaux portent notamment sur la théorie des graphes, les structures combinatoires et les fondements de l'informatique. Adolescent, il rencontre Paul Erdős après avoir lu l'un de ses articles. Leur travail commun nourrit chez Lovász une pratique ouverte et collaborative de la recherche.

Trois résultats jalonnent le portrait. En 1972, Lovász démontre la première conjecture de Claude Berge sur les graphes parfaits, devenue le théorème faible des graphes parfaits. En 1978, il démontre la conjecture de Kneser par une approche topologique et contribue ainsi à ouvrir la combinatoire topologique. Il co-invente aussi l'algorithme LLL avec Arjen et Hendrik Lenstra ; son nom reprend les initiales des trois chercheurs.

L'algorithme LLL trouve des applications en théorie des nombres, en cryptographie et en informatique théorique. Après des postes universitaires en Hongrie et à l'étranger, Lovász reçoit le prix Abel en 2021 pour l'ensemble de ses contributions aux fondements de l'informatique et à la combinatoire.

Pour lire son parcours sans mélanger distinctions et résultats, suivons quatre repères annoncés par la source : les médailles d'or de 1963 à 1965, le théorème de 1972, la démonstration de 1978 et le prix de 2021.

1. En 1963, 1964 et 1965, Lovász obtient trois médailles d'or consécutives aux Olympiades internationales de mathématiques.
2. En 1972, il démontre la première conjecture de Berge sur les graphes parfaits : c'est le théorème faible des graphes parfaits.
3. En 1978, il démontre la conjecture de Kneser grâce à une approche topologique.
4. En 2021, le prix Abel distingue l'ensemble de ses contributions à la combinatoire et aux fondements de l'informatique.

Le contrôle consiste à associer chaque année à un fait précis : 1972 concerne les graphes parfaits, tandis que 1978 concerne la conjecture de Kneser. La frise matérialise cette séparation et évite de présenter le prix Abel comme la date d'un résultat isolé.

Dans un cours ou un index, chercher « théorème faible des graphes parfaits » permet d'identifier le résultat concerné ; « théorème de Lovász » est trop vague et peut renvoyer à d'autres travaux. L'intitulé précis relie immédiatement le nom au bon objet : les graphes parfaits.

Pour manipuler un cas miniature du problème de Kneser, inscrivez les dix paires formées avec les nombres de 1 à 5, puis reliez deux paires lorsqu'elles n'ont aucun nombre commun. Essayez de colorier ce graphe avec deux couleurs en donnant des couleurs différentes aux paires reliées : le cycle {1,2}–{3,4}–{1,5}–{2,3}–{4,5}–{1,2}, qui comporte cinq arêtes, rend cette tentative impossible. Le problème de départ reste discret — des paires, des relations de disjonction et des couleurs — ; pour traiter la famille générale, Lovász traduit l'impossibilité d'utiliser trop peu de couleurs en une obstruction topologique.

En théorie des nombres, en cryptographie ou en informatique théorique, le nom de Lovász apparaît aussi dans l'algorithme LLL. L'indice observable est le sigle à trois lettres : il renvoie à Lovász et aux deux frères Lenstra, et non à un travail solitaire.

Le théorème faible des graphes parfaits et la conjecture de Kneser. Le premier est le résultat démontré par Lovász en 1972 à partir d'une conjecture de Claude Berge. La seconde est démontrée en 1978 par une approche topologique. La date et l'objet permettent de les distinguer.

Un résultat et une distinction. Le prix Abel reçu en 2021 couronne un ensemble de contributions. Il ne faut pas le traiter comme un théorème supplémentaire : dans une chronologie, son rôle est celui d'une reconnaissance, non d'une démonstration.

Le nom « algorithme LLL » peut masquer une attribution collective. Les trois lettres viennent de László Lovász, Arjen Lenstra et Hendrik Lenstra. Si une présentation n'en cite qu'un, il faut rétablir les trois co-inventeurs.

Employer une approche topologique pour la conjecture de Kneser ne transforme pas la conjecture en énoncé de topologie. L'exemple des paires prises parmi cinq nombres montre seulement un petit cas grâce à un cycle impair ; il ne reconstitue pas la preuve générale de Lovász. Pour mesurer la portée de la méthode, il faut examiner l'objet discret précis — les sous-ensembles, leur disjonction et le nombre de couleurs — puis l'obstruction que la topologie permet d'établir. Cette démarche ne fournit ni une recette valable pour tout problème combinatoire ni, à elle seule, un algorithme de coloriage.

Les trois médailles d'or de 1963, 1964 et 1965 signalent un parcours précoce, mais elles ne résument pas l'œuvre scientifique. Pour situer celle-ci, il faut aussi considérer les résultats de 1972 et 1978, l'algorithme LLL et les contributions récompensées en 2021.

Le graphe parfait prolonge le résultat de 1972 en précisant l'objet auquel se rapporte le théorème faible des graphes parfaits.

La cryptographie éclaire l'un des domaines d'application cités pour l'algorithme LLL.