Richard P. Stanley Seminar in Combinatorics

Expansion of graphs can be given equivalent definitions in combinatorial and algebraic terms. This is the most basic connection between combinatorics and algebra illuminated by expanders and the quest to construct them. The talk will survey how fertile this connection has been to both fields, focusing on recent results.

Algebraic shifting introduced by Gil Kalai is an algebraic operation that given a simplicial complex $\Gamma$ produces a shifted complex $\Delta(\Gamma)$. This new complex has a simpler combinatorial structure, yet it shares with $\Gamma$ several combinatorial, topological, and algebraic properties such as face numbers, (topological) Betti numbers, extremal (algebraic graded) Betti numbers, etc. In the talk I will survey existing results and will present several new ones on algebraic shifting and their applications to combinatorics. This is a joint work with Eric Babson and Rekha Thomas.

Our point of departure are three fiber theorems for posets from a 1978 paper by Quillen. These theorems, which have been very influential in topological combinatorics, concern how properties are transferred between two posets connected by a poset map under suitable conditions on the fibers (contractibility, k-connectivity, Cohen-Macaulayness).

I will begin with a review of basics in the area. Then I will describe generalizations and new applications of all three theorems. Among the applications are generalizations of the crosscut theorem for posets, and poset-theoretic constructions corresponding to the weighted Segre product and Rees construction for semigroup rings.

This is based on joint work with M. Wachs and V. Welker.

This will be an expository talk on the Eulerian numbers, which arise in several contexts in enumerative combinatorics, probability, and algebra. The Eulerian numbers count permutations by descents and also by excedances, they give the volumes of slices of hypercubes, and they are dimensions of certain vector spaces associated with quotients of polynomial rings by symmetric functions. They also appear in the solution of the Smith College diploma problem.

I will describe all of these interpretations of Eulerian numbers and prove some of them.

