Richard P. Stanley Seminar in Combinatorics

A finite collection of hyperplanes in a real vector space partition the vector space into subsets called the `faces' of the arrangement. The set of faces has an associative product and the resulting semigroup algebra turns out to have connections with probability and algebraic combinatorics. The talk will begin with a survey of these connections and will explain how the geometry and combinatorics of the hyperplane arrangement give nice results about the structure of the algebra. In particular, I will describe the quiver of the algebra, say that it is a Koszul algebra; and explain why the algebra depends only on the combinatorics of the arrangement.

In the theory of random matrices, and in the study of various related combinatorial problems, one of the key tools is the fact that certain probabilities of interest have a determinantal structure. One of the most general results along those lines is the Eynard-Mehta theorem; I'll discuss some recent work with Borodin giving a simple proof of this theorem using only linear algebra, and discuss its application to a certain growth model (the Schur process). I'll also discuss pfaffian versions (typically arising from symmetry conditions).

Given two projective varieties X and Y, their join X*Y is obtained by taking the Zariski closure of the union of all lines spanned by a point in X and a point in Y. The join of a variety X with itself is called the secant variety of X. In this talk, I will describe the construction of joins and secants in the combinatorial context of monomial ideals. For ideals generated by squarefree quadratic monomials, the generators of the secant ideals are obstructions to graph colorings and this leads to a commutative algebra version of the Strong Perfect Graph Theorem. Questions about secant varieties of combinatorially defined varieties (e.g. Grassmannians, determinantal varieties, toric varieties) can often be reduced to the monomial case. I will try to emphasize the combinatorial aspects of all of this, including the connections to graph theory, regular triangulations, and partially ordered sets. This is joint work with Bernd Sturmfels.

In 1965, Germain Kreweras published an enumerative result for planar lattice walks made of South, West and North-East steps. He proved that the number of walks of length 3n starting and ending at the origin and staying in the first quadrant is kn = 4^n /((n+1)(2n+1)) Binomial(3n,n). Kreweras' formula has a striking similarity with another result published the same year by Ronald Mullin: the number of loopless planar triangulations with 3n edges is tn = 2^n /((n+1)(2n+1)) Binomial(3n,n). The original proof of Kreweras received major simplifications by Niederhausen, Gessel and Bousquet-Melou. Yet, the enumerative formula remained without combinatorial explanation. As for Mullin's result, a bijective proof was obtained only recently by Poulalhon and Schaeffer. In my talk, I will present a bijective proof of both results. The bijection concerning triangulations is different from the one by Poulalhon and Schaeffer. These bijections gives convincing combinatorial explanations of the enumerative formulas and allow the random sampling of triangulations in linear time.

Kerov and Stanley introduced two different polynomials both of which evaluate characters of the symmetric group. In this talk, I will introduce these polynomials, discuss their various properties and address the main conjectures concerning these polynomials. Namely, it is conjectured that both polynomials display positivity properties. Although the positivity questions are not answered fully, some progress has been made on them.

A positional game is a played on a finite board V, where a family of subsets (a hypergraph) H, whose members are usually called winning sets, is specified. The game is played by two players, taking turns in claiming previously unoccupied elements of V, and ends whenever there are no unoccupied elements. In general, there are two additional parameters, p and q, the first player takes p elements in his turn, while the second one claims q elements.

There are several types of positional games. In the so called Strong Game, a player completing a winning set A of H first wins, otherwise the game ends in a draw. In a Weak Game, the first player (Maker) wins if he completes a winning set by the end of the game, otherwise the game is won by the second player (Breaker). In the Avoider-Enforcer version, the first player (Avoider) aims to avoid occupying a winning set completely, while the second player (Enforcer) tries to force Avoider to do just so. There are also hybrid versions, where, for example, the first player acts both as Breaker and Avoider.

There is an amazing variety of recreational and mathematical games that can be casted into the above described framework. Examples include Tic-Tac-Toe and its multi-dimensional generalizations, the game of Hex played and studied by John Nash, and various achievement games played on the edges of the complete graph K^n, where for example Maker tries to create a Hamilton cycle, while Breaker aims to prevent Maker from fulfilling his goal.

In this survey-type talk I will introduce the subject of positional games, and will define and discuss a variety of types of positional games. I will indicate some typical approaches and tools available. Some recent results will be discussed too. I will stress a perhaps surprising yet quite ubiquitous role of probabilistic intuition in analyzing these deterministic games.

No experience (theoretical at least) with positional games will be assumed.

A number of combinatorial problems can be viewed as problems of counting lattice points in a certain convex set, which may be full-dimensional or involve some linear equations. For this there is a well-developed theory. Other problems, like graph coloring, are similar but involve linear antiequations, where a quantity cannot equal a constant. Matthias Beck and I have found a way to modify the standard theory so it can apply to such problems. I will show how this is done and how it yields new insights into coloring of graphs and signed graphs, counting magic squares, etc.

In this talk, we will survey some old and new results about the Stern sequence, a highly underappreciated mathematical object. It is defined by the recurrence

s(0) = 0, s(1) = 1, s(2n) = s(n), s(2n+1) = s(n) + s(n+1).

It is most easily written by imagining a Pascal triangle with memory, and starting with (1,1). The rows of the resulting "diatomic" array give s(n) for 2^r \le n \le 2^{r+1}:

(r=0): 1 1
(r=1): 1 2 1
(r=2): 1 3 2 3 1
(r=3): 1 4 3 5 2 5 3 4 1

Stern himself proved in 1858 that every pair of relatively prime positive integers (a,b) occurs exactly once as the pair (s(n),s(n+1)), and the binary representation of n is encoded by the continued fraction representation of a/b. The maximum values in the r-th row is the (r+2)-nd Fibonacci number. The sum of the entries in the r-th row is 3^r + 1; the sum of the cubes of the entries is 9*7^{r-1} for r > 0. The Stern sequence also has many interesting divisibility properties: s(n) is even iff n is a multiple of 3; the set of n for which s(n) is a multiple of 3 has a simple recursive description. The set of n for which s(n) is a multiple of the prime p has density 1/(p+1). Further, s(n) counts the number of binary representations of n-1, if one allows digits from {0,1,2}. If n is odd and m is the integer whose base 2 representation is the reversal of n's, then s(n) = s(m) and s(n+1)s(m+1) = 1 mod (s(n)). The Stern sequence affords a clear understanding of the alluringly-named Minkowski ?-function, which gives a strictly increasing map from [0,1] to itself, taking the rationals to the dyadic rationals, and the quadratic irrationals to the non-dyadic rationals. There are few other mathematical objects which are as generous in their grooviness; as one final example, s(729) = 64.

This talk will be rather elementary and accessible to alert undergraduates.

We prove that the Poisson distribution maximises entropy in the class of ultra-log-concave distributions, extending a result of Harremoes. The proof uses ideas concerning log-concavity, and a semigroup action involving adding Poisson variables and then thinning. In particular, we show that any sum of independent indicator random variables has smaller entropy (so is `less random than') the Poisson distribution with the same mean.

