Richard P. Stanley Seminar in Combinatorics

The classical theory of rook polynomials gives a way to count permutations p of [n] = {1,2,..., n} according to the number of pairs (i, p(i)) lying in some specified subset of [n] x [n]. I will discuss a generalization in which we keep track of the number of cycles of the permutation. The theory involves a new basis for polynomials and gives some new "twisted" versions of the Eulerian polynomials.

Given $n$ reference points in real $d$-space, we specify a finite set of hyperplanes that are perpendicular to lines that join pairs of the $n$ points. These hyperplanes dissect the space into a number of regions which is determined by the intersection semilattice of the hyperplanes. The semilattice in turn is, for generic reference points, determined by $d$ and the lift matroid of a gain graph that corresponds to the specifications of the hyperplanes.

Dissections of this kind arise from generalizing a problem in geometric voting theory. Particular examples of possible interest for voting lead to dissections whose matroids are truncations of those of simple, symmetrical deformations of the braid hyperplane arrangement of rank $n-1$. (Our dissections themselves are not deformations of the braid arrangement.) The intersection semilattices of these examples consist of composed partitions, which are partitions in which each block has an ordered partition, and generalizations to $k$-composed partitions (sometimes called "generalized partitions").

The talk will to a great extent depend on pictures and will not assume any knowledge of weird technical machinery.

Gröbner bases are a general purpose method in symbolic computation for polynomials in several variables. They have many applications throughout the mathematical sciences. This talk gives an introduction to Gröobner bases, by illustrating three such applications: Linear integer programming, solving polynomial systems by eigenvalue methods, symbolic analysis of linear partial differential equations with polynomial coefficients.

Number walls of Toeplitz determinants have recently appeared by name in books by Sloane & Plouffe and Conway & Guy. Similar arrays of Hankel determinants can be used to make unexpected connections between sequences of integers with combinatorial interpretations. For this see recent articles by Aigner, Ehrenborg, or Dumont & Zeng, although the study of Hankel determinants of combinatorial sequences goes back to Radoux in 1979 and probably earlier. The work of Gessel and Viennot with nonintersecting lattice paths is also related.

Several Hankel number walls have nice symmetry properties with respect to their diagonal or are otherwise noteworthy. I have many examples. In July I made a simple observation using number walls to connect a sequence related to Catalan numbers and Motzkin numbers to the Somos-4 sequence and also to some alternating sign matrix enumeration sequences. Some of this is partly based on an article by David Cantor which relates hyperelliptic curves to Hankel determinants via Pade approximants which go back to Jacobi.

Many integer sequences arising from combinatorics turn out to be unimodal, or even log-concave. The aim of this talk is to present such an example. Recall that a sequence (f_i)_i=>0 of nonnegative integers is called unimodal if there exists an index h => 0 such that f_i <= f_i+1 for i < h and f_i => f_i+1 for i => h. The sequence is log-concave if f_i² => f_i+1 f_i-1 for i => 1, which implies the unimodality of (f_i) if this sequence has no internal zeros.

An integer basis is a strictly increasing sequence B = (b_i)_i=>0 of positive integers with the following property: there exists a sequence (c_i)_i=>1 of positive integers (called multiplicity sequence) such that every positive integer n can be written uniquely in the form

For instance, the most common integer bases are the powers of a fixed integer b => 2, (ie b_i := bⁱ); the associated multiplicity sequences are constant, given by c_i = b-1 for all i => 1. Set θ_B(m,l) := # { n in {0,1,...,m-1}: n has l nonzero digits when written in basis B}. The result is: (θ_B(m,l))_l=>0 is strongly log-concave, for any positive integer m and any integer basis B.

We will see that this result is indeed an inequality for elementary symmetric polynomials, and we will specialize it to obtain inequalities for sums of binomial coefficients, sums of Stirling numbers of the first kind, or sums of q-analogues of these numbers. I will end with a few words about a proof of this theorem.

Schubert polynomials represent cohomology classes of certain subvarieties of flag manifolds. Results of Billey-Jockusch-Stanley, Fomin-Kirillov, and Bergeron-Billey show why these polynomials have nonnegative integer coefficients, by producing combinatorial formulae for them involving "rc-graphs". These are subsets of [n]x[n] defined in terms of reduced expressions for permutations. In this talk, I'll explain how rc-graphs represent coordinate subspaces in the vector space of n x n matrices, by showing that the determinants defining Schubert rank conditions are a Gröbner basis. This gives a new geometric proof of positivity, and produces as a corollary simple expressions for double Schubert polynomials. The proof is based on ordinary and equivariant K-theory of flag manifolds, via properties of Grothendieck polynomials. This is joint work with Allen Knutson.

