Algorithmique des matroïdes et polynômes log-concaves
Arnaud de Mesmay1
1LIGM Laboratoire Informatique Gaspard Monge Univ Gustave Eiffel, CNRS, LIGM, F-77454 Marne-la-Vallée, France
Journées mathématiques X-UPS, Combinatoire et géométries exotiques (2025), pp. 105-149

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.

Publié le :
DOI : 10.5802/xups.2025-03

Arnaud de Mesmay  1

1 LIGM Laboratoire Informatique Gaspard Monge Univ Gustave Eiffel, CNRS, LIGM, F-77454 Marne-la-Vallée, France 
Arnaud de Mesmay. Algorithmique des matroïdes et polynômes log-concaves. Journées mathématiques X-UPS, Combinatoire et géométries exotiques (2025), pp. 105-149. doi: 10.5802/xups.2025-03
@incollection{XUPS_2025____105_0,
     author = {Arnaud de Mesmay},
     title = {Algorithmique des matro{\"\i}des et~polyn\^omes log-concaves},
     booktitle = {Combinatoire et g\'eom\'etries exotiques},
     series = {Journ\'ees math\'ematiques X-UPS},
     pages = {105--149},
     year = {2025},
     publisher = {Les \'Editions de l{\textquoteright}\'Ecole polytechnique},
     doi = {10.5802/xups.2025-03},
     language = {fr},
     url = {https://proceedings.centre-mersenne.org/articles/10.5802/xups.2025-03/}
}
TY  - JOUR
AU  - Arnaud de Mesmay
TI  - Algorithmique des matroïdes et polynômes log-concaves
JO  - Journées mathématiques X-UPS
PY  - 2025
SP  - 105
EP  - 149
PB  - Les Éditions de l’École polytechnique
UR  - https://proceedings.centre-mersenne.org/articles/10.5802/xups.2025-03/
DO  - 10.5802/xups.2025-03
LA  - fr
ID  - XUPS_2025____105_0
ER  - 
%0 Journal Article
%A Arnaud de Mesmay
%T Algorithmique des matroïdes et polynômes log-concaves
%J Journées mathématiques X-UPS
%D 2025
%P 105-149
%I Les Éditions de l’École polytechnique
%U https://proceedings.centre-mersenne.org/articles/10.5802/xups.2025-03/
%R 10.5802/xups.2025-03
%G fr
%F XUPS_2025____105_0

[1] Karim Adiprasito; June Huh; Eric Katz Hodge theory for combinatorial geometries, Annals of Mathematics. Second Series, Volume 188 (2018) no. 2, pp. 381-452 | DOI | Zbl | MR

[2] Yeganeh Alimohammadi; Nima Anari; Kirankumar Shiragur; Thuy-Duong Vuong Fractionally log-concave and sector-stable polynomials : counting planar matchings and more, STOC ’21—Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, NY, 2021, pp. 433-446 | DOI

[3] Omid Amini Géométries combinatoires, Combinatoire et géométries exotiques (Journées X-UPS), Les Éditions de l’École polytechnique, Palaiseau, 2025 (ce volume) | DOI

[4] Nima Anari; Kuikui Liu; Shayan Oveis Gharan; Cynthia Vinzant Log-concave polynomials III : Mason’s ultra-log-concavity conjecture for independent sets of matroids, Proceedings of the American Mathematical Society, Volume 152 (2024) no. 5, pp. 1969-1981 | DOI | MR | Zbl

[5] Nima Anari; Kuikui Liu; Shayan Oveis Gharan; Cynthia Vinzant Log-concave polynomials II : High-dimensional walks and an FPRAS for counting bases of a matroid, Annals of Mathematics. Second Series, Volume 199 (2024) no. 1, pp. 259-299 | DOI | Zbl | MR

[6] Nima Anari; Shayan Oveis Gharan; Cynthia Vinzant Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids, 59th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2018, IEEE Computer Soc., Los Alamitos, CA, 2018, pp. 35-46 | DOI | MR

[7] Nima Anari; Alireza Rezaei A tight analysis of Bethe approximation for permanent, 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. Press, Los Alamitos, CA, 2019, pp. 1434-1445 | DOI | Zbl | MR

[8] Nima Anari; Cynthia Vinzant; Kuikui Liu; Shayan Oveis Gharan; Thuy-Duong Vuong Log-concave polynomials IV : approximate exchange, tight mixing times, and near-optimal sampling of forests, STOC ’21—Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2021, pp. 408-420 | DOI | Zbl

[9] Petter Brändén Polynomials with the half-plane property and matroid theory, Advances in Mathematics, Volume 216 (2007) no. 1, pp. 302-320 | DOI | Zbl | MR

[10] Petter Brändén; June Huh Lorentzian polynomials, Annals of Mathematics. Second Series, Volume 192 (2020) no. 3, pp. 821-891 | DOI | Zbl | MR

[11] Petter Brändén; Jonathan Leake Lorentzian polynomials on cones and the Heron-Rota-Welsh conjecture, 2021 | arXiv | Zbl

[12] Young-Bin Choe; James G. Oxley; Alan D. Sokal; David G. Wagner Homogeneous multivariate polynomials with the half-plane property, Advances in Applied Mathematics, Volume 32 (2004) no. 1-2, pp. 88-187 (Special issue on the Tutte polynomial) | DOI | MR | Zbl

[13] Mary Cryan; Heng Guo; Giorgos Mousa Modified log-Sobolev inequalities for strongly log-concave distributions, The Annals of Probability, Volume 49 (2021) no. 1, pp. 506-525 | DOI | MR | Zbl

[14] Jack Edmonds Submodular functions, matroids, and certain polyhedra, Combinatorial optimization – Eureka, you shrink. Papers dedicated to Jack Edmonds. 5th international workshop, Aussois, France, March 5–9, 2001, Springer, Berlin, 2003, pp. 11-26 | DOI | Zbl | MR

[15] G. P. Egorychev The solution of van der Waerden’s problem for permanents, Advances in Mathematics, Volume 42 (1981) no. 3, pp. 299-305 | MR | DOI | Zbl

[16] D. I. Falikman Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix, Mathematical Notes, Volume 29 (1981), pp. 475-479 | DOI | Zbl

[17] Tomás Feder; Milena Mihail Balanced matroids, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing (1992), pp. 26-38 | DOI

[18] Joachim von zur Gathen; Jürgen Gerhard Modern computer algebra, Cambridge University Press, Cambridge, 2013 | DOI | Zbl | MR

[19] Heng Guo; Mark Jerrum A polynomial-time approximation algorithm for all-terminal network reliability, SIAM Journal on Computing, Volume 48 (2019) no. 3, pp. 964-978 | DOI | Zbl | MR

[20] Leonid Gurvits Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials : one theorem for all, Electronic Journal of Combinatorics, Volume 15 (2008) no. 1, 66, 26 pages | DOI | MR | Zbl

[21] Leonid Gurvits On multivariate Newton-like inequalities, Advances in combinatorial mathematics : Proceedings of the Waterloo Workshop in Computer Algebra 2008, Springer, Berlin, 2009, pp. 61-78 | MR | Zbl | DOI

[22] Leonid Gurvits; Alex Samorodnitsky Bounds on the permanent and some applications, 55th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2014, IEEE Computer Soc., Los Alamitos, CA, 2014, pp. 90-99 | DOI | MR

[23] A. P. Heron Matroid polynomials, Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), The Institute of Mathematics and Its Applications, Southend-on-Sea, 1972, pp. 164-202 | MR

[24] S. G. Hoggar Chromatic polynomials and logarithmic concavity, Journal of Combinatorial Theory. Series B, Volume 16 (1974), pp. 248-254 | DOI | MR | Zbl

[25] Shlomo Hoory; Nathan Linial; Avi Wigderson Expander graphs and their applications, American Mathematical Society. Bulletin. New Series, Volume 43 (2006) no. 4, pp. 439-561 | DOI | MR | Zbl

[26] June Huh Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs, Journal of the American Mathematical Society, Volume 25 (2012) no. 3, pp. 907-927 | DOI | MR | Zbl

[27] June Huh Combinatorial applications of the Hodge-Riemann relations, Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures, World Scientific Publications, Hackensack, NJ, 2018, pp. 3093-3111 | MR | Zbl

[28] June Huh; Eric Katz Log-concavity of characteristic polynomials and the Bergman fan of matroids, Mathematische Annalen, Volume 354 (2012) no. 3, pp. 1103-1116 | DOI | MR | Zbl

[29] Mark Jerrum Counting, sampling and integrating : algorithms and complexity, Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel, 2003 | DOI | MR | Zbl

[30] Mark Jerrum; Alistair Sinclair; Eric Vigoda A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, Journal of the ACM, Volume 51 (2004) no. 4, pp. 671-697 | DOI | MR | Zbl

[31] Mark R. Jerrum; Leslie G. Valiant; Vijay V. Vazirani Random generation of combinatorial structures from a uniform distribution, Theoretical Computer Science, Volume 43 (1986) no. 2-3, pp. 169-188 | DOI | MR | Zbl

[32] David R Karger A randomized fully polynomial time approximation scheme for the all terminal network reliability problem, Proceedings of the twenty-seventh annual ACM Symposium on Theory of Computing, ACM, New York, NY, 1995, pp. 11-17 | DOI | Zbl

[33] Tali Kaufman; Izhar Oppenheim High order random walks : beyond spectral gap, Combinatorica. An International Journal on Combinatorics and the Theory of Computing, Volume 40 (2020) no. 2, pp. 245-281 | DOI | Zbl

[34] Andreas Krause; Daniel Golovin Submodular function maximization, Tractability, Cambridge University Press, Cambridge, 2014, pp. 71-104 | DOI

[35] Joseph B. Kruskal On the shortest spanning subtree of a graph and the traveling salesman problem, Proceedings of the American Mathematical Society, Volume 7 (1956), pp. 48-50 | DOI | MR | Zbl

[36] G. Laman On graphs and rigidity of plane skeletal structures, Journal of Engineering Mathematics, Volume 4 (1970), pp. 331-340 | DOI | MR | Zbl

[37] Jonathan Leake; Kasper Lindberg; Shayan Oveis Gharan Optimal trickle-down theorems for path complexes via C-Lorentzian polynomials with applications to sampling and log-concave sequences, 2025 | arXiv

[38] David A. Levin; Yuval Peres Markov chains and mixing times, American Mathematical Society, Providence, RI, 2017 | DOI | MR | Zbl

[39] Alexander Lubotzky High dimensional expanders, Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. I. Plenary lectures, World Scientific Publications, Hackensack, NJ, 2018, pp. 705-730 | MR | Zbl

[40] J. H. Mason Matroids : unimodal conjectures and Motzkin’s theorem, Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), The Institute of Mathematics and Its Applications, Southend-on-Sea, 1972, pp. 207-220 | MR

[41] Michael Mitzenmacher; Eli Upfal Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis, Cambridge University Press, Cambridge, 2017 | MR | Zbl

[42] Matthieu Piquerez Algèbres et volumes des polytopes, Combinatoire et géométries exotiques (Journées X-UPS), Les Éditions de l’École polytechnique, Palaiseau, 2025 (ce volume) | DOI

[43] J. Scott Provan; Michael O. Ball The complexity of counting cuts and of computing the probability that a graph is connected, SIAM Journal on Computing, Volume 12 (1983) no. 4, pp. 777-788 | DOI | MR | Zbl

[44] Ronald C. Read An introduction to chromatic polynomials, Journal of Combinatorial Theory, Volume 4 (1968), pp. 52-71 | DOI | MR | Zbl

[45] Gian-Carlo Rota Combinatorial theory, old and new, Actes du Congrès International des Mathématiciens (Nice, 1970), Tome 3, Gauthier-Villars Éditeur, Paris, 1971, pp. 229-233 | MR | Zbl

[46] Herbert John Ryser Combinatorial mathematics, The Carus Mathematical Monographs, 14, Mathematical Association of America, 1963 | DOI | MR | Zbl

[47] Leslie G. Valiant The complexity of enumeration and reliability problems, SIAM Journal on Computing, Volume 8 (1979) no. 3, pp. 410-421 | DOI | MR | Zbl

[48] D. J. A. Welsh Combinatorial problems in matroid theory, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), Academic Press, London-New York, 1971, pp. 291-306 | MR | Zbl

[49] Hassler Whitney On the abstract properties of linear dependence, American Journal of Mathematics, Volume 57 (1935) no. 3, pp. 509-533 | DOI | MR | Zbl

[50] Avi Wigderson Mathematics and computation. A theory revolutionizing technology and science, Princeton University Press, Princeton, NJ, 2019 | DOI | MR | Zbl

Cité par Sources :