The partially asymmetric exclusion process (PASEP) is an important model from statistical mechanics which describes a system of interacting particles hopping left and right on a one-dimensional lattice of n sites. It is partially asymmetric in the sense that the probability of hopping left is q times the probability of hopping right. In this talk we will describe a surprising connection between the PASEP model and the combinatorics of certain 0-1 tableaux called permutation tableaux. Namely, we prove that in the long time limit, the probability that the PASEP model is in a particular configuration tau is essentially the weight generating function for permutation tableaux of shape lambda(tau).

This result suggests a connection between the PASEP model and total positivity for the Grassmannian (via work of Postnikov). Additionally, there should be connections to Stanley's theory of differential posets.

The convex dimension of a graph $G=(V,E)$ is the smallest dimension d for which G admits an embedding $f:V \rightarrow R^d$ of its vertices into $d$-space, such that the barycenters of the images of its edges are in convex position. We say that $d$ is the strong convex dimension of $G$ if the above condition is augmented with the requirement that the image of the vertices of $G$ are in convex position. The convex and strong convex dimensions of graphs arise naturally in connection with a special class of convex combinatorial optimization problems. In this talk we will study the convex and strong convex dimensions and the extremal number of edges of graphs with given convex dimension.

Joint work with Shmuel Onn (Technion) and Uriel G. Rothblum (Technion).

