Richard P. Stanley Seminar in Combinatorics

In the context of the Stanley-Wilf conjecture, permutations avoiding all patterns of a given shape (in the sense of Robinson-Schensted-Knuth) are considered. We show that the shapes of all such permutations are contained in a suitable thick hook, and deduce an exponential growth rate for their number.

This is a joint work with Ron Adin.

We combinatorially prove that the number $R(n,k)$ of permutations of length $n$ having $k$ runs is a log-concave sequence in $k$, for all $n$. Our proof involves a simple and useful lattice path interpretation of permutations. We also give a new combinatorial proof for the log-concavity of the Eulerian numbers. This is joint work with Richard Ehrenborg.

Many enumeration problems in algebraic combinatorics lead to quasi-symmetric generating functions, for example Schur functions, P-partitions, and Stanley symmetric functions. Some of these have been shown to have interesting algebraic properties, most notably the Hopf structures of Ehrenborg's quasi-symmetric generating function for the flag f-vector of a polytope and Bergeron and Sottile's generating function for descents in a labeled poset.

This talk will describe joint work with Bergeron, Mykytiuk, and van Willigenburg which gives a unified construction of many such quasi-symmetric functions. Our approach is motivated by work on the Schubert calculus for flag manifolds and uses representations of the algebra of non-commutative symmetric functions generated by what we call Pieri operators.

In a joint work with Arkady Berenstein, a family of explicit "polyhedral" combinatorial expressions is given for multiplicities in the tensor product of two simple finite-dimensional modules over a complex semisimple Lie algebra. Here "polyhedral" means that the multiplicity in question is expressed as the number of lattice points in some convex polytope. Our answers use a new combinatorial concept of i-trails which resemble Littelmann's paths but seem to be more tractable. We also study combinatorial structure of Lusztig's canonical bases or, equivalently of Kashiwara's global bases. Although Lusztig's and Kashiwara's approaches were shown by Lusztig to be equivalent to each other, they lead to different combinatorial parametrizations of the canonical bases. One of our main results is an explicit description of the relationship between these parametrizations.

Let V = {x_1,...,x_n} be a set of independent true/false random variables. A literal is a variable or the negation of a variable in V. A term is a conjunction of literals. We say a term t contains the variable x_i if it contains x_i or not-x_i.

Let T = {t_1,...,t_m} be a set of terms. Write t_j ~ t_k if they contain a common variable. Thus, viewing t_i as the event that t_i is true, (T, ~) is a Lovasz dependency graph. Let N_i be the neighborhood of t_i in T, including t_i.

If S is a subset of T, let let Pr(S) = Pr( at least one term in S is true ) and U(S) = Pr( exactly one term in S is true ). The following conjecture was motivated by considerations in computational complexity.

Conjecture (Rudich, 1984): There exist epsilon, delta > 0 such that if T is any set of terms over any set of variables V (as above),

if U(T) >= 1-epsilon then for some N_i, Pr(N_i) >= delta.

We prove a correlation inequality that is in some sense dual to Reimer's inequality (a.k.a. the van den Berg-Kesten conjecture). This inequality makes possible a short proof of Rudich's conjecture and other complexity theory results.

This is joint work with Mike Saks and Jeff Kahn.

The Leech lattice is a remarkable lattice in 24-dimensional Euclidean space. Its symmetry group (modulo its center Z/2Z) is the sporadic simple group Co_2, with order around 8*10^15. We will explain an algorithm for quickly detecting whether two lattice vectors are equivalent under a symmetry.

The solution of the alternating sign matrix problem by Zeilberger is likely to be only the end of the first chapter of a very long and interesting story. In the first part of this talk I discussed symmetry classes of ASMs and halved ASMs. I also discussed conjectured enumerations that arise from viewing ASMs as states in a densely-packed loop model.

Yet another chapter-in-the-making of the ASM story concerns the matrix condensation process, due to Dodgson, that inspired Mills, Robbins, and Rumsey to invent ASMs in the first place. Variant forms of condensation give rise to new analogues of ASMs that are enumerated by Somos sequences. These curious integer sequences were originally introduced by Michael Somos in connection with the theory of elliptic functions.

NOTE: despite the title, this talk will be entirely self-contained and will not depend in any way on the first part (given last semester).

We show how Cheeger-type inequalities can be derived relating various vertex isoperimetric constants to Poincaré-type functional constants such as eigenvalues. Our approach is functional-analytic, adapted to a discrete setting, and our results refine those of Noga Alon (and others) relating the spectral gap of a graph to the so-called magnification of a graph.

This is joint work with Sergey Bobkov and Christian Houdré.

