Summer School on Algebraic and Enumerative Combinatorics

Confirmed Participants

S. Miguel de Seide, Portugal

José Antonio Agapito Ruiz, University of Lisboa, Portugal Poster
Carlos André, University of Lisboa, Portugal
Samuel Asefa, Addis Ababa University, Ethiopia
Olga Azenhas, University of Coimbra, Portugal
Eli Bagno, Jerusalem College of Technology, Israel Talk 3.7.2012
Sabine Beil, University of Vienna, Austria
Adam Bohn, Queen Mary, University of London, UK Poster
Francesco Brenti, Universitá di Roma “Tor Vergata”, Italy
Francesca Camagni, Universitá di Bologna, Italy
Wathek Chammam, Faculty of Sciences of Gabes, Tunisia
Yao-ban Chan, University of Vienna, Austria Poster
Steven Collazos, San Francisco State University, USA
Laura Colmenarejo, University of Seville, Spain
Alessandro Conflitti, CMUC & University of Coimbra, Portugal
Julien Courtiel, Université de Bordeaux I, France
Agnieszka Czyżewska-Jankowska, Wroclaw University, Poland
Jessica Delgado, San Francisco State University, USA
Tiago Dinis da Fonseca, Université de Montréal, Canada Talk 11.7.2012
Maciej Dołęga, Wroclaw University, Poland Talk 11.7.2012
Rui Duarte, University of Aveiro, Portugal
Aram Emami, University of Coimbra, Portugal Talk 4.7.2012
Pedro Freitas, University of Lisboa, Portugal
Regina Gente, Philipps-Universität Marburg, Germany Talk 4.7.2012
António Guedes de Oliveira, University of Porto, Portugal
Ayşin E. Gürsoy, Istanbul Technical University, Turkey Poster
Stuart A. Hannah, University of Strathclyde, UK
Aoife Hennessy, University College Cork, Ireland Poster
Lech Jankowski, Wroclaw University, Poland
Matthieu Josuat-Vergès, Université Paris-Est Marne-la-Vallée, France Talk 4.7.2012
Yvonne Kemper, University of California Davis, USA Poster
William J. Keith, University of Lisboa, Portugal
Masahide Konishi, Nagoya University, Japan Poster
Christian Krattenthaler, Universität Wien, Austria
Robin Langer, CNRS (at LIAFA, University Paris Diderot), France Talk 11.7.2012
Inês Legatheaux Martins, University of Lisboa, Portugal Talk 4.7.2012
Matthias Lenz, Technische Universität Berlin, Germany Talk 4.7.2012
Zhicong Lin, Institut Camille Jordan, France Poster
Jocelyn Lochon, University of Lisboa, Portugal
Jack Love, San Francisco State University, USA Poster
Ricardo Mamede, University of Coimbra, Portugal
Maria Leonor Moreira, University of Porto, Portugal
Henri Mühle, Universität Wien, Austria
Mulugeta Naizghi, Addis Ababa University, Ethiopia
Marc Noy, Universitat Politècnica de Catalunya, Spain
Michaela Puck Rombach, University of Oxford, UK
Lander Ramos, Universitat Politècnica de Catalunya, Spain
Vic Reiner, University of Minnesota, USA
Vivien Ripoll, Université du Québec à Montréal, Canada Talk 11.7.2012
Lukas Riegler, Universität Wien, Austria
Maria de Fátima Rodrigues, NOVA University of Lisbon, Portugal
Christina Savvidou, University of Athens, Greece
Travis Scrimshaw, University of California Davis, USA Poster
Fiona Skerman, University of Oxford, UK
Vasu Tewari, University of British Columbia, Canada
Marko Thiel, University of Vienna, Austria
Maria Manuel Torres, University of Lisbon, Portugal
Omar Tout, University of Bordeaux 1, France Talk 11.7.2012
Eleni Tzanaki, University of Crete, Greece Talk 4.7.2012
Mirkó Visontai, University of Pennsylvania, USA Poster
Vincent Vong, LIGM, Université Paris-Est Marne-la-Vallée, France
Nathan Williams, University of Minnesota, USA Talk 11.7.2012
Thomas Wong, University of British Columbia, Canada Poster

Contributions

Talk 3.7.2012