I will present two amazing results in what seem to be elementary combinatorics. The first is the Thurston's linear time algorithm for testing whether a region is tileable by dominoes. The second is the Conway-Lagarias invariant for trominoes (along with the tileability criteria). An attempt will be made to lose all the advanced mumbo jumbo (which apparently motivated the authors), and give a complete proof in simple combinatorial terms, accessible to all undergraduates.

In this talk we describe a centralizer algebra of the quantum group corresponding to the even orthogonal algebras. We use combinatorics of the theory of weights for labeling irreducible representations of Lie algebras and their correspondence to Young diagrams to give a labeling set for the irreducibles of this centralizer algebra.

We will describe the connection of this algebra to q-Brauer algebras and in particular to the type B q-Brauer algebra, which has been defined by Häring under the name B-BMW algebra. Our approach gives combinatorial proofs for the results about the structure of the B-BMW algebra. Moreover, we obtain an explicit formula for the weights of the Markov trace on this algebra. These weights are important in determining exactly when the B-BMW algebra is semisimple.

Joint work with H. Wenzl

We will present a notion of invariants of polyomino and prove an advance generalization of Conway-Lagarias invariants. First, we will review a proof by the author for row convex regions and then present a proof for all simply connected regions (joint work with C. Moore).

While this talk is formally independent of the first one, we advise to attend both talks so as to understand the underlying logic behind the recent results.

We color the vertices of a hypergraph with two colors (say red and blue). The discrepancy of this coloring is the maximum of the absolute value of the difference of the red and blue elements for every edge. The discrepancy of the hypergraph is the minimum discrepancy of all two-colorations. The hereditary discrepancy is the maximum discrepancy of all restrictions of the original hypergraph. These notions have connections with many topics in combinatorics and number theory. For example, the hereditary discrepancy is 1 if and only if the incidence matrix of the hypergraph is totally unimodular. One can also give a very nice geometric interpretation of the different discrepancy notions. In spite of deep work by Sos, Beck, Spencer, Matousek and others, many simple questions on discrepancy remain unsolved. For example: how much can the addition of a single new edge increase the hereditary discrepancy? After surveying the basic theory, some partial results on this question will be discussed.

Linear recurrences (and, with them, ordinary generating functions) are ubiquitous in combinatorics, as part of a broad general framework that is well-studied and well-understood; in contrast, bilinear recurrences such as

In this talk I will describe some types of combinatorial objects whose properties make them well-suited to a (nascent) general theory of bilinear recurrence relations. In some interesting cases (e.g., the Somos-4 recurrence given above), algebra is one step ahead of combinatorics, and we are temporarily in the unusual position of being able to enumerate combinatorial objects for which we lack a combinatorial description!

I will attempt to convince members of the audience that some basic problems connected with bilinear recurrence relations are compelling and accessible. If I succeed at this, I plan to organize a working group that will jointly explore these problems over the next several months.

(Most of the lecture should be accessible to advanced undergraduates.)

In 1994 Garsia and Haiman conjectured that a certain sum of rational functions in two variables q and t (now known as the (q,t)-Catalan number) always evaluates to a polynomial with nonnegative coefficients. Based on empirical discoveries, the speaker was led to a stronger form of this conjecture, which involves an explicit expression for the (q,t)-Catalan as a sum over Dyck paths. After introducing this conjecture we discuss a proof of it which has recently been found by A. Garsia and the speaker using plethystic identities for Macdonald polynomials.

The papers on which this talk is based can be found at http://www.math.ucsd.edu/~jhaglund/

Greg Levin, in his Ph.D. thesis, found upper and lower bounds for a combinatorial problem (described below). Unfortunately, the bounds were sufficiently complicated, that we were unable to prove they were the same (they are) but only that they differed by less than 10^-2000. In this talk, I will concentrate on the technique used to prove the equality of the bounds; this technique uses the fact that the two quantities in question are very close to each other. The main point of the talk will be: When does "close enough" imply "equal."

The combinatorial question that motivated this research is the following. Given a (finite, simple) graph G=(V,E), define a partially ordered set P(G) whose ground set is V union E in which we have x<y exactly when x is in V, y is in E, and x is an endpoint of y. Let dim P denote the dimension of a partial order and let dim_f P denote its fractional dimension. [The dimension of a poset can be defined via an integer linear program (IP) and the fractional dimension is the value of the linear programming (LP) relaxation of the dimension IP.]

