Abstract: In this talk, we survey some enumerative aspects of Tamari lattices. We first look at several generalizations of the Tamari lattice defined on lattice paths, including ν-Tamari lattices, and their properties. We then lay out many known bijections between Tamari intervals and other combinatorial objects in a categorized way, and discuss their enumerative consequences. We end with generalizations of the Tamari lattice in the context of Coxeter groups.

Abstract: We study parabolic aligned elements associated with the type-B Coxeter group and the so-called linear Coxeter element. These elements were introduced algebraically in (Mühle and Williams, 2019) for parabolic quotients of finite Coxeter groups and were characterized by a certain forcing condition on inversions. We focus on the type-B case and give a combinatorial model for these elements in terms of pattern avoidance. Moreover, we describe an equivalence relation on parabolic quotients of the type-B Coxeter group whose equivalence classes are indexed by the aligned elements. We prove that this equivalence relation extends to a congruence relation for the weak order. The resulting quotient lattice is the type-B analogue of the parabolic Tamari lattice introduced for type A in (Mühle and Williams, 2019). These lattices have not appeared in the literature before. As work in progress, we will also talk about various combinatorial models and bijections between them. Joint work with Henri Mühle and Jean-Christophe Novelli.

Abstract: The enumeration of linear λ-terms has attracted quite some attention recently, partly due to their link to combinatorial maps. Zeilberger and Giorgetti (2015) gave a recursive bijection between planar linear normal λ-terms and planar maps, which, when restricted to 2-connected λ-terms (i.e., without closed sub-terms), leads to bridgeless planar maps. Inspired by this restriction, Zeilberger and Reed (2019) conjectured that 3-connected planar linear normal λ-terms have the same counting formula as bipartite planar maps. In this article, we settle this conjecture by giving a direct bijection between these two families. Furthermore, using a similar approach, we give a direct bijection between planar linear normal λ-terms and planar maps, whose restriction to 2-connected λ-terms leads to loopless planar maps. This bijection seems different from that of Zeilberger and Giorgetti, even after taking the map dual. We also explore enumerative consequences of our bijections.

Abstract: In 2006, Chapoton defined a class of Tamari intervals called "new intervals" in his enumeration of Tamari intervals, and he found that these new intervals are equi-enumerated with bipartite planar maps. We present here a direct bijection between these two classes of objects using a new object called "degree tree". Our bijection also gives an intuitive proof of an unpublished equi-distribution result of some statistics on new intervals given by Chapoton and Fusy.

Abstract: A compacted binary tree is a directed acyclic graph encoding a binary tree in which common subtrees are factored and shared, such that they are represented only once. We show that the number of compacted binary trees of size n grows asymptotically like $\Theta(n! 4^n exp(3a_1 n^{1/3}) n^{3/4})$, where $a_1 \sim -2.338$ is the largest root of the Airy function. Our method involves a new two parameter recurrence which yields an algorithm of quadratic arithmetic complexity for computing the number of compacted trees up to a given size. We use empirical methods to estimate the values of all terms defined by the recurrence, then we prove by induction that these estimates are sufficiently accurate for large n to determine the asymptotic form. Our results also lead to new bounds on the number of minimal finite automata recognizing a finite language on a binary alphabet. As a consequence, these also exhibit a stretched exponential.

Abstract: We examine the asymptotics of a class of banded plane partitions under a varying bandwidth parameter m, and clarify the transitional behavior for large size n and increasing m = m(n) to be from $c_1 n^{-1} \exp(c_2 n^{1/2})$ to $c_3 n^{-49/72} \exp(c_4 n^{2/3} + c_5n^{1/3})$ for some explicit coefficients $c_1, ... , c_5$. The method of proof, which is a unified saddle-point analysis for all phases, is general and can be extended to other classes of plane partitions.

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.

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.

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.

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.

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.

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).

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.