\documentclass[XUPS,XML,SOM,Unicode,francais, NoFloatCountersInSection]{cedram} \setcounter{tocdepth}{2} %\XUPScorrections \graphicspath{{xups25-03_figures}} \usepackage{../xups25} \newtheorem{theorem}{Théorème} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemme} \theoremstyle{definition} \newtheorem{remark}{Remarque} \newcommand\mto{\mathchoice{\longmapsto}{\mapsto}{\mapsto}{\mapsto}} \DeclareMathOperator{\diag}{diag} \DeclareMathOperator{\Id}{Id} \DeclareMathOperator{\link}{link} \DeclareMathOperator{\per}{per} \begin{document} \frontmatter \title[Algorithmique des matroïdes]{Algorithmique des matroïdes et\nobreakspace polynômes log-concaves} \author{\firstname{Arnaud} \lastname{de Mesmay}} \address{LIGM Laboratoire Informatique Gaspard Monge Univ Gustave Eiffel, CNRS, LIGM, F-77454 Marne-la-Vallée, France} \email{arnaud.de-mesmay@univ-eiffel.fr} \urladdr{https://monge.univ-mlv.fr/~demesma/} \thanks{Journées X-UPS 2025. Combinatoire et géométries exotiques. Éditions de l'École polytechnique, 2026} \begin{abstract} 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 \cite{amini} et de Mathieu Piquerez \cite{piquerez} 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. \end{abstract} \maketitle \vspace*{-.5\baselineskip} \enlargethispage{2\baselineskip} \tableofcontents \mainmatter L'objectif de ces notes est de proposer un survol de quelques versants algorithmiques des combinatoires et géométries exotiques présentées dans les autres textes. Le~point focal est une série de papiers assez récents d'Anari, Liu, Oveis Gharan et Vinzant~\cite{anari2018log,anari2024log,anari2024logbis,anari2021log}, en~particulier le deuxième et le troisième, où les auteurs ont montré de façon remarquable comment résoudre des vieux problèmes d'informatique théorique avec des outils modernes d'origine géométrique, regroupés sous le thème des \emph{polynômes log-concaves}. Le~résultat principal auquel nous aspirerons est le suivant. \begin{theorem}[{\cite[Cor.\,1.4]{anari2024log}}] \label{th:main} Il existe un algorithme randomisé qui, pour tout matroïde à $n$ éléments de rang $r$ fourni par un oracle d'indépendance et pour tous $\varepsilon\in{}]0,1[$ et $\delta\in{}]0,1[$, compte le nombre de bases de $M$ à facteur multiplicatif de $1\pm\varepsilon$ près, avec probabilité $1-\delta$ et en temps polynomial en $n,r,1/\varepsilon$ et $\log(1/\delta)$. \end{theorem} En parallèle, Brändén et Huh~\cite{branden2020lorentzian} ont développé une théorie des \emph{polynômes lorentziens}, qui sont très proches des polynômes log-concaves, et~ont obtenu des résultats similaires. Nous adopterons plutôt dans ces notes le point de vue plus informatique du premier groupe d'auteurs. Cela a l'avantage, ou le défaut, selon le point de vue, de cacher la théorie de Hodge derrière des atours étonnamment élémentaires. En~particulier, nous proposerons une preuve presque complète du théorème~\ref{th:main} dans ce texte, ainsi que de plusieurs autres résultats qui découlent de la théorie. Quelques remarques feront le lien entre notre point de vue très combinatoire et les aspects géométriques mis en avant dans les autres textes. Mais tout cela est probablement assez abscons pour l'instant, donc commençons par présenter le contexte, en~débutant par l'usage des matroïdes en informatique. \section{Des matroïdes en informatique} Un matroïde est un objet combinatoire introduit par Whitney~\cite{whitney} généralisant en même temps la notion d'indépendance en algèbre linéaire et la notion d'acyclicité en théorie des graphes. Il y a de nombreuses définitions équivalentes et nous nous concentrons sur l'une d'elles pour fixer les notations. Un \emph{matroïde} fini $M=(E,\mathcal{I})$ est constitué d'un ensemble fini $E$ et d'une famille $\mathcal{I}$ de sous-ensembles de $E$, appelés \emph{ensembles indépendants} tels que: \begin{enumerate} \item L'ensemble vide est indépendant. \item Pour tous $A \subseteq B \subseteq E$, si $B \in \mathcal{I}$ alors $A \in \mathcal{I}$. \item\label{matroid:ajout} Si $A$ et $B$ sont dans $\mathcal{I}$ et que $A$ a strictement plus d'éléments que $B$, alors il existe un $x$ dans $A \setminus B$ tel que $B \cup \{x\}$ est indépendant. \end{enumerate} L'intuition à avoir est celle de l'algèbre linéaire. Il est immédiat de vérifier que les familles de vecteurs indépendantes satisfont les axiomes ci-dessus. De nombreux autres concepts des matroïdes sont directement inspirés de ce cadre. Ainsi les \emph{bases} sont des ensembles indépendants de taille maximale, et~on peut facilement prouver qu'elles ont toutes la même cardinalité, appelé le \emph{rang} du matroïde. De manière similaire, pour tout sous-ensemble $A$ de $E$, son rang $r(A)$ sera la cardinalité maximale d'un sous-ensemble indépendant de $A$. Il est important de noter cependant que c'est une généralisation stricte: certains matroïdes ne sont pas obtenus de cette façon. On~dit qu'un matroïde obtenu comme l'ensemble des vecteurs indépendants d'un espace vectoriel sur un corps $\mathbb{F}$ est \emph{représentable} sur $\mathbb{F}$. De façon moins évidente, un matroïde est aussi une généralisation d'un graphe. Dans toutes ce texte, un graphe $G=(V,E)$ est juste un ensemble fini de sommets $V$ et un ensemble fini d'arêtes $E \subseteq V^2$ qui sont des paires de sommets. En~particulier nous autorisons les boucles mais pas les arêtes multiples. Un tel graphe définit un matroïde en considérant pour $E$ l'ensemble des arêtes $E$ (les notations sont bien choisies), et~pour les ensembles indépendants $\mathcal{I}$ les ensembles d'arêtes ne contenant aucun cycle. On~peut facilement vérifier que cela satisfait bien aux axiomes des matroïdes. Une autre façon de s'en convaincre est de considérer la \emph{matrice d'incidence} d'un graphe, définie comme la matrice $I$ telle que $I_{v,e}=1$ si et seulement si le sommet~$v$ est incident à une arête $e$ qui n'est pas une boucle, et d'observer que ses vecteurs colonnes engendrent un sous-espace vectoriel de $(\mathbb{Z}/2\mathbb{Z})^{|E|}$, où une famille de vecteurs est indépendante si et seulement si les arêtes correspondantes ne contiennent pas de cycle. Ainsi, les \emph{matroïdes graphiques} que nous venons de définir sont représentables sur $\mathbb{Z}/2\mathbb{Z}$, et~en fait sur n'importe quel corps. De tels matroïdes, représentables sur n'importe quel corps, sont dits \emph{réguliers}. Pour un élément $x$ de $E$, on~définit un matroïde où $x$ a été \emph{supprimé} $M\setminus x:= (E\setminus x,\{I \cap (E \setminus x)\mid I \in \mathcal{I}\})$, et~un matroïde où $x$ a été \emph{contracté} $M / x = (E \setminus x, \{I \cap (E \setminus x) \mid I\cup \{x\} \in \mathcal{I}\}$. L'intuition pour ces deux notions vient de la théorie des graphes, où on peut obtenir de manière similaire deux graphes différents en supprimant ou en contractant une arête. \subsubsection*{Algorithmes gloutons} Une des premières raisons de s'intéresser aux matroïdes en informatique est qu'ils donnent la structure combinatoire sous-jacente à tout problème pour lequel un \emph{algorithme glouton} est optimal. Un algorithme glouton apparaît naturellement dès que l'on considère un problème où l'on a un nombre fini \hbox{objets $E$} (là~encore, la notation n'est pas choisie au hasard), chacun ayant un certain coût ou une certaine valeur $w(e)$, et~on cherche à choisir un sous-ensemble de $E$ de coût minimal ou de valeur maximale mais soumis à certaines conditions. Par exemple, il~peut s'agir d'acheter des produits avec la condition qu'on ne veut jamais deux exemplaires du même produit et on veut minimiser le coût. L'algorithme glouton consiste alors à choisir un premier élément de coût minimal, puis un second parmi les éléments restants compatibles de coût minimal, et~ainsi de suite. Lorsque les ensembles admissibles sont stables par inclusion, la question de savoir si la solution trouvée est globalement optimale revient exactement à se demander s'ils forment les ensembles indépendants d'un matroïde: la propriété d'ajout~\eqref{matroid:ajout} montre qu'à n'importe quel moment de l'algorithme glouton, après avoir pris un élément de coût minimal on peut compléter avec des éléments de la solution optimale, ce~qui permet de conclure puisque celle-ci est globalement minimale. La direction opposée de l'équivalence n'est pas beaucoup plus dure à établir en jouant sur les coûts. Ce point de vue permet d'éclairer et de généraliser des algorithmes classiques de théorie des graphes. Par exemple, un problème fondamental d'algorithmique des graphes est de trouver un \emph{arbre couvrant minimal}, c'est-à-dire un sous-ensemble d'arêtes de poids total minimal ne formant pas de cycles dans un graphe. Comme on l'a vu, les ensembles d'arêtes ne contenant pas de cycles définissent un matroïde, et~donc l'idée naturelle est d'appliquer un algorithme glouton: c'est ce que fait le célèbre algorithme de Kruskal~\cite{kruskal1956shortest}. Pour voir où cette idée mène à des problèmes de recherche contemporains, continuons sur notre exemple d'achat de produits, mais dans un cadre où l'on généralise notre fonction de coûts à une fonction \emph{sous-modulaire}, c'est-à-dire une fonction définie non plus sur les objets mais sur les ensembles, et~satisfaisant à une propriété de rendements décroissants: pour tous $A\subseteq B\subseteq E$ et $x \not\in B$, \[ f(A \cup {x}) - f(A) \geq f(B \cup {x}) - f(B). \] C'est un modèle classique en économie et en théorie algorithmique des jeux: par exemple la valeur perçue d'un manteau est moins grande si l'on est déjà habillé des pieds à la tête que si l'on est en tenue d'Ève ou d'Adam. Notez par ailleurs que la fonction de rang d'un matroïde satisfait à une telle propriété de sous-modularité. Si~l'on souhaite maximiser la valeur de notre panier sans énumérer tous les achats possibles (ce qui serait algorithmiquement prohibitif puisqu'il~y~aurait un nombre exponentiel de choix), il~est naturel de se tourner encore vers un algorithme glouton et de se demander s'il trouve une solution optimale. Ce ne sera pas le cas en général, même si les paniers admissibles forment un matroïde, mais pour certains matroïdes, la qualité de la solution gloutonne sera sensiblement meilleure que pour d'autres et de nombreux travaux ont été consacrés à de tels problèmes d'\emph{optimisation sous-modulaire}, voir par exemple l'article de survol~\cite{krause2014submodular}. \subsubsection*{Matroïdes et intersections de matroïdes.} Les matroïdes forment donc un cadre généralisant à la fois les sous-ensembles acycliques d'un graphe et les familles de vecteurs indépendants dans un espace vectoriel. D'autres matroïdes apparaissent également en informatique théorique. Voici une liste non exhaustive de leurs incarnations. \begin{enumerate} \item \emph{Matroïde dual et co-graphique.} Bien qu'il n'y ait pas de notion naturelle de dualité pour un graphe (du moins s'il n'est pas plongé), il~y en a une pour les matroïdes. Le~\emph{matroïde dual} $M^*$ d'un matroïde~$M$ a le même ensemble d'éléments $E$ et ses ensembles indépendants $\mathcal{I}^*$ sont les ensembles $U \subseteq E$ tels qu'il existe une base $B$ de~$M$ telle que $U$ et $B$ sont disjoints. Il est facile de voir que lorsque le matroïde $M$ est graphique pour un graphe $G$, son dual $M^*$ a pour ensembles indépendants les ensembles d'arêtes dont la suppression laisse $G$ connexe. Tutte a montré qu'un graphe $G$ est planaire si et seulement si son matroïde dual est également graphique, auquel cas c'est le matroïde du graphe dual $G^*$ de $G$, dont les sommets sont les faces de $G$ (composantes connexes de $\mathbb{R}^2 \setminus G$) et les arêtes sont les adjacences entre ces faces. \item \emph{Matroïde de rigidité.} Des matroïdes différents apparaissent dans l'étude des phénomènes de rigidité. Il s'agit de l'étude des \emph{cadres}, c'est-à-dire des graphes $G=(V,E)$ munis d'une application $f:V \rightarrow \mathbb{R}^d$ indiquant la position des sommets, les arêtes étant réalisées par des segments de longueur fixée. Un tel cadre est dit \emph{rigide} s'il n'existe pas de modification locale de l'application $f$ préservant la longueur des arêtes, modulo les symétries de $\mathbb{R}^d$ qui sont bien sûr toujours présentes. La motivation vient de l'ingénierie: une structure se doit d'être rigide pour ne pas s'effondrer au moindre coup de vent. De manière similaire, quiconque a monté des étagères en kit sait qu'un empilement de rectangles n'est pas rigide, mais peut le devenir lorsqu'on ajoute un X derrière, comme illustré en figure~\ref{F:ikea}. Il~se trouve que la rigidité d'un cadre ne dépend pas de la longueur des segments\footnote{Du moins \emph{génériquement}, c'est-à-dire que la rigidité sera toujours la même sauf pour un ensemble de longueur de segments de mesure nulle. Le~choix de l'étagère de la figure~\ref{F:ikea} n'est d'ailleurs pas tout-à-fait générique, et~comme il m'a été signalé pendant le cours, elle peut être rigidifiée en rajoutant un seul X au lieu de deux. Mais la théorie de la rigidité montre que cela est impossible dès que les longueurs sont un peu perturbées: c'est par exemple le cas si les suites d'arêtes de chaque côté de l'étagère ne sont pas tout-à-fait verticales.}, et~qu'elle est encodée dans un matroïde: le \emph{matroïde de rigidité} d'un graphe a pour éléments les arêtes du graphe, et~pour bases les ensembles d'arêtes induisant un sous-graphe rigide minimal. En~dimension $2$, la structure des matroïdes de rigidité est entièrement décrite grâce à un théorème célèbre de Laman~\cite{laman1970graphs} mais, en~dimension $3$ et plus, ils sont beaucoup moins bien compris. \begin{figure}[t] \begin{center} \includegraphics[width=.8\textwidth]{Rigidite.pdf} \caption{À gauche, un graphe non rigide, que l'on peut déformer comme au milieu. À droite, le~graphe est rigidifié par l'ajout de deux X. L'exemple de droite est minimalement rigide: le graphe tout entier est une base du matroïde de rigidité, et~rajouter des arêtes serait superflu du point de vue de la rigidité, ce~qui s'exprimerait comme des dépendances.} \label{F:ikea} \end{center} \end{figure} \item \emph{Couplages et graphes bipartis.} Les matroïdes apparaissent également dans d'autres problèmes classiques de théorie des graphes. Par exemple, considérons un graphe biparti $G = (U, V, E)$, c’est-à-dire que l’ensemble des sommets est partitionné en $U$ et $V$ et il n’y a pas d’arête entre sommets de $U$ ou entre sommets de $V$. Il est très fréquent de vouloir calculer un \emph{couplage}, c'est-à-dire un ensemble d'arêtes sans sommets en commun, avec certaines propriétés, dans un graphe biparti (pensez à Parcoursup). \begin{itemize} \item On peut voir cela sous l'angle des matroïdes en considérant un premier \emph{matroïde de partition} $M_U$ dont les éléments sont les arêtes $E$ et les ensembles indépendants sont les familles d'arêtes n'ayant pas d'extrémités en commun dans $U$. De manière similaire, on~définit l'autre matroïde de partition $M_V$. Un couplage est alors un ensemble indépendant commun aux deux matroïdes. Calculer un couplage de taille maximale revient donc à calculer un ensemble indépendant commun à deux matroïdes de taille maximale, et~un théorème classique d'Edmonds~\cite{edmonds2003submodular} permet de résoudre ces deux problèmes en temps polynomial. \item Un autre matroïde $M_T(U)$, appelé \emph{matroïde transversal}, apparaît lorsqu'on fixe un côté de la bipartition comme ensemble d'éléments, par exemple $U$, et~que l'on choisit comme ensembles indépendants les sous-ensembles $U'$ de $U$ qui peuvent être couplés parfaitement dans le graphe $G$, c'est-à-dire tels qu'il existe un ensemble d'arêtes disjointes dans $G$ reliant chaque sommet de $U'$ à un sommet de $V$. Si $|U|\geq |V|$, l'existence d'un couplage parfait (où tous les sommets sont appareillés) pour~$G$ se ramène donc à l'existence d'un ensemble indépendant de taille $|U|$ dans $M_T(U)$. \end{itemize} \end{enumerate} \subsubsection*{Problèmes de fiabilité.} Il est maintenant possible de motiver un peu notre théorème~\ref{th:main}. Pour toutes les structures décrites par ces matroïdes, un problème fondamental est celui de calculer leur \emph{fiabilité}. Regardons d'abord au cas par cas de quoi il s'agit. \begin{enumerate} \item Étant donné un graphe, s'il modélise un réseau de distribution d'électricité, une propriété primordiale à conserver est sa connexité. Si certaines arêtes viennent à dysfonctionner, indépendamment avec une certaine probabilité, quelle est la probabilité que le graphe reste connexe ? \item Étant donné un cadre, s'il modélise un bâtiment ou un meuble, on~voudra conserver sa rigidité lorsque certaines arêtes viennent à faillir, indépendamment avec une certaine probabilité. Quelle est la probabilité que le cadre perde sa rigidité ? \item Étant donné un graphe biparti, s'il modélise un système d'affectation d'étudiants, on~veut que chaque étudiant ait une formation. Si l'on ajoute un certain nombre d'étudiants aléatoirement, quelle est la probabilité que ce soit le cas ? \item Un \emph{code correcteur binaire linéaire} est un sous-espace vectoriel de $(\mathbb{Z}/2\mathbb{Z})^n$ tel que tout vecteur est assez éloigné de chaque autre vecteur. Cette propriété de \emph{distance} permet de reconstruire un message (pensé comme une suite de bits $0$ ou $1$, donc comme un élément de $(\mathbb{Z}/2\mathbb{Z})^n$) s'il venait à être corrompu lors d'un transfert d'informations. Si le canal de transfert venait à être corrompu au point que l'on perde complètement l'information contenu dans le $k$-ième bit, pour des valeurs de $k$ choisies indépendamment avec une certaine probabilité, quelle est la probabilité pour que le code correcteur fonctionne encore ? \end{enumerate} Lorsque l'on demande la probabilité dans tous ces problèmes, c'est un problème de nature \emph{algorithmique}: on cherche à trouver un bon algorithme qui, prenant comme entrée un graphe, un cadre, etc., va déterminer la probabilité de fiabilité de cet objet. Via les différentes incarnations des matroïdes que nous avons vues, ces problèmes peuvent être pensés comme des cas particuliers du problème de fiabilité de matroïde: Étant donné un matroïde $M=(E,\mathcal{I})$ et un entier $k$, comment calculer la probabilité que si l'on choisit $k$ éléments distincts aléatoirement et uniformément, ceux-ci soient indépendants ? Ce problème est $\#P$-complet~\cite{valiant}: cela signifie que modulo les conjectures classiques de théorie de la complexité, il~n'existe pas d'algorithme capable de le résoudre exactement en temps polynomial. On va donc chercher à l'approximer. Calculer la probabilité de fiabilité revient à calculer le quotient $\sfrac{|\mathcal{I}_k|}{\binom{|E|}{k}}$, où on a noté~$\mathcal{I}_k$ les ensembles indépendants de taille $k$, et~donc à compter efficacement le nombre d'ensembles indépendants d'une taille fixée dans un matroïde. Notez que tout matroïde peut être \emph{tronqué} à une certaine taille~$k$, c'est-à-dire qu'on peut retirer des ensembles indépendants tous les ensembles de taille strictement plus grande que $k$, et~obtenir un matroïde de rang $k$. Les ensembles indépendants de taille $k$ deviennent alors des bases. Nous avons donc enfin tous les ingrédients pour apprécier une des forces du théorème~\ref{th:main}: celui-ci permet, en~temps polynomial, de résoudre de façon approximée (avec une approximation aussi bonne qu'on le souhaite), tous les problèmes de fiabilité que nous avons mentionnés. \begin{remark} Il faut faire attention au modèle de calcul lorsque l'on traite d'algorithmique des matroïdes. Lorsqu'on prend un matroïde en entrée d'un algorithme, si cette entrée contient tous les ensembles indépendants du matroïde, elle est de taille considérable. Notamment, pour les matroïdes graphiques, elle peut facilement être exponentiellement plus grande que le graphe correspondant. Il y a alors beaucoup moins d'intérêt à développer des algorithmes polynomiaux lorsque l'entrée est énorme. C'est pourquoi il est plus standard de considérer, comme dans le théorème~\ref{th:main}, un modèle avec \emph{oracle}: plutôt que de fournir tous les ensembles indépendants en entrée de l'algorithme, on~considère que celui-ci a accès à un oracle, c'est-à-dire qu'il peut demander à tout instant, pour un coût 1, si un ensemble donné est indépendant. Demander tous les ensembles indépendants nécessiterait possiblement alors un temps exponentiel, ce~qui rend encore plus remarquable la dépendance polynomiale annoncée dans le théorème~\ref{th:main}. \end{remark} \enlargethispage{.5\baselineskip}% Nous concluons cette introduction au domaine par quelques notes historiques. Le~problème de fiabilité dans les graphes est un problème classique, datant au moins des années 80, qu'on ne peut résoudre en temps polynomial si l'on admet les hypothèses standard en théorie de la complexité~\cite{valiant,provanball}. Karger a montré en 95~\cite{karger} comment approximer efficacement la probabilité qu'un graphe devienne déconnecté, et~il a fallu attendre Guo et Jerrum en 2017~\cite{guojerrum} pour avoir un algorithme correspondant pour estimer la probabilité que le graphe reste connecté\footnote{De façon un peu contre-intuitive, lorsque l'on traite d'algorithmes d'$(1+\varepsilon)$-approximation avec une garantie multiplicative, ce~qui est le cas ici, deux problèmes complémentaires ne sont pas équivalents. Dans le premier cas, pour une probabilité $p$ que le graphe soit déconnecté, l'algorithme fournit une valeur $p'$ telle que\vspace*{-5pt} \[ p(1-\varepsilon)p'>p(1+\varepsilon)-\varepsilon, \] ce~qui est très sensiblement différent par exemple lorsque $p\ll\varepsilon$. }. Ainsi, le~théorème~\ref{th:main} généralise grandement ces résultats en englobant des objets combinatoire bien plus variés que les graphes. \section{Algorithmes de comptage, échantillonnage et\nobreakspace marches\nobreakspace aléatoires} \Subsection{Comptage et échantillonnage} L'algorithme derrière le théorème~\ref{th:main} est très simple, et~c'est son analyse qui s'avère délicate. Un algorithme randomisé naturel pour compter les bases d'un matroïde est de calculer d'abord son rang~$r$, puis de générer aléatoirement un ensemble de $r$ éléments et de tester, via l'oracle, s'il est indépendant. En~répétant ce test un nombre suffisant de fois, on~obtient une estimation de la probabilité qu'un ensemble de $r$ éléments soit indépendant, et~donc une estimation du nombre de bases. Cela peut être formalisé avec des inégalités de type Markov, comme par exemple les bornes de Chernoff~\cite[Chap.\,4]{mitzenmacher2017probability}. Le~problème de cette approche est que si le nombre de bases est très petit par rapport à $\binom{|E|}{r}$, l'oracle répondra négativement la plupart du temps, et~il faudra un temps très long, peut-être exponentiel, pour obtenir une estimation correcte, comme celle promise par le théorème~\ref{th:main}. Cet algorithme, bien que trop lent, illustre une propriété fondamentale commune à de nombreux problèmes de comptage: il~y~a un lien fort entre le problème d'\emph{échantillonner} correctement (c'est-à-dire de générer aléatoirement uniformément un élément) un ensemble et de compter sa taille. Ici, l'obstacle est le même dans les deux cas: l'ensemble des bases d'un matroïde peut être tellement petit qu'un échantillonnage naïf amènera à de trop nombreux rejets. Un théorème fondateur, dû à Jerrum, Valiant et Vazirani~\cite{jerrum1986random} montre que cette connexion est valide dans les deux sens pour une très large classe de problèmes, appelés problèmes auto-réductibles (\emph{self-reducible}), dont le problème de compter les bases de matroïde fait partie. Par souci de simplicité, nous ne l'énonçons que pour ce cas particulier. On~dit qu'un problème spécifié par un entier $n$ et un ensemble cible $M_n$ admet un \emph{algorithme polynomial d’échantillonnage approximé randomisé uniforme}, si, pour tout $\varepsilon\in{}]0,1[$, il~existe un algorithme polynomial en $\log(1/\varepsilon)$ et $n$ qui échantillonne un élément~$u$ de l'ensemble~$M_n$ selon une probabilité $\pi$ telle que \hbox{$\|\pi - \mu\|_1\!\leq\! \varepsilon$}, où $\mu$ est la distribution uniforme sur $M_n$. Le~nom étant assez lourd, on~\hbox{utilisera} l'\hbox{abréviation} consacrée, qui est FPAUS pour \emph{Fully Polynomial Appro\-ximate \hbox{Uniform} Sampler}. La distance $\ell_1$ dans ce contexte est appelée \emph{distance de variation totale}\footnote{Les experts objecteront ici que ces deux distances diffèrent d'un facteur~$2$, que nous négligerons.}: pour deux distributions de probabilités~$\pi$ et~$\mu$ dont la distance de variation totale est faible, chaque événement arrive avec presque la même probabilité pour $\pi$ et pour $\mu$. \begin{theorem}\label{th:jerrum} Il existe un algorithme polynomial de \emph{comptage} randomisé approximé\footnote{L'abréviation consacrée est FPRAS pour \emph{Fully Polynomial Randomized Approximation Scheme}.} des bases de matroïde (au sens du théorème~\ref{th:main}) si et seulement il existe un algorithme polynomial d'\emph{échantillonnage} approximé randomisé uniforme des bases de matroïde. \end{theorem} \begin{proof}[Ébauche de preuve] Nous présentons les idées principales de la preuve sans fournir l'analyse probabiliste dans le détail et nous renvoyons à l'article~\cite{jerrum1986random} ou au livre~\cite[Prop.\,3.4]{jerrum2003counting} pour celle-ci. Fixons un matroïde $M=(E,\mathcal{I})$ et notons $\mathcal{B}(M)$ l'ensemble de ses bases. \begin{itemize} \item Imaginons d'abord que l'on sache compter efficacement les bases d'un matroïde. On~peut alors échantillonner efficacement de la façon suivante: on fixe un élément $x$ de $E$ et on utilise notre algorithme pour compter les bases qui contiennent cet élément. De manière similaire, on~compte les bases qui ne le contiennent pas. Cela nous permet d'estimer la probabilité $p(x)$ qu'une base aléatoire tirée uniformément contienne $x$. On~peut alors tirer au sort, selon la probabilité $p(x)$, si $x$ est dans notre base, et~appliquer le même algorithme récursivement dans le matroïde $M / x$ si $x$ y est ou dans le matroïde $M \setminus x$ sinon. \item Dans l'autre sens, imaginons que l'on sache échantillonner efficacement les bases d'un matroïde. On~fixe encore un élément~$x$ de~$E$, et~on échantillonne un nombre de fois suffisant pour obtenir une bonne estimation de la probabilité $p(x)$ qu'il soit dans une base, ou bien de la probabilité $1-p(x)$ qu'il ne soit pas dans une base. De manière cruciale, au moins l'une de ces deux probabilités n'est pas trop petite, et~il n'est pas difficile de montrer que, dans ce contexte, le~nombre suffisant est de taille polynomiale (c'est la différence avec notre algorithme naïf: pour l'un des deux choix, on~peut contrôler le nombre de rejets). La probabilité $p(x)$ vaut $\sfrac{|\mathcal{B}(M / x)|}{|\mathcal{B}(M)|}$ et la probabilité $1-p(x)$ vaut $\sfrac{|\mathcal{B}(M \setminus x)|}{|\mathcal{B}(M)|}$. On~peut alors appliquer récursivement le même algorithme dans $M /x$ ou $M \setminus x$ jusqu'à arriver au matroïde vide, qui a une unique base de taille $1$. La quantité $1/\mathcal{B}(M)$ s'obtient en prenant le produit télescopique de toutes les probabilités estimées.\qedhere \end{itemize} \end{proof} Ce résultat fondamental montre que le c\oe{}ur du problème est donc d'échantillonner efficacement des bases de matroïde. Pour ce faire, l'algorithme utilisé consiste en une marche aléatoire très facile à décrire, appelée \emph{marche d'échange de bases}. Il s'agit simplement de partir d'une base quelconque $B$, et~de la modifier en une base $B'$ en \begin{enumerate} \item retirant un élément $x$ de $B$ au hasard uniformément, \item et en rajoutant un élément $y$ à $B \setminus x$, choisi aléatoirement uniformément parmi ceux tels que $(B \setminus x) \cup y$ est une base. \end{enumerate} Une conjecture célèbre de 1989 de Mihail et Vazirani stipulait que cette marche aléatoire permet d'échantillonner une base efficacement. Le~moteur derrière le théorème~\ref{th:main} est une preuve de cette conjecture. \begin{proposition}[{\cite[Cor.\,1.3]{anari2024log}}]\label{prop:sampling} Pour un matroïde de rang $r$ avec $n$~éléments, appliquer la marche d'échange de bases pendant un temps $O(r^2\log(n/\varepsilon))$ donne un FPAUS. \end{proposition} Précédemment, il~y avait une longue ligne de travaux autour des algorithmes d'approximation pour les problèmes de matroïdes. Pour une classe particulière de matroïdes appelés matroïdes \emph{équilibrés}, \hbox{Feder} et Mihail~\cite{fm92} ont obtenu dès les années 90 des résultats d'échantillonnage de bases, mais très peu de choses étaient connus dans le cas général avant les travaux d'Anari, Liu, Oveis Gharan et Vinzant~\cite{anari2024log}. \subsection{Mélange de marches aléatoires}\label{sec:mixing} Avant de prouver la proposition~\ref{prop:sampling}, prenons un peu de recul. Notre objectif est d'analyser combien de temps une marche aléatoire met pour se propager uniformément dans un espace fixé. Cela se rattache à la théorie des \emph{chaînes de Markov}, et~plus précisément au \emph{temps de mélange} qu'elles mettent pour converger (presque) à leur \emph{distribution stationnaire}. Si~vous n'êtes pas familiers avec ces concepts, voici quelques notions qui permettent d'appréhender de quoi il retourne. Nous renvoyons à l'article de survol de Hoory, Linial et Wigderson pour une introduction au sujet~\cite[\S\,3]{hoory2006expander} et au livre classique de Levin, Peres et Wilmer~\cite{peres} pour une référence plus poussée. On modélise une marche aléatoire avec un graphe dirigé $G$: ses sommets sont les différentes étapes de la marche, et~on met une arête dirigée $uv$ lorsque la marche a une probabilité non nulle de passer de $u$ à $v$, et~une autre arête dirigée $vu$ lorsque la marche a une probabilité non nulle de passer de $v$ à $u$. Nous nous restreignons dans cette discussion au cas où $G$ est fini, qui suffira pour notre application. En~général, une marche aléatoire est spécifiée par une \emph{matrice de transition} $M$, qui spécifie pour chaque arête la probabilité que la marche emprunte cette arête, de telle sorte que ces probabilités somment à~$1$ autour de chaque sommet. Pour la marche d'échange des bases, la~marche est symétrique (c'est-à-dire qu'il~y~a une arête~$uv$ si et seulement s'il~y~a une arête $vu$ et elles ont les mêmes probabilités) et le graphe est connexe. Dans ce contexte, il~est facile de voir qu'il existe une unique \emph{distribution stationnaire} pour la marche aléatoire, c'est-à-dire une distribution de probabilités $\mu$ sur les sommets du graphe telle que si l'on choisit un sommet selon $\mu$ et que l'on réalise une étape de la marche, la probabilité de se retrouver quelque part est également gouvernée par $\mu$. De façon équivalente, en~voyant $\mu$ comme un vecteur de $\mathbb{R}^V$, il~existe une unique solution à $M\mu=\mu$, ce~qui découle du théorème de Perron-Frobenius. Dans notre cas simplifié où $M$ est symétrique, on~a même $\mu=(1, \ldots , 1)$ puisque $\mu^T M=\mu^t$ (les probabilités sortant d'un sommet somment à $1$) et $M$ est symétrique, et~donc la distribution stationnaire est la distribution uniforme. Notre problème se ramène ainsi à étudier un opérateur $M$ qui a un unique point fixe, pour voir s'il converge vers ce point fixe et, si oui, à quelle vitesse. Dans le cas où le graphe est $d$-régulier (c'est-à-dire que les degrés de tous les sommets ont la même valeur $d$) et que les probabilités sont uniformes (égales à $1/\deg^+(v)$ pour chaque arête autour d'un sommet~$v$, où~$\deg^+$ est le degré sortant du sommet), le~comportement de la marche est complètement gouverné par la géométrie du graphe~$G$, qui a donc un impact direct sur le temps que la marche aléatoire mettra à converger. Cet impact se caractérise de deux façons très différentes: \begin{enumerate} \item Il peut y avoir un problème de \emph{période}. Si le graphe $G$ est biparti, les temps pairs de la marche aléatoire seront toujours d'un côté de la bipartition, alors que les temps impairs seront toujours de l'autre. Dans ces conditions, il~est impossible que la marche aléatoire converge vers une distribution fixe. \item Il peut y avoir un problème d'\emph{expansion}. Par exemple, si le graphe $G$ est déconnecté, la marche ne pourra jamais passer d'une composante connexe à l'autre. De façon plus subtile, s'il est \emph{mal connecté}, comme illustré dans la figure~\ref{F:expansion}, quand bien même la marche finira par converger, le~goulot d'étranglement aura un fort impact sur le temps de convergence. \end{enumerate} \begin{figure}[t] \begin{center} \includegraphics[width=8cm]{expansion.pdf} \caption{À gauche, un graphe biparti dans lequel une marche aléatoire n'a aucune chance de converger. À droite, un goulot d'étranglement qui limitera fortement la vitesse de convergence d'une marche aléatoire.} \label{F:expansion} \end{center} \end{figure} Le premier problème est généralement résolu en rendant la marche aléatoire \emph{paresseuse}: on va modifier celle-ci pour qu'à chaque itération, avec probabilité $1/2$, on~reste paresseusement au même sommet, et~avec probabilité $1/2$ on se déplace comme indiqué par la matrice~$M$. Cela résout tous les problèmes de période, comme vous pouvez le vérifier sur notre exemple d'un graphe biparti. En~terme de graphe, cela revient à rajouter des boucles sur chaque sommet de $G$. Le deuxième problème est sensiblement plus épineux et constitue tout le n\oe{}ud du sujet. On~peut quantifier la connectivité d'un graphe $d$-régulier via la \emph{constante de Cheeger} qui est définie comme \[ h(G) = \min \Bigl\{\frac{|\partial A|}{d|A|} \Bigm| A \subseteq V,\; 0 < |A| \leq \frac{1}{2}|V(G)|\Bigr\}, \] où $\partial A$ désigne l'ensemble d'arêtes ayant exactement une extrémité dans $A$. Cette constante mesure dans quelle proportion des goulots d'étranglement séparent des gros morceaux du graphe. Dans l'exemple de la figure~\ref{F:expansion}, où il~y~a un goulot d'étranglement constitué par une arête coupant le graphe en deux, la constante de Cheeger $h(G)$ vaut donc environ $\sfrac{1}{d|V|/2}$. Plus cette constante est petite, moins le graphe est bien connecté. La matrice $M$ étant stochastique, par le théorème de Perron-Frobenius, sa plus grande valeur propre est $1$ et correspond à l'unique vecteur propre $\mathbf{1}:=(1, \ldots , 1)$. Il se trouve que la constante de Cheeger $h(G)$ est intimement reliée à la valeur de la \emph{deuxième} valeur propre $\lambda_2$, lorsqu'on les ordonne $\lambda_1 \geq \lambda_2 \ldots \geq \lambda_n$. Cela est généralement exprimé via le \emph{trou spectral} $\gamma:= \lambda_1 - \lambda_2=1-\lambda_2$: \begin{lemma}[inégalité de Cheeger] Pour tout graphe $G$ où tous les sommets sont de degré $d$, si on dénote par $\gamma$ le trou spectral de la matrice d'adjacence normalisée\footnote{La littérature en théorie spectrale des graphes utilise parfois la matrice d'adjacence, parfois la matrice laplacienne. Parfois elle les normalise et parfois non. Nous fixons ici le choix de matrices d'adjacence normalisées, qui est le choix naturel pour l'étude des marches aléatoires mais tous les résultats se transcrivent facilement d'un cadre à l'autre.} $M:=A(G)/d$, on~a: \[ h(G)^2/2 \leq \gamma \leq 2h(G). \] \end{lemma} \begin{proof} Nous prouvons juste la borne supérieure dans ces notes puisque c'est celle qui nous intéresse, et~renvoyons à~\cite[Th.\,13.3]{peres} pour la preuve complète. Notons par $n$ le nombre de sommets de $G$, il~y a donc $dn/2$ arêtes. La clé est d'exploiter les interprétations variationnelles (formules de Courant-Fischer) des valeurs propres. En~effet, comme $\mathbf{1}$ est vecteur propre associé à $\lambda=1$, on~a\vspace*{-3pt}\enlargethispage{\baselineskip} \[ \lambda_1(G)=\max_{x\neq 0} \frac{x^TMx}{x^Tx} \qquad\text{et}\qquad \lambda_2(G)=\max_{\substack{x\neq 0 \\ x \perp \mathbf{1}}}\frac{x^TMx}{x^Tx}, \] et donc\vspace*{-5pt} \[ 1-\lambda_2(G)=\min_{\substack{x\neq 0 \\ x \perp \mathbf{1}}} \frac{\sum_{u,v \in V}M_{u,v}(x_u-x_v)^2}{2x^Tx}=\min_{\substack{x\neq 0 \\ x \perp \mathbf{1}}} \frac{\sum_{u,v \in E}(x_u-x_v)^2}{2dx^Tx}. \] D'un autre côté,\vspace*{-5pt} \begin{align*} h(G) &= \min \Bigl\{\frac{|\partial A|}{d|A|} \mid A \subseteq V,\; 0 < |A| \leq \frac{1}{2}|V(G)|\Bigr\}\\ & = \min_{\substack{x \neq \mathbf{0} \\ x \in \{0,1\}^n\\ \sum_u x_u \leq n/2}} \frac{\sum_{u,v \in E}|x_u-x_v|}{d\sum_{u \in V} x_u} \\[-3pt] &\geq \min_{\substack{x \neq \mathbf{0}, x \neq \mathbf{1} \\ x \in \{0,1\}^n}} \frac{\sum_{u,v \in E}|x_u-x_v|}{2d(\sum_{u \in V} x_u)(n-\sum_{u \in V} x_u)/n} \\ &= \min_{\substack{x \neq \mathbf{0}, x \neq \mathbf{1} \\ x \in \{0,1\}^n}} \frac{\sum_{u,v \in E}(x_u-x_v)^2}{2d(\sum_{u \in V} x_u)(n-\sum_{u \in V} x_u)/n} \\ &= \min_{\substack{x \neq \mathbf{0}, x \neq \mathbf{1} \\ x \in \{0,1\}^n}} \frac{\sum_{u,v \in E}(x_u-x_v)^2}{2d\sum_{u,v \in V}(x_u-x_v)^2/n} \\ &\geq \min_{\substack{x \neq \mathbf{0}, x \neq \mathbf{1} \\ x \in \mathbb{R}^n}} \frac{\sum_{u,v \in E}(x_u-x_v)^2}{2d\sum_{u,v \in V}(x_u-x_v)^2/n} \\ &= \min_{\substack{x \neq \mathbf{0}, x \neq \mathbf{1} \\ x \in \mathbb{R}^n, x\perp \mathbf{1}}} \frac{\sum_{u,v \in E}(x_u-x_v)^2}{2d\sum_{u,v \in V}(x_u-x_v)^2/n} \\ &= \min_{\substack{x \neq \mathbf{0}, x \neq \mathbf{1} \\ x \in \mathbb{R}^n, x\perp \mathbf{1}}} \frac{\sum_{u,v \in E}(x_u-x_v)^2}{4dx^Tx} =\frac{1-\lambda_2(G)}{2}.\qedhere \end{align*} \end{proof} Pour obtenir une borne inférieure sur la constante de Cheeger, il~suffit donc d'obtenir une borne inférieure sur le trou spectral de la matrice de transition. Une autre façon d'analyser la convergence de la marche aléatoire, qui ne requiert pas d'hypothèse de régularité et qui prend en compte simultanément le problème de période et celui d'expansion, est de penser à $t$ étapes de la marche aléatoire comme une application de~$M^t$. En~diagonalisant $M$, on~voit que $M^t$ est semblable à la matrice $\diag(\lambda_1^t=1,\lambda_2^t, \ldots ,\lambda_n^t)$, et~donc les contributions qui ne sont pas celles de la distribution stationnaire $\mathbf{1}$, associée à la valeur propre $1$, disparaissent d'autant plus vite que $\lambda_*=\max(|\lambda_2|,|\lambda_n|)$ est faible, et~donc que le \emph{trou spectral absolu} $1-\lambda_*$ est grand. On~arrive ainsi à la proposition suivante, où le \emph{$\varepsilon$-temps de mélange} $t_\varepsilon$ d'une marche aléatoire est le temps au bout duquel, pour n'importe quelle distribution de départ, la distribution $\mu$ obtenue après $t_\varepsilon$ application de la marche aléatoire satisfait à $\|\mu-\mathbf{1}/n\|_1\leq \varepsilon$ (comparer avec la définition d'un FPAUS). \begin{proposition}\label{prop:mixingtime} Pour un graphe $G$ connexe et une marche aléatoire symétrique sur $n$ sommets, le~temps de mélange de la marche aléatoire satisfait à \[ t_\varepsilon=O\Bigl(\frac{\log{n/\varepsilon}}{1-\lambda_*}\Bigr). \] \end{proposition} \begin{proof} Soit $v_1, \ldots ,v_n$ une base orthonormale de $M$. Pour toute distribution de départ $\pi$, on~écrit $\pi=\sum_i \pi_i$ où chaque $\pi_i$ est un multiple de $v_i$. On~a $\pi_1 =\mathbf{1}/n$ puisque $\pi$ est une distribution de probabilité. Donc \begin{align*} \|M \pi - \mathbf{1}/n\|^2 &= \|M\pi_1+M\pi_2 + \ldots + M\pi_n -\mathbf{1}/n\|^2 \\ &= \|M\pi_2 + \ldots + M\pi_n\|^2\\ &\leq \lambda_*^2(\|\pi_2^2 + \ldots + \pi_n^2\|)\\ &= \lambda_*^2 \|\pi - \mathbf{1}/n\|^2. \end{align*} Et donc \[ \|M^{\ell} \pi - \mathbf{1}/n\| \leq \lambda_*^\ell \|\pi - \mathbf{1}/n\| \leq \lambda_*^\ell \|\pi\| \leq \lambda_*^\ell \|\pi\|_1 \leq \lambda_*^\ell. \] On conclut avec une application de Cauchy-Schwarz: \[ \|M^{\ell} \pi - \mathbf{1}/n\|_{1} \leq \|M^{\ell} \pi - \mathbf{1}/n\| \sqrt{n}, \] qui est donc au plus $\varepsilon$ pour \[ \ell=O(\sfrac{\log (\varepsilon/n)}{\log \lambda_*})=O(\spfrac{\log(n/\varepsilon)}{1-\lambda_*}).\qedhere \] \end{proof} Notons que la plus petite valeur propre $\lambda_n$ satisfait toujours à \hbox{$|\lambda_n \leq 1|$} pour une matrice stochastique, et~que lorsqu'on rend une marche paresseuse, on~ajoute $\Id/2$ à $M$. Cela a donc pour effet de pousser $\lambda_n$ loin de $-1$, et~donc de réconcilier le trou spectral qui intervient dans l'expansion avec le trou spectral absolu qui intervient dans la borne de la proposition~\ref{prop:mixingtime}. Pour analyser le trou spectral de notre marche d'échange de bases, on~se lance maintenant dans une longue digression. \section{Polynômes log-concaves} L'outil principal derrière la preuve du théorème~\ref{th:main} et de la proposition~\ref{prop:sampling} est l'étude d'une certaine classe de polynômes qui a l'air, de prime abord, complètement déconnectée de nos considérations de fiabilité et de comptage. \subsection{Définitions et mises en bouches} On considère des polynômes homogènes multivariés d'inconnues $z_1, \ldots , z_n$ et à coefficients réels positifs. On~dit qu'un tel polynôme $p$ est \emph{log-concave} sur $\mathbb{R}^n_{\geq 0}$ si $\log p$ est concave dans l'\emph{orthant positif} \[ \mathbb{R}^n_{\geq 0}:=\{z_1, \ldots, z_n \in \mathbb{R}^n \mid \forall i,\, z_i \geq 0\}. \] Pour que le logarithme soit défini, il~faut déjà que $p$ soit positif sur cet orthant positif, ce~qui est garanti par la positivité des coefficients. De façon équivalente, la log-concavité s'exprime comme la propriété que pour tous $u,v \in \mathbb{R}^n_{\geq 0}$ et $\lambda \in [0,1]$, on~a \[ p(\lambda u+(1-\lambda)v) \geq p(u)^\lambda \cdot p(v)^{1-\lambda}. \] Pour un vecteur $v \in \mathbb{R}^n$, on~désigne par $D_v$ la dérivée directionnelle par rapport à $v$, c'est-à-dire \[ D_v=\sum_{i=1}^n v_i \partial_i, \] où $\partial_i$ est la dérivée partielle $\sfrac{\partial}{\partial z_i}$. Un polynôme est dit \emph{complètement log-concave} si pour toute famille de vecteurs $v_1, \ldots , v_k \in \mathbb{R}^n_{\geq 0}$, le~polynôme $D_{v_1}\ldots D_{v_k}p$ est positif et log-concave sur $\mathbb{R}^n_{\geq 0}$. \begin{remark} Dans cette définition de polynôme complètement log-concave, il~est important de considérer les dérivées directionnelles et pas seulement les dérivées partielles. Par exemple, le~polynôme $p(z_1,z_2)=z_1^3+z_2^3$ a pour dérivées partielles $\partial_1p=3z_1^2$ et $\partial_2p=3z_2^3$ qui sont tous deux log-concaves, mais la dérivée directionnelle $(\partial_1+\partial_2)p=3z_1^2+3z_2^2$ n'est pas log-concave. On~verra plus loin (théorème~\ref{th:reduction}) qu'avec des hypothèses en plus, les dérivées partielles suffiront. \end{remark} Une propriété immédiate est la suivante: \begin{lemma}\label{lem:easy} Si $p(z_1, \ldots, z_n)$ est complètement log-concave, pour toute transformation affine $T:\mathbb{R}^m \rightarrow \mathbb{R}^n$ telle que $T(\mathbb{R}^m_{\geq 0}) \subseteq T(\mathbb{R}^n_{\geq 0})$, le~polynôme $p \circ T$ est complètement log-concave. \end{lemma} \begin{proof} Pour tout $u,v \in \mathbb{R}^m_{\geq 0}$ et pour tout $\lambda \in [0,1]$, \[ p(T(\lambda u+(1-\lambda)v))=p(\lambda T(u) + (1-\lambda)T(v)) \geq p(T(u))^\lambda p(T(v))^{1-\lambda}, \] puisque $T(u)$ et $T(v)$ sont dans $\mathbb{R}^n_{\geq 0}$ par hypothèse. Cela montre que la log-concavité est préservée sous l'action de $T$. Ensuite, comme $T$ est affine, $T(x)=Ax+b$ pour une matrice $A \in \mathbb{R}^{n \times m}_{\geq 0}$ et un vecteur $b \in \mathbb{R}^n_{\geq 0}$. Pour un ensemble de vecteurs $v_1, \ldots , v_k \in \mathbb{R}^m_{\geq 0}$, on~a $Av_1, \ldots, Av_k \in \mathbb{R}^n_{\geq 0}$ et donc $D_{Av_1}\ldots D_{Av_k}p$ est log-concave. On~conclut en observant que \[ D_{v_1}\ldots D_{v_k}(p \circ T)=(D_{Av_1}\ldots D_{Av_k}p)\circ T.\qedhere \] \end{proof} En particulier, fixer la valeur d'une inconnue d'un polynôme complètement log-concave à une valeur positive, ou bien projeter plusieurs inconnues sur une seule, sont deux opérations qui préservent la complète log-concavité. Cette observation, d'apparence inoffensive, va se révéler d'une efficacité redoutable dans ce qui suit. \subsection{Log-concavité et log-concavité} Un des résultats qui sous-tend le théorème~\ref{th:main} est le théorème suivant: \begin{theorem}[{\cite[Th.\,4.1]{anari2024logbis}}]\label{th:logconcave} Pour tout matroïde $M=(E,\mathcal{I})$ où $E$ est constitué de $n$ éléments, le~polynôme \[ g_M(y,z_1, \ldots, z_n)= \sum_{I\in \mathcal{I}} y^{n-|I|} \prod_{i\in I}z_i \] est complètement log-concave. \end{theorem} Le terme \emph{log-concave} fait écho à la log-concavité des \emph{coefficients} de certains polynômes, comme les polynômes de volumes mixtes explorés dans le texte de Mathieu Piquerez \cite{piquerez}. Récemment, Karim Adiprasito, June Huh et Eric Katz~\cite{huh2012milnor,huh2012log,adiprasito2018hodge} ont montré que le \emph{polynôme caractéristique} (Nous renvoyons au texte d'Omid Amini \cite{amini} pour la définition) $\chi_M(\lambda)=\sum a_k \lambda^k$ d'un matroïde a des coefficients log-concaves, c'est-à-dire que ceux-ci satisfont à $|a_{k-1}|\,|a_{k+1}| \leq |a_k|^2$ pour tout $1 \leq k \leq r$. Ce résultat majeur, originellement conjecturé par Read~\cite{read1968introduction} et Hoggar~\cite{hoggar1974chromatic} pour les graphes, puis par Rota~\cite{rota1970combinatorial}, \hbox{Heron}~\cite{heron1972matroid} et Welsh~\cite{welsh1971combinatorial} pour les matroïdes, a été cité lors de l'obtention de la médaille Fields par June Huh. Les techniques d'Adiprasito, Huh et Katz s'appliquent aussi à la suite $f_k(M)$ qui dénombre le nombre d'ensemble indépendants de taille $k$ d'un matroïde $M$: \begin{theorem}[{\cite[Conj.\,1.2]{adiprasito2018hodge}}, corollaire de leur théorème~1.4]\label{th:masonweak} La suite $f_k(M)$ est log-concave: \[ f_{k-1}(M)f_{k+1}(M) \leq f_k(M)^2 \text{ pour tout $1\leq k\leq r$}. \] \end{theorem} Ce théorème prouve une conjecture de Mason~\cite{mason1972matroids}, qui a même conjecturé que les nombres $f_k(M)$ satisfont une propriété plus forte, appelée \emph{ultra log-concavité}: \[ f_k(M)^2 \geq \Bigl(1+\frac{1}{k}\Bigr) \cdot \Bigl(1+\frac{1}{n-k}\Bigr) \cdot f_{k-1}(M) \cdot f_{k+1}(M), \] ou de façon équivalente: \[ \biggl(\frac{f_k(M)}{\binom{n}{k}}\biggr)^2 \geq \frac{f_{k-1}(M)}{\binom{n}{k-1}} \cdot \frac{f_{k+1}(M)}{\binom{n}{k+1}}. \] Il n'y a, a priori, aucune raison pour que les propriétés de convexité d'un polynôme, vu en tant que fonction, aient un lien avec d'éventuelles propriétés de convexité de ses coefficients. Pourtant, la proposition suivante, d'abord établie par Gurvits~\cite{gurvits09}, montre une telle coïncidence pour les polynômes complètement log-concaves: \begin{proposition}[{\cite[Prop.\,5.1]{anari2024logbis} et \cite[Prop.\,2.7]{gurvits09}}]\label{prop:ulc} Si \[ p(y,z)=\sum_{k=1}^n c_k y^{n-k}z^k \] est complètement log-concave et $n\geq 2$, alors la suite $c_0, \ldots , c_n$ est ultra log-concave. \end{proposition} La preuve ferait peut-être un bon exercice difficile de khôlle. \begin{proof} Comme $p$ est complètement log-concave, cela implique que pour tout $k$ tel que $10}$, $x^TQx=2q(x)>0$ puisque $p$ et donc $q$ ont des coefficients positifs. Le~déterminant de $Q$ est donc négatif. Cela implique immédiatement le résultat. \end{proof} Cette preuve montre plus généralement que la matrice hessienne de tout polynôme log-concave de degré au moins deux, évaluée en un point de l'orthant positif, a exactement une valeur propre strictement positive. Nous verrons plus tard une réciproque de cette propriété. Le théorème~\ref{th:logconcave} implique via le lemme~\ref{lem:easy} que $g_M(y, z, \ldots ,z)=\sum_k f_k(M)y^{n-k}z^k$ est complètement log-concave. Avec cette proposition, on~obtient donc directement la conjecture la plus forte de \hbox{Mason}. Cela renforce donc un des résultats phares d'Adiprasito, Huh et Katz~\cite{adiprasito2018hodge}, obtenu initialement avec des techniques inspirées de la théorie de Hodge. Il y a donc quelque chose de très puissant qui se cache derrière ces polynômes (complètement) log-concaves. De façon encore plus remarquable, la preuve du théorème~\ref{th:logconcave} est suffisamment simple pour être entièrement incluse dans ces notes. \subsection{Inspiration} Avant de plonger dans la preuve du théorème~\ref{th:logconcave}, il~est instructif de prendre un peu de recul pour expliquer d'où viennent ces polynômes log-concaves. L'inspiration première est la classe des \emph{polynômes à racines réelles}, polynômes univariés dont le nom contient la définition. \begin{lemma}\label{lem:realroots} Soit $f$ un polynôme à racines réelles et à coefficients positifs. Alors $f$ est une fonction log-concave de $\mathbb{R}_{\geq 0}$. \end{lemma} \begin{proof} On néglige le coefficient du monôme de plus haut degré qui n'importe pas. En~nommant $\alpha_i$ les racines de $f$, on~a alors \[ \log f= \log \prod_{i=1}^n (x-\alpha_i) = \sum_{i=1}^n \log (x -\alpha_i). \] Comme les coefficients sont positifs, les racines sont négatives, et~donc $\log f$ est une somme de fonctions concaves sur $\mathbb{R}_{\geq 0}$ et est ainsi elle-même concave. \end{proof} Notez que si un polynôme a des racines réelles, tous ses polynômes dérivés également. Cela découle par exemple du théorème de Gauss-Lucas, qui place en général les racines complexes d'un polynôme dérivé $p'$ dans l'enveloppe convexe de celles de $p$. On~obtient donc également la log-concavité complète. L'articulation entre la log-concavité d'un polynôme et celle de ses coefficients est alors une généralisation très puissante de l'équivalence entre \og $ax^2 +bx +c$ a une racine réelle\fg et \og $b^2 -4ac\geq 0$\fg (pour $a\neq 0$), où le coefficient $4$ est celui qui sort de la propriété d'ultra log-concavité. Dans le cas général de polynômes à racines réelles, le~résultat d'ultra-log-concavité des coefficients, qui découle donc de notre proposition~\ref{prop:ulc} et du lemme~\ref{lem:realroots}, constitue les \emph{inégalités de Newton}, qui sont plus généralement exprimées via l'expression des coefficients d'un polynôme comme polynôme élémentaire symétrique de ses racines. Une première tentative de généraliser les polynômes à racines réelles au cas multivarié est la classe des \emph{polynômes réels stables} (souvent juste appelés \emph{polynômes stables}), qui sont les polynômes réels $p$ tels que pour tout $a \in \mathbb{R}^n_{>0}$ et $b\in \mathbb{R}^n$, le~polynôme univarié $p(at+b)$ n'est pas nul et a des racines réelles. Une des motivations de cette généralisation est qu'une méthode très puissante pour montrer qu'un polynôme univarié a des racines réelles est d'en définir une version multivariée et de montrer que celle-ci est réelle stable. Dans le cas multi-affine, c'est-à-dire lorsqu'une variable n'apparaît jamais avec un degré plus grand que $1$ dans un monôme, il~y a une connexion frappante entre les polynômes réels stables et la théorie des matroïdes. Le~\emph{support} d'un polynôme est l'ensemble des collections d'indices de ses monômes non nuls. \begin{theorem}[Choe, Oxley, Sokal, Wagner~{\cite[Th.\,7.1]{chloe}}]\label{th:realstable} Le support de tout polynôme réel stable homogène multi-affine est l'ensemble des bases d'un matroïde. \end{theorem} Cependant, la réciproque n'est pas vraie, par exemple Brändén~\cite{branden2007polynomials} a montré qu'un certain matroïde appelé matroïde de Fano n'est le support d'aucun polynôme réel stable homogène. Cela a motivé l'introduction des polynômes complètement log-concaves, qui sont une classe strictement plus large, et~dont les coefficients satisfont aux mêmes propriétés d'ultra-log-concavité que les polynômes à racines réelles et les polynômes réels stables, et~pour lesquels la réciproque voulue au théorème~\ref{th:realstable} est vraie: elle est donnée par le théorème~\ref{th:logconcave}. \subsection{Réduction au cas quadratique} La preuve du théorème~\ref{th:logconcave} repose sur une astucieuse réduction au cas quadratique. On~dit qu'un polynôme $p$ est \emph{indécomposable} si on ne peut pas l'écrire comme une somme $p=p_1+p_2$ où $p_1$ et $p_2$ sont des polynômes non nuls ayant des ensembles de variables disjoints. \begin{lemma} Un polynôme log-concave de degré au moins $2$ est indécomposable. \end{lemma} \begin{proof} Supposons par l'absurde que $p$ log-concave s'écrit $p=p_1+p_2$ avec $p_1$ et $p_2$ non nuls et ayant des variables disjointes. La matrice hessienne de $p$ s'écrit \[ \nabla^2 p =\begin{pmatrix}\nabla^2 p_1 & 0 \\ 0 & \nabla^2 p_2\end{pmatrix}. \] Puisque $p_1$ et $p_2$ peuvent être obtenus de $p$ en mettant certaines variables à zéro, ils sont tous les deux log-concaves par le lemme~\ref{lem:easy}, et~donc leurs hessiennes ont chacune une valeur propre strictement positive. Donc la hessienne de $p$ en a au moins deux, ce~qui contredit la log-concavité (\cf la preuve de la proposition~\ref{prop:ulc}). \end{proof} Réciproquement, le~résultat de réduction quadratique suivant montre que l'indécomposabilité permet de réduire la log-concavité complète au cas quadratique. Pour un vecteur $\alpha \in \{1, \ldots , n\}^k$, on~écrit $\partial^\alpha$ pour $\partial_{\alpha_1} \circ \ldots \circ \partial_{\alpha_k}$. \begin{theorem}\label{th:reduction} Soit $p$ un polynôme homogène à coefficients positifs de degré $d \geq 2$. Le~polynôme $p$ est complètement log-concave si et seulement si les deux conditions suivantes sont satisfaites: \begin{enumerate} \item Pour tout $\alpha \in \mathbb{Z}^n_{\geq 0}$, avec $|\alpha|\leq d-2$, le~polynôme $\partial^\alpha p$ est indécomposable. \item Pour tout $\alpha \in \mathbb{Z}^n_{\geq 0}$, avec $|\alpha|= d-2$, le~polynôme quadratique $\partial^\alpha p$ est log-concave. \end{enumerate} \end{theorem} On commence par établir quelques lemmes. Le~premier est la réciproque d'une observation précédente qui montre que la propriété d'avoir une matrice hessienne ayant exactement une valeur propre positive caractérise les polynômes log-concaves. \begin{lemma}\label{lem:lorentzien} Si $p$ est un polynôme homogène à coefficients positifs à $n$ variables et de degré $d\geq 2$, et~$a \in \mathbb{R}^n_{\geq 0}$, alors si $\nabla^2p_{|z=a}$ a exactement une valeur propre strictement positive, $p$ est log-concave en $a$. \end{lemma} \begin{proof} Comme précédemment, on~calcule \[ \nabla^2 \log(p) = \frac{p \cdot \nabla^2p - \nabla p \nabla p^T}{p^2}. \] L'une des nombreuses identités d'Euler est que pour un polynôme homogène de degré $d$, on~a $dp(z_1, \ldots, z_n)=\sum_i z_i \partial_ip(z_1, \ldots, z_n)$. On~a donc, en~notant $P:=\nabla^2p_{|z=a}$, que $Pa=(d-1)\nabla p(a)$ et $a^TPa=d(d-1)\cdot p(a)$. Ainsi, \[ \nabla^2 \log(p) = d(d-1)\frac{a^TPa \cdot P - \frac{d}{d-1}(Pa)(Pa)^T}{(a^TPa)^2}. \] Il s'agit donc d'étudier les valeurs propres de $a^TPa \cdot P - \frac{d}{d-1}(Pa)(Pa)^T\!$. On~commence par étudier celles de $a^TPa \cdot P - (Pa)(Pa)^T$. Pour ce faire, prenons $x$ dans $\mathbb{R}^n$. Par hypothèse, $P$ est une forme quadratique qui est négative sur un espace vectoriel de dimension $n-1$ qu'on appelle $L$. \begin{itemize} \item Si $x$ est colinéaire à $a$, \[ x^T(a^TPa \cdot P - (Pa)(Pa)^T)x= a^TPa x^TPx - x^TPa a^TPx = 0. \] \item Sinon, une combinaison linéaire $y$ de $x$ et de $a$ intersecte $L$. On~considère la forme quadratique induite par $P$ dans le sous-espace engendré par $x$ et $a$: elle n'est pas négative parce que $a^TPa>0$, mais elle n'est pas positive non plus puisque $y^TPy\leq 0$. Donc son déterminant est négatif, et~par suite \[ x^T(a^TPa \cdot P - (Pa)(Pa)^T)x= a^TPa x^TPx - x^TPa a^TPx \leq 0. \] \end{itemize} Ainsi, la forme quadratique associée à $a^TPa \cdot P - (Pa)(Pa)^T$ est négative. C'est encore le cas lorsqu'on soustrait $\frac{1}{d-1}(Pa)(Pa)^T$, ce~qui conclut la preuve. \end{proof} \begin{remark} Cette propriété justifie l'appellation de \emph{polynôme lorentzien} utilisée par Brändén et Huh~\cite{branden2020lorentzian}, qui est équivalente à notre notion de polynôme complètement log-concave. En~effet, la signature de la hessienne d'un polynôme log-concave à coefficients positifs est $(+,-, \ldots , -)$, et~de telles signatures sont appelées \emph{lorentziennes} de par leur usage en théorie de la relativité générale. Cette propriété d'avoir exactement une valeur propre strictement positive est une incarnation combinatoire des relations de Hodge-Riemann en degrés $q \leq1$, qui fournissent de manière similaire des formes bilinéaires ayant exactement une valeur propre strictement positive. Comme illustré dans les textes d'Omid Amini \cite{amini} et de Mathieu Piquerez \cite{piquerez}, les applications combinatoires de ces relations de Hodge-Riemann découlant généralement de ce cas particulier de bas degré (voir par exemple l'article de survol de June Huh~\cite{huh2018combinatorial}), les polynômes complètement log-concaves (ou lorentziens) permettent ainsi d'extraire le sel combinatoire de ces constructions algébriques. \end{remark} Bien qu'immédiate, la propriété suivante est la clé qui différencie les polynômes log-concaves des polynômes réels stables, qui n'ont pas d'analogue. \begin{lemma}\label{lem:descent} Pour un polynôme $p$ homogène de degré $d \geq 3$, $p$ est log-concave en $z=a$ si et seulement si $D_ap$ est log-concave en $z=a$ \end{lemma} \begin{proof} Cela découle immédiatement de la même identité d'Euler que celle utilisée dans le lemme précédent, stipulant que que $dp(z_1, \ldots, z_n)=\sum_i z_i \partial_ip(z_1, \ldots, z_n)$. \end{proof} Un dernier lemme permet d'additionner des polynômes log-conca\-ves sous certaines conditions. \begin{lemma}\label{lem:cle} Si $p_1$ et $p_2$ sont homogènes, à coefficients positifs, complètement log-concaves et s'il existe $b,c \!\in\! \mathbb{R}^n_{\geq 0}$ tels que $D_b p_1=D_c p_2 \neq 0$, alors $p_1+p_2$ est complètement log-concave. \end{lemma} \begin{proof} Par le lemme~\ref{lem:lorentzien}, il~suffit de vérifier que la hessienne $\nabla^2(p_1+p_2)_{|z=a}$ a exactement une valeur propre positive pour tout $a \in \mathbb{R}^n_{\geq 0}$. On~note comme avant $P_1=\nabla^2(p_1)_{|z=a}$ et $P_2=\nabla^2(p_2)_{|z=a}$. Comme $D_bp_1=D_cp_2$, $p_1$ et $p_2$ ont le même degré, et~on a $P_1b=P_2c$ puisque pour tout $i=1, \ldots, n$, \[ (P_1b)_i=(\partial_i D_bp_1)_{|z=a}=(\partial_iD_cp_2)_{|z=a}=(P_2b)_i. \] Comme $D_bp_1 =D_cp_2\neq 0$, $P_1b=P_2c$ sont non nuls et ont des coefficients positifs puisque c'est le cas pour $p_1$, $p_2$, $b$ et~$c$. Donc~$P_1$ et~$P_2$ sont toutes deux des formes quadratiques négatives sur $(P_1b)^{\perp}=(P_2c)^{\perp}$ qui sont des sous-espaces de dimension $n-1$. Il~en résulte que $P_1+P_2$ est également une forme quadratique négative sur un espace de dimension $n-1$, ce~qui conclut. \end{proof} Nous avons maintenant tous les éléments pour prouver le théorème~\ref{th:reduction}. L'idée est de descendre en degré via le lemme~\ref{lem:descent}. Pour cela, il~faut montrer que les dérivées directionnelles $D_ap$ sont log-concaves si les dérivées directionnelles $\partial_ip$ le sont. Cela sera garanti par le lemme~\ref{lem:cle}, l'indécomposabilité et l'identité $\partial_i\partial_j=\partial_j\partial_i$. \begin{proof}[Démonstration du théorème~\ref{th:reduction}] Le théorème se prouve par récurrence sur le degré $d$. Pour $d=2$, il~n'y a rien à faire, ce~qui fait la base de la récurrence. On~suppose ensuite que le théorème est vrai pour tous les polynômes de degré $d-1$. Prenons un polynôme $p$ homogène de degré $d\geq 3$ satisfaisant les hypothèses du théorème, et~regardons $D_{v_1}\cdots D_{v_k}p$ pour tous $v_1, \ldots , v_k \in \mathbb{R}^k_{\geq 0}$ et $0\leq k\leq d-2$. Si $k=0$, par le lemme~\ref{lem:descent}, $p$ est log-concave en $a$ si et seulement si $D_ap$ l'est, donc on ramène le cas $k=0$ au cas $k=1$. Remarquons ensuite qu'une façon équivalente d'exprimer l'indécomposabilité d'un polynôme $p$ est que le graphe où les sommets sont les $i$ tels que $\partial_i p \neq 0$ et les arêtes sont les $i,j$ tels que $\partial_i \partial_jp \neq 0$ est connexe. Par indécomposabilité, on~peut donc supposer, quitte à renuméroter, que pour tout $i$, $\partial_i p \neq 0$ (quitte à jeter les variables pour lesquelles la dérivées est nulle), et~que pour tout $j\geq 2$, il~existe $i0$. On~va montrer la log-concavité de $g_M$ en $a$, ce~qui implique la log-concavité dans tout l'orthant positif parce que la hessienne ne dépend pas de $a$. Par le même calcul que dans la preuve du lemme~\ref{lem:lorentzien}, cela revient à montrer que $Q'=a^TQa\cdot Q-(Qa)(Qa)^T$ est négative. On~obtient \[\arraycolsep4pt Q'_{|a^{\perp}}=(n-1)(nB-(n-1)\mathbf{1})=(n-1)\cdot \left(\mathbf{1} - n\begin{pmatrix}\mathbf{1} & \mathbf{0} & \ldots &\mathbf{0} \\\mathbf{0} & \mathbf{1} &\ldots & \mathbf{0} \\ & & \ddots & \mathbf{0}\\ \mathbf{0} & \ldots & \mathbf{0} & \mathbf{1}\end{pmatrix}\right). \] Or, pour tout vecteur $x$, \begin{align*} Q'_{|a^{\perp}}(x)&=(n-1)\biggl(\sum_i x_i^2-n \sum_i \Bigl(\sum_{j\in P_i} x_j\Bigl)^2\biggl)\\ &=(n-1)\biggl(\sum_i \sum_{j\in P_i} x_j^2-n \sum_i \Bigl(\sum_{j\in P_i} x_j\Bigr)^2\biggr)\leq 0, \end{align*} en utilisant Cauchy-Schwarz et le fait qu'il~y~a au plus $n$ blocs dans~$B$. \end{proof} On peut maintenant conclure la preuve du théorème~\ref{th:logconcave} \begin{proof}[Démonstration du théorème~\ref{th:logconcave}] Par le théorème~\ref{th:reduction}, il~suffit de tester l'indécomposabilité de tous les polynômes $\partial^\alpha g_M$ pour $|\alpha| \leq d-2$ et la log-concavité des polynômes $\partial^\alpha g_M$ pour $|\alpha| = d-2$. On~décompose $\alpha=\alpha_1+\alpha_2$ où $\partial^{\alpha_2}=\partial_y^k$. Ensuite, si $\alpha_1$ contient le même indice plusieurs fois, le~polynôme est nul, donc on peut considérer que $\alpha_1$ est la fonction indicatrice d'un ensemble $J$. De manière similaire, si~$J$ n'est pas un ensemble indépendant, $\partial^{\alpha_1}$ est nul, et~on voit alors que $\partial^{\alpha_1} g_M$ est exactement le polynôme $g_{M / J}$ du matroïde où l'on a contracté $J$. Par les bornes sur les tailles des $\alpha$, les matroïdes $M /J$ sont de rang au moins $2$, et~donc le variable $y$ apparaît dans un monôme avec tous les éléments de $M /J$ qui ne sont pas des boucles. Cela prouve l'indécomposabilité. La log-concavité des polynômes $\partial^\alpha g_M$ pour $|\alpha|=d-2$ découle alors du fait que qu'il s'agit des polynômes $g_M'$ pour des matroïdes $M'=M \setminus J$ où l'on a tronqué la taille des ensembles indépendants pour qu'il soient de taille au plus $2$. Ce sont donc des matroïdes de rang $2$, et~la proposition~\ref{prop:rank2} permet de conclure. \end{proof} \section{Complexes simpliciaux et théorème local-global pour l'expansion en grande dimension} Revenons maintenant au problème de compter les bases de matroïdes, que nous avons réduit au problème de borner la seconde valeur propre (en valeur absolue) de la marche aléatoire d'échange de bases. Nous commençons par un exemple pour illustrer l'application des polynômes log-concaves à ce problème. \subsection{Un exemple illustratif} Considérons le polynôme symétrique $p=\sum_{1 \leq i< j\leq 4} x_ix_j$, qui est le polynôme des bases d'un matroïde sur~$4$~éléments où tous les ensembles de deux éléments distincts sont des bases. La marche d'échange des bases sur ce matroïde considère une base, en~retire un élément puis en remet un. Elle commence donc par \og descendre\fg dans le matroïde avant de \og remonter\fg, et~on l'appelle marche \emph{bas-haut}. De manière similaire, on~peut définir une marche \emph{haut-bas} qui part d'un ensemble indépendant de taille~$1$, ajoute un élément puis en retire un pour revenir à une taille~$1$. Cette marche haut-bas a pour matrice de transition \[\arraycolsep4pt M=\begin{pmatrix} 1/2 & 1/6 & 1/6 & 1/6 \\ 1/6 & 1/2 & 1/6 &1/6 \\ 1/6 & 1/6 & 1/2 & 1/6 \\ 1/6 & 1/6& 1/6 & 1/2\end{pmatrix}. \] En effet, partant d'un élément $i$, la probabilité de monter à $ij$ est de $1/3$ pour chaque $j \neq i$, puis celle de redescendre à $j$ est de $1/2$. La probabilité de rester en $i$ au final est de $3 \cdot 1/3 \cdot 1/2=1/2$. Comparons cette matrice avec la matrice hessienne de $p$, qui est \[\arraycolsep5pt P=\nabla^2p=\begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 &0 & 1 & 1 \\ 1 &1 & 0 & 1 \\ 1 &1 & 1 & 0\end{pmatrix}. \] On observe que $M= \Id/2 + 1/2 (P/3)$. La marche haut-bas est donc exactement celle obtenue lorsqu'on rend paresseuse (\cf section~\ref{sec:mixing}) la matrice de transition associée à $\nabla^2p/3$. Et la propriété de log-concavité de $p$ a le versant spectral suivant sur $M$: comme $p$ est log-concave, $P$ a exactement une valeur propre positive, et~donc c'est aussi le cas pour $P/3$. Il s'ensuit que la seconde valeur propre de $M= \Id/2 + 1/2 (P/3)$ a pour valeur au plus $1/2$. Le~trou spectral est donc constant, et~la marche est paresseuse, et~ainsi la marche aléatoire se mélange très vite. La matrice $M$ étant la matrice de la marche haut-bas, elle peut s'écrire $M=1/6 \cdot A A^T$ où la matrice $A$, de taille $4 \times 6$, est la matrice \[ A_{i,jk}=\begin{cases}1& \text{si $i\in\{j,k\}$,}\\0&\text{sinon.}\end{cases} \] C'est la marche bas-haut qui nous intéresse, et~non la marche haut-bas. Mais il est facile de voir que celle-ci s'écrit $M'=1/6 \cdot A^TA$. Elle a donc les mêmes valeurs propres que $M$, et~donc le même trou spectral (absolu)! Nous voyons bien ici comment la propriété de log-concavité intervient pour obtenir un mélange rapide de la marche d'échange des bases. \subsection{Complexes simpliciaux} Cet exemple ne se généralise pas facilement aux matroïdes de rang supérieur. En~effet, en~général la matrice hessienne du polynômes des bases d'un matroïde ne contrôle pas la marche d'échange des bases, mais seulement une version \emph{locale}: en considérant un ensemble indépendant $S$ du matroïde, la matrice hessienne de la dérivée $\partial^S g_M$ décrit (à un changement d'échelle près) une marche aléatoire consistant à rajouter et à enlever des éléments à un ensemble indépendant qui contient $S$. L'ingrédient manquant est donc une façon de recoller l'expansion de ces marches locales pour obtenir une borne sur la marche globale. Il se trouve que l'étude de telles propriétés locales-globales d'expansion, qui généralisent de façon très subtile les propriétés d'expansion dans les graphes que nous avons esquissées dans au paragraphe~\ref{sec:mixing}, a été l'objet d'une très forte attention dans les quinze dernières années, et~nous renvoyons à l'arti\-cle de survol de Lubotzky~\cite{lubotzky2018high} pour un aperçu (déjà un peu daté) du sujet. Cela fait appel à des techniques venant de l'étude des \emph{expanseurs en grande dimension}, dont nous commençons par introduire le langage. Un \emph{complexe simplicial} $\Delta$ est un ensemble de sous-ensembles de $\{1, \ldots , n\}$, stable par inclusion, c'est-à-dire que si $T$ est un élément de $\Delta$, tous ses sous-ensembles $S \subseteq T$ sont également dans $\Delta$. Il est \emph{pur} de dimension $d-1$ si tous les sous-ensembles maximaux sont de taille $d$. Il est immédiat de voir que les ensembles indépendants d'un matroïde forment un complexe simplicial de dimension $r-1$, où $r$ est le rang. Pour un complexe simplicial $\Delta$, on~note $\Delta(k)$ l'ensemble des \emph{simplexes} de dimension $k-1$: $\Delta(k)=\{S \in \Delta \mid |S|=k\}$, et~pour tout $S \in \Delta$, on~définit un autre complexe, le~\emph{lien} $\link_S(\Delta)$ qui correspond aux différentes façons de compléter un ensemble $S$ en restant dans $\Delta$, c'est-à-dire $\link_S(\Delta):=\{T \subseteq \{1, \ldots , n\} \subseteq S \mid S \cup T \in \Delta\}$. Si~l'on associe des poids $w(S)$ à chaque simplexe de dimension maximale~$d$, qui représentent des probabilités, ces poids descendent récursivement aux dimensions inférieures en définissant pour $S \in \Delta(k)$, $w(S)=\sum_{S\subseteq T, |T|=k+1}w(T)$. On~utilisera toujours, par la suite, des poids uniformes sur les simplexes de dimension maximale, qui représentent donc notre quête d'échantillonner de façon uniforme les bases d'un matroïde. On peut maintenant associer un polynôme à tout complexe simplicial $\Delta$, pur de dimension $d$, avec des poids $w$: \[ (\Delta,w) \mto p=\sum_{T\in \Delta(d)}w(T)z^T. \] Le complexe $\link_S(\Delta)$ a alors pour polynôme \[ (\link_S(\Delta),w) \mto p=\sum_{\substack{T\in \Delta(d)\\S\subseteq T}}w(T)z^{T\setminus S}=\partial^Sf. \] Dans ce langage, la marche d'échange de bases est la marche bas-haut qui part d'un simplexe de $\Delta(d)$ (où $d=\text{rang}-1$), retire un élément au hasard pour arriver à un simplexe de $\Delta(d-1)$ puis en rajoute un au hasard (potentiellement le même) pour remonter à $\Delta(d-1)$. La formule définissant les poids récursivement a été spécifiquement conçue pour que les probabilités d'ajout et de soustraction soient gouvernées par les poids $w$. De manière similaire, on~peut définir la marche \emph{haut-bas} qui part de $\Delta(d-1)$, ajoute un élément puis en retire un pour revenir à $\Delta(d-1)$, et~même définir de telles marches haut-bas et bas-haut pour pour chaque ensemble $\Delta(k)$ de simplexes de dimension $k$. \subsection{Théorème local-global} On veut maintenant démontrer le théorème suivant, où l'on choisira un ensemble de poids uniforme sur les simplexes de dimension maximale. \begin{theorem}\label{th:bashaut} Si $p=\sum_{T\in \Delta(d)}w(T)z^T$ est complètement log-concave, la matrice de transition pour la marche \emph{bas-haut} de $\Delta(d)$ satisfait $\lambda_*=\max(\lambda_2,\lambda_n) \leq 1-1/d$. \end{theorem} De façon concomitante aux travaux de~\cite{anari2024log}, Kaufman et Oppenheim~\cite{kaufman2020high} ont démontré le théorème suivant qui fournit miraculeusement la pièce manquante du puzzle. On~dit que $(\Delta,w)$ est un \emph{expanseur spectral} $\lambda$-local si $\lambda_2(P_S) \leq \lambda$ pour tout $S \in \Delta$, où $P_S$ est la matrice définie par \[ (P_S)_{i,j}=\frac{w(S\cup i \cup j)}{w(S \cup i)} \quad\text{pour $i,j \not\in S$}. \] \begin{theorem}[Kaufman, Oppenheim~{\cite[Th.\,1.4]{kaufman2020high}}]\label{th:trickledown} Si $(\Delta,w)$ est un expanseur spectral $\lambda$-local, alors la matrice de transition pour la marche bas-haut sur $\Delta(d)$ satisfait à: \[ \lambda_* \leq 1-\Bigl(\frac{1}{d}-\frac{d-1}{2}\lambda\Bigr). \] \end{theorem} Une force de ce théorème est qu'il permet d'analyser la marche aléatoire d'échanges de bases, qui est potentiellement très complexe, impliquant jusqu'à $n^r$ éléments et explorant tout le matroïde, en~terme de marche aléatoires locales dans le voisinage de chaque ensemble indépendant: en particulier la matrice $P_S$ n'a que $n^2$ entrées. La proposition suivante permet alors de recoller tous les morceaux. \begin{proposition}\label{spectralprop} Si $p=\sum_{T\in \Delta(d)}w(T)z^T$ est complètement log-concave, alors $(\Delta,w)$ est un expanseur spectral $0$-local. \end{proposition} \begin{proof} Il suffit d'observer que $P_S$ est la matrice hessienne de $\partial^Sp$ évaluée en $z=\mathbf{1}$, modulo la multiplication par une matrice diagonale à coefficients positifs pour rendre cette dernière stochastique. Par log-concavité de $p$, $P_S$ a donc exactement une valeur propre positive, ce~qui est maintenu par la multiplication par une matrice diagonale à coefficients positifs, et~donc $(\Delta,w)$ est bien un expanseur spectral $0$-local. \end{proof} La réciproque de cette proposition est également vraie, nous renvoyons à~\cite{anari2024log} pour la preuve. On~peut maintenant conclure. \begin{proof}[Démonstration du théorème~\ref{th:main}] Pour un système de poids uniforme sur $\Delta(d)$, le~théorème~\ref{th:logconcave} montre que le polynôme $p=\sum_{T\in \Delta(d)}z^T=\sum_{B\in\mathcal{B}(M)} \prod_{i \in B} z^i$ est complètement log-concave, et~donc on peut appliquer la proposition~\ref{spectralprop} et le théorème~\ref{th:trickledown} pour borner la seconde valeur propre de la marche d'échange des bases. La marche d'échange des bases est symétrique et connexe donc par la proposition~\ref{prop:mixingtime}, cela donne un algorithme efficace pour échantillonner uniformément des bases de matroïde. Avec le théorème~\ref{th:jerrum} qui utilise cette échantillonnage pour compter les bases, nous obtenons enfin la preuve du théorème~\ref{th:main}. \end{proof} \begin{remark} La propriété lorentzienne des polynômes log-concaves ne donne a priori qu'un contrôle sur le trou spectral des marches $P_S$, et~pas sur le trou spectral absolu. Mais comme illustré dans l'exemple, il~se trouve que la marche d'échange des bases est naturellement paresseuse. De façon remarquable, le~théorème~\ref{th:trickledown} montre que les valeurs propres négatives des $P_S$ ne sont pas un obstacle pour trouver une borne sur le trou spectral absolu de la marche globale. \end{remark} La preuve du théorème~\ref{th:trickledown} n'est pas très difficile mais nous ne la détaillerons pas dans ces notes et renvoyons à~\cite{kaufman2020high} ou à~\cite[\S\,4]{anari2024log} où le théorème est reprouvé. L'idée est que pour passer des marches locales indiquées par les $P_S$ à la marche globale que l'on veut contrôler, on~procédera par récurrence en montant de dimension progressivement. Le~cas de base de la récurrence est similaire à celui de l'exemple. Ensuite, on~combinera deux outils. Le~premier est la même observation que celle que nous avons faite dans l'exemple introductif: la~marche haut-bas sur $\Delta(k)$ et la marche bas-haut sur $\Delta(k-1)$ ont les mêmes valeurs propres. L'autre outil est que la propriété d'expan\-sion spectrale 0-locale permet de relier les valeurs propres de la marche bas-haut sur $\Delta(k)$ à celles de la marche haut-bas sur $\Delta(k)$. La combinaison de ses deux outils permet d'arriver à la conclusion sur la marche bas-haut des simplexes de dimension maximale et de conclure. Pour un matroïde sur $n$ éléments et de rang $r$, l'algorithme d'échantillonnage utilise une marche aléatoire en $O(r \log(n^r/\varepsilon))=O(r^2 \log(n/\varepsilon))$ étapes. Peu après~\cite{anari2024log}, une analyse plus fine a été proposée par Cryan, Guo et Mousa~\cite{cryan2021modified}, puis dans le quatrième papier de la série sur les polynômes log-concaves~\cite{anari2021log}, où les auteurs ont établi une borne $O(r \log(r/\varepsilon))$ qui est optimale. Notons que chaque étape de la marche aléatoire requiert d'échantillonner parmi les $n$ éléments du matroïde, donc la complexité de l'algorithme d'échantillonnage qui en résulte est $O(nr \log(r/\varepsilon))$. \begin{remark}\label{rem:clc} Comme on l'a vu tout au long de ce texte, la possibilité de pouvoir prendre des dérivées (directionnelles ou non) et de conserver la log-concavité est cruciale pour la théorie. Cependant, lorsqu'on considère des polynômes multi-affines, comme c'est le cas par exemple pour le polynôme des bases de matroïde, la complète log-concavité est une conséquence gratuite de la log-concavité. En~effet, pour $p$ multi-affine et log-concave, on~peut considérer $\lim_{\lambda \rightarrow \infty} \frac{1}{\lambda} p(\lambda z_1, \ldots , z_n)=z_1 \partial_1p$ qui est log-concave (c'est une propriété fermée), et~comme $p$ est multi-affine le terme $\partial_1 p$ n'a pas de variable en $z_1$. Pour que le produit de deux polynômes à variables disjointes soit log-concave, il~faut que les deux polynômes le soient, et~donc $\partial_1p$ est log-concave. On~obtient ainsi immédiatement la log-concavité de toutes les dérivées partielles, et~donc la complète log-concavité via le théorème~\ref{th:reduction}. \end{remark} \begin{remark} La complète log-concavité des polynômes peut être généralisée de multiples façons pour capturer encore plus de phénomènes combinatoires. Une de ces généralisations est de considérer une log-concavité fractionnaire: on demande alors qu'il existe un $\alpha\in{}]0,1]$ tel que la fonction $(z_1, \ldots, z_n) \mto p(z_1^\alpha, \ldots, z_n^\alpha)$ soit complètement log-concave. Cette généralisation a été mise à profit dans~\cite{alimohammadi2021fractionally} pour obtenir des algorithmes de comptage approximés pour une classe encore plus large de problème. Une autre généralisation importante est obtenue en ne considérant la propriété de log-concavité que sur un cône $\mathcal{C}$ plus petit que l'orthant positif. La notion obtenue de polynômes $\mathcal{C}$-lorentziens a ainsi permis à Brändén et Leake~\cite{branden2021lorentzian} d'obtenir une nouvelle preuve de la log-concavité du polynôme chromatique des matroïdes, et~a aussi mené à de nouveaux résultats sur l'expansion en grande dimension et l'échantillonnage~\cite{leake2025optimal} \end{remark} \section{Aparté: algorithmes de comptage exacts et permanent} Nous avons atteint notre objectif principal, mais en guise de conclusion nous proposons un aparté sur un autre aspect des algorithmes de comptage, où les polynômes log-concaves vont également nous être utiles. Comme on l'a vu, l'existence et l'efficacité de tels algorithmes de comptage sont intimement liés au problème d'échantillonner des éléments efficacement. De tels algorithmes d'échantillonnage sont, par essence, randomisés. Mais il n'y a pas de raison, a priori, pour que les algorithmes de comptage le soient, et~on peut légitimement se demander s'il existe des algorithmes \emph{déterministes} qui seraient tout aussi efficaces, par exemple pour notre problème de compter les bases de matroïdes. De façon plus générale, la question de l'utilisation du hasard et de quels algorithmes peuvent être dérandomisés, est une question centrale en informatique théorique. De façon étonnante, il~y a désormais de bonnes raisons de penser que tous les algorithmes peuvent être dérandomisés, mais ce n'est à ce stade qu'une conjecture. Le~livre récent d'Avi Wigderson~\cite{wigderson2019mathematics} propose une introduction très accessible à ces problématiques. Nous allons dans cette section nous intéresser à l'existence d'algorithmes déterministes pour un problème très proche de celui de compter les bases d'un matroïde. Notre objet d'étude principal est le \emph{permanent} d'une matrice, qui est défini comme un déterminant mais sans les signes négatifs: \[ \per(A)= \sum_{\sigma \in S_n} \prod_i A_{i,\sigma(i)}. \] Il ne faut pas se laisser tromper par la similitude apparente avec le déterminant. Le~déterminant est un objet de nature géométrique (c'est un volume), qui s'appréhende très bien sous différents aspects et en particulier peut être calculé très efficacement par élimination gaussienne\footnote{Le nombre d'opérations arithmétiques effectuées pendant une élimination gaussienne est clairement polynomial, mais une subtilité peu connue est que la taille des rationnels impliqués dans le calcul peut facilement exploser. Pour éviter cette explosion, il~faut avoir recours à des techniques plus précises, voir par exemple l'algorithme de Bareiss~\cite[\S\,5.5]{von2003modern}.}. Le~permanent, en~revanche, ne s'interprète pas bien géométriquement, et~son calcul est très difficile: même lorsque les entrées de $A$ sont $0$ ou $1$, calculer le permanent est $\# P$-complet~\cite{valiant}, ce~qui signifie qu'on ne peut pas, modulo les hypothèses classiques de la théorie de la complexité, le~calculer en temps polynomial. Le~meilleur algorithme connu, dû à Ryser~\cite{ryser1963combinatorial}, requiert $O(2^nn)$ opérations arithmétiques. Nous avons déjà rencontré ce permanent de façon déguisée. Si l'on considère un graphe biparti $G=(V,U,E)$ où $|V|=|U|$, et~sa matrice d'incidence $I_G$ dont l'entrée $ij$ est $1$ si et seulement s'il~y~a une arête entre $v_i$ et $u_j$, le~permanent $\per(I_G)$ compte toutes les bijections entre~$V$ et~$U$ réalisées par des arêtes, c'est-à-dire tous les couplages parfaits du graphe $G$. Ainsi, calculer un permanent revient à compter le nombre de bases dans l'intersection des deux matroïdes de partition $M_V$ et $M_U$. En~général, les techniques du théorème~\ref{th:main} ne s'appliquent pas pour le problème d'intersection de bases qui est plus délicat que celui de compter les bases d'un seul matroïde, mais dans le cas particulier des couplages parfaits, un article célèbre de Jerrum, Sinclair et Vigoda~\cite{jerrum2004polynomial} fournit un analogue au théorème~\ref{th:main}, c'est-à-dire un FPRAS pour le calcul du permanent. Les algorithmes déterministes pour approximer le permanent sont considérablement moins bons: les meilleurs connus ne fournissent que des bornes d'approximation exponentielles. L'objectif de cette section est de démontrer le théorème suivant, et~les polynômes log-concaves feront encore une apparition dans sa preuve. \begin{theorem}\label{th:main2} Pour une matrice $A$ de taille $n \times n$ et à entrées positives, il~existe un algorithme polynomial qui calcule une $e^n$-approximation du permanent $\per(A)$, c'est-à-dire une quantité $P$ telle que \[ P\cdot e^{-n}\leq \per(A) \leq P. \] \end{theorem} Ce théorème n'est pas le meilleur connu, l'état de l'art permettant une approximation à un facteur $(\sqrt{2})^n$~\cite{anari2021tight,gurvits2014bounds}, ce~qui est également exponentiel. Trouver des algorithmes déterministes qui rivalisent avec les algorithmes randomisés pour approximer le permanent est l'un des problèmes ouverts les plus fondamentaux du domaine de la dérandomisation. L'algorithme derrière le théorème~\ref{th:main2} provient du théorème suivant, originellement formulé pour les polynômes stables et dû à Gurvits~\cite{gurvits2008van}. \begin{theorem}\label{th:gurvits} Soit $p(z_1,\ldots,z_n)$ un polynôme complètement log-con\-cave à coefficients positifs. Alors \[ e^{-n} \inf_{z >0} \frac{p(z_1, \ldots , z_n)}{z_1\ldots z_n} \leq \partial_1\ldots\partial_np_{|z=0} \leq \inf_{z>0} \frac{p(z_1, \ldots , z_n)}{z_1\ldots z_n}. \] \end{theorem} L'intérêt algorithmique de ce problème est que la quantité \[ \inf_{z >0} \frac{p(z_1, \ldots , z_n)}{z_1\cdots z_n}, \] appelée \emph{capacité} de $p$, peut être calculée rapidement. En~effet, on~commence par effectuer un changement de variable $z_i=e^{y_i}$, qui est valide puisque $z>0$, et~le quotient s'écrit alors $\sfrac{p(e^{y_1}, \ldots , e^{y_n})}{e^{y_1}\ldots e^{y_n}}$. Pour minimiser le quotient, on~peut aussi bien minimiser son logarithme et il s'agit donc de minimiser \[ \log p(e^{y_1},\ldots,e^{y_n})-\sum_i y_i. \] C'est une fonction facile à minimiser parce qu'elle est convexe: c'est évident pour les $y_i$ qui sont des fonctions linéaires, mais également facile à voir pour le premier terme car la fonction log-sum-exp \[ (y_1, \ldots ,y_n) \mto \log \sum_i a_i e^{\langle b_i,y_i\rangle} \] est convexe pour des $a_i$ positifs. Pour relier le théorème~\ref{th:gurvits} au calcul du permanent, on~considère le polynôme \[ p(z)=\prod_{i=1}^n \sum_{j=1}^n A_{i,j}z_j. \] C'est un produit de polynômes complètement log-concaves (des formes linéaires à coefficients positifs). Un tel produit est toujours complètement log-concave, mais le prouver requiert un peu de travail sur les dérivées directionnelles. Cependant, dans ce cas précis, on~peut utiliser le tour de passe-passe suivant: on commence par considérer le produit comme si les variables étaient disjointes. Le~polynôme que l'on obtient étant multi-affine, il~est complètement log-concave car il est log-concave (\cf remarque~\ref{rem:clc}). On~peut ensuite spécifier les variables comme il faut en préservant la log-concavité complète de par le lemme~\ref{lem:easy}. On observe alors que \[ \partial_1\ldots\partial_np_{|z=0}=\per(A), \] et donc le théorème~\ref{th:gurvits} implique directement le théorème~\ref{th:main2}. Avant de le démontrer, observons que le théorème~\ref{th:gurvits} implique également immédiatement le résultat suivant, qui est une conjecture classique de van der Waerden datant de 1926 et qui n'a été résolue qu'en 1981~\cite{egorychev1981solution,falikman1981proof}. Une matrice est \emph{doublement stochastique} si la somme de chaque colonne et la somme de chaque ligne vaut $1$. \begin{theorem} Si $A$ est une matrice positive doublement stochastique, alors $\per(A) \geq e^{-n}$. \end{theorem} \begin{proof} Il suffit de montrer que pour $A$ doublement stochastique, $\inf_{z >0} \Psfrac{p(z_1, \ldots , z_n)}{z_1\ldots z_n}\geq 1$, où $p$ est le polynôme défini ci-dessus. Pour cela, on~fera appel à l'inégalité arithmético-géométrique dans une version pondérée, qui énonce que pour tous $a_1, \ldots, a_n \geq 0$ et $\lambda_1, \ldots, \lambda_n \geq 0$ tels que $\sum \lambda_i=1$, on~a \[ \sum \lambda_i a_i \geq \prod_i a_i^{\lambda_i}. \] On écrit alors \begin{align*} p(z_1, \ldots , z_n) &=\prod_{i=1}^n \sum_{j=1}^n A_{i,j}z_j\\ &\geq \prod_{i=1}^n\prod_{j=1}^n z_j^{A_{i,j}}= \prod_{i=1}^n z_j^{\sum_{i=1}^n A_{i,j}}=\prod_{i=1}^n z_j.\qedhere \end{align*} \end{proof} On passe maintenant à la preuve du théorème~\ref{th:gurvits}. \begin{proof} L'inégalité de droite est triviale et est valide pour tout polynôme à coefficients positifs. En~effet, $\partial_1\ldots\partial_np_{|z=0}$ est exactement le coefficient du monôme $z_1\ldots z_n$ dans $p$. Ensuite, on~considère le cas univarié qui servira de cas de base à une récurrence. Pour $p$ un polynôme positif log-concave en une seule variable $t$, $\log p$ est inférieur à sa dérivée et donc \[ \log p(t) \leq \log p(0) + t\, \frac{p'(0)}{p(0)}. \] On~prend $t=p(0)/p'(0)$, ce~qui donne $\log p(t) \leq \log p(0) +1$ et donc \[ \log (\sfrac{p(t)}{t}) \leq 1+ \log p(0) -\log \Psfrac{p(0)}{p'(0)}=1+ \log p'(0). \] Ainsi, dans le cas univarié, on~a $\frac{1}{e} \inf_{t>0} (p(t)/t) \geq p'(0)$. Le théorème se déduit par récurrence sur le nombre de variables: on note $q(z_1, \ldots , z_{n-1})=\partial_np_{|z_n=0}$, et~on suppose que $q$ satisfait la conclusion du théorème par hypothèse de récurrence. On~a donc \[ \partial_1\ldots\partial_np_{|z=0} = \partial_1 \ldots \partial_{n-1}q_{|z=0} \geq e^{-(n-1)} \inf_{z_1,\ldots,z_{n-1} >0} \frac{q(z_1, \ldots , z_{n-1})}{z_1\ldots z_{n-1}}. \] Si on nomme $z_1^*, \ldots z_{n-1}^*$ les points où l'infimum est atteint (si~celui-ci n'est pas atteint, un même argument approximé avec des~$\varepsilon$ et des~$\delta$ fera l'affaire), on~peut définir notre polynôme univarié $f(z_n)=p(z_1^*, \ldots, z_{n-1}^*,z_n)$, et \[ q(z_1^*, \ldots , z_{n-1}^*)=f'(0) \geq \frac{1}{e}\inf_{z_n>0} \frac{f(z_n)}{z_n}. \] Le théorème est prouvé en combinant ces inégalités. \end{proof} La première application des polynômes complètement log-con\-ca\-ves~\cite{anari2018log} a été de généraliser cette approche pour obtenir un algorithme déterministe permettant d'approximer le nombre de bases d'un matroïde, ou d'une intersection de matroïdes, à un facteur multiplicatif $2^{O(r)}$ près. \backmatter \bibliographystyle{jepplain+eid} \bibliography{xups25-03} \end{document}