Titles and abstracts


Massachusetts institute of technology, June 23-27, 2014

Home    contacts/feedback    PROGRAM    ABSTRACTS    Local Info    registration    Photos    tournament



Partitions with fixed difference between largest and smallest parts

This is joint work with Matthias Beck and Neville Robbins. We begin with a short history of related problems. Our main object will be consideration of \(p(n,t)\), the number of partitions of \(n\) in which the difference between largest and smallest parts is \(t\). We show that when \(t>1\) the related generating function is an explicitly given rational function. We then generalize this to \(p(n,t_1,t_2,...,t_k)\) which denotes the number of partitions of \(n\) in which there is a subsequence of parts \(s_0,s_1,s_2,\ldots s_k\) (where \(s_0\) is the smallest part and \(s_k\) is the largest part) such that \(s_1-s_0=t_1, s_2-s_1=t_2, s_3-s_2=t_3, ...\) Again the related generating function is an explicitly given rational function.


The combinatorics of \(CAT(0)\) cube complexes


Weighted walks around dissected polygons

In 1973, Conway and Coxeter introduced arithmetical frieze patterns via a local determinant condition, and they classified the friezes via triangulated polygons. Broline, Crowe and Isaacs in 1974 explained the frieze matrix associated to the fundamental region of the frieze pattern as enumerating special arcs of the triangulated polygon, and they gave a formula for the determinant of this matrix. This result was generalized 2012 by Baur and Marsh to frieze patterns of cluster variables arising from the Fomin-Zelevinsky cluster algebra of type A.

In joint work with Thorsten Holm and Peter Jörgensen, the results by Broline, Crowe and Isaacs were generalized and refined in a different direction, namely to \(d\)-angulations of polygons and associated generalized arithmetical frieze patterns. Going further, in the talk arbitrary polygon dissections and polynomially weighted walks around such dissected polygons are discussed. The weight matrix associated to the walks around a dissected polygon satisfies a complementary symmetry condition; its determinant is a multisymmetric multivariate polynomial given explicitly. Furthermore, this matrix may be transformed over a ring of Laurent polynomials into a nice diagonal form depending only on the pieces of the dissection. Considering the polynomial frieze associated to the dissection, the non-zero local determinants are explicitly given monomials, a result generalizing the original Conway-Coxeter association of friezes to triangulated polygons.


Even more intriguing, if rather less plausible...

The title is how Peter McMullen described his own conjectured characterization of the f-vectors of simplicial polytopes in his 1971 lecture notes on the upper bound conjecture written with Geoffrey Shephard. Yet by the end of that decade, the so-called g-conjecture would become the g-theorem, and algebraic combinatorics (as practiced at MIT) would have attracted the attention of mainstream mathematics, almost entirely due to the startling proof given by Richard Stanley.

I will briefly describe some of the events leading to this proof and some of its still developing consequences.


Let C be a Cohen-Macaulay complex...

The concept of Cohen-Macaulay complexes emerged in the mid-1970s in the work of Richard Stanley, inspired by important results of Mel Hochster and his student Gerald Reisner. Independently around the same time, Ken Baclawski launched the idea of Cohen-Macaulay posets. Others soon followed, and an attractive new area of mathematics took shape. As the main architect of these developments, Richard has made fundamental contributions to the area over many years.

Much of the appeal of the concept of C-M-ness stems from its “interdisciplinary” character, building on and having bearing on several mathematical areas in addition to combinatorics, notably several parts of algebra, geometry and topology. However, what bestows lasting importance on the concept is its remarkable record of being a key ingredient not only for "abstract" theoretical understanding but also for "concrete" problem solving in several of these diverse areas.

In this talk I will briefly share some memories from the heady early days of Cohen-Macaulay complexes, I will mention some of the ways that the concept has developed and I will exemplify the role played by the notion of Cohen-Macaulay complexes in some current developments.


Peak algebras, paths in the Bruhat graph, and Kazhdan-Lusztig polynomials

