|A. Björner (Monday 8/8)
Posets and order complexes
9:30 - 10:30am
2:15 - 3:15pm
We review basic definitions and facts from the combinatorics of posets and lattices, such
as M"obius function, etc. Then we define the order complex, which attaches a topological space (and hence homology groups, etc) and a commutative ring (the Stanley-Reisner ring) to every poset. Shellable and Cohen-Macaulay posets are defined and exemplified,
and the idea of ``algebras with straightening laws'' is sketched. Cell complexes and CW posets are mentioned. Some interesting classes of posets, such as face lattices of convex polytopes, lattices of subgroups, and posets of words, are discussed.
|A. Björner (Tuesday 8/9)
Graphs and matroids
9:30 - 10:30am
2:15 - 3:15pm
We begin by explaining how monotone graph properties can be viewed as simplicial complexes, and mention cases where questions about such complexes have come up in research in algebra and topology. Several of these questions (e.g. concerning matchings and
k-connectivity) have been answered using poset tools and techniques. We then go on to explain some key tools, such as fiber theorems and Morse matchings, illustrating their use on various graph complexes. The action of the symmetric group on a graph complex induces representations on homology, and this leads to another set of tools for the analysis of such complexes. Among the applications we mention Vassiliev stratification of spaces of knots and resolution of certain determinantal rings.
Matroids and geometric lattices are introduced and discussed in terms of the relevant simplicial complexes and the representations as hyperplane arrangements. The case of real hyperplane arrangements and the dual zonotope is of particular importance. We then move on to oriented matroids and explain the topological representation theorem, which relies on poset-theoretic constructions. The final topic is random walks on the regions of an oriented matroid.
|A. Björner (Wednesday 8/10)
9:30 - 10:30am
2:15 - 3:15pm
We define the intersection lattice of a subspace arrangement and discuss properties of the arrangement that can be read or constructed from this lattice. One such result is the theorem of Ziegler and Zivaljevic, which gives the homotopy type of the singularity link at the origin. We sketch how the Z-Z theorem is obtained via a poset fiber argument and an appropriate cell complex. Such complexes are constructed via the zonotope of a hyperplane embedding. We illustrate this general and useful cell complex construction with some additional examples, e.g. for complex hyperplane arrangements.
The Z-Z theorem implies the Goresky-MacPherson theorem, which gives a formula for the cohomology of the complement of a real subspace arrangement in terms of the order complex of its intersection lattice. This allows for useful computations in special cases. For instance, the solution to some decision tree complexity problems is given as an application.
Subspace arrangements over finite fields are examples of singular varieties, so the conclusions of the Weil conjectures don't all apply. But still a lot can be said. We review some of the technical tools, such as zeta function and l-adic cohomology. We recall some well-known combinatorial q-identities that illustrate the deep connections between q-counting and complex Betti numbers. The l-adic Goresky-MacPherson formula for subspace arrangements over a finite field is presented, showing that the summands known from the original Goresky-MacPherson formula are here eigenspaces of the Frobenius map. Discussion: Are there complexity-theoretic implications also here?
Time permitting, we briefly discuss the vanishing ideals of subspace arrangements (over general fields). What is sought is a good combinatorial construction of generators for such ideals. This is known in some interesting cases motivated by graph theory, and there are partial results related to the poset-theoretic ``blocker'' construction.
|A. Björner (Thursday 8/11)
9:30 - 10:30am
2:15 - 3:15am
We begin with a 5-10 minute introduction to finite reflection groups and (more generally) Coxeter groups. Then we introduce the Bruhat order on such a group and give a glimpse of its geometric and algebraic origins. What can be said about the structure of intervals
in Bruhat order? The basic fact is sphericity, which is proved via shellability. Short intervals in the finite groups have been classified. For longer intervals there is some information on the
rank-generating function, particularly for intervals beginning at the identity element. We survey results of this type and the methods used to obtain them (combinatorial and cohomological tools).
We end with a discussion of some remarkable recent discoveries, initiated by work in algebraic geometry. One such discovery is that much of the combinatorial structure of Bruhat order is inherited by the subposet of involutions (group elements of order two). Another that the poset of intervals of Bruhat order appears as the face poset of certain cell decompositions.
|A. Björner (Friday 8/12)
9:30 - 10:30am
2:15 - 3:15pm
We now turn to f-vector theory, that is, the study of rank-generating functions for order ideals in face lattices of polytopes (and other CW posets). We review the fundamental
theorems of Kruskal-Katona and Macaulay for complexes of sets and of multisets. Then we discuss the circle of ideas around the still open g-conjecture for simplicial spheres and its solution in the polytope case some 25 years ago. As a consequence of the g-theorem we derive a generalized Upper Bound Theorem for simplicial polytopes.
The method of algebraic shifting of simplicial complexes was introduced some 20 years ago by Kalai. It is a wonderful tool for extracting information about a complex by simplifying its
structure without destroying too much of its essential properties. This method has in the last 10 years attracted the interest of some algebraists, who view it in terms of ``generic initial
ideals'' within Gr\"obner basis theory.
As an application of algebraic shifting we derive a complete set of relations characterizing f-vectors and Betti numbers coming from a simplicial complex (thus extending the Euler-Poincar\'e formula). More generally, we present a theorem that contains this characterization, as well as the Kruskal-Katona theorem and the characterization of f-vectors of Cohen-Macaulay complexes, as special cases.
We end with a brief introduction to Scarf complexes determined by real matrices. Some open problems and some results for f-vectors of Scarf complexes are discussed. In the case of integer matrices there are connections with minimal free resolutions of lattice ideals.
Diaconis 11: 00 - 11:50 Applications of
algebraic topology in probability
There has been very limited contact between the powerful tools of algebraic topology and probability theory. I will describe random walk with reinforcement. Picture a graph with edges having weight one. A random walk starts at a fixed vertex. Each time the walker chooses the next vertex with probability proportional to weight. Each time the walk crosses an edge, one is added to the current edge weight. The question is, what happens as time goes on. The answer depends on the homology group of the graph. There are applications to DNA testing and many open questions.
|W. Bruns 11:00 - 11:50 Cohomology of partially
We study the cohomology of the Alexandrov topology underlying a partially ordered set P with coefficients in a sheaf S of rings. Examples of such structures naturally arise in connection with simplicial complexes or similar combinatorial objects. In the case of a simplicial complex and the natural choice of S the ring of global sections is the Stanley-Reisner ring of the complex, and the main goal is to generalize Hochster's formula. It
computes the local cohomology of the ring of global sections in terms of the local cohomology of the stalks and the cohomology of the poset. The generalization allows one to prove results of Yuzvinsky on the Cohen-Macaulay property of section rings in the
``right'' conceptual framework.
For technical reasons sheaves of rings and modules are represented by so-called RP-algebras and modules over them.
This is a report on joint work with Morten Brun and Tim Römer.
Barvinok 11: 00 - 11:50 Faces of some
interesting non-polyhedral convex bodies
I plan to survey known results on the facial structure of some interesting convex bodies, such as the cone of positive semidefinite matrices, the cone of non-negative polynomials and the convex hull of the real oriented Grassmannian under the Plucker embedding into the real sphere. Understanding of the facial structure of such convex bodies turns out to be relevant to a variety of questions from low rank approximations of matrices to solving systems of polynomial equations to calibrated geometries.
|I.Novik 3:50 - 4:40 How neighborly can a
centrally symmetric polytope be?
In the talk I will give a survey of what we know and what we would like to know about the face numbers of centrally symmetric polytopes. In particularly, I will concentrate on the
following question: How neighborly can a centrally symmetric polytope be as a function of its dimension and the number of vertices? This question was pursued in papers by Grünbaum (1967), McMullen and Shephard (1968), Schneider (1975), and Burton (1991). The answer turns out to be quite surprising: there exist k-neighborly centrally symmetric d-dimensional polytopes with 2(n+d) vertices, where
k(d,n)=\Theta(d / (1 + log (d+n)-log d),
and this bound is tight.
This is a joint work with Nathan Linial.
Wachs 11: 00 - 11:50 Posets of partitions,
graphs and trees
We discuss some remarkable connections between the homology of four different simplicial complexes, which have arisen in various contexts. The first of these is the order complex of a generalization of the partition lattice, namely the poset of partitions of a finite set whose block sizes are congruent to 1 mod k, for some fixed k. The second is the complex of graphs that don't contain a perfect matching; the third is the complex of
graphs that are not k-edge connected; and the fourth is Hanlon's generalization
of the complex of homeomorphically irreducibe trees.
We give equivariant versions of results of Linusson-Shareshian-Welker and Jonsson relating the homology of the odd block size partition poset to the nonperfect matching complex and the not 2-edge connected graph complex. Our proofs rely on the construction of an interesting basis for homology of the 1 mod k partition poset, which
generalizes the well-known nbc basis of Bj\"orner for the homology of
the partition lattice.
This is joint work with John Shareshian
Carlsson 11: 00 - 11:50 Algebraic topology of
point cloud data with examples
Algebraic topology is an algebraic formalism which allows one to make precise various kinds of qualitative information (called briefly "connectivity information") about geometric objects, even in high dimensions. This kind of information can be quite useful in attempting to understand the overall structure of the space in question. The methods have mostly been restricted to situations in which one has complete information about the spaces, and have typically only been evaluated by hand. In recent years, however, methods have been developed which allow one to infer connectivity information about a geometric object even though one may only be given a finite (but large) set of points (called a point cloud) sampled
from it. We will discuss these developments, and illustrate the techniques with an example from natural image statistics.
|N. White 3:50 - 4:40 An introduction to
Coxeter matroids are a generalization of ordinary matroids, based on a finite Coxeter group. We give some background material on matroids and finite Coxeter groups (or finite reflection groups) which will supplement material given in Prof. Bjorner's lectures. We then introduce the concept of Coxeter matroid. This concept has both a geometric aspect, involving polytopes, and an algebraic aspect, involving Coxeter groups and Bruhat order. In particular, we will introduce several classes of Coxeter matroids, including flag matroids, symplectic matroids, and orthogonal matroids. We will also state some unsolved problems in the field.
Sturmfels 3:50 - 4:40 Tropical Discriminants
This lecture reports on an ongoing joint project with Alicia Dickenstein and Eva Feichtner, aimed at giving a complete and self-contained combinatorial description of the A-discriminant. The book of Gel'fand, Kapranov and Zelevinsky offers an alternating formula for the extreme monomials of the A-discriminant under the restrictive hypothesis that A represents a smooth toric variety. Our new formula is positive and valid for any configuration A of lattice points. It is derived by studying the geometry of the Bergman fan of the matroid dual to A.