Abstract: As a classical object, the Tamari lattice has many generalizations, including ν-Tamari lattices and parabolic Tamari lattices. In this article, we unify these generalizations in a bijective fashion. We first prove that parabolic Tamari lattices are isomorphic to ν-Tamari lattices for bounce paths ν. We then introduce a new combinatorial object called “left-aligned colored tree”, and show that it provides a bijective bridge between various parabolic Catalan objects and certain nested pairs of Dyck paths. As a consequence, we prove the Steep-Bounce conjecture using a generalization of the famous zeta map in q, t-Catalan combinatorics.Same topic: Séminaire SPACE of Université de Tour, Tours, 2018/11; AG Diskrete Mathematik in University of Vienna, Vienna, 2018/12
Abstract: The random k-uniform hypergraph H^k(n,p) with vertex set V of size n is constructed by picking subsets of V of size k as hyperedges with probability p. We consider the subcritical phase of the emergence of the giant component on H^k(n,p), under the notion of high-order connectedness. More precisely, for j an integer strictly smaller than k, we say that two hyperedges are j-connected if we can reach one from another through a chain of hyperedges, in which consecutive hyperedges share at least j vertices. We determine precisely the size and the structure of the k-largest components of H^k(n,p) in the subcritical case, closer to the critical window than previous research.Same topic: Séminaire CALIN, Université Paris Nord, 2018/11.
Abstract: In 2017, Duchi, Guerrini, Rinaldi and Schaeffer proposed a new combinatorial object called "fighting fish", which is counted by the same formula as more classical objects, such as two-stack sortable permutations, non-separable planar maps and $\nu$-Tamari intervals. In this talk, we explore the bijective aspect of fighting fish by establishing a bijection to two-stack sortable permutations, using a new recursive decomposition of these permutations. With our bijection, we give combinatorial explanations of several results of fighting fish previously proved previously with generating functions. We also discuss ideas on extending this bijective connections to other objects.
Abstract: Motivated by the study of phase transitions in the models of random graphs with a condition of embeddability, we are interested by the asymptotic enumeration of cubic multigraphs embeddable on a given surface of genus $g$. We obtained the asymptotic number of this family of cubic multigraphs. Our method consists of first reducing the enumeration problem to the 3-connected case, then transfer it to the domain of maps using a well-known theorem about uniqueness of embedding of certain graphs, and finally count the corresponding maps using previous results and bijections. The transfer of enumeration problems from maps to graphs is done with singularity analysis on generating functions. This is a joint work with Mihyun Kang, Michael Moßhammer and Philipp Sprüssel.Same topic: Journées ALEA, CIRM, 2018/03.
Abstract: In additive combinatorics, the recent work of Croot, Lev and Pach introduces a powerful and simple method called the ``polynomial method'', which led to breakthroughs in upper bounds of several problems in additive and extremal combinatorics. In this talk, we present an analysis of the polynomial method by Sawin and Tao, which is centered around a new notion called "slice rank" on tensors. Through two examples, cap set and sunflower-free families, we will see a general scheme of the polynomial method and how it can be applied to various problems. We will also see some limits of this method. This is a presentation of a work of Sawin and Tao, not the work of the presentater.
Abstract: Let v be an arbitrary path made of north and east steps. The lattice Tam(v), based on all paths weakly above the path v sharing the same endpoints as v, was introduced by Préville-Ratelle and Viennot (2014) and corresponds to the usual Tamari lattice in the case v=(NE)^n. They showed that Tam(v) is isomorphic to the dual of Tam(v'), where v' is the reverse of v with N and E exchanged. Our main contribution is a bijection from intervals in Tam(v) to non-separable planar maps. It follows that the number of intervals in Tam(v) over all v of length n is 2(3n+3)!/(n+2)!/(2n+3)!. This formula was first obtained by Tutte(1963) for non-separable planar maps. We also show that the isomorphism between Tam(v) and the dual of \Tam(v') is equivalent to map duality under our bijection.Same topic: Journées ALEA, CIRM, 2016/03; Journée cartes, IHES, 2015/04; Séminaire Combinatoire, LIX, 2016/06
Abstract : In the study of combinatorial maps, constellations possess a particular position. They are both a special model and a generalization of bipartite maps, and they are also related to factorisations in the symmetric group. Even if planar constellations are well-understood thanks to bijections, their general functional equation remains unsolved. Constellations in higher genera remains mysterious. In this talk, we will see the formulation of a functional equation for constellations, in both planar and higher genera case, the resolution for the planar case, and a result of rationality in higher genera for the bipartite case.Same topic: Séminaire Combinatoire, LIAFA, 2015/03; Séminaire SpecFun, INRIA Saclay, 2015/05.
Abstract : Irreducible characters in the symmetric group are of special interest in combinatorics. They can be expressed either combinatorially with ribbon tableaux, or algebraically with contents. In this paper, these two expressions are related in a combinatorial way. We first introduce a fine structure in the famous jeu de taquin called "trace forest", with which we are able to count certain types of ribbon tableaux, leading to a simple bijective proof of a character evaluation formula in terms of contents that dates back to Frobenius (1901). Inspired by this proof, we give an inductive scheme that gives combinatorial proofs to more complicated formulae for characters in terms of contents.
Abstract : Constellations and hypermaps generalize combinatorial maps, i.e. embedding of graphs in a surface, in terms of factorization of permutations. In this paper, we extend a result of Jackson and Visentin (1990) on an enumerative relation between quadrangulations and bipartite quadrangulations. We show a similar relation between hypermaps and constellations by generalizing a result in the original paper on factorization of characters. Using this enumerative relation, we recover a result on the asymptotic behavior of hypermaps of Chapuy (2009).Same topic: Journée Cartes, LIX, 2013/02; ALEA, CIRM, 2013/03; Workshop "Enumerative Combinatorics", Oberwolfach, 2014/03; Seminar Diskrete Mathematik und Optimierung, TU Graz, 2014/11.
Abstract : The Sand Pile Model (SPM) and its generalization, the Ice Pile Model (IPM), originate from physics and have various applications as simple discrete dynamical systems. In this talk, we will deal with enumeration and exhaustive generation of accessible configurations of the system. The central ingredient is a unique decomposition theorem for SPM configurations, based on the notion of staircase bases. Based on this theorem, we provide a unified treatment leading to a recursive formula for counting, to a random generation method and to a constant amortized time (CAT) algorithm for the exhaustive generation of all SPM configurations with given weight. The same approach is extended to the Ice Pile Model. Joint work with Roberto Mantaci.