Séminaire de Combinatoire Philippe Flajolet Séminaire de Combinatoire Philippe Flajolet
Avec le soutien des projets ANR MAGNUM et ICOMB .
Le Séminaire de Combinatoire Enumérative et Analytique, rebaptisé Séminaire Philippe Flajolet le 7 avril 2011, a pour objectif de couvrir un large spectre de recherche en combinatoire, et est ouvert à tous les chercheurs et étudiant intéressés.
10h30 -- 11h30 - Marc Mezard (LPTMS, Paris Sud), Une approche probabiliste au problème d'acquisition comprimée (compressed sensing) , transparents .
Résumé : L'acquisition comprimée est une évolution majeure de ces dernières années en ce qui concerne l'acquisition de signaux et le traitement de l'information. Le problème majeur posé par l'acquisition comprimée est celui de la reconstruction d'un signal parcimonieux à partir d'un nombre de mesures inférieur au nombre d'inconnues. En utilisant des concepts de physique statistique, nous avons récemment introduit une nouvelle procédure qui permet de réaliser cette reconstruction parfaitement dans une vaste gamme de taux de mesure. Cette procédure permet en fait d'atteindre la performance optimale, c'est à dire de n'utiliser qu'un nombre de mesures égal au nombre de composants non nulles du signal. Elle est basée sur une approche probabiliste de la reconstruction, un algorithme de passage de messages, et une structuration de la matrice de mesures, fondée sur des principes de la théorie de nucléation des cristaux en physique statistique. L'implémentation numérique de cette nouvelle approche montre une amélioration remarquable des performances, par rapport aux algorithmes habituels fondés sur une minimisation de norme L1. Cet exposé est basé sur des travaux en collaboration avec Florent Krzakala, Francois Sausset, Yifan Sun, et Lenka Zdeborova, voir l'article : Phys. Rev. X 2, 021005 (2012) [18 pages], disponible en open access sur http://prx.aps.org/abstract/PRX/v2/i2/e021005
14h00 -- 15h - Christian Krattenthaler (Wien Universitat) , Crible cyclique pour partitions non-croiéees généralisées associées aux groupes de réflection complexes , transparents .
Résumé : Le crible cyclique est un phénomène énumeratif énoncé par Reiner, Stanton et White. Bessis et Reiner ont proposé deux conjectures sur des phénomènes de crible cyclique pour les partitions non-croisées généralisées associées aux groupes de réflection complexes de Armstrong et Bessis. Je commencerai en expliquant ce qu'est le crible cyclique et les partitions non-croisées généralisées, et ensuite j'exposerai les idées principales d'une démonstration de ces deux conjectures. Ce travail a été effectué en partie avec Thomas Muller.
15h30 -- 16h30 - Frédérique Bassino (LIPN, Paris Nord) , Enumération asymptotique d'automates finis , transparents .
Résumé : Cet exposé portera sur l'énumération d'automates finis. Les automates peuvent être vus comme des graphes orientés dont les arêtes sont étiquetées sur un alphabet fini et dont deux sous-ensembles de sommets sont distingués (l'ensemble respectivement des états initiaux et des états terminaux). Nous présenterons les résultats obtenus depuis la fin des années 70 concernant l'énumération des automates détermnistes et accessibles, i.e. dans lesquels tout état peut-être atteint par un chemin partant de l'unique état initial. Nous déterminerons ensuite précisément la proportion asymptotique d'automates minimaux parmi les automates déterministes accessibles et complets. Toutes ces estimations peuvent être obtenue grâce à une interprétation combinatoire des propriétés structurelles des automates et des bijections pour se ramener à l'étude combinatoire de tableaux particuliers.
10h30 -- 11h30 - Kirone Mallick (IPhT, Orsay), Fluctuations du courant dans le modèle d'exclusion et Processus de croissance, transparents .
Résumé : Le processus d'exclusion asymétrique (ASEP) fournit une représentation microscopique des phénomènes de transport unidimensionnel. Il possède des propriétés physiques et mathématiques remarquables, qui en font un paradigme de la mécanique statistique. Son étude a connu un grand essor après une contribution fondamentale de Derrida, Evans, Hakim et Pasquier (1993), qui utilisèrent des algèbres quadratiques pour représenter les poids des configurations microscopiques du système~: cette `technique matricielle' a ouvert la voie à une interprétation combinatoire de ces poids en termes d'arbres, de chemins ou de tableaux. Nous commencerons par un rappel général des propriétés d'ASEP et de sa pertinence pour la physique statistique hors d'équilibre. Ensuite, nous expliquerons comment la méthode algèbrique peut être étendue pour calculer la fonction de grande déviation du courant, une observable très importante du point de vue de la physique. Nos résultats impliquent des produits tensoriels d'algèbres quadratiques et sont une nouvelle fois de type combinatoire~: ils sont exacts pour toutes les tailles du système. Dans la derniere partie de l'exposé, nous présenterons une généralisation bidimensionnelle du processus d'exclusion, qui permet de représenter la forme limite d'un cristal cubique en croissance.
14h00 -- 15h - Christophe Tollu (LIPN, Villetaneuse) , Nombres de Littlewood-Richardson : modèles combinatoires, calcul et complexité , transparents .
Résumé : Les nombres de Littlewood-Richardson sont des entiers naturels paramétrés par trois partitions d'entiers, qui énumèrent des points entiers dans des polytopes à sommets rationnels. Ils apparaissent dans l'étude des représentations des groupes généraux linéaires. L'exposé présentera quelques propriétés importantes de ces nombres, connues de longue date ou plus récemment découvertes, puis traitera de la complexité de leur calcul et du test de leur non-nullité, ce qui permettra de faire le lien avec la théorie géométrique de la complexité, un programme d'approche du problème P vs. NP à travers la théorie des invariants et la théorie des représentations, lancé il y a quelques années par K. Mulmuley et M. Sohoni.
15h30 -- 16h30 - Julien Clément (GREYC, Caen) , Trier des clés: une analyse en moyenne du nombre de comparaisons de symboles ,
Résumé : On aborde classiquement l'analyse en moyenne d'algorithmes en s'intéressant à la complexité mesurée en nombre de comparaisons. On a alors des résultats de complexité du type "tel algorithme est en O(n log n) en moyenne" (par exemple Quicksort pour citer un des plus connus). Ces affirmations se basent sur des hypothèses spécifiques -- que les comparaisons entre les données (ou clés), pour les deux premiers, et les comparaisons entre symboles pour le troisième ont un coût unitaire -- et elles ont le mérite évident de présenter un tableau facile à assimiler de la complexité des algorithmes de tri. Cependant, ces hypothèses simplificatrices sont de fait discutables: elles ne permettent pas de comparer précisément les avantages et inconvénients d'algorithmes reposant sur des principes différents (i.e., ceux qui comparent les clés et ceux qui utilisent une représentation sous forme de suite de symboles) d'une manière qui soit totalement satisfaisante à la fois du point de vue de la théorie de l'information et du point de vue algorithmique. En effet, d'abord le calcul n'est pas vu à son niveau le plus fondamental, c'est-à-dire, par la manipulation de symboles élémentaires tels que le bit, l'octet, le caractère ou le mot-machine. De plus les analyses simplifiées ne sont pas toujours informatives dans beaucoup d'applications (bases de données ou traitement de la langue naturelle), où l'information est de nature hautement 'non atomique' , au sens qu'elle ne se réduit pas à un seul mot-machine. J'exposerai à l'aide de plusieurs exemples d'algorithmes de tri une méthode qui permet d'analyser en moyenne le nombre de comparaisons de symboles. Les clés à trier sont vues comme des séquences de symboles produit par un modèle de source général. Pour des sources particulières (comme les sources sans mémoire) on accède à une analyse fine (avec le calcul de constantes explicites...) de certains de ces algorithmes de tri. En collaboration avec Brigitte Vallée, Thu Hien Nguyen-Thi (et initié avec Philippe Flajolet).
10h30 -- 11h30 - Jean-Yves Thibon (LIGM, Marne-la-Vallée), Réalisations polynomiales d'algèbres de Hopf combinatoires, transparents .
Résumé : L'idée d'utiliser des algèbres de Hopf en combinatoire n'est pas très récente, elle remonte au moins à Rota dans les années 1970. Toutefois, c'est seulement depuis une quinzaine d'années qu'on a vu apparaître de nombreux exemples nouveaux. Ces algèbres de Hopf combinatoires (AHC) sont formées de combinaisons linéaires formelles d'objets combinatoires classiques, et leurs opérations (produit et coproduit) s'expriment en termes d'algorithmes de composition ou de décomposition de tels objets. Ces exemples sont souvent reliés (par des homomorphismes) aux fonctions symétriques ou quasi-symétriques. Or, ces dernières sont définies au moyen de variables auxiliaires, et leurs opérations sont induites par le produit ordinaire des polynômes, et une opération simple de dédoublement des variables. Il est donc tentant de rechercher des variables auxiliaires permettant une description similaire des autres AHC. Lorsque cela est possible, on parle de réalisation polynomiale de l'algèbre. On obtient alors en général une simplification importante de la théorie, ainsi que de nouvelles bases qui semblent paver la voie vers une théorie des fonctions spéciales non-commutatives.
14h00 -- 15h - Dominique Poulalhon (LIX, Ecole polytechnique) , Preuve bijective de la formule d'Hurwitz,
Résumé : En 1891, Hurwitz donne une formule dénombrant certains revêtements ramifiés de la sphère S^2 par elle-même, qui en termes combinatoires correspondent aux m-uplets de transpositions engendrant un sous-groupe transitif de S_n et dont le produit est une permutation à l = m-n+2 cycles de longueurs fixées par une partition α_1, ..., α_l. Cette formule relativement simple fait entre autres intervenir les nombres d'arbres de Cayley à α_i sommets, mais aucune des démonstrations obtenues jusqu'à présent n'explique vraiment pourquoi ces termes apparaissent. Le parallèle avec les formules énumérant des familles de cartes planaires, qui font intervenir les nombres (d'arbres) de Catalan, est pourtant tentant. J'exposerai la preuve bijective obtenue récemment avec Enrica Duchi et Gilles Schaeffer, en montrant sa parenté avec les constructions bijectives obtenues précédemment pour les cartes planaires.
15h30 -- 16h30 - Jean-Francois Marckert (LABRI, Bordeaux) , Animaux dirigés, systèmes quadratiques et systèmes de réécritures,
Résumé : Un animal dirigé A sur le réseau carré est une partie de N^2 contenant l'origine 0, et telle que chaque point de A peut-être atteint depuis 0 en restant à l'intérieur de A, uniquement par des pas (0,1) ou (1,0). Le cardinal de A s'appelle l'aire de A, et l'ensemble des sommets de N^2 que l'on peut ajouter à A sans lui faire perdre sa qualité d'animal dirigé (AD), s'appelle le périmètre de A. On s'intéresse à la question du calcul de la série génératrice G(x, y) des AD sur réseau carré selon l'aire et le périmètre. Il s'agit d'une question centrale dans l'étude des AD, très directement liée au problème de la percolation dirigée, pour lequel le seuil critique, qui est sup { p : G( p, 1-p) = 1 }, est inconnu (alors qu'il existe de nombreuses méthodes pour calculer G(x,1)). Dans cet exposé, nous montrons l'équivalence entre le calcul de G et le calcul d'une solution à un système quadratique dont les inconnues sont des matrices (équations relativement proches de celles apparaissant pour le TASEP). Incapable de résoudre ce problème, nous montrons que des matrices infinies obtenues comme point fixe d'un système de type "système de réécriture", sont "solutions naturelles" de ce problème quadratique. Trouver un vecteur propre pour l'une d'elle, devrait permettre de calculer G...
10h30 -- 11h30 - Jérémie Bouttier (IPHT, CEA et LIAFA, CNRS et Université Paris Diderot), Des boucles sur les cartes aléatoires ,
Résumé : Introduit en physique statistique, le modèle $O(n)$ peut être formulé en termes de boucles évitantes (ou cycles disjoints) sur un graphe, $n$ jouant le rôle d'un poids par boucle. Ce modèle a été naturellement considéré sur les cartes aléatoires et, dans certains cas, "résolu" à l'aide d'intégrales matricielles. Nous proposons ici une nouvelle approche combinatoire à ce modèle. Le problème combinatoire consiste à énumérer les cartes planaires munies d'une configuration de boucles évitantes. A une telle carte, l'opération consistant à effacer toutes les boucles et leurs intérieurs associe une autre carte, sans boucles mais à "trous". Cette opération n'est bien sûr pas bijective, mais donne une décomposition qui se traduit par des relations de substitutions entre séries génératrices, que nous pouvons résoudre explicitement dans certains cas. En termes probabilistes, notre décomposition établit un lien entre le modèle $O(n)$ et le modèle des "cartes stables" introduit par Le Gall et Miermont. Travail en collaboration avec G. Borot et E. Guitter
14h00 -- 15h - Nicolas Broutin (INRIA Rocquencourt), Recherches partiellement spécifiées dans les arbres multidimensionnels ,
Résumé : Nous considérons la recherche d'éléments dans des structures de données multidimensionnelles (quad trees, k-d trees), en particulier lorsque certaines coordonnées ne sont pas spécifiées (partial match query). Nous supposons que les données consistent en un ensemble de points uniformes dans le carré unité. Pour ce modèle, dans une structure contenant $n$ points, Flajolet et Puech ont montré que le nombre de noeuds $C_n(U)$ à visiter pour répondre à une requête demandant l'ensemble des données dont la première coordonnée est $x=U$ est tel que $E[C_n]\sim \kappa n^{\beta}$, où $\kappa$ et $\beta$ sont des constantes explicites. Nous développons une approche basée sur l'analyse des coûts $C_n(s)$ pour des requêtes à $x=s$ fixé. Nous donnons en particulier des estimations précises de la variance et de la distribution limite de $C_n(s)$ lorsque $n\to\infty$. Nos résultats permettent de décrire un processus limite pour $C_n(s)$ lorsque $s$ varie dans $(0,1)$. Nous en déduisons par exemple que le coût de la pire requête est aussi de la forme $\kappa' n^{\beta}$, pour la puissance $\beta$ que précédemment.(Travail en collaboration avec Ralph Neininger et Henning Sulzbach).
15h30 -- 16h30 - Bernhard Keller (IMJ, Université Paris Diderot), Mutation des carquois et identités dilogarithmiques quantiques ,
Résumé : Dans cet exposé, nous commencerons par présenter une opération élémentaire sur les graphes orientés (les carquois) : la mutation. Cette opération est apparue en physique dans la dualité de Seiberg dans les années 90 et en mathématiques dans la définition des algèbres amassées (cluster algebras) par Fomin-Zelevinsky en 2002. A des suites de mutations, nous associerons des produits de certaines séries formelles non commutatives : les (exponentielles de) dilogarithmes quantiques. Il s'avère que ces produits, construits de facon élémentaire, sont reliés aux "invariants de Donaldson-Thomas raffinés" introduits récemment par Joyce, Kontsevich-Soibelman et d'autres.