We give a new characterization of the peak subalgebra of the algebra of quasisymmetric functions and use this to construct a new basis for this subalgebra with certain properties. As an application of these results we obtain a combinatorial formula for the Kazhdan-Lusztig polynomials which holds in complete generality and is simpler and more explicit than any existing one. We then show that, in a certain sense, this formula cannot be simplified. This is joint work with Fabrizio Caselli.


Lattice path enumeration


Split graphs and counting NG-graphs

A graph \(G\) is an NG-graph if it satisfies the Nordhaus-Gaddum inequality, that its chromatic number plus the chromatic number of its complement is less than or equal to its number of vertices plus 1, with equality. In this talk, we will explore connections between NG-graphs and split graphs and count the number of NG-graphs on n vertices. This is joint work with Ann N. Trenk (Wellesley College).


Bijective Enumerations on Humps and Peaks in \((k,a)\)-paths and \((n,m)\)-Dyck paths

I will talk about some recent work on two kinds of lattice paths: \((k,a)\)-paths and \((n,m)\)-Dyck paths. Recently Mansour and Shattuck studied \((k,a)\)-paths and gave formulas that relate the total number of humps (peaks) in all \((k,a)\)-paths to the number of super \((k,a)\)-paths. These results generalize earlier results of Regev on Dyck paths and Motzkin paths. Their proofs are based on generating functions and they asked for bijective proofs for their results. We will first give bijective proofs of Mansour and Shattuck's results. Then we extend the study to \((n,m)\)-Dyck paths and give a bijection that relates the total number of peaks in all \((n,m)\)-Dyck paths to certain free \((n,m)\)-paths when \(n\) and \(m\) are coprime. From this bijection we get the number of \((n,m)\)-Dyck paths with exactly \(j\) peaks, which is a generalization of the well-known result that the number Dyck paths of order \(n\) with exactly \(j\) peaks is the Narayana number \(\frac{1}{k}{n-1\choose k-1}{n\choose k-1}\). This is joint work with Yingying Nie and Xuezhi Sun.


The surprising similarity of shifted simplicial complexes and matroids


Character Polynomials

Character polynomials provide a combinatorial description of the characters of the irreducible representations of the symmetric group. Using generating functions and some facts about integer partitions, but no representation theory, we can use these polynomials to show that certain row sums in the character table for the symmetric group are positive. Since the properties of partitions needed also hold when restricted to self-conjugate partitions, we can establish the positivity of two rows for the price of one polynomial.


Two EC tidbits

This talk will give bijective proofs of two enumerative results that, as Richard Stanley noticed right away, can also be proved non-bijectively as consequences of some exercises in a certain two-volume book on enumerative combinatorics. The first one is the fact that the distribution of the major index on 321-avoiding involutions is given by the central \(q\)-binomial coefficients. The second one is that the number of pairs of non-crossing Grand Dyck paths is equal to the number of pairs of non-crossing Dyck path prefixes of the same length."


Subtraction-free complexity

I will discuss the problem of dependence of computational complexity on the set of allowed arithmetic operations. An important role in this context is played by the notion of subtraction-free complexity, the version that allows addition, multiplication, and division, but not subtraction. This is joint work with D. Grigoriev and G. Koshevoy (arXiv:1307.8425).



This will be a historical survey of P-partitions, with emphasis on the early work of MacMahon and others.


The Legend of Richard Stanley


Real-rootedness results for triangulation operations inspired by the Tchebyshev polynomials

We will review Tchebyshev posets and a triangulation operation on simplicial complexes that gives rise to the Tchebyshev polynomials. We outline how this construction may be used to prove that the derivative polynomials for hyperbolic tangent and secant have real roots. Then we turn to generalized Tchebyshev triangulations, explore results, counterexamples, and open questions regarding their real-rootedness. The results on generalized Tchebyshev triangulations are joint work with Eran Nevo.