A hereditary property of combinatorial structures is a collection of structures (e.g. graphs, words, permutations) which is closed under isomorphism and under taking induced substructures (like induced subgraphs), and contains arbitrarily large structures. Given a property $\mathcal{P}$, we write $\mathcal{P}_n$ for the number of distinct (non-isomorphic) structures in $\mathcal{P}$ with $n$ elements, and the sequence $|\mathcal{P}_n|$ is the {\it speed} of $\mathcal{P}$. The speed of words was studied first by Morse and Hedlund in 1938. In the last few years, the ex-Stanley-Wilf conjecture, now Klazar-Marcus-Tardos Theorem was known on the speed of permutations. In this talk I survey that area, pointing out generalizations toward ordered graphs, including few short proofs as well.

A central problem of extremal combinatorics is to determine the Tur\'an number of a given $r$-uniform hypergraph $\mathcal{F}$, i.e. the maximum number of edges in an $r$-uniform hypergraph on $n$ vertices that does not contain a copy of $\mathcal{F}$. Since the problem was introduced over sixty years ago, it has only been solved for relatively few hypergraphs $\mathcal{F}$. Many of these results were found very recently by means of the stability method, which has brought new life to research in a challenging area. However, this method only has the potential to solve the problem when the extremal configuration is unique, so in other cases we need new techniques.

In this talk we will discuss some methods for Tur\'an problems due to various authors, that incorporate some algebraic ideas. In particular we will present two new results: one gives bounds for the Tur\'an numbers of projective geometries, and another gives a general bound for the Tur\'an number of a hypergraph in terms of the number of edges that it contains.

We describe different realizations with integer coordinates for the associahedron (i.e., the Stasheff polytope) and for the cyclohedron (i.e., the Bott-Taubes polytope), and compare them to the permutahedra of type A and B, respectively.

The coordinates are obtained by an algorithm which uses an oriented Coxeter graph of type A or B respectively as the only input and which specialises to a procedure presented by J.-L. Loday for a certain orientation of the Coxeter graph of A.

This is joint work with Christophe Hohlweg.