We construct a "standard monomial basis" for the co-ordinate ring of the variety of nilpotent matrices in the space M(n) of n by n matrices (over a field of characteristic 0). For this construction, using a result of Lusztig, we identify the variety of nilpotent matrices with a open subset of a Schubert variety in the affine grassmannian \hat{Gr}_n. We then use the Plucker co-ordinates on the affine grassmannian \hat{Gr}_n, and construct the required basis as certain monomials in the Plucker co-ordinates (in the same spirit as that of Hodge's work on the classical Grassmannian.). As a consequence, we obtain some interesting connections between our basis and Schur functions & Yamanouchi words.

Joint meeting with Lie Theory Seminar

We present several recent results, in which new bounds are derived for the number of incidences between points and curves in two and three dimensions, as well as several related results, where these new bounds are applied. We also review the recent history of the incidence problem and its relatives.

We first consider the problem of cutting circles and pseudocircles in the plane (closed Jordan curves, each pair of which intersect at most twice) into pseudo-segments, that is, arcs with the property that each pair of them intersect at most once. We derive new bounds for the number of cuts, which improve a general previous bound, due to Tamaki and Tokuyama.

Combining these results with Sz\'ekely's technique, which is based on crossing numbers of graphs, and with dual space partitioning techniques, we obtain improved bounds for incidences between points and circles, between points and parabolas, between points and pseudo-circles, and between points and graphs of polynomials of fixed maximum degree.

Similar bounds are also obtained for the complexity of many faces in arrangements of curves of these classes. Improved bounds are also derived for levels in such arrangements.

We also discuss algorithms for computing incidences and many faces in such arrangements. The algorithms make use of a new duality transform (related to an earlier one due to Goodman) between points and pseudolines. This transform has also several other applications.

We next consider the problem of incidences between points and curves in three dimensions. This area has not been studied before, and we obtain a variety of new bounds for incidences between points and lines, between points and `equally-inclined' lines, between points and circles, and between points and certain kind of helices.

Finally, there are several additional applications of the new bounds. We mention two of them: A new lower bound for the number of distinct distances in three dimensions, and improved upper bounds for the number of simplices spanned by a point set in three or four dimensions and congruent to a given simplex.

Obviously, all of this will not fit into a single talk. In fact, we will most likely not even reach the middle of this abstract. The purpose of the abstract is to provide extra information for interested people.

A tile is a unit size square with colored edges. A palette P is a finite set of tiles with copies of which one can tile the plane so that the colors of adjacent tiles match. Classical works constructed palettes that can tile an infinite plane, but cannot do this recursively. That is, consider all P-squares, i.e. those appearing in P-tilings of a plane. For any c, only P-squares of bounded size can be generated (from their diameter) by c-bit programs. We pushed these results to the limit, with a palette for which all such squares have diameter c or less. This bound is tight since specifying the tiles on the square's frame suffices for tiling the square recursively. Thus, this palette allows only tilings with all frames being "nearly-random".

My talk, however, will only briefly mention this our result. I will mostly talk about just one old tool we are using: a palette P which precludes any translational symmetry in any P-tiling. The set of all P-tilings is, of course, symmetric under translations. Yet, any specific P-tiling is aperiodic, this symmetry spontaneously broken. Classical proofs of this result are very cumbersome. I will try to present a more transparent construction and proof.

Joint work with Bruno Durand and Alexander Shen.

Fulton's Universal Schubert polynomials represent general degeneracy loci for maps of vector bundles with rank conditions coming from a permutation. The Buch-Fulton Quiver formula expresses this polynomial as an integer linear combination of products of Schur polynomials in the differences of the bundles. We present a positive combinatorial formula for the coefficients. Our formula counts sequences of semi-standard Young tableaux satisfying certain conditions.

This is joint work with Anders Buch, Andrew Kresch and Harry Tamvakis.

The marriage between combinatorics and topology has been a long and fruitful one. There is, however, one notable exception, namely the lack of a combinatorial model for the local structure present in smooth manifolds. The first stumbling block has been the difficulty of finding a combinatorial way of capturing the linear algebraic apparatus present in the tangent bundle. The most successful approach turns out to rely on the language of oriented matroids.

I will explain what oriented matroids are and how they enter the study of manifolds. After sketching recent progress in this direction, I will then present several tantalizingly open-ended questions. The talk should be accessible to those unfamiliar in both oriented matroids and smooth manifolds.

The mirror symmetry phenomenon of physical string theory predicts that certain varieties come in pairs $(X,Y)$ that should determine 'the same physics'.

Essentially all known examples of mirror pairs come from convex polytopes. More precisely, they arise as hypersurfaces in projective toric varieties, and mirror duality comes from duality of polytopes.

I will sketch this construction due to Batyrev. Along the way, I will mention words like reflexive polytope, Hilbert basis of a rational cone, and unimodular triangulation; while I try to avoid scary things like moment map, large complex structure limit, and alike. If time permits, I will outline a combinatorial model for the more recent Strominger-Yau-Zaslow interpretation of mirror symmetry.

I would like to assume that people have seen a convex polytope before, at least from afar.

The higher Bruhat orders are a generalization of weak Bruhat order on S_n. They can be defined combinatorially in terms of inversion sets, generalizing the notion of inversion set of a permutation, or geometically as sets of d-faces of an n-cube, generalizing the description of S_n as paths through an n-cube. The higher Stasheff-Tamari posets (which generalize the Tamari lattices) have an analogous geometric definition where the cube is replaced by a simplex. In this talk, I will review all the necessary definitions, and then discuss a new combinatorial "inversion set" description of the higher Stasheff-Tamari posets which amounts to giving from each Stasheff-Tamari poset into a corresponding higher Bruhat order.

A graph is called a string graph if its vertices can be represented by continuous curves ("strings") in the plane so that two of them cross each other if and only if the corresponding vertices are adjacent. That is, string graphs are the crossing patterns of planar curves. They turned out to be relevant in the area of geographic information systems and in graph drawing. We show that out of the $2^{n\choose 2}$ labeled graphs on $n$ verices, roughly $2^{3/4{n\choose 2}}$ are string graphs.

We study also the cases when the strings representing the vertices of the graph are (a) segments, (b) curves, but any two can intersect at most $k$ (given constant) times. It turnes out that there are much less graphs that can be represented with this restriction. So, most (almost all) of the string graphs require an enermous number of crossings in any representation. We will show an easy example of a string graph that requires an exponential number of crossings.

Joint work with J\'anos Pach. The talk should be understandable for a general audience.

A cluster algebra of rank $n$ is a commutative ring generated inside its ambient field by a certain distinguished family of generators called cluster variables. These generators are obtained from some initial cluster by an explicit "mutation" process. The initial study of cluster algebras started by A.Zelevinsky and S.Fomin is motivated by dual canonical bases and total positivity in semisimple groups. Coordinate rings of such varieties, as, for instance, Bruhat cells in flag varieties and Grassmanians possess cluster algebra structures.

Poisson bracket on a manifold is a skew-commutative bilinear operation on the space of functions of this manifold, that turns the space of functions into Lie algebra. Symplectic structure on the manifold is a nondegenerate closed differential $2$-form on this manifold. There is a natural correspondence between symplectic structures and nondegenerate Poisson bracket.

We introduce a notion of Poisson bracket and closed differential $2$-form on $R^n$ compatible with the cluster algebra structure and describe all such Poisson brackets and $2$-forms. Moreover, any cluster algebra gives rise to a unique symplectic form (equivalently, nondegenerate Poisson bracket) on some affine space, generally speaking, of smaller dimension.

We hope that these objects shed some light on cluster algebra axioms. This is a joint work with M. Gekhtman and A. Vainshtein.

This is a joint meeting with Lie Theory Seminar.

We will survey the (old) combinatorial and (new) analytical definitions of the Jack polynomials as special functions of a parameter. We will define and explain the relationship between Jack and Multivariate Orthogonal Polynomials. Along the way, we will generalize univariate combinatorial quantities, like the binomial coefficients and the Pochhammer symbol.

We will also present one or two applications of the theory to eigenvalue statistics problems. We will show how these polynomials can be computed, talk about the inherent slowness of the algorithms, and if time allows, present a few computational examples, implemented in our new Maple Library MOPs (Multivariate Orthogonal Polynomials symbolically).

No background is necessary. This is joint work with Alan Edelman and Gene Shuman.

A projective variety with a complex torus acting on it is a GKM space if there are only a finite number of fixed points and a finite number of one dimensional orbits. (For instance flag varieties and toric varieties are such spaces.) Computing the equivariant cohomology rings of these spaces is equivalent to to a problem in graph theory the solution to which involves some interesting "topological" invariants of graphs.

No previous knowledge of equivariant cohomology is required. This talk will be accessible to general audience.

Introduced by Whitney in 1935, matroids are a combinatorial abstraction of linear dependence. Most matroid theory is motivated by graph theory or projective geometry. Beginning in the 70's matroids began to appear in topology. I will examine several topological representations and applications of matroids. These will include hyperplane and pseudosphere arrangements, linear quotients of spheres by elementary abelian p-groups, and arrangements of homotopy spheres. I will not assume any special knowledge in topology.

A geometric graph is a straight-line plane drawing of a graph, possibly with intersecting edges. Elementary fact (about planar graphs) is that if a geometric graph does not have intersecting edges then it has at most 3v-6 edges, where v is the number of vertices.

What happens if we want the intersection-free property to hold locally, i.e., we require that some k radius (graph-theoretic) neighborhood of every vertex be intersection-free. In other words all self-intersecting paths have to be of length at least 2k+1. Surprisingly, such a locally planar graph can have a super-linear number edges: we construct such a graph with average degree approximately k-times-iterated log of v (where v is the number of vertices). Matching upper bound is not known, the exact order of magnitude of the number of edges in the extremal graph is only known for the simplest case when only self-intersecting paths of length 3 are forbidden. (This is joint result with J. Pach and G. Toth.)

The construction is based on a recursive thinning procedure of bipartite graphs. This same procedure yields interesting results also in the Turan-type extremal theory of matrices. Consider the following question:

How many 1 can there be in an n by n 0-1 matrix that avoids certain configurations of 1's (submatrices)?

It was noted first by Z. Furedi that the number of 1 entries in a matrix avoiding the configuration

11

1 1

(not necessarily consecutive rows/columns) is O(n\log n). We show that if a matrix avoids both the configuration

11

1 1

and its mirror image:

1 1

11

then it has O(n\log\log n) 1 entries, and this bound is tight.

Introduced by Whitney in 1935, matroids are a combinatorial abstraction of linear dependence. Most matroid theory is motivated by graph theory or projective geometry. Beginning in the 70's matroids began to appear in topology. I will examine several topological representations and applications of matroids. These will include hyperplane and pseudosphere arrangements, linear quotients of spheres by elementary abelian p-groups, and arrangements of homotopy spheres. I will not assume any special knowledge in topology.

The study of the sequence of Catalan numbers $C_{n}$, given by

$$ C_{n} = {1 \over (n+1)}bin(2n,n), n \geq 0, $$

seems almost to have gained a life of its own; Richard Stanley, in his Enumerative Combinatorics II, gives an exercise in 66 parts, each part giving a different structure enumerated by this sequence according to some parameter of interest.

The sequence of Fine numbers $F_{n}$ is perhaps less well-known, but is linked to the Catalan numbers by the equation

$$ C_{n} = 2F_{n} + F_{n-1}, n \geq 1; F_{0} = 1, $$

although this is not how the sequence might be defined in the first instance, and there are other ways in which the sequences are intertwined.

But to verfify this equation it would be very nice to have a partition of the Catalan structures into Fine structures in which the equation is reflected in the subsets of the partition. This talk takes up the quest for such a demonstration, giving a generally accessible guided research tour that culminates in a successful proof technique for this identity amongst others.

The Kazhdan-Lusztig polynomials P_{x,w} associated to permutations x and w arise in the representations of the symmetric group S_n, in the geometry of Schubert varieties and in the context of Verma modules. There are many questions about these areas whose answers require a better combinatorial understanding of these polynomials. We look at one such question.

We present several counterexamples to the 0-1 conjecture: "The coefficient of highest possible degree in P_{x,w} is either 0 or 1." These counterexamples imply, in particular, that the representations of S_n constructed by Kazhdan and Lusztig are encoded by weighted graphs rather than simply by graphs. We will also mention how the combinatorial techniques used in the discovery and proof of the counterexamples may shed light on the coefficients of lower order terms of these polynomials.

This is joint work with Tim McLarnan.

Joint meeting with Lie Theory Seminar.

Even after Mark Haiman algebraic-geometric proofs of the $n!$ conjecture and of the more involved fact that the Frobenius characteristic $F_n$ of the bigraded $S_n$-module of Diagonal Harmonics is explicit given by an intricate formula involving Macdonald symmetric polynomials, there are still many open questions concerning both properties of Macdonald polynomials and related $S_n$-modules. Many of these involve an operator, called $\nabla$, that we introduced many years ago to simplify Haiman's expression for $F_n$. After reviewing the basics, we will discuss these open problems, including a program for a combinatorial proof of the $n!$ conjecture and several extensions.

The reliability polynomial $R(G;q)$ of a (finite, connected, loopless, multi-) graph is the probability that if each edge is deleted independently with probability $q$, then the remaining spanning subgraph is still connected. In 1992, Brown and Colbourn conjectured that every complex zero of the polynomial $R(G;q)$ lies in the closed unit disc $|q|\leq 1$. In this talk I will review the progress which has been made towards understanding this conjecture over the past decade, including work of Brown, Colbourn, Sokal, Chari, Choe, Royle, and others. Possible generalizations to matroids, and implications for the $f$--vectors of matroids will also be discussed.

Let P be a partial ordering of 1,2,...,n. The sign imbalance ofP is defined by I_P = \sum_\pi (-1)^{inv(\pi)}, where \pi ranges over all linear extensions of P (regarded as permutations of 1,2,...,n) and inv(\pi) denotes the number of inversions of \pi. The maj imbalance is defined analogously with inv replaced by maj (the major index). We will give a survey of sign and maj imbalance, including connections with promotion and evacuation, domino tilings, P-partitions, and symmetric functions.

Fairly easy exercise: If P is a product of two chains of even cardinalities, then I_P=0.

Much more difficult exercise: If P is a product of two chains of odd cardinalities >1, then I_P=0.

We study random automorphisms of binary trees of depth n. The order of such an automorphism is 2^K for a random integer K=K_n. We show that K_n/n converges to a constant which we specify explicitly. The proof uses a simple combinatorial random-tree description. This description is developed further to study random words and subgroups generated by random elements.

The methods generalize to many groups acting on trees. In the case of symmetric p-groups (Sylow-p subgroups of the symmetric group) we get an answer to an old question of Turan. Open questions will be presented. No background in probability or groups is assumed. This is joint work with M. Abert.

The set of all non-negative integer pxq-tables with fixed row sums and column sums can be connected by local moves involving changes in 2x2-subtables in each step. The difficult question of finding analogous moves for random walks on higher-dimensional contingency tables arises in statistics. Aoki and Takemura proved recently that 3x3xr-tables can be connected by moves of format 3x3x5, and they conjectured a similar finiteness theorem for pxqxr-tables when p and q are fixed and r increases. In this talk we prove their conjecture, by developing a general theory of higher Lawrence polytopes.

Joint work with Francisco Santos (math.CO/0209326)