Name: Eli Bagno
Affiliation: Jerusalem College of Technology, Israel
Title: Permutation statistics on the alternating colored permutation group
Abstract: The alternating colored permutation group is the analogue of the alternating group inside the wreath product $\mathbb{Z}_r \wr S_n$. We present a set of 'Coxeter like' presentation for these groups and calculate the length function with respect to this presentation. Then we present this group as covering of $\mathbb{Z}_{\frac{r}{2}} \wr S_n$ and use this view to give another expression for the length function. We also apply this covering to lift a known parameter of $\mathbb{Z}_{\frac{r}{2}} \wr S_n$ to the alternating colored permutation group.

Talks 4.7.2012

Name: Matthieu Josuat-Vergès
Affiliation: Université Paris-Est Marne-la-Vallée, France
Title: Coxeter theoretic interpretations of Euler numbers
Abstract: The so-called Euler numbers count alternating permutations in the symmetric group. Springer showed that there is a generalization of alternating permutations to any finite Coxeter group, namely the biggest descent class. Besides, Stanley showed that Euler numbers count orbits of maximal chains in the set partition lattice. The purpose of this work is twofold: give an alternative proof of Springer's result, and present a Coxeter theoretic perspective of Stanley's result.

Name: Regina Gente
Affiliation: Philipps-Universität Marburg, Germany
Title: The Varchenko Matrix for Cones
Abstract: Let ${\mathcal A}$ be an arrangement of hyperplanes and ${\mathcal P}({\mathcal A})$ the set of its regions and attach to each hyperplane H its weight $a_H$. Varchenko defined a bilinear form $B(\cdot,\cdot)$ on the vector space freely generated by the regions by setting $B(P,Q)=\prod_{H\in T} a_H$, $T:=\{H \in {\mathcal A}: \text{H separates P and Q}\}$. Varchenko proved, that the determinant of the matrix of $B(\cdot,\cdot)$ is determined by the geometry of the arrangement and allows a nice factorization.
Now consider a central subarrangement ${\mathcal C}$ of ${\mathcal A}$. Let ${\mathcal K}$ be a region of the subarrangement. We restrict the bilinear form $B(\cdot,\cdot)$ to the regions from ${\mathcal P}({\mathcal A})$ that lie in ${\mathcal K}$. Then we show that the determinant of this restricted matrix is determined by the geometry of the arrangement inside the cone ${\mathcal K}$ and factors nicely.

Name: Matthias Lenz
Affiliation: Technische Universität Berlin, Germany
Title: Zonotopal algebra and forward exchange matroids
Abstract: Zonotopal algebra is the study of a family of pairs of dual vector spaces of multivariate polynomials that can be associated with a list of vectors $X$. It connects objects from combinatorics, geometry, and approximation theory. The origin of zonotopal algebra is the pair $(D(X),P(X))$, where $D(X)$ denotes the Dahmen-Micchelli space that is spanned by the local pieces of the box spline and $P(X)$ is a space spanned by products of linear forms. A common property of all these spaces is that their Hilbert series is a matroid invariant.
In this talk, I will give an introduction to zonotopal algebra and I will define a new family of zonotopal spaces. The underlying combinatorial structure of those spaces is called forward exchange matroid. A forward exchange matroid is an ordered matroid together with a subset of its set of bases that satisfies a weak version of the basis exchange axiom.
This talk will be based on this preprint.

Name: Aram Emami
Affiliation: University of Coimbra, Portugal
Title: Non-symmetric Cauchy formula for Demazure characters and semi-skyline augmented fillings
Abstract: The well known Cauchy identity is the best characterization of Schur functions that can be derived using the Robinson-Schensted-Knuth (RSK) correspondence. The Cauchy kernel expands as a sum of products of Schur functions in two distinct set of variables and RSK algorithm gives a bijective proof of this identity by providing a bijection between words in commutative biletters and pairs of semi-standard Young tableaux of the same shape.
Alain Lascoux used Demazure operators to show that half of the Cauchy kernel expands as a sum of products of two families of key polynomials, one Demazure characters and the other Demazure atoms. The special case of nonsymmetric Macdonald polynomials when $q=t=0$ determines Demazure atoms that have a combinatorial description in terms of semi-skyline augmented fillings.
From the RSK correspondence we know that this half Cauchy kernel can be expanded as a sum of products of monomials determined by a subfamily of pairs of semi-standard Young tableaux. To characterize those pairs of semi-standard Young tableaux, we use an analogue of RSK for pairs of semi-skyline augmented fillings whose shapes are rearrangements of the same partition. Sarah Mason has shown that the shape of a semi-skyline augmented filling defines the right key of a semi-standard Young tableau. These shapes are precisely the key conditions, due to Alain Lascoux and Marcel-Paul Schützenberger, to characterize the pairs in that subfamily of semi-standard Young tableaux. This gives a bijective proof for the non-symmetric Cauchy formula.

