2004 Application

Home

Institute for Advanced Study

Questions and Comments

IAS/Park City Mathematics Institute
Graduate Summer School 2004

Geometric Combinatorics

Course Titles and Descriptions:

Geometric combinatorics concerns discrete structures that arise in a wide array of mathematical contexts, ranging from enumerative questions about polytopes and other constructions from linear algebra to the topology of manifolds and algebraic varieties.  The 2004 PCMI Graduate Summer School will consist of seven or eight courses intended to introduce the basic geometric objects in a combinatorial setting, and then to develop combinatorial tools for studying them, as well as geometric perspectives that can be brought to bear on more traditional combinatorial problems.  One of the purposes will be to foster an understanding of the interconnections between the topics in the various courses.  Among the techniques to be covered are such algebraic constructions as generating functions and homology, and also discrete analogues of continuous geometric notions such as curvature and fibration.

 1. Alexander Barvinok, University of Michigan
Lattice points, polyhedra, and complexity

The topic of integer points in polyhedra is classical, and it has many applications.  In this course, I plan to discuss a simple and powerful theory of enumeration of lattice points in rational polyhedra, through rational generating functions.  This approached has emerged over the past fifteen years.

As a preparatory step, I will introduce the calculus of polyhedra based on Euler characteristic.  Issues of computational complexity for lattice point enumeration reduce to unimodular decompositions of cones, which I will argue are the "right" multidimensional versions of continued fractions.  Finally, I will discuss enumeration of lattice points beyond polyhedra including lattice points in balls and lattice semigroups.

2.  Sergey Fomin, University of Michigan
Root systems and generalized associahedra

In a number of mathematics theories, "simple" objects are naturally labeled by the same set of labels: the Cartan matrices of finite type, (or equivalently, disjoint unions of Dynkin diagrams.)  These lectures focus on two instances of this ubiquitous Cartan-Killing classification, one of them classical and another very recent.

Firstly, we will discuss the classification of finite crystallographic root systems, and the related classification of finite groups generated by orthogonal reflections in a Euclidean space.  Some related combinatorial constructions (hyperplane arrangements, the root poset, etc.) will be briefly discussed, along with a glimpse into Weyl group combinatorics.

Lastly, we will describe the classification of cluster algebras of finite type, recently obtained in joint work with Andrei Zelevinsky.  The treatment of this topic will concentrate on its combinatorial aspects, foregoing the original representation-theoretic motivations.  The link between these two instances of the Cartan-Killing classification will then be provided by the construction of a generalized associahedron, a ployhedral complex associated with an arbitrary root system.  These associahedra, and the cluster algebras that they underlie, make appearances in contexts as diverse as invariant theory, hyperbolic geometry, total positivity, configuration spaces, and homotopy theory.  We will briefly survey some of these constructions.

3. Robin Forman, Rice University
Topics in combinatorial differential topology and geometry

In 1925, Marston Morse introduced a powerful tool, now known as Morse theory, for studying the topology of smooth manifolds using gradient flows.  The first half of this course will be an introduction to a discrete analogue of Morse theory that has proved useful for the study of spaces.  We will see how this theory can be applied to some combinatorial problems arising in graph theory, complexity theory, and algebraic combinatorics.

The second half of the course will be about some notions of curvature for polyhedral spaces as well as relationships (known and conjectured) between these notions, and the topology of the underlying space.  This is a vast subject, which we can only touch upon.  Among the topics to be discussed are various combinatorial notions of "non-positive curvature" such as CAT(0) and hyperbolic, that can be applied to combinatorial spaces.  In particular, we will see some topological and geometric implications of non-positive curvature, and the conjectured relationships (due to Hopf, Charney-Davis, and others) between this notion and the sign of the Euler characteristic.  Other topics for this half of the course include the use of the combinatorial Laplace operator as a tool for relating curvature to topology.

4.Mark Haiman, University of California Berkeley
Geometry of q- and q, t-analogs in combinatorial enumeration

Many familiar quantities from enumerative combinatorics have natural q-analogs.  Some examples are: (a) two different q-analogs of Catalan numbers, (b) a q-analog of the number (n+1)^{n-1}, which enumerates rooted forests and parking functions, (c) the Kostka-Foulkes polynomials, which are q-analogs of the number of semistandard Young tableau of given shape and content.  Examples (a) and (b) are closely connected with the theory q-Lagrange inversion, while (c) is connected with Hall-Littlewood symmetric functions and the Springer correspondence.