Posets that are homotopy equivalent to a ball or a sphere

This talk will introduce a new class of poset edge-labelings called \(SB\)-labelings. I will briefly indicate why lattices with \(SB\)-labelings have the property that each open interval is homotopy equivalent to a ball or a sphere of some dimension. Then I will describe \(SB\)-labelings for several familiar lattices and suggest other examples that could perhaps also admit \(SB\)-labeling. This is joint work with Karola Meszaros.


Stanley's Influence on Monomial Ideals

Following the pioneering work [R.P. Stanley, The upper bound conjecture and Cohen--Macaulay rings, Stud. Appl. Math., 54 (1975), 135-142] of Richard Stanley, in the late 1970s a new and exciting trend of commutative algebra, the combinatorial study of squarefree monomial ideals, broke out. Since then, it has been one of the most active areas of commutative algebra. In my talk a quick survey of monomial ideal theory developed for the last few decades will be supplied.


Given a finite real hyperplane arrangement with isometric cones, is it a Coxeter arrangement?


Truncations of Stanley symmetric functions and amplituhedron cells

Stanley symmetric functions were invented (by Stanley) with applications to the enumeration of reduced words in the symmetric group in mind.
Recently, the ""amplituhedron"" was introduced in the study of scattering amplitudes in \(N=4\) super Yang Mills. I will talk about a formula for the cohomology class of a (tree) amplituhedron variety as the truncation of an affine Stanley symmetric function.


Cutting Polytopes

We studies two examples of polytope slices, hypersimplices as slices of hypercubes and edge polytopes. For hypersimplices, the main result is a proof of a conjecture by R. Stanley which gives an interpretation of the Ehrhart \(h^*\)-vector in terms of descents and excedances. Our proof is geometric using a careful book-keeping of a shelling of a unimodular triangulation. We generalize this result to other closely related polytopes. We next study slices of edge polytopes. Let \(G\) be a finite connected simple graph with \(d\) vertices and let \(P_G\) be the edge polytope of \(G\). We call \(P_G\) decomposable if \(P_G\) decomposes into integral polytopes \(P_{G_+}\) and \(P_{G_-}\) via a hyperplane, and we give an algorithm which determines the decomposability of an edge polytope. Based on a sequence of papers by Ohsugi and Hibi, we prove that when \(P_G\) is decomposable, \(P_G\) is normal if and only if both \(P_{G_+}\) and \(P_{G_-}\) are normal. We also study toric ideals of \(P_G\), \(P_{G_+}\) and \(P_{G_-}\). This part is joint work with Hibi and Zhang.


Quasisymmetric functions


\(h\)-polynomials of triangulations of flow polytopes

The \(h\)-polynomial of a simplicial complex is a way of encoding the number of faces of each dimension. I will introduce a multivariate generalization of the \(h\)-polynomials of unimodular triangulations of flow polytopes. The inspiration for this generalization lies in the subdivision algebra of flow polytopes, whose relations prescribe a way of subdividing flow polytopes. I will show how to use the generalization of the \(h\)-polynomials to prove certain nonnegativity properties in the subdivision and related algebras.


Questions on volumes of flow polytopes


Can irrational tilings give Catalan numbers?

We introduce and study irrational tilings on a line. We show that they are enumerated by diagonals of N-rational generating functions. We then discuss an intriguing conjecture on Catalan numbers. Joint work with Scott Garrabrant. The talk assumes no background and be somewhat entertaining, time permitting.


The Kronecker coefficients: an unexpected journey

Kronecker coefficients live at the intersection of representation theory, algebraic combinatorics and, most recently, complexity theory. They count the multiplicities of irreducible representations in the tensor product of two other irreducible representations of the symmetric group. While their journey started 75 years ago, they still haven't found their explicit positive combinatorial formula, and present a major open problem in algebraic combinatorics. Recently, they were given a new role in the field of Geometric Complexity Theory, initiated by Mulmuley and Sohoni, where certain conjectures on the complexity of computing and deciding positivity of Kronecker coefficients are part of a program to prove the ""P vs NP"" problem.
We will take the Kronecker coefficients to asymptotics land and bound them. As an unexpected consequence of this trip, we find bounds for the difference of consecutive coefficients in the q-binomial coefficients (as polynomial in q), generalizing Sylvester's unimodality theorem and connecting with results of Richard Stanley.
Joint work with Igor Pak.