Name: Inês Legatheaux Martins
Affiliation: University of Lisboa, Portugal
Title: Symmetries and partial symmetries of tensors: applications to matroid theory
Abstract: In this talk, we will introduce an elegant duality, usually referred to as Schur-Weyl duality, between the representations of the general linear group $GL_{m}(\mathbb{C})$ and those of an algebraic structure called the rook monoid.
Since the rook monoid contains the symmetric group, its representation theory provides a natural context to generalize concepts such as symmetry classes of tensors and decomposable symmetrized tensors. Our approach using Schur-Weyl dualities will allow us to obtain extensions of such notions and discuss some applications to matroids that arise naturally within this context.

Name: Eleni Tzanaki
Affiliation: University of Crete, Greece
Title: Generalized cluster complexes, integer partitions and extended Catalan arrangements
Abstract: This is joint work with Susanna Fishel and Myrto Kallipoliti.
We study the relation between the $m$-generalized cluster complex $\Delta^m(\Phi)$ and the $m$-extended Catalan arrangement ${\rm Cat}^m(\Phi)$, where $\Phi$ is a root system of type $A$ or $C$. It is known that the facets of $\Delta^m(\Phi)$ as well as the dominant regions in ${\rm Cat}^m(\Phi)$ are counted by the $m$-th generalized Catalan number. Moreover, the facets of the positive part of $\Delta^m(\Phi)$ as well as the bounded dominant regions in ${\rm Cat}^m(\Phi)$ are counted by the $m$-th ``positive'' generalized Catalan number. However, no bijection between either pair of sets is known for $m \geq 2$. This work presents a method of constructing a bijection between the first pair of sets with the property that facets containing the negative simple root $-\alpha$ are mapped to regions having the hyperplane $H_{\alpha,m}$ as a separating wall. As a result, the restriction of such a bijection on the positive part of $\Delta^m(\Phi)$, is a bijection between the second pair of sets.

Talks 11.7.2012

Name: Maciej Dołęga
Affiliation: Wroclaw University, Poland
Title: Jack characters and combinatorics of bipartite maps
Abstract: Jack characters are functions on the set of Young diagrams which can be considered as continous deformation of normalized characters of the symmetric group. It is quite unexpected that the problem of studying their structure seems to be very close to the problem of understanding the combinatorics of bipartite maps. I am going to explain this connection and I am going to present some conjectures related to this problem.

Name: Vivien Ripoll
Affiliation: Université du Québec à Montréal, Canada
Title: Asymptotical behaviour of roots of infinite Coxeter groups
Abstract: Let $W$ be an infinite Coxeter group. We study the set $E$ of limit roots of $W$, i.e., the limit points of the “normalized” roots of $W$ (representing the directions of the roots in a root system of $W$). We show that it is contained in the isotropic cone of the bilinear form $B$ associated to a geometric representation, and we illustrate this behaviour with examples and pictures in rank 3 and 4. After defining a natural geometric action of $W$ on $E$, we exhibit a natural finite subset of $E$ (formed by the limit roots of some dihedral reflection subgroups of $W$), and prove that its orbit is dense in $E$. (Joint work with M. Dyer, Ch. Hohlweg and J.-P. Labbé; see preprint)

