Algorithmique des matroïdes et polynômes log-concaves
Journées mathématiques X-UPS · 03.07.2026 · 105-149
DOI: 10.5802/xups.2025-03 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journées mathématiques X-UPS, online erschienen am 03.07.2026. Verfasst von Arnaud de Mesmay. Die Arbeit nennt 50 Literaturangaben.
Abstract (Originalsprache)
L’objectif de ce texte est de faire découvrir un pendant algorithmique des résultats présentés dans les textes d’Omid Amini [3] et de Mathieu Piquerez [42] en théorie des matroïdes, en nous concentrant sur des algorithmes récents d’Anari, Liu, Oveis Gharan et Vinzant permettant de compter et d’échantillonner de façon très efficace des bases de matroïdes. Nous commençons par un survol des enjeux de la théorie des matroïdes en informatique théorique, qui permettent de généraliser à des contextes plus larges le cadre, désormais très bien compris, des graphes. Nous introduisons ensuite les polynômes log-concaves (également connus sous le nom de polynômes lorentziens dans les travaux de Brändén et Huh), dont les définitions d’apparence simple cachent des propriétés très riches qui sont intimement liées aux sujets traités dans les deux autres textes. Ces propriétés en font un outil très efficace pour résoudre de multiples problèmes combinatoires et algorithmiques, et nous esquissons comment elles sont exploitées dans les algorithmes sus-cités pour résoudre des problèmes d’informatique théorique ouverts depuis une trentaine d’années.
Zitieren
APA
Mesmay, A. D. (2026). Algorithmique des matroïdes et polynômes log-concaves. Journées mathématiques X-UPS, 105-149. https://doi.org/10.5802/xups.2025-03
Vancouver
Mesmay AD. Algorithmique des matroïdes et polynômes log-concaves. Journées mathématiques X-UPS. 2026:105-149. doi:10.5802/xups.2025-03
BibTeX
@article{Mesmay2026,
author = {Mesmay, Arnaud de},
title = {Algorithmique des matroïdes et polynômes log-concaves},
journal = {Journées mathématiques X-UPS},
year = {2026},
pages = {105--149},
doi = {10.5802/xups.2025-03}
}
EUVIMED