Le séminaire a eu lieu les jeudis 3 octobre 2013, 5 décembre 2013, 6 février 2014, 3 avril 2014, et 5 juin 2014.
3 octobre 2013
-
Valentin Féray (Institut für Mathematik, Universität Zürich),
Une formule d’équerre avec des paramètres bi-indicés pour les arbres croissants.
Transparents.
Les formules d'équerre permettent d'énumérer les extensions linéaires de certaines familles d'ensembles ordonnés (arbres, tableaux de Young). En appliquant des bijections classiques, elles impliquent des identités combinatoires surprenantes, appelées formules sommatoires d'équerre. De nombreuses variantes et généralisations sont apparues dans la littérature ces dernières années. Dans cet exposé, nous présenterons une nouvelle formule sommatoire d'équerre pour les arbres croissants. Pour des arbres de taille $r$, elle contient $O(r^2)$ paramètres alors que les formules connues n'en ont qu'un nombre fixé. Le membre de droite de notre formule est un produit de facteurs de degré 1 ou 2. La preuve est bijective, et fait apparaître une opération de recollement d'arbres croissants. Travail en collaboration avec Ian Goulden (Waterloo) et Alain Lascoux (Marne-La-Vallée)
-
Eric Colin de Verdière (CNRS, ENS),
Théorèmes à la Helly, motifs d’intersections et combinatoire topologique.
Transparents.
Le théorème de Helly (1923) énonce une propriété des motifs d'intersections des familles (finies) de convexes de $R^d$: Pour vérifier qu'une telle famille est d'intersection non vide, il suffit de vérifier que chaque sous-famille de taille au plus $d+1$ est d'intersection non vide. On peut représenter combinatoirement les motifs d'intersections d'une famille quelconque d'ensembles à l'aide d'un complexe simplicial, son _nerf_. Le théorème du nerf en combinatoire topologique permet de montrer une version topologique du théorème de Helly. Je décrirai une généralisation de ce dernier résultat à des familles d'objets non connexes de $R^d$, qui repose sur une variante de la notion de nerf et sur une extension d'un théorème de projection dû à Kalai et Meshulam, et des applications en géométrie combinatoire. Travail en commun avec Grégory Ginot et Xavier Goaoc.
-
Philippe Nadeau (CNRS, Institut Camille Jordan),
Éléments pleinement commutatifs dans les groupes de Coxeter.
Transparents. Synthèse.
Dans un groupe de Coxeter, les éléments ont une représentation par certains ensembles de mots liés entre eux par des relations. Un élément $w$ est dit pleinement commutatif (PC) si, étant donné deux mots de longueur minimale représentant $w$, il existe toujours une série de commutations de lettres adjacentes pour passer de l'un à l'autre. Ces éléments sont importants car ils indicent une base des algèbres de Temperley-Lieb généralisées; ils interviennent également en connexion avec les représentations d'algèbres de Hecke. Dans cet exposé, nous nous intéresserons à la combinatoire des éléments PC. Nous les caractériserons précisément pour chaque groupe de Coxeter fini ou affine. Dans ce dernier cas, la suite énumérant les éléments PC selon leur longueur s'avère être ultimement périodique; on donnera la taille de la pré-période et la période minimale de cette suite, et on expliquera comment calculer sa série génératrice. Dans le cas d'un groupe de Coxeter général, on montrera que cette série est toujours rationnelle, via l'utilisation d'automates finis. Basé en partie sur des travaux communs avec Riccardo Biagioli et Frédéric Jouhet.
5 décembre 2013
-
Piotr Sniady (TU Munich),
Hydrodynamic limit of Robinson-Schensted algorithm.
Transparents.
We consider Robinson-Schensted-Knuth algorithm (RSK) applied to random input data and study the time-evolution of the insertion tableau. We show that in the appropriate scaling limit, this insertion tableau evolves like a deterministic, stationary flow of a non-compressible liquid. Joint work with Dan Romik
-
Mathilde Bouvel (Université de Zurich),
Operators of equivalent sorting power, and related Wilf-equivalences.
Transparents.
Permutation patterns and permutation classes (defined by the avoidance of a set of patterns) have been first introduced in the seventies, in connection with the analysis of sorting devices and partial sorting algorithm. Enumerative combinatorics soon became interested in the study of permutation classes, and many so-called Wilf-equivalences have been proved. Two permutation classes (or two sets of excluded patterns that characterize them) are said Wilf-equivalent when they are enumerated by the same sequence. In this talk, I will start with a (biased) panorama of these early results on permutation classes, and present new results obtained first with Olivier Guibert (LaBRI, Bordeaux) and then with Michael Albert (Univ. Otago, New Zealand). The main point of this work is the study of some partial sorting operators. But it has unexpected enumerative consequences, as our study allows us to deduce families of Wilf-equivalences.
-
Markus Nebel (TU Kaiserslautern),
Markus Nebel (TU Kaiserslautern).
Java 7’s Dual Pivot Quicksort — Analysis and Engineering.
Transparents.
Recently, a new Quicksort variant due to Yaroslavskiy was chosen as standard sorting method for Oracle's Java 7 runtime library. The decision for the change was based on empirical studies showing that on average, the new algorithm is faster than the formerly used classic Quicksort. Surprisingly, the improvement was achieved by using a dual pivot approach, an idea that was considered not promising by several theoretical studies in the past. In this talk, we identify the reason for this unexpected success. Moreover, we present the first precise average case analysis of the new algorithm showing e. g. that a random permutation of length n is sorted using $1.9n \ln n - 2.46n + O(\ln n)$ key comparisons and $0.6n \ln n + 0.08n + O(\ln n)$ swaps. Our analysis reveales a highly asymmetric nature of the algorithm. This suggest that asymmetric pivot choices are preferable to symmetric ones. From a theoretical point of view, this should allow us to improve on the current implementation in Oracle's Java 7 runtime library. We present results derived by means of our tool MaLiJAn to confirm this for asymptotic combinatorial cost measures such as the total number of executed instructions (Java bytecodes). However, the observed running times show converse behavior. With the support of data provided by MaLiJAn we are able to identify the profiling capabilities of Oracle's just-in-time compiler to be responsible for this unexpected outcome.
6 février 2014
-
Marie Albenque (Laboratoire d’Informatique de l’École Polytechnique),
Marie Albenque (Laboratoire d’Informatique de l’École Polytechnique).
Bijections entre cartes planaires et arbres bourgeonnants.
Transparents.
Les arbres bourgeonnants sont des arbres portant des décorations qui permettent de leur associer une carte planaire. Trouver des bijections entre des familles de cartes et d'arbres bourgeonnants fournit un outil précieux dans l'étude des cartes planaires; cela permet en effet de ramener l'étude de la carte à celle de l'arbre associé, souvent plus simple. De nombreuses bijections ont été obtenues ces 15 dernières années et dans cet exposé je présenterai un schéma général qui, en se spécialisant, permet d'obtenir beaucoup de ces constructions comme des cas particuliers ainsi que de nouvelles constructions. Ce résultat s'inscrit dans la lignée de travaux par Bernardi et Fusy et qui visent à unifier les bijections existantes entre cartes et arbres. Une question fondamentale, encore largement ouverte, est maintenant de comprendre comment les distances entre deux sommets de la carte peuvent être retrouvées à partir de l'arbre bourgeonnant. J'expliquerai comment cette question peut être résolue dans le cas des triangulations simples. Cet exposé repose sur des travaux avec Louigi Addario-Berry et Dominique Poulalhon
-
Frédéric Chapoton (Institut Camille Jordan – ICJ, CNRS),
Combinatoire des couplages et des ensembles indépendants dans les arbres.
Transparents.
En théorie des graphes, les notions de couplage et d'ensemble indépendant sont très classiques et fondamentales. Dans cet exposé, je présenterai une description élégante (due à Zito et Bauer-Coulomb) de ce qui se passe dans les arbres, qui fait intervenir un tri-coloriage canonique des sommets. Il sera notamment question de diagrammes de Feynman, et d'une relation amusante entre le principe de dissymétrie et le Lagrangien d'une théorie quantique des champs. On esquissera aussi une relation avec la géométrie de certaines variétés.
-
Paul Zinn-Justin (Laboratoire de Physique Théorique et Hautes Energies – LPTHE, CNRS),
Des fibrés conormaux des variétés de Schubert au modèle de boucles de Brauer.
Dans ce travail en collaboration avec A. Knutson, nous investiguons la correspondance entre géometrie algébrique et systemes intégrables quantiques, sous l'angle des dégénerescences de Gröbner. Ce dernier point de vue a l'avantage d'être très combinatoire et de s'appliquer à la fois en cohomologie et en K-théorie. Suivant Knutson et Miller, je rappellerai le cadre le plus simple dans lequel on peut développer cette approche, qui est celui des variétés (matricielles) de Schubert et des polynômes de Schubert et de Grothendieck. Ensuite je formulerai plusieurs variations et extensions successives de cette approche, qui nous amèneront naturellement aux modèles de boucles sur réseaux: d'abord de boucles non-croisantes (modèle de Temperley--Lieb), puis si le temps le permet, de boucles croisantes (modèle de Brauer).
3 avril 2014
-
Guillaume Chapuy (LIAFA, CNRS),
Une formule pour compter les cartes de genre positif.
Transparents.
Je parlerai de cartes, qui sont des graphes dessinés sur des surfaces orientables. L'énumération de ces objets est un domaine très riche qui a fait l'objet de nombreux travaux. Je donnerai une formule extrêmement simple, apparemment nouvelle, obtenue récemment avec Sean Carrell (Waterloo) permettant d'énumérer les cartes orientables par le genre et le nombre d'arêtes. Cette formule repose sur le fait «classique» que les séries génératrices multivariées de cartes et objets apparentés sont des tau-fonctions de la hiérarchie KP. J'essaierai de dédramatiser un peu cet énoncé en donnant une idée brève de la combinatoire algébrique sur laquelle il repose. Puis je tenterai de montrer comment obtenir une formule toute simple à partir de là dans le cas des cartes générales. Si le temps le permet je tenterai de mettre ce résultat en perspective en le comparant avec ce que l'on peut dire via d'autres approches, bijectives ou à base d'équations de Tutte/boucles. Bien que notre formule soit de saveur très combinatoire, je ne parlerai pas de son interprétation bijective, car je ne la connais pas!
-
Christophe Hohlweg (LaCIM, Université du Québec à Montréal),
Ordre faible et cône imaginaire dans les groupes de Coxeter infinis.
Transparents.
L'ordre faible est un outil combinatoire intimement liée à l'étude des mots réduits dans les groupes de Coxeter. Dans les groupes de Coxeter finis, c'est un treillis qui oriente le graphe sommets/arêtes du permutaèdre et qui donne un cadre naturel pour construire les associaèdres généralisées (via les treillis Cambrien de N. Reading). Lors cet exposé, nous allons discuter une conjecture de Matthew Dyer qui propose une généralisation de l'ordre faible et des mots réduits aux groupes de Coxeter infinis. Il sera notamment question de la relation entre les limites des racines et le pavage de leur enveloppe convexe, des ensembles biclos et d'ensemble d'inversions de mots réduits infinis. Partiellement basé sur des travaux communs avec M. Dyer, JP Labbé et V. Ripoll
-
Filippo Colomo (Istituto Nazionale di Fisica Nucleare, Firenze),
Limit shapes of large Alternating Sign Matrices.
Transparents.
Alternating Sign Matrices (ASMs) are square matrices satisfying the following conditions: a) possible entries are 0,1,-1; b) non-zero entries alternate in sign along each row and column; c) the sum of entries of any fiven row or column is equal to 1. In the limit of large dimensions ASMs are known to develop a limit shape, with the appearance of four corner regions containing only 0's, and sharply separated from a central and approximately circular region, containing also non-zero entries. The original derivation of an analytic expression for the curve describing the limit shape is reviewed. The corresponding expression for the case of weighted enumerations of ASMs is provided as well. An alternative derivation is discussed, which allows for extension of the above results to ASMs of generic shape (more precisely, to generic shape subregions of the square lattice graph, with an entry associated to each vertex, and all entries satisfying ASMs'conditions). Joint works with Andrei Pronko, Paul Zinn-Justin, Andrea Sportiello
5 juin 2014
-
Jonathan Novak (Department of Mathematics, Massachusetts Institute of Technology),
Lozenge tilings of sawtooth domains near a turning point.
Transparents.
Random tilings of planar regions by three types of tiles known as "lozenges" have been heavily investigated over the past decade, partly due to their intrinsic appeal and partly due to their status as an especially tractable class of random surface models. There are many connections between lozenge tilings and the representation theory of the classical groups, and consequently representation-theoretic techniques can sometimes be used to effectively answer natural probabilistic questions about tilings. I will discuss tilings of a particular class of regions called "sawtooth domains" for which the relation to representation theory is particularly clear, and focus on the behaviour of a uniformly random tiling of a large sawtooth domain near a "turning point." As recently observed by Gorin and Panova, understanding the asymptotic joint distribution of tiles of one type in this regime comes down to understanding the asymptotics of the Harish-Chandra-Itzykson-Zuber integral in a certain scaling limit. There is a robust combinatorial model for the HCIZ integral which allows to analyze the required asymptotics at a very fine level of detail, and in particular extract a certain limit law. If time permits, I will explain how the techniques discussed can be modified to deal with tilings exhibiting certain additional symmetries.
-
Marc Noy (Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya),
Random planar graphs with given minimum degree.
We determine the asymptotic growth of planar graphs with a condition on the minimum degree, and properties of random graphs from these classes. In particular we show that the size of the largest tree attached to the 2-core of a random planar graph is of order $c \log(n)$ for an explicit constant $c$. These results provide new information on the structure of random planar graphs. Joint work with Lander Ramos.
-
Alan Sokal (New York University and University College London),
Coefficientwise total positivity (via continued fractions) for some Hankel matrices of combinatorial polynomials.
Transparents.
A matrix $M$ of real numbers is called totally positive if every minor of $M$ is nonnegative; I will call a matrix $M$ of polynomials (in some set of indeterminates) coefficientwise totally positive if every minor of $M$ is a polynomial with nonnegative coefficients. I will call a sequence $(a_k)_{k \ge 0}$ of real numbers (or polynomials) (coefficientwise) Hankel-totally positive if the Hankel matrix $H = (a_{i+j})_{i,j \ge 0}$ associated to $(a_k)$ is (coefficientwise) totally positive. The (coefficientwise) Hankel-total positivity of a sequence $(a_k)$ implies its (coefficientwise) log-convexity, but is much stronger. (For sequences of real numbers, Hankel-total positivity is equivalent to being a Stieltjes moment sequence.)
I will point out a simple sufficient condition for the (coefficientwise) total positivity of a Hankel matrix, based on expanding the power series $\sum_{k=0}^\infty a_k t^k$ into a Stieltjes-type continued fraction. As a consequence I can show that a number of sequences of polynomials arising in enumerative combinatorics are coefficientwise Hankel-totally positive; this approach also gives combinatorial interpretations of all the Hankel minors, and explicit formulae for the first few leading principal minors.
I conclude by giving some examples of sequences of combinatorial polynomials that appear empirically to be Hankel-totally positive but which cannot be handled by this continued-fraction approach. Foremost among these are the inversion enumerator for trees, $I_n(y)$, which is related to the generating polynomials $C_n(v)$ of connected graphs.