Richard P. Stanley Seminar in Combinatorics

Border strips and snakes are certain subsets of the Young diagram of a skew partition $\lambda/\mu$. Both are closely related to a certain binary sequence code$(\lambda/\mu)$ which encodes $\lambda/\mu$ in a convenient way. The theory of border strips is highly developed and is intimately connected to ordinary and modular characters of the symmetric group $S_n$, as well as to more recent work on noncommutative symmetric functions, Fock space representations, etc. We will briefly survey some of this subject and then discuss new results concerning the decompositions of $\lambda/\mu$ into a \emph{minimal} number of border strips. No knowledge of representation theory will be assumed.

BACKGROUND READING: R. Stanley, \emph{Enumerative Combinatorics}, vol.\ 2, Exercises 7.59 and 7.66.

We will survey some recent results concerning arrangements of circles and pseudocircles in the plane. For example, new bounds on the number of incidences between points and circles (Aronov and Sharir), and how it relates to counting empty digons in arrangements of circles. Applications to Sylvester-type theorems and more.

Many modern telecommunications networks are based on so-called "bidirectional SONET rings." One might suppose that optimal routing on a cycle graph would be a trivial problem, but this is not always true because certain variables are constrained to assume integer values. Schrijver, Seymour, Winkler, and others have studied the so-called "ring loading problem," in which the cost of a network is assumed to be proportional to the amount of traffic on the edge with the heaviest load, and they have obtained good approximation algorithms. Often, however, a more realistic assumption is that the cost of a network is proportional to the amount of electronic hardware needed to support the traffic. This assumption leads to the "ring grooming problem," which appears to be harder than the ring loading problem. Our main result is a constant- factor approximation algorithm (i.e., a polynomial time algorithm that produces a solution whose cost is within a constant multiplicative factor of the optimum) for uniform traffic. The algorithm is based on the construction of covering designs. The problem of finding a constant- factor approximation algorithm for an arbitrary set of traffic demands remains open.

No background in telecommunications will be assumed. This is joint work with Philip Lin.

A stable family is a collection of subsets of a finite set of n elements which are "stable" under perturbations in the following sense: if any coordinate of the incidence vector of a set in the family is changed (a break), there is some other coordinate that can be changed (a repair) to obtain another set in the family. Stable families arise in the context of fault tolerance in computation (especially search). We study the extremal properties of these families under suitable restrictions e.g. when the repair to every break is uniquely determined (we call these sparse stable families). We prove that stable families have to be linear in size. An upper bound is trivial, however we prove that the largest minimal stable family has size between 2^{2n/3} and (2/3) 2^{n-1}. For sparse stable families, we prove a tight lower bound of 2^{n/2} and an upper bound of 2^{n+1}/(n+2). We will also mention some results on the computational complexity of recognizing when an input search problem has a stable family of solutions and point out many open questions.

Joint work with Eugene M. Luks, Christopher Wilson.

I will give a geometric proof of the hook length formula for the number of standard Young tableaux of a given shape. We reduce the problem to an equality of the integer volumes of two polytopes. The latter is proved directly by an explicit continuous volume-preserving map.

The talk assumes no background whatsoever. With some luck, this will be the most transparent proof of the hook length formula you have ever seen...

The paper is published here: Séminaire Lotharingien de Combinatoire, vol. 46 (2001), article B46f, 13 pp.

For integers n,q,and k, a q-ary error-correcting code (or simply code) of message length k, and block length n, is a collection C, with |C| = q^k, of sequences of length $n$ over the letters {1,..,q}. The Hamming distance between two sequences x and y is the number of coordinates where they differ. A code C has minimum distance at least d if every pair of distinct sequences contained in the code have Hamming distance at least d. The parameter k/n is called the rate of a code, and the parameter d/n is the relative distance of the code.

Error-correcting codes have been studied for over fifty years now due to their immense practical use. The rate and relative distance are the two classical parameters of interest. In this talk we focus on a different parameter ``the list-decoding radius of a code'', and study its behaviour as a function of the more classically studied parameters. We describe the reasons to study this parameter, and some well-known bounds. Time permitting, we will describe some recent work (with V. Guruswami, J. Hastad, and D. Zuckerman), showing the existence of codes with non-trivial list-decoding radii.

On Wednesday October 10, 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.

Combinatorial games lead to several interesting, clean problems in mathematics, algorithms, and complexity theory. A combinatorial game typically involves two players; other interesting cases include combinatorial puzzles, in which there is only one player, and cellular automata such as Conway's Game of Life, in which there are zero players. In a perfect-information combinatorial game, no randomness (e.g., dice) or privacy (e.g., hidden cards) is allowed: all players know all information about gameplay. The problem is thus purely strategic: how to best play the game against an ideal opponent.