Slicing permutohedra and zonotopes

Richard Stanley asked the question "How to calculate volumes of slices of the permutohedron?" We calculate volumes of slices for a more general class of polytopes, called zonotopes. We discuss how this leads to a certain bipartite analogue of the Tutte polynomial. We mention a connection of this work with the theory of knot invariants. The talk is based on a joint work with Nan Li, and also on a joint work with Tamas Kalman.


Lattice-point counting and cyclic sieving

Given a cyclic group \(G = \langle g \rangle\) acting on an integral polytope \(P\), let \(F(N,k)\) be the number of fixed points in \(NP\) (the \(N\)-fold dilation of \(P\)) under the action of \(g^k\). Can we write \(F(N,k)\) as the sum, over \(x\) in \(NP\), of \(\zeta^{f(x)}\), where \(\zeta\) is a primitive \(|G|\)th root of unity and \(f\) is some nice function on the lattice?


A problem from \(q\)-analogues and modular invariant theory


Rowmotion: Classical & Birational

If \(P\) is a finite poset, (classical) rowmotion (aka the Fon-der-Flaass map aka Panyushev complementation) is a certain permutation of the set of order ideals (or equivariantly the antichains) of \(P\). Various surprising properties of rowmotion have been exhibited in work of Brouwer/Schrijver, Cameron/Fon der Flaass, Panyushev, Armstrong/Stump/Thomas, Striker/Williams, and Propp/Roby. For example, its order is \(p + q\) when \(P\) is the product \([p] \times [q]\) of two chains, and several natural statistics have the same average over every rowmotion orbit (i.e., are "homomesic"). Recent work of Einstein/Propp generalizes rowmotion twice: first to the piecewise-linear setting of a poset's "order polytope", defined by Stanley in 1986, and then via detropicalization to the birational setting.

In these latter settings, generalized rowmotion no longer has finite order in the general case. Results of Grinberg and the speaker, however, show that it still has order \(p + q\) on the product \([p] \times [q]\) of two chains, and still has finite order for a wide class of forest-like ("skeletal") graded posets and for some triangle-shaped posets. Our methods of proof are partly based on those used by Volkov to resolve the type AA (rectangular) Zamolodchikov Periodicity Conjecture. Full details are in ArXiv:1402.6178v3.


Factoring the Characteristic Polynomial of a Poset

Given a poset \(P\), its characteristic polynomial \(\chi(P,t)\) is the generating function in the variable \(t\) for the Möbius function of \(P\). For many families of posets, every root of \(\chi(P,t)\) is in the set \(\mathbb{P}\) of positive integers. A number of different techniques have been devised for showing that \(\chi(P,t)\) factors over \(\mathbb{P}\) including Zaslavsky's theory of signed graphs, results by Saito and Terao about free hyperplane arrangements, and Stanley's Supersolvability Theorem. We will present a new, totally combinatorial method for proving factorization. This is joint work with Joshua Hallam.


Growth of ideals in subword posets


Evaluation of Hecke algebra traces at Kazhdan-Lusztig basis elements