Young tableaux provide a combinatorial model for the irreducible characters of the Lie algebra of type $A$. A simple combinatorial model for the irreducible characters of an arbitrary semisimple Lie algebra (and, more generally, of a symmetrizable Kac-Moody algebra) was recently developed in joint work with A. Postnikov. This model is based on the combinatorics of the corresponding Weyl group and, in the finite case, of the affine Weyl group. It leads to an extensive generalization of the combinatorics of Young tableaux. In this talk, we present recent developments in this direction. We use the setup of crystal graphs, which are colored directed graphs on the canonical basis of a representation. In this context, we present an explicit combinatorial description (generalizing Sch\"utzenberger's ``evacuation'' procedure for tableaux) of the involution which realizes the crystals as self-dual posets. We also discuss combinatorial aspects related to the product of crystals. The talk will be largely self-contained.

If a group $G$ is a union of finitely many left cosets $a_1G_1,\ldots,a_kG_k$ of subgroups $G_1,\ldots,G_k$, then the system $\{a_iG_i\}_{i=1}^k$ is said to be a cover of $G$. In this talk we give a survey of results on extremal problems concerning covers of groups, and introduce progress on the famous Herzog-Sch\"onheim conjecture which states that if $\{a_iG_i\}_{i=1}^k\ (1 < k < \infty)$ is a partition of a group $G$ by left cosets then the (finite) indices $[G:G_1],\ldots,[G:G_k]$ cannot be distinct. We will also mention some new challenging conjectures in the field.

"There are many characterizations proved because they are elegant, with no apparent further use." In joint work with Joe Blitzstein, we show how to convert these into algorithms for counting and random generation. Examples include graphs with given degree sequences (Erdos-Gallai characterization) simplicial complexes with given f-vectors (Kruskal-Katona characterization) and many others. Application to ecology and statistics are given."

A connection is exhibited between Thompson monoids and Tamari lattices. In the most basic case, it relates the positive monoid P of Thompson group F to Tamari lattices on finite Coxeter groups of type A regarded as lattices under the weak Bruhat order. The Tamari congruence classes correspond to classes of equivalent elements in P. The two well known normal forms in P correspond to endpoints of intervals in the weak Bruhat order that determine the Tamari classes. In the monoid P these correspond to the lexicographically largest and lexicographically smallest form, while on the level of permutations they correspond to 132-avoiding and 231-avoiding permutations.

Suppose we have a collection of $n$ curves in the plane. How large a subcollection can we necessarily find such that either every pair of curves in the subcollection pairwise intersects or every pair of curves in the subcollection are pairwise disjoint? The qualitative answer is, "quite large." We will discuss how to employ different algebraic, combinatorial, geometric, and topological methods to tackle this problem and several variants of it. Along the way, we will come across several old and new conjectures in combinatorial geometry.

The talk is based on joint work with Janos Pach.

A permutation a_1 a_2 ... a_n of integers is *alternating* if a_1 > a_2 < a_3 > a_4 < ... After a brief survey of this subject we will discuss two new directions of research. (1) The distribution of the length of the longest alternating subsequence of a permutation of 1,2,...,n, analogous to the theory of longest increasing subsequences. (2) The use of symmetric functions to enumerate various classes of alternating permutations of 1,2,...,n, such as those whose inverse is also alternating, or those with a given cycle type.

We consider the problem of testing whether a graph on $n$ vertices and average degree $d$ is triangle-free. The algorithm should accept graphs that are triangle-free and reject graphs that are far from being triangle-free in the sense that a large fraction of the edges should be removed in order to obtain a triangle-free graph. The algorithm is allowed a small probability of error. This problem has been studied quite extensively in the past, but the focus was on dense graphs, that is, when $d = \Theta(n)$.

Our main finding is a lower bound of $\Omega(n^{1/3})$ on the necessary number of queries, where this bound holds for *every* $d < n^{1-o(1)}$. Since when $d = \Theta(n)$ the number of queries sufficient for testing does not depend on $n$, we observe an abrupt, *threshold-like* behavior of the complexity of testing around $n$.

In the course of our analysis we show that dense random Cayley graphs behave like quasi-random graphs in the sense that relatively large subsets of vertices have the "correct" edge density. The result for subsets of this size cannot be obtained from the known spectral techniques that only supply such estimates for much larger subsets.

This is joint work with Noga Alon, Michael Krivelevich and Dana Ron.

Descent and peak compositions yield to two remarkable and well-studied subalgebras of the group algebra of the symmetric group $S_n$: the descent algebra and the peak algebra. They are also sub-Hopf algebras of the Malvenuto-Reutenauer Hopf algebra $P$ (the direct sum over $n$ of the group algebras of $S_n$). There graded dual are commutative algebras: the algebra QSym of Gessel's quasisymmetric functions and Stembridge's peak algebra. They can be obtained by a nice combinatorial construction: the standardized permutation of a word yields to a realization into words of $P$. Letting the variables be commutative gives a morphism from $P$ to QSym. This is the core of the theory of noncommutative symmetric functions.

In this talk, we will see how this picture can be colored to fit with the wreath product $G\wr S_n$, where $G$ is a finite abelian group. Coloring descent compositions yields the Mantaci-Reutenauer algebra and coloring peak compositions yields a colored peak subalgebra of the Mantaci-Reutenauer algebra. Coloring the Solomon's epimorphism from the descent algebra to the ring of symmetric functions lead us to a colored version of Gessel-Reutenauer's formula involving the characters of the colored descent representations of Adin-Brenti-Roichman, and Bagno-Biagioli.

(From works with Pierre Baumann and Nantel Bergeron).

An important topic in the representation theory of algebras is the study of derived equivalences between their derived module categories; only few invariants for these equivalences are known. In joint work with T. Holm we have investigated special algebras which have come up several times in this context and which are defined in purely combinatorial terms by a quiver (i.e., a finite directed graph) and homogeneous relations; we also allow weights on the arrows of the quiver.

In this situation the weighted Cartan matrix collects the weighted counts of the non-zero paths in the quiver. For our special quivers, we have obtained an explicit formula for the weighted Cartan determinant in terms of the combinatorics of the quivers. This gives new and easy ways to compute combinatorial invariants for the special algebras mentioned above.