Name: Omar Tout
Affiliation: University of Bordeaux 1, France
Title: Polynomiality of the structure coefficients of Hecke ring $\mathcal{S}_{2n},\mathcal{B}_n)$
Abstract: The algebra of the symmetric group $\mathbb{C}[S_n]$ is the algebra of linear combinations of permutations of size n. A basis of the center of $\mathbb{C}[S_n]$ is given by $K_\lambda$, which are the sums of permutations with cycle-type $\lambda$. The structure coefficients $\alpha_{\lambda\mu}^{\nu}$ describe the product in the center of $\mathbb{C}[S_n]$: $$K_\lambda K_\mu=\sum_\nu \alpha_{\lambda\mu}^{\nu}K_\nu$$ In 1958, Farahat and Higman proved the polynomiality of the coefficients $\alpha_{\lambda\mu}^{\nu}$ in n when $\lambda$, $\mu$ and $\nu$ are fixed partitions, completed with parts equal to $1$ to get partitions of $n$. In 1999, Ivanov and Kerov gave a new proof of this result through the introduction of partial permutations. In this talk, we will first recall these results. Second, we will give an analogous statement arising in the context of Hecke ring $(S_{2n},B_n)$, recently investigated by Aker and Can. Third, we will propose a new method, based on Ivanov and Kerov's one to get Aker and Can's result.

Name: Nathan Williams
Affiliation: University of Minnesota, USA
Title: Cyclic Symmetry of the Scaled Simplex
Abstract: Let $\mathcal{Z}_m^k$ consist of the $m^k$ alcoves contained in the $m$-fold dilation of the fundamental alcove of the type $A_k$ affine hyperplane arrangement. As the fundamental alcove has a cyclic symmetry of order $(k+1)$, so does $\mathcal{Z}_m^k$. By bijectively exchanging the natural poset structure of $\mathcal{Z}_{m}^k$ for a natural cyclic action on a set of words, we prove that $(\mathcal{Z}_{m}^k,\prod_{i=1}^{k} \frac{1-q^{m i}}{1-q^i},C_{k+1})$ exhibits the cyclic sieving phenomenon. This is joint work with Hugh Thomas.

Name: Robin Langer
Affiliation: CNRS (at LIAFA, University Paris Diderot), France
Title: Cylindric Plane Partitions
Abstract: Cylindric plane partitions may be thought of as a natural generalization of reverse plane partitions, which are in turn a natural generalization of regular plane partitions. In this talk I shall outline a new bijective proof for Borodin's hook-product formula for the enumeration of cylindric plane partitions. The proof makes use of Fomin's growth diagram framework and local rules for generalized RSK correspondences. The identity may also be proved using the theory of symmetric functions. I will discuss the relationship between these two approaches as well as a generalization involving Macdonald polynomials.

Name: Tiago Dinis da Fonseca
Affiliation: Université de Montréal, Canada
Title: Higher spin 6-Vertex model and Macdonald polynomials
Abstract: Symmetric polynomials play an interesting role in physics. For example, it is known that the partition function (a function that encodes the properties of the physical system) of the 6-Vertex model (in bijection with the Alternating Sign Matrices) is a Schur polynomial.
Recently, we discovered that the partition function, of a natural generalization of the 6-Vertex model (by a process called fusion), is also a symmetric polynomial, namely a precise Macdonald polynomial.
I'll start my talk, I briefly present the 6-Vertex model and its generalisation. In the rest of time, I show how to use the surprising result of Jimbo, Miwa, Feigin and Mukhin about Macdonald polynomials and vanishing conditions in order to obtain our main result: the partition function is in fact a Macdonald polynomial.

Posters

Name: José Antonio Agapito Ruiz
Title: A symbolic umbral characterization of Riordan arrays
Abstract: Riordan arrays are infinite lower triangular complex valued-matrices that have been applied to a wide range of subjects, from Computer Science to Combinatorial Physics, in connection with combinatorial identities, recurrence relations, walk problems, asymptotic approximation and the problem of normal ordering for boson strings, among other relevant topics. The usual way of approaching Riordan arrays is by means of generating functions. I will present a promising alternative characterization of Riordan arrays based on a symbolic renewed approach to umbral calculus. A deep generalization of an Abel's identity for polynomials is a key tool in our symbolic approach.