The theory of Macdonald polynomials leads to expressions involving two parameters q and t, including q, t-analogs of the aforementioned examples.  These q, t-quantities are defined as rational functions, in such a way that it is far from obvious that they are actually polynomials in q and t with non-negative integer coefficients.  Most existing proofs of polynomiality and positivity for q, t-quantities rely on a geometric interpretation involving the Hilbert scheme of points in the plane, which leads to a quasi-combinatorial interpretation of the coefficients as character multiplicities in a doubly-graded representation of the symmetric group.

Good conjectures are now available giving purely combinatorial interpretations of some of these q,t-quatities.  Some cases, such as that of the q, t-Catalan polynomials, have been proved using elementary methods.  To solve the full conjectures, probably some direct connection between the combinatorial and the geometric/representation-theoretic sides of the question will ultimately be needed.

1. Review of classical q-analogs

2. Introduction to Macdonald polynomials and q,t-analogs

3. Combinatorial conjectures for the q, t-analogs

4. Symmetric function theory techniques: can compute specializations such as t=1 or t=1/q; suffice for elementary proofs of some combinatorial result

5. Geometry/representation-theory techniques:  main tool for positivity and polynomiality theorems

6. Robert MacPherson, Institute for Advanced Study
Calculating equivariant invariants

Many topological spaces determine an associated classical combinatorial structure, such as a graph, a poset, an arrangement of linear subspaces, or a polyhedron.  Sometimes rings and modules that are invariants of the topological space, such as homology, equivariant cohomology, or intersection homology, can be calculated directly from the associated combinatorial structure.  This mini-course will emphasize the calculation of interesting rings and modules from combinatorial data.  No prior knowledge of topology will be assumed.

6. Richard Stanley, Massachusetts Institute of Technology
Hyperplane arrangements  

A (finite) \emph{hyperplane arrangement} is a collection of finitely many affine hyperplanes in some vector space (which for us will usually be over the real numbers.)  We will give an introduction to the theory of hyperplane arrangements, focusing on their combinatorial properties.  Topics will include the number of regions, intersection lattices, characteristic polynomials, graphical arrangements, modular elements, and supersolvable arrangements.  Some special arrangements will be analyzed, such as the braid, Catalan, Shi and Linial arrangements.  Some more algebraic aspects of hyperplane arrangements, such as homology of the complements of arrangements in complex vector spaces, free arrangements, and random walks on the regions of an arrangement, will be briefly discussed without proofs.

7. Michelle Wachs, University of Miami
Poset Topology:  Applications and Tools  

To every partially ordered set one can associate a simplicial complex called, the order complex of the poset.  The order complex links combinatorics with topology and other areas of mathematics in a deep and fundamental way.  Combinatorial interest in poset topology dates back to Gian-Carlo Rota's seminal 1964 paper on the M\"obius function of a partially ordered set.  The M\"obius number of a poset, an important combinatorial invariant, is equal to the reducted Euler characteristic of the order complex, and important topological invariant.

In this course we will discuss various applications of poset topology in areas such as the theory of hyperplane and subspace arrangements, group theory, complexity theory, and knot theory.  There are powerful methods for computing homotopy type and homology of posets, which will be presented.  These methods include shellability, fiber theorems, Whitney homology, and discrete Morse theory.  We will also discuss group actions on posets and the group representations on homology that they induce.

8. Günter Ziegler, Technical University- Berlin
Convex polytopes  

A central problem of Discrete Geometry asks for a description of the possible range of flag vectors for the polytopes of dimension d, whose entries count the chains of faces of specified dimensions.  For three-dimensional polytopes this was achieved a long time ago (Steinitz 1906), but for dimension four the picture is still incomplete.  In the lectures, we will analyze the four-dimensional case in detail, and thus see that there si a narrowing gap between "the constraints we know", and the "the examples we construct."

In the last thirty years there has been spectacular progress in the derivation of constraints (for example, via commutative algebra and algebraic geometry.)  Less visible progress was made in terms of constructions.  Although polytopes have been studied since antiquity, "...overall, we are short of examples" (Gil Kalai, 2000).  Therefore, we will look at some new construction methods and at the polytopes they produce.

A limited number of graduate students who have not completed the basic courses may attend. These students will attend some graduate level courses and may be involved as teaching assistants in other programs or work as audio-visual assistants.