Brightwell and Scheinerman proved that for any (finite) tree T, dim_f P(T) < 1 + \phi where \phi=(1+sqrt(5))/2 is the golden mean and that sup_n dim_f P(K_1,n) = 1 + sqrt(2). Let

where the supremum is over all finite trees, T. The earlier work locates Z somewhere in the interval between 2.41 and 2.62. Levin showed that the correct value of Z is (approximately) 2.445.

The 321,hexagon-avoiding permutations are introduced by Sara Billey and Gregory Warrington in a recent preprint. In the language of permutations with forbidden subsequences, they are the permutations avoiding all of the patterns 46718235, 46781235, 56718234, 56781234, and 321.

Standard 'generating tree' techniques lead to a recursive construction of the 321,hexagon-avoiding permutations. The nodes on level n of the generating tree correspond to the 321,hexagon-avoiding permutations on n symbols. Each node is further labelled with four parameters which summarize the important features of the permutation; the subtree below a node can be reconstructed from these four parameters alone.

The linear ordering problem is easy to state: given a complete weighted directed graph on $n$ nodes, find a spanning acyclic tournament of maximum weight (i.e. a maximum acyclic subgraph). Although the problem is NP-hard, it is easy to estimate the optimum to within a factor of 2 (take any linear ordering L; the spanning acyclic tournament consistent with either L or the opposite ordering L' has weight at least half the maximum). It is not known whether the maximum can be estimated to a better factor using a polynomial-time algorithm.

In this talk, we discuss widely-studied polyhedral relaxations for this problem. The integrality gap of a relaxation is the extremal ratio between the estimate provided by the relaxation and the true optimum. We show that the integrality gap for the basic linear relaxation (solvable in polynomial-time) is 2 and that this gap remains 2 even when the relaxation is strengthened by the so-called "fence" constraints. Our proof is nonconstructive --we demonstrate an extremal example via the probabilistic method. Finally, we show that no relaxation that is solvable in poly-time can have an integrality gap less than 66/65 unless P=NP.

This is joint work with Santosh Vempala.

Boolean functions are of great interest in extremal combinatorics, probability theory and complexity theory.

We will define and discuss the Welsh-Fourier coefficients \hat f(S) of a Boolean function f and what can we learn from them. Some results and applications will be presented but I will emphasize open problems.

Among the fact we mention:

1. (Parseval) The sum of squares of the Fourier coefficients is the probability that f=1.
2. Sum \hat f(S) |S| is the SENSITIVITY (also known as the sum of influences, edge-expansion) of f.
3. If the support of f is small then the W-F coefficients are supported on "large" coefficients (coefficients where |S| is large).
4. If f can be described by a bounded depth circuit of small size then the W-F coefficients are supported on "small" coefficients. (OPEN PROBLEM: they are also supported on a few coefficients)
5. The connection of W-F coefficients to stability of f under noise, applications for questions in probability.

Among the question we ask: Better description of F-W coefficients of functions in AC0, "noise stability" for functions expressable with threshold circuits, and more.

The lecture will be self-contained and elementary.

The problem of decomposing certain natural representations of the infinite symmetric group into irreducibles gives rise to a remarkable 2-parameter family of probability distributions on the Young diagrams. This family includes the images of the uniform measures on (generalized) permutations under the Robinson-Schensted-Knuth correspondence. When the size of the Young diagrams goes to infinity, the distributions tend to a certain determinantal stochastic point process on the real line. This process is similar to those describing the spectra of random unitary and Hermitian matrices. It also provides a complete solution to the initial representation theoretic problem.

This is a joint work with Grigori Olshanski.

A depth first search algorithm has been used by Gessel and Wang to establish the connection between labeled connected graphs and inversions of trees. In this talk, we extend this algorithm to certain multicolored graphs. We also introduce a breadth first search algorithm which gives the connection between multicolored graphs and generalized parking functions. Combining these results, we prove an identity between the inversion enumerator of sequences of labeled forests, and the sum enumerator of generalized parking functions.

Let $A$ be a $(d+1) \times d$ real matrix whose row vectors positively span $R^d$ and which is generic in the sense of Bárány and Scarf. Such a matrix determines a certain infinite $d$-dimensional simplicial complex $\Sigma$, on which the group $Z^d$ acts with finitely many orbits. Let $f_i$ be the number of orbits of $(i+1)$-simplices of $\Sigma$. The sequence $f=(f_0,f_1,..., f_{d-1})$ is the $f$-vector of a certain triangulated $(d-1)$-ball $T$ embedded in $\Sigma$. When $A$ has integer entries it is also, as shown by work of Peeva and Sturmfels, the sequence of Betti numbers of the minimal free resolution of $k[x_1,...,x_{d+1}]/I$, where $I$ is the "lattice ideal" $I = \langle \mathbf{x}^{a} - \mathbf{x}^b | a,b\in N^{d+1} mbox{and} a-b\in \{A\cdot y | y\in Z^d\} \rangle$.

The talk will give an introduction to the construction of such ``Scarf complexes'' $\Sigma$ and $T$ and their motivation. No previous familiarity will be assumed.

Then we will discuss relations among the numbers $f_i$. It is shown that $f_0,f_1, \dots, f_{\lfloor \frac{d-3}{2} \rfloor}$ determine the other numbers via linear relations (confirming a conjecture of Scarf), and that there are additional non-linear relations. In more precise (and more technical) terms, our analysis shows that $f$ is linearly determined by a certain $M$-sequence $(g_0,g_1, \dots, g_{\lfloor \frac{d-1}{2} \rfloor})$, namely the $g$-vector of the $(d-2)$-sphere bounding $T$. Although $T$ is in general not a cone over its boundary, it turns out that its $f$-vector behaves as if it were.

We give a combinatorial overview of the plethystic Hopf algebra structure of the MacMahon relying on the construction of a plethystic Hopf algebra from any alphabet of neutral letters obtained by G.-C. Rota and J. Stein. A MacMahon symmetric function is a formal power series of bounded degree, in a finite number of infinite alphabets, that is invariant under the diagonal action of the symmetric group.

On Wednesday Nov. 29 (the week after Thanksgiving), the combinatorics seminar will hold an open problems session. Come find out what other people in the department are thinking about -- or aren't, but think is interesting.

You are invited to submit a problem to present to the seminar. Problems should be presentable in no more than 5 minutes, in a way which makes them accessible to the wide variety of people the combinatorics seminar draws together.

If you know you wish to present a problem, please send me email in advance so I can make sure there's enough time for everyone. Limit yourselves (at least initially) to only one question per person.

Reply to Michael Kleber, kleber@math.mit.edu

I will discuss some interesting integer sequences that have arisen in the contexts of coding theory, lattices, number theory and combinatorics.

I will also talk about the On-Line Encyclopedia of Integer Sequences which currently receives over 12,000 hits per day. Judging by the amount of email it stimulates, the data-base continues to fulfil the purpose for which it was designed, helping people identify sequences (it has been called an "on-line fingerprint service" for mathematics).

Let G be a graph, digraph or multigraph and let b be a positive integer. The set of subgraphs of G for which every node has degree at most b forms a simplicial complex. Some important special cases which have arisen in various contexts in the recent literature are the matching complex (G is a complete graph and b=1) and the chessboard complex (G is a complete bipartite graph and b=1). I will present some recent results on the homology of these complexes. In particular, the representation of the symmetric group on complex homology and torsion in integral homology will be discussed.

A monotone graph property is a collection of graphs on a fixed, labeled vertex set V which is closed under removal of edges and permutation of vertices. Each monotone graph property determines a simplicial complex whose vertices correspond to the edges in the complete graph on V. The topological structure of such complexes was first investigated by J. Kahn, M. Saks and D. Sturtevant in their study of computational complexity of monotone graph properties. More recently, certain classes of monotone graph properties have appeared in various areas of algebra, topology and combinatorics. I will discuss some of these classes and the techniques used to investigate them.

If a PDE model of a diffusion or a wave is observed at a finite number of points, is it possible to distinguish between a classical continuous PDE and a PDE (difference equation) on a graph? In other words, do finite restrictions of solutions of differential and difference equations coincide? I will talk about examples that suggest that the answers are no and yes, and about applications to inverse problems (determining the type and coefficients of an equation from its solutions) and to numerical approximations of continuous PDEs.

The constructions of difference equations on planar graphs matching continuous diffusion and wave equations involve study of totally positive matrices, pseudoline arrangements, rectanglizations and various continued fractions. I will teach a special topics class around the above this spring. The talk will be practically self-contained and graduate and undergraduate students are welcome.