Given an irreducible S_n-module M, the Branching Rule, how the restriction of M to S_{n-1} decomposes into irreducibles over a field F, is well known and a wonderful source of combinatorics, when F has characteristic 0.

One can hope to find the Branching Rule for the finite Hecke algebra H_n^{\fin}, which is a deformation of the symmetric group, or for the cyclotomic Hecke algebra H_n^\lambda, which is a deformation of the wreath product of S_n with Z/rZ. However, these algebras are rarely semisimple, for instance when char(F) is prime, when lambda is large, or when q is a root of unity. The restriction of irreducible modules is thus not a direct sum of irreducibles and can be quite complicated.

Kleshchev has given a partial Branching Rule for the symmetric group in prime characteristic: he describes the socle of the restriction of M from S_n to S_{n-1}, and in particular shows that it is multiplicity-free and isomorphic to the cosocle of restriction. We prove that the socle of restriction of any irreducible module of the cyclotomic Hecke algebra is multiplicity free and isomorphic to the cosocle.

We do this by proving the result for the irreducible modules of the affine Hecke algebra, which in particular includes all cyclotomic Hecke algebra irreducibles.

This is joint work with Ian Grojnowski

Jing defined some linear operators on the space of symmetric functions using so-called vertex operators. He showed that certain compositions of such operators, when acting on the symmetric function 1, create the Hall-Littlewood symmetric functions. Using this he gave formulas for the Kostka-Foulkes polynomials, which are the change of basis matrix between the HL basis and the modified Schur function basis.

We define operators that give rise in a similar manner, to the so-called generalized Kostka polynomials, which are defined as graded multiplicities of isotypic components of the Euler characteristic characters of some nice modules supported in the closure of a nilpotent conjugacy class. Using the vertex operators one may easily derive various new relations among the above characters and hence among the "genKostkas". Finally, one may realize as a graded R(GL(n))-module, the (GL(n) x C^*)-equivariant K-theory of the nullcone, as a vector space spanned by certain of these vertex operators. This also works for other nilpotent conjugacy class closures in gl(n).

The task of finding small spanning graphs of a prescribed connectivity is a fundamental problem in network optimization. Unfortunately, it is also a hard probem. I will present a 4/3-approximation algorithm for the Minimum 2-Edge Connected Subgraph problem in undirected graphs. This result verifies one implication of the well known "4/3-Conjecture" regarding the subtour relaxation for the Travelling Salesman Problem. Our main tools are techniques from matching theory and a decomposition theorem that allows us to focus upon relatively simple graphs. For directed graphs I will outline an approximation algorithm for the Minimum Strongly Connected Subgraph problem with a 3/2-approximation guarantee. These factors improve upon the previously best known values (1.42 and 1.61 resp.). This is work with Santosh Vempala.

We construct maps between smooth Schubert varieties which are fiber bundles whose fibers are again smooth Schubert varieties. In particular, these maps give an alternative proof of a smoothness criterion by Lakshmibai and Sandhya, and also show that the Poincaré polynomials of such varieties are always products of q-binomial coefficients. This is a joint work with Vic Reiner.

We describe the totally nonnegative part of Spec(qH^*(Gr_d(n))).

An operator on symmetric functions was introduced by Jing that adds a row to the partition indexing a Hall-Littlewood symmetric function. The action of this operator on the Schur basis is a of q-analog of the Pieri rule and can be used to calculate Schur function expansions of the Hall-Littlewood polynomials.

We consider instead the recursion for building the Hall-Littlewood symmetric functions by adding columns. We constuct operators that have a very combinatorial action on the Schur function basis and give a new and elegant recurrence for building the Hall-Littlewood symmetric functions from smaller ones.

The main tool that we use is simple and suprising involution on the space of operators that exchanges the unit for the counit in the Hopf algebra structure of this space. When the involution is applied to our combinatorial operators, the effect is that it permutes them in a very natural manner.

We study four operations defined on pairs of tableaux. Algorithms for the first three involve the familiar procedures of jeu de taquin, row insertion, and column insertion. The fourth operation, hopscotch, is new, although specialised versions have appeared previously. Like the other three operations, this new operation may be computed with a set of local rules in a growth diagram, and it preserves Knuth equivalence class. Each of these four operations gives rise to an a priori distinct theory of dual equivalence. We show that these four theories coincide. The four operations are linked via the involutive tableau operations of complementation and conjugation in an illuminating commutative diagram. We we also show some unusual ways to rectify a skew tableau to normal shape.

This is joint work with Frank Sottile, Jeff Stroomer, and Julian West. A copy of the preprint is available at http://seki.csuhayward.edu.

A finite interval order is a partially ordered set whose elements are in correspondence with a finite set of intervals in a linear order, with disjoint intervals ordered by their relative position. Such set of intervals is a representation of the interval order.

A finite interval order of length n has a unique representation using intervals with endpoints in the set [n]. A basic interval order of length n has the property that removal of any element yields an order of length less than n. I will construct and enumerate the set of basic length n interval orders using a recurrence relation.

A quiver is an oriented graph Q=(Q_0,Q_1) where Q_0 is the set of vertices and Q_1 is the set of arrows. For an arrow a in Q_1, a: tail(a) -> head(a). A representation V of a quiver Q is a collection of vector spaces at each vertex, together with linear maps corresponding to each arrow. Specifiying a dimension at each vertex of the quiver, a representation is then determined by specifying the linear maps., or in other words by a point in a certain affine space, Rep(Q,d).

Given a finite connected quiver Q, we are interested in when the action of SL(Q,d) on Rep(Q,d) gives a cofree representation. In particular, we are interested in studying the situation when the modules of covariants are free k[Rep(Q,d)]^{SL(Q,d)}-modules. We will discuss when quivers have free modules of covariants.

In 1974, Dumont gave an interpretation of the Eulerian numbers which extends to a number of statistics on permutations and on arbitrary words. We apply one such statistic to a special case of a result of Stanley concerning the flag h-vectors of balanced Cohen-Macaulay complexes. Specifically, we give a bijective proof that for each distributive lattice J(P) which is a product of chains, there is a poset Q such that the f-vector of Q is the h-vector of P. We conjecture that the result holds for all finite distributive lattices.

I'll give an update on my current attempt to fix the incomplete proof I announced in November of the n! conjecture, and an explanation of the things that ARE proved, with more technical detail than in my December talk, which was aimed at a broader audience. }

We present an explicit combinatorial construction for the minimal free resolutions of the ideals arising from hyperplane arrangements and matroids. This "lifts" Stanley's formula for the Betti numbers of such ideals. Connections to hyperplane arrangements on a torus are explored. A relationship is given between graphic and co-graphic arrangements, Tutte dichromatic polynomials, and Hermite orthogonal polynomials. This is a joint work with Isabella Novik and Bernd Sturmfels.

We construct the space of coinvariants corresponding to the space of all possible compositions of $N$ intertwiners of integrable $\widehat{sl}_2$ modules with fixed level. We obtain an explicit basis for this space, as vectors in the integrable module itself. The construction leads to recursion relations for the characters of these spaces, resulting from a bijection with the space of (specially graded) Verlinde paths. The fermionic character formulas which result from the dual space description are finite analogs of those obtained by Feigin and Stoyanovsky. These imply some highly nontrivial statements about the dimensionality of certain spaces of symmetric polynomials.

Consider the finite-dimensional irreducible representations of SL(n) whose highest weights are multiples of a fundamental weight -- or alternatively, the Schur functions associated to rectangular Young diagrams. They turn out to be a solution to a discrete version of an integrable dynamical system, the ``discrete Hirota relations.'' Surprisingly, if we try to solve the same system for the other classical root systems, the representations that pop out appear to be irreducibles of the associated quantum affine algebra.

We will talk about current work to generalize this whole picture to all highest weights, not just rectangles. The first step is a multi-time generalization of the discrete Hirota system, and the second step is finding a solution over symplectic or orthogonal representations.

While extensive work has been done bounding rates of convergence of symmetric and/or reversible Markov chains, less is known about the convergence behavior of arbitrary non-reversible chains. We give detailed descriptions of the long-term behavior of some simple families of non-reversible chains; these families have many deterministic transitions and underlying graphs ``close'' to a one-way cycle. We obtain local limit theorems for the distributions of these chains prior to stationarity. In all cases considered, the time to arrive at a fixed distance from stationarity is asymptotically O(n^3/m(n)), where n is the total number of states and m(n) is the number of states with more than one possible successor.

We construct block space-time codes with low decoding (recognition) complexity with coherent detection at the receiver. For a given number of transmit antennas, the codes have maximum diversity and good coding gain for Rayleigh or Rician faded AWGN channels. Tradeoffs between information rate, diversity and decoder complexity are also presented. Decoding is non-iterative. These results are the best known to date with respect to code rate and decoder complexity and are applicable for arbitrary signal constellations in the complex plane.

The results are obtained by exploiting the properties of three kinds of associative and non-associative algebras:

1. real division algebras
2. real and complex Clifford algebras
3. real Cayley Dickson algebras