Algorithmique des matroïdes et polynômes log-concaves

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.