Richard P. Stanley Seminar in Combinatorics

We will give a survey of results in the geometry of convex polyhedra in three dimensional Euclidean, hyperbolic, and some other geometries of constant curvature. We will point out some connections with the geometry of surfaces, number theory, and three-dimensional topology.

A simplicial complex K is d-Leray if all reduced homology groups H_i(L)vanish when i is equal or greater than d for every induced subcomplex L or K.

I will discuss d-Leray complexes and how they appear in combinatorial geometry problems, and present the following recent result, which in a commutative algebra formulation, settles a conjecture by Terai.

If K is d-Leray and L is r-Leray than their union is (r+d+1)-Leray and their intersections is (r+d)-Leray.

The celebrated Szemeredi-Trotter Theorem gives an asymptotically tight bound for the number of incident point-line pairs among n points and m lines in the Euclidean plane. No nontrivial tight bound is known in general for the incidences of points and any other type of curves or surfaces in the Euclidean space. All hyperplanes may be incident to all points in a degenerate configuration where the points are collinear. It turns out that one can give a tight incidence bound if we disregard all degenerate and close-to-degenerate hyperplanes. The new incidence bound has several applications involving distance sets, minimum volume simplices, and point-line configurations in 3D.

The minimal blow-ups of simplicial Coxeter complexes are natural generalizations of the real moduli space of Riemann spheres. The inherit a tiling by the graph-associahedra convex polytopes. We obtain explicit configuration space models for the classical infinite families of finite and affine Weyl groups (A, B, D, A~, B~, C~, D~) using particles on lines and circles. A Fulton-MacPherson compactification of these spaces is described and this is used to define a Coxeter operad.

Following Jacques Tits' geometric interpretation of the exceptional complex Lie groups, Francis Buekenhout generalized in the late seventies certain aspects of this theory in order to achieve a combinatorial understanding of all finite simple groups. Since then, two main traces have been developed in diagram geometry. One is to classify geometries over a given diagram, mainly over geometries extending buildings. Another trace is to classify coset geometries for a given group under certain conditions.

We will start the talk by explaining what an incidence geometry is. Then we will give some examples of results obtained in the first and the second approach. We will explain the connection between incidence geometries and finite groups which essentially arise as automorphism groups. We will also show how computational algebra softwares like {\sc Magma} may be used to explore incidence geometries and insist on the fact that experimental work in this field has already been very fruitful and has led to several theoretical results.

Consider an array of variables indexed by the entries of a three dimensional lattice obeying the relation f(n+1,i,j)*f(n-1,i,j)=f(n,i-1,j)*f(n,i+1,j)+f(n,i,j-1)*f(n,i,j+1). This is the octahedron recurrence, which emerged from the study of the Hirota equation in integrable systems and was brought to the attention of combinatorialists by Propp. The cube recurrence is a similar relation introduced by Propp and again defined on a three dimensional lattice. Each of these recurrences was motivated by the study of the Somos sequences.

If we fix a roughly two dimensional set of initial conditions, all of the other f's are rational expressions in the initial terms. Propp conjectured and Fomin and Zelevinsky proved that in each recurrence these rational expressions are actually Laurent polynomials. Propp additionally conjectured that the coefficients of these Laurent polynomials were all 1.

I will describe combinatorial proofs of these conjectures, due to myself in the octahedral case and joint work between myself and Gabriel Carroll in the cube case. In the octahedron case, the monomials turn out to be in bijection with perfect matchings of certain planar graphs, recovering results of Ciucu and others. In the cube case, the monomials are in bijection with groves, certain highly symmetric spanning forests deserving of more study.

Consider a poset P with its elements labeled by integers. For example, Young tableaux arise this way when P is a Young diagram, and P-partitions arise for more general posets P. In joint work with Allen Knutson and Alex Yong we define, for any finite set of labelings of P, a simplicial complex whose facets correspond to these labelings and whose smaller faces are labelings of P with sets of integers. Under interesting conditions, these \emph{tableau complexes} are (vertex-decomposable, and hence shellable) balls or spheres, and their interior faces are easily identified. Explicit Hilbert series formulas result. The special case where the facets are semistandard Young tableaux yields formulas for polynomials arising in Schubert Calculus.

A *bull* is a graph consisting of a triangle and two pendant edges. A graph is said to be *bullfree* if it contains no induced subgraph isomorphic to a bull. An obvious example of a bull free graph is a graph with no triangle, or a graph with no stable set of size three; but there are others. It turns out, however, that all bullfree graphs can built starting from graphs that belong to a few basic classes, and gluing them together by certain operations; and this is the main topic of this talk. Using this structure theorem, in joint work with S. Safra, we were able to prove that in every bull free graph there is either a stable set or a clique containing at least |V(G)|^\delta vertices, thus settling the Erdos-Hajnal conjecture for the bull

The main result to be discussed is a non-commutative version of the following linear algebra result: if $T$ is a linear transformation of order $n$ ($T^n=Id$) on a vector space $V$, then $T$ diagonalizes and the eigenvalues are the $n$-th roots of unity.

In the non-commutative version, the role of V is played by the group of characters on a graded connected Hopf algebra, and the role of $T$ by a canonical automorphism associated to the grading. These notions will be defined and illustrated with several examples of a combinatorial nature.

The factorization corresponding to the Hopf algebra of quasi-symmetric functions will be one of the main focuses. It involves interesting combinatorial constructions and allows for various applications.

A coloring of the constituents of a combinatorial structure is k-finite (k-bounded) if it uses only k colors (uses each color only k times). A combinatorial structure is homogeneously (heterogeneously) colored if every constituent is colored the same (differently). A Ramsey-type theorem asserts that every k-finite coloring of a certain structure induces a homogeneous substructure of a certain size. An anti-Ramsey type theorem asserts that that every k-bounded coloring of a certain structure induces a heterogeneous substructure of a certain size. Clearly k-finiteness or something like it is necessary for the Ramsey theorems, otherwise the structure may be colored heterogeneously. Similarly k-boundedness is necessary for the anti-Ramsey type theorems.

We'll talk a little about anti-Ramsey theorems in general and thresholds for anti-Ramsey properties in random graphs.

Given two projective varieties X and Y, their join X*Y is obtained by taking the Zariski closure of the union of all lines spanned by a point in X and a point in Y. The join of a variety X with itself is called the secant variety of X. In this talk, I will describe the construction of joins and secants in the combinatorial context of monomial ideals. For ideals generated by squarefree quadratic monomials, the generators of the secant ideals are obstructions to graph colorings and this leads to a commutative algebra version of the Strong Perfect Graph Theorem. Questions about secant varieties of combinatorially defined varieties (e.g. Grassmannians, determinantal varieties, toric varieties) can often be reduced to the monomial case. I will try to emphasize the combinatorial aspects of all of this, including the connections to graph theory, regular triangulations, and partially ordered sets.

This is joint work with Bernd Sturmfels.