Name: Adam Bohn
Affiliation: Queen Mary, University of London, UK
Title: Chromatic roots as algebraic integers
Abstract: A chromatic root is a zero of the chromatic polynomial of a graph. At a Newton Institute workshop on Combinatorics and Statistical Mechanics in 2008, two conjectures were proposed on the subject of which algebraic integers can be chromatic roots, known as the “$\alpha + n$ conjecture” and the “$n\alpha$ conjecture”. These say, respectively, that given any algebraic integer $\alpha$ there is a natural number n such that $\alpha + n$ is a chromatic root, and that any positive integer multiple of a chromatic root is also a chromatic root. I will discuss recent progress I have made towards a proof of these conjectures. This includes the discovery that any quadratic or cubic integer is an integer shift of a chromatic root of a bipartite graph's complement, and that any positive integer multiple of a chromatic root of a generalized theta graph is also a chromatic root.

Name: Yao-ban Chan
Affiliation: Universität Wien, Austria
Title: A Monte Carlo study of non-trapped self-avoiding walks
Abstract: The enumeration of self-avoiding walks (a walk on a regular lattice which does not intersect itself) is a famous and heavily-studied problem in combinatorics. In this talk, we study non-trapped self-avoiding walks, which are self-avoiding walks that can be extended to an infinite length. For this purpose, we apply a powerful Monte Carlo method, flatPERM. We show how we have adapted this algorithm to generate non-trapped SAWs of length up to 1024 on the square, triangular and hexagonal lattices. We also present the results of this calculation: we find strong evidence that the growth constant and entropic and metric exponents are identical for non-trapped and all SAWs, and calculate the limiting ratio of non-trapped to all self-avoiding walks.

Name: Ayşin E. Gürsoy
Affiliation: Istanbul Technical University, Turkey
Title: Catalan Numbers and Parking Functions
Abstract: Joint work with Kürşat Aker.
In this work, we prove that two generating functions constructed from different incarnations of Catalan Numbers are equal. The sets $$U(n)= \left\{ (u_i) \in \mathbb{N}^{n+1}: \sum_{i=0}^n u_i = n \; \text{and} \; \sum_{i=0}^n i u_i \equiv {r \pmod {n+1}} \right\}$$ and $$V(n)= \left\{ (v_i) \in \mathbb{N}^n: \sum_{i=1}^n v_i = n \; \text{and} \; \sum_{i=1}^j v_i \geq j \right\}$$ have the same cardinality, Catalan number, $$C_n = \frac{1}{n+1}{2n \choose n}.$$
The generating function $\sum q^{n \choose u}$, where $u\in U(n)$, appears in [Aker, Kürşat. & Can, Mahir B. (2012). Proceedings of the American Mathematical Society Volume 140, Number 4, Pages 1113-1124] as the dimension counting generating function for the parking function module. In the same article, the authors conjecture that (Conjecture $1.1$ in [Aker & Can, op. cit.]) this generating function coincides with $\sum q^{n \choose v}$, where $v\in V(n)$. We prove this conjecture by combinatorial arguments.

Name: Aoife Hennessy
Affiliation: University College Cork, Ireland
Title: Riordan arrays and labelled Motzkin, Łukasiewicz and Schröder Lattice Paths
Abstract: We study a family of orthogonal polynomials. The coefficient array of these orthogonal poly\-nomials is shown to be an ordinary Riordan array. We introduce Riordan arrays. We express the generating function of the sequence of polynomials under study as a continued fraction and give a characterization of these polynomials in terms of related Riordan arrays. These Riordan arrays are associated with Motzkin, Łukasiewicz and Schröder paths. The special form of the production matrices is exhibited in these cases. This allows us to produce a bijection from a set of labelled Łukasiewicz paths to a set of labelled Motzkin and a set of labelled Schröder paths.

Name: Yvonne Kemper
Affiliation: University of California Davis, USA
Title: Flows on Simplicial Complexes
Abstract: Given a graph $G$, the number of nowhere-zero $Z_q$-flows $f_G(q)$ is known to be a polynomial in $q$. In this talk, we extend the definition of nowhere-zero $Z_q$-flows to simplicial complexes $D$ of dimension greater than one, and prove the polynomiality of the corresponding function $\#f_D(q)$ for certain $q$ and certain subclasses of simplicial complexes.