For \(w\) a \(3412\)-, \(4231\)-avoiding permutation and \(\chi\) an irreducible Hecke algebra character, we use planar networks and a variation on Young tableaux to compute the polynomial \(\chi(q^{\ell(w)/2} C'_w)\), where \(C'_w\) is the signless Kazhdan-Lusztig basis element indexed by \(w\). Computations for induced sign and trivial characters are performed similarly. We present a conjecture for the evaluation of other Hecke algebra traces, and describe connections to the Shareshian-Wachs chromatic quasisymmetric functions.


Shuffles of Permutations

A shuffle of two words intersperses the letters of the words in such a way as to leave the letters in their original order in relationship to the original words. For example, the set of 2-shuffles of 1234 and 5678 includes the distinct shuffles 15236478 and 56123748, along with \({8\choose4} - 2=68\) others. A 3-shuffle intersperses the letters of three words simultaneously, as in 142758693, which is a 3-shuffle of 123, 456, and 789. In general, an \(n\)-shuffle of a list of \(n\) words can be defined similarly for any integer \(n\ge 2\).

While it is easy to count the number of shuffles of any finite number of words that are pairwise disjoint (in the sense that no two of the words share any common entries), it is more complex to determine the number of \emph{distinct} shuffles of words that are not pairwise disjoint, as some duplicate shuffles arise. In particular, my previous work has enumerated the distinct 2-shuffles of permutation words of any finite length, such as the distinct 2-shuffles of 1234 with 4132. This preliminary report will address progress on enumeration of the distinct 3-shuffles of certain permutations as well as on related questions.


Wishful thinking as a proof technique

I will give three examples from my own research of the efficacy of wishful thinking.


Topology of the permutation pattern poset

An occurrence of the pattern \(p\) in a permutation \(\pi\) is a subsequence of length \(|p|\) in \(\pi\) whose letters appear in the same order of size as the letters in \(p\). For example, the subsequence \(425\) in \(146253\) is an occurrence of \(213\). The set of all finite permutations forms a poset with respect to pattern containment. As this poset embodies all pattern containment (and avoidance) in permutations, it is a fundamental object in all studies of avoidance and containment. As for any poset, an irresistible question is what the Möbius function is and, more generally, the homotopy type of its intervals. We only know answers to that in a few special cases, but are very far from a general solution. For example, we know that intervals of \emph{layered} permutations are shellable and we can compute their Mö function in polynomial time. (A layered permutation is a concatenation of decreasing sequences, each with smaller letters than the next, such as 321465). The same is true for intervals of permutations with a fixed number of descents, and we can also compute, in polynomial time, the Möbius function for intervals of \emph{separable} permutations (those avoiding 2413 and 3142) and we conjecture that they are also shellable. This is a poset with an enormously rich structure, only a little of which is understood so far. I will report on joint work with Peter McNamara and work of my student Jason Smith.


Generalized stability of Kronecker coefficients

Kronecker coefficients are tensor product multiplicities for symmetric group representations. It is well-known that not much is known about them. In this talk we plan to discuss some new theorems and conjectures about how these coefficients stabilize or de-stabilize in various limiting cases. A typical (easy) case is the classical result of Murnaghan that corresponds to incrementing the first rows of a triple of Young diagrams.


Fingerprinting Richard Stanley

Suppose that mathematician M has just proved theorem T. How is M to know if her result is truly new, or if T already exists in the literature? I will discuss existing databases of theorems which assign a small, language-free, canonical, and searchable ``fingerprint'' to their entries -- a concept that is, in a way, orthogonal to Richard Stanley's Catalan compilation. This talk is also intended as a call to the mathematical community to devise such encodings of mathematical results, which can then be catalogued in searchable fingerprint databases. The pace of mathematical research makes these databases crucial tools for the advancement of our field, enhanced experimental mathematics, and even the refereeing process. This talk is based on joint work with Sara Billey.


Assembling the genome of gingivitis from a single cell

The lion's share of bacteria in various environments cannot be cloned in the laboratory and thus cannot be sequenced using conventional technologies. We present a single-cell genome sequencing approach to address this problem, and apply it to bacterial cells within a complex biofilm from a hospital bathroom sink drain. Here we focus on recovery of a novel strain of Porphyromonas gingivalis (gingivitis) using the single-cell assembly tool SPAdes.
Assembly of single-cell data is challenging because of highly non-uniform read coverage as well as elevated levels of sequencing errors and chimeric reads.
I will explain the de Bruijn Graph approach to conventional genome assembly and adaptations made for single-cell data.


Chromatic quasisymmetric functions, Eulerian numbers, and Hessenberg varieties

We consider three distinct topics of independent interest; one in symmetric function theory, one in enumerative combinatorics, and one in algebraic geometry. The topic in symmetric function theory deals with a refinement of Stanley's chromatic symmetric functions, the one enumerative combinatorics concerns q-Eulerian numbers, and the one in algebraic geometry deals with a representation of the symmetric group on the cohomology of the regular semisimple Hessenberg variety of type A. Our purpose is to explore some connections between these topics and consequences of these connections. This talk is based on joint work with John Shareshian.


Comparative Cryptanalytic Complexity of System-Solving, an EC1 Exercise

The F4/F5 Groebner basis method are the de facto standard when cryptographers consider the complexity of solving systems of nonlinear equations. However, we show that for many classes of systems of cryptographical importance, we should evaluate the complexity of solving such systems using simpler methods such as XL or even brute force. We back this up with combinatorial analysis and experiments.


The Toda lattice and Bruhat interval polytopes

The Toda lattice is an integrable system representing the dynamics of \(n\) particles of unit mass, moving on a line under the influence of exponential repulsive force. The famous sorting property says that as time goes to \(\pm \infty\), the solution \(L(t)\) becomes a diagonal matrix, with eigenvalues sorted in descending and ascending order, respectively. In joint work with Kodama, we give a generalization of this property for the full Kostant-Toda lattice, using the combinatorics of the totally non-negative flag variety. This work naturally leads to the study of the Bruhat interval polytope \(P_{v,w}\), that is, the convex hull of all permutation vectors \(z\) with \(v \leq z \leq w\) in Bruhat order. I'll end with some combinatorial results (joint with Tsukerman) on Bruhat interval polytopes.


Diagrams of Affine Permutations and Their Labellings

We study affine permutation diagrams and their labellings with positive integers. Balanced labellings of a Rothe diagram of a finite permutation were defined by Fomin-Greene-Reiner-Shimozono, and we extend this notion to affine permutations. The balanced labellings give a natural encoding of the reduced decompositions of affine permutations. We show that the sum of weight monomials of the column-strict balanced labellings is the affine Stanley symmetric function which plays an important role in the geometry of the affine Grassmannian. Furthermore, we define set-valued balanced labellings in which the labels are sets of positive integers, and we investigate the relations between set-valued balanced labellings and nilHecke words in the nilHecke algebra. A signed generating function of column-strict set-valued balanced labellings is shown to coincide with the affine stable Grothendieck polynomial which is related to the \(K\)-theory of the affine Grassmannian. Moreover, for finite permutations, we show that the usual Grothendieck polynomial of Lascoux-Schützenberger can be obtained by flagged column-strict set-valued balanced labellings. Using the theory of balanced labellings, we also give a necessary and sufficient condition for a diagram to be a permutation diagram.
This is joint work with Hwanchul Yoo (KIAS).


Patterns in the Chip-firing game

The parallel chip-firing game is an automaton on graphs in which vertices “fire” chips to their neighbors. This simple model contains much emergent complexity and has many connections to different areas of mathematics, such as the abelian sandpile model, graph Laplacians, and self-organized criticality. In this work, we completely characterize the periodic firing sequences that can occur in an ordinary game, which have a surprisingly simple combinatorial description. This is joint work with Ziv Scully and Damien Jiang.


Ping-pong tournament, puzzles and juggling

Wednesday afternoon there will be a ping-pong tournament. To play in the tournament, you must sign-up on this form. Concurrent with the tournament, Peter Winkler will lead a puzzle activity and Allen Knutson and Greg Warrington will have a juggling demonstration. All events take place at the MIT Dupont Gym, 120 Vassar St. (see campus map).