Lieu : Cette rencontre aura lieu à l'Ecole Polytechnique (Palaiseau), bâtiment Alan Turing, dans la salle Gilles Kahn au rez de chaussée. On trouve à cette adresse des informations sur l'accès à l'Ecole Polytechnique et ici un plan récent du campus avec l'emplacement du bâtiment Alan Turing. Attention : suite aux attentats du 13 novembre, le bus 91-06 ne traverse plus le campus de Polytechnique, l'arrêt Polytechnique-Laboratoire est supprimé et le bus s'arrête au niveau du bâtiment 21 sur le plan.

Orateurs : Clément Dervieux, Bertrand Eynard, Jean-François Le Gall, Marc Lelarge.

Organisatrice, Organisateurs : Marie Albenque, Jérémie Bettinelli, Igor Kortchemski, Laurent Ménard.

Soutien : ANR Cartaplus.


Programme

  • 9h00-10h00: café d'accueil
  • 10h00-11h00: Bertrand Eynard, Méthodes de systèmes intégrables en combinatoire, Application: preuve de la récurrence topologique pour les nombres de Hurwitz pondérés.
  • 11h00-11h30: pause
  • 11h30-12h30: Clément Dervieux, Le nombre de graphes de polyèdres en coin
  • 12h30-14h00: déjeuner
  • 14h00-15h00: Marc Lelarge, Counting matchings in irregular bipartite graphs and random lifts
  • 15h00-15h30: pause café
  • 15h30-16h30: Jean-François Le Gall, Autour de l'article "An axiomatic characterization of the Brownian map" par Miller et Sheffield

Résumés

  • Clément Dervieux, Le nombre de graphes de polyèdres en coin
    Eppstein et Mumford (2014) ont récemment défini l'ensemble des polyèdres en coin comme l'ensemble des polyèdres 3D dont les sommets sont à coordonnées entières positives, les arêtes sont parallèles aux axes de coordonnées et tous les sommets sont visibles depuis l'infini dans la direction (1,1,1). Ils décrivent l'ensemble des graphes de polyèdres en coin, i.e. l'ensemble des graphes qui peuvent être squelette d'un polyèdre en coin : vus comme cartes planaires, il s'agit exactement des graphes duaux de certaines triangulations bicoloriées particulières, que nous appelons triangulations en coin enracinées.
    Nous comptons les graphes de polyèdres en coin en déterminant la série génératrice des triangulations en coin enracinées selon leur nombre de sommets : nous en obtenons une expression explicite en fonction de la série génératrice des nombres de Catalan. Nous montrons tout d'abord que ce résultat découle de la méthode classique de décomposition de Tutte. Ensuite, pour expliquer l'apparition des nombres de Catalan, nous donnons une décomposition algébrique directe des triangulations en coin : en particulier nous mettons en évidence une famille de triangulations en amande qui admet une décomposition structurellement équivalente à celle des arbres binaires. Pour finir nous présentons rapidement une bijection directe entre les arbres binaires et ces triangulations en amande.
  • Jean-François Le Gall, Autour de l'article "An axiomatic characterization of the Brownian map" par Miller et Sheffield
    Cet exposé continuera la présentation de l'article de Miller et Sheffield "An axiomatic characterization of the Brownian map", qui a déjà fait l'objet d'un exposé de Nicolas Curien lors de la précédente journée Cartes. En particulier, nous discuterons l'identification du "metric net" associé à la carte brownienne. L'exposé pourra être suivi indépendamment de celui de Nicolas.
  • Marc Lelarge, Counting matchings in irregular bipartite graphs and random lifts
    We give a sharp lower bound on the number of matchings of a given size in a bipartite graph. When specialized to regular bipartite graphs, our results imply Friedland's Lower Matching Conjecture and Schrijver's theorem proven by Gurvits and Csikvari. Indeed, our work extends the recent work of Csikvari done for regular and bi-regular bipartite graphs. Moreover, our lower bounds are order optimal as they are attained for a sequence of 2-lifts of the original graph as well as for random n-lifts of the original graph when n tends to infinity.
    We then extend our results to permanents and subpermanents sums. For permanents, we are able to recover the lower bound of Schrijver recently proved by Gurvits using stable polynomials. Our proof is algorithmic and borrows ideas from the theory of local weak convergence of graphs, statistical physics and covers of graphs. We provide new lower bounds for subpermanents sums and obtain new results on the number of matching in random n-lifts with some implications for the matching measure and the spectral measure of random n-lifts as well as for the spectral measure of infinite trees.