MIT-Harvard-MSR Combinatorics Seminar

Schedule 2000 Fall

Organizer: Sara C. Billey

2-338 - Wednesdays and Fridays 4:15pm
Refreshments at 3:45pm

September 8

Ira Gessel, Brandeis University

Rook polynomials and counting permutations by cycles

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.

September 11

Thomas Zaslavsky, Binghamton University

Perpendicular dissections, composed partitions, and deformations of the braid arrangement

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.

September 15

Bernd Sturmfels, University of California, Berkeley

Groberner Bases

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.

September 20

Michael Somos, Cleveland State University

Number Walls in Combinatorics

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.

September 27

Philippe Pitteloud, MIT

A theorem of log-concavity or inequalities for elementary symmetric polynomials

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 (fi)i=>0 of nonnegative integers is called unimodal if there exists an index h => 0 such that fi <= fi+1 for i < h and fi => fi+1 for i => h. The sequence is log-concave if fi2 => fi+1 fi-1 for i => 1, which implies the unimodality of (fi) if this sequence has no internal zeros.

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

n = a1b0 + a2b1 +... + akbk-1 with 0 <= ai <= ci and ak nonzero.

For instance, the most common integer bases are the powers of a fixed integer b => 2, (ie bi := bi); the associated multiplicity sequences are constant, given by ci = 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.

September 29

Ezra Miller, MIT

Gröbner geometry of formulae for Schubert polynomials

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.

October 4

Igor Pak, MIT

Ribbon Tile Invariants, part I:
Domino and Tromino Tilings

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.

October 6

Rosa Orellana, Dartmouth College

q-Centralizer algebras for spin group

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

October 11

Igor Pak, MIT

Ribbon Tile Invariants, part II: Tilings by Ribbon Polyomino

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.

October 13

Katalin Vesztergombi, University of Washington

Discrepancy of hypergraphs and geometry

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.

October 18

James Propp, University of Wisconsin and MIT

Somos sequences and bilinear combinatorics

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

sn+4 = (sn+1 sn+3 + sn+22) / sn
are encountered far less often, and these encounters tend to be viewed in isolation from one another.

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

October 20

Jim Haglund, UC San Diego

Statistics for the (q,t)-Catalan Numbers

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

October 25

Edward R. Scheinerman, Johns Hopkins University

On the Fractional Dimension of Posets of Trees:
Closing a 10-2000 Gap

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 dimf 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, dimf P(T) < 1 + \phi where \phi=(1+sqrt(5))/2 is the golden mean and that supn dimf P(K1,n) = 1 + sqrt(2). Let

Z = supT dimf P(T)

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.

October 27

Julian West, Malaspina University-College, British Columbia, Canada

A generating tree for 321,hexagon-avoiding permutations

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.

November 1

Alantha Newman, MIT

On Linear Relaxations for Linear Orderings

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.

November 3

Gil Kalai, Hebrew University, Jerusalem and I.A.S, Princeton

The Fourier Transform of Boolean functions

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.

November 8

Alexei Borodin, University of Pennsylvania

Harmonic analysis on the infinite symmetric group and random matrices

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.

November 15

Catherine Yan, Institute of Advanced Study and TAMU

Generalized parking functions, tree inversions, and multicolored graphs

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.

November 17

Anders Bjorner, KTH-Stockholm

Face numbers of Scarf complexes

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.

November 20

Mercedes Rosas, Universidad Simon Bolivar, Caracas, Venezuela

The plethystic Hopf algebra of MacMahon symmetric functions

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.

November 29

Organizer: Michael Kleber, MIT

Open Problems Session

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,

December 1

Neil Sloane, AT&T Shannon Lab, Florham Park, NJ

Solved and Unsolved Problems in Integer Sequences

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

December 6

Michelle Wachs, University of Miami

Homology of Bounded Degree Graph Complexes

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.

December 8

John Shereshian, University of Miami

Monotone graph properties

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.

December 13

David Ingerman, MIT

PDEs on graphs vs. continuous PDEs

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.


All announcements since Fall 2007 are in the Google Calendar