Name: Masahide Konishi
Affiliation: Nagoya University, Japan
Title: Counting the number of primitive idempotents of cyclotomic KLR algebras of type $A_{n}^{(1)}$.
Abstract: Recently, an interesting family of algebras, called KLR algebras, is introduced. They are generated by diagrams and relations among them. Then, in a special case, we can count up the number of primitive idempotents. I start this talk from the definition of KLR algebras, and explain how to count up primitive idempotents at the end.

Name: Zhicong Lin
Affiliation: Institut Camille Jordan, Lyon, France
Title: Jacobi-Stirling polynomials and P-partitions.
Abstract: We investigate the diagonal generating function of the Jacobi-Stirling numbers of the second kind ${\rm{JS}}(n+k,n;z)$ by generalizing the analogous results for the Stirling and Legendre-Stirling numbers. More precisely, letting ${\rm{JS}}(n+k,n;z)=p_{k,0}(n)+p_{k,1}(n)z+\dots+p_{k,k}(n)z^k$, we show that $(1-t)^{3k-i+1}\sum_{n\geq0}p_{k,i}(n)t^n$ is a polynomial in $t$ with nonnegative integral coefficients and provide combinatorial interpretations of the coefficients by using Stanley's theory of $P$-partitions.

Name: Jack Love
Affiliation: San Francisco State University, USA
Title: Home polytopes between regular polytopes
Abstract: Hom-polytopes are the polytopes of affine maps between two convex polytopes. Their study is motivated by categorical analysis of polytopes, a recent trend in this classical part of geometry. First steps towards a systematic theory were recently undertaken by Bogart-Contois-Gubeladze. Currently, our understanding is very limited even in the case of regular source and target polygons. We report on our joint ongoing project with J. Gubeladze on the hom-polytopes between higher dimensional regular polytopes. Counting their vertices is a blend of combinatorial, geometric, and arithmetic challenges.

Name: Travis Scrimshaw
Affiliation: University of California Davis, USA
Title: Combinatorial model for computing Hall-Littlewood Polynomials
Abstract: Hall-Littlewood polynomials are a class of symmetric functions that are indexed by partitions, depend on an additional parameter t, and in a sense interpolate between monomial functions and Schur functions. Inka Klostermann recently devised an algorithm using a class of SSYT to compute Hall-Littlewood polynomials in types $A_n$, $B_n$, and $C_n$ and is a combinatorial version of the Gaussent-Littelmann formula for computing Hall-Littlewood polynomials. In this talk, we will extend these results to certain cases of type $D_n$.

Name: Mirkó Visontai
Affiliation: University of Pennsylvania, USA
Title: On the roots of generalized Eulerian polynomials
Abstract: In recent years there has been much interest in studying the roots of generalized Eulerian polynomials. These generalizations arise from enumerative and algebraic generalizations of the descent generating polynomials. In this talk we present a novel approach.
We interpret Eulerian polynomials as the generating polynomials of inversion sequences. Recently, Savage and Schuster studied inversion sequences (also known as Lehmer codes) and introduced their generalizations, called $s$-inversion sequences. They defined various statistics on $s$-inversion sequences and explored their connection with $s$-lecture hall polytopes.
In this talk, we show that, for any sequence $s$, $E^{(s)}(x)$, the ascent polynomial — the generating polynomial of the ascent statistic over all $s$-inversion sequences — has only real roots. This result can be extended to a variety of $q$-analogs of $E^{(s)}(x)$. One corollary is that the MacMahon-Carlitz $q$-Eulerian polynomial has only real roots for nonnegative real $q$. This result proves a corollary of a conjecture of Chow and Gessel and corroborates their conjecture on the separation of these real roots.
This is joint work with Carla Savage.

Name: Thomas Wong
Affiliation: University of British Columbia, Canada
Title: Common Edges in Polygonal Triangulations
Abstract: Edge-flip distance between polygonal triangulations measures the degree of similarity between two rooted triangulations and has applications in balancing rooted binary trees. Currently, there are no known poly-time algorithm for computing edge-flip distances. However, the existence of matched edges makes computing geodesic distances more manageable. In this talk, we will describe a method of reducing the problem by partitioning it into smaller components. We will present some initial insight into the asymptotic distribution of these components as they are central to determining the effectiveness of this method.

Summer School on Algebraic and Enumerative Combinatorics Confirmed Participants