A beautiful mathematical theory has been developed for analyzing such games, but many algorithmic problems remain open. Many classic games and puzzles, such as Minesweeper, Go, and Chess, are known to be computationally intractable, as well as several seemingly simple games. I will mention several such results I have been involved in: robot pushing-block puzzles such as Sokoban, a block-removal puzzle Clickomania, and Conway's game Philosopher's Football. More exciting results are positive, proving that some games can be played optimally by efficient (polynomial-time) algorithms. I will describe one main result in this area, a wide class of coin-sliding puzzles. Other still-open problems I will discuss include Conway's angel-devil problem, and a cat-and-mouse game whose computational reduction (in a particular sense) would prove that P does not equal NP.

The quantum mechanical many-body problem has been a rich source of combinatorial problems. The algebra underlying the bosonic degrees of freedom, the Heisenberg-Weyl algebra, embodies the theory of the Stirling and Bell numbers, and provides a systematic route towards their $q$-deformation. The role of the symmetric group in the description of spin and fermionic systems has suggested, among several other problems, the characterization of the minimal amount of data required to specify an irreducible representation. The (incomplete) result will be contrasted with its Hecke algebra analogue.

The talk will not require any familiarity with physics. Open problems will abound.

A classic problem in logic design involves testing whether two Boolean functions have the same network realization. This is the case if the functions are NPN-equivalent, that is, related via permutations and negations of the m variables as well as negation of the function values. Proposed heuristics have been, in the worst case, no better than brute force enumeration of all the transformations. Even considering the input size to be n=2^m (functions are given via truth tables), the existence of a polynomial-time alternative was open.

The question is equivalent to testing isomorphism of hypergraphs on m vertices in `simply-exponential' c^m time. Such better-than-brute-force (m!) isomorphism had once appeared elusive even for ordinary graphs on m vertices. However, applying elementary group theory, we now handle the graph case using only naive divide-and-conquer. At first glance, there appear to be serious bottlenecks in an extension to hypergraphs. Nevertheless, a dynamic-programming reorganization settles the hypergraph problem as well. In turn, this yields polynomial time for Boolean-function equivalence. In fact, the procedure is strongly parallelizable.

This is a joint meeting with the Theory of Computation Seminar.

Gessel's enumerator of posets partitions may be seen as a morphism from a Hopf algebra of labeled posets to the Hopf algebra of quasisymmetric functions. This map factors through a third Hopf algebra consisting of permutations, which was introduced by Malvenuto and Reutenauer. This talk will describe the structure of this Malvenuto-Reutenauer Hopf algebra in detailed combinatorial terms. This description is obtained through careful analysis of the weak Bruhat order on the symmetric groups and their subsets of shuffles.

This is joint work with Marcelo Aguiar.

We give a closed-form formula, in both group theoretic and combinatorial terms, for the Hilbert function of the tangent cone at any point of a Schubert variety X in the Grassmannian. We also give a formula for the multiplicity of X at any point.

We study a natural family of graphs associated to symplectic manifolds with torus actions. These graphs encode information about the manifold, in particular they are useful for computations in equivariant cohomology. For this reason, it is important to understand the combinatorics and combinatorial significance of the structures inherited from the geometric setting. Accordingly, we can start with a graph $\Gamma$, and define combinatorial analogues of geometric objects, including Morse functions and Betti numbers. We will examine several examples, and then state theorems about these objects, some motivated by differential geometry and topology, and some purely combinatorial. I will not assume any background in symplectic geometry.

We investigate the quotient ring $R$ of the ring of formal power series $\Q[[x_1,x_2,\ldots]]$ over the closure of the ideal generated by non-constant quasi-symmetric functions. We show that a Hilbert basis of the quotient is naturally indexed by Catalan paths (infinite Dyck paths). We also give a filtration of ideals related to Catalan paths from $(0,0)$ and above the line $y=x-k$. We investigate as well the quotient ring $R_n$ of polynomial ring in $n$ variables over the ideal generated by non-constant quasi-symmetric polynomials. We show that the dimension of $R_n$ is bounded above by the $n$th Catalan number. [the equality is expected]

Ceilings of Gothic churches containing ribbed vaults present interesting mathematical patterns. A ribbed vault is a framework of diagonal arched ribs carrying the cells which cover ceiling in the spaces between them. Such a structure can be represented as a graph on a surface or as a tiling of a plane. The bosses and columns are vertices, the ribbed arches are edges and the cells are faces of the embedded graph. Although such geometric patterns can be found in Gothic churches throughout Europe we present some special masterpieces of star vault networks from the ceilings of late Gothic churches in Slovenia. In some cases the complicated structure of such patterns can be explained by applying some transformations that turn simple small graphs into larger, more complicated ones. In most cases it is sufficient to use the transformations that can produce from the graph of tetrahedron successively the graphs of all other four Platonic and the thirteen Archimedean solids. By combining simple transformations into more complicated ones an interesting tool for investigating maps on surfaces, tilings and polyhedra is obtained. For instance, one of the composed transformations is known in theoretical chemistry under the name of leapfrog transformation.

Carmichael's function of $n$ is the order of the largest cyclic subgroup of the multiplicative group of integers modulo $n$. What could be simpler? Actually, a lot could! Related to factoring, primality testing, Artin's conjecture, and Euler's function, there is still much that we don't know, and in some of the problems it is even hard to find the right conjecture.

I will give an elementary introduction to the theory of Macdonald polynomials (for a root system of type A), and then explain my work with A.Kirillov Jr. (1994) where this theory is connected with representation theory of the quantum group U_q(gl(n)). This allows to obtain a representation theoretic interpretation of all the main identities with Macdonald polynomials (constant term, inner product, evaluation, symmetry, Macdonald-Mehta-Cherednik), and to generalize Macdonald polynomials to the affine root system \hat A_n.

This is a survey of results on properties of random regular graphs, together with an exposition of some of the main methods of obtaining these results. A major feature in this area is the small subgraph conditioning method. This establishes a relationship between random regular graphs with uniform distribution, and other non-uniform models of random regular graphs in which the probability of a graph occurring is weighted according to some random variable. Information can be obtained in this way on the probability of existence of various types of spanning subgraphs, such as Hamilton cycles and decompositions into perfect matchings, as well as other properties such as smallest dominating set. Some results about interesting non-uniform models appear as spin-offs from the same method.

Lusztig defined {\it totally positive parts} in partial flag manifolds. The aim of this talk is to discuss total positivity in Grassmann manifolds and its links with the {\it inverse boundary problem} for planar oriented networks. This problem emerged in an attempt to generalize and simplify several recent combinatorial and algebraic constructions related to representation theory of GL(N) and canonical bases. The combinatorial classes of networks correspond to certain {\it totally positive Grassmann cells}. The collection of these cells forms a (conjecturally regular) CW-complex. They give a finer subdivision of the Grassmannian than the decomposition into the Schubert cells. The totally positive Grassmann cells extend the notion of {\it double Bruhat cells} (for type A) that were recently studied by Fomin and Zelevinsky.

We present several combinatorial constructions for the totally positive Grassmann cells in terms of web diagrams, tableaux, chord diagrams, and matroids. The totally positive Grassmann cells can also be thought of as all possible degenerations of {\it cyclic polytopes}. We describe the partial order on the cells by containment of closures, which is a certain extension of the Bruhat order on the symmetric group.

This theory seems to have deep and intriguing relations with {\it honeycombs} of Knutson and Tao and with {\it cluster algebras} of Fomin and Zelevinsky.

This talk will be joint with the Lie Groups Seminar.

Abstract: To what extent can the representation theory of a simple Lie algebra $\mathcal{L}$ be recovered from straighforward (say, combinatorial) manipulations of information from the associated root system? Among other things, we might seek out a procedure for obtaining "labels" which can be used to generate characters for the irreducible representations of $\mathcal{L}$. For another, we might try to describe actions of Lie algebra elements on these labels.

Lately, Littelmann (following work of Lakshmibai, Seshadri, and others) has prescribed a method for generating labels by manipulating paths in the weight lattice for $\mathcal{L}$. We will present another way to obtain labels for the rank two simple Lie algebras $A_2$, $B_2$, and $G_2$ (joint work with Norman Wildberger). This method realizes labels as order ideals in certain partially ordered sets. In many cases, the distributive lattices obtained from these ideals can be used to realize actions of Lie algebra generators (joint work with Scott J.\ Lewis and Robert Pervine). In particular, we obtain new realizations of an infinte family of irreducible representations of $G_2$.

Supersolvable lattices were introduced in 1972 by Stanley. Examples include finite distributive lattices, the lattice of partitions of $[n]$ and the lattice subgroups of a supersolvable group (hence the terminology.) Stanley showed that the edges of the Hasse diagram of a supersolvable lattice can be labeled to give an EL-labeling with the additional property that the labels along any maximal chain form a permutation. We call such a labeling an $S_n$ EL-labeling and we show that the converse result is true: if a finite lattice has an $S_n$ EL-labeling then it must be supersolvable.

In the second part of the talk we investigate a natural action on the maximal chains of an $S_n$ EL-labeled lattice. We show that this action gives a representation of the Hecke algebra of type $A$ at $q=0$. As a further desirable property, the character of this representation has Frobenius characteristic that is closely related to Ehrenborg's flag quasisymmetric function. We ask what other classes of lattices have an action with these properties and we show that finite graded lattices have such an action if and only if they have an $S_n$ EL-labeling.