Richard P. Stanley Seminar in Combinatorics

A set S of positive integers has distinct subset sums if for any distinct subsets I and J of S the sum of the elements in I does not equal the sum of the elements in J. For example, the sets {1,2,4,8} and {3,5,6,7} have distinct subset sums. How small can the largest element of such a set be? In other words, what is

f(n)=min{max S :|S|=n and S has distinct subset sums}?

Erdos conjectures that f(n) > c2^n for some constant c. In 1967 Conway and Guy constructed an interesting sequence of sets of integers. They conjectured not only that these sets have distinct subset sums but also that they are the best possible (with respect to the largest element). I will show a technique for proving that sets of integers have distinct subset sums. This technique can be used to show that the sets from the Conway-Guy sequence (as well as some other interesting sets) have distinct subset sums. A generalization of the Conway-Guy sequence now gives the best known upper bound on f(n).

The combinatorics of polynomial systems has grown tremendously thanks to the the beautiful formula of Kouchnirenko, Khovanskii, and Bernshtein (the BKK bound) relating mixed volume to the number of roots of a system of polynomial equations. In this talk, we'll see a new extension of this formula to different subsets of affine space. (The original BKK bound runs into complications when applied to counting roots with some coordinates equal to zero.) A corollary is a new formula for local intersection multiplicities in terms of an alternating sum of mixed volumes, generalizing an earlier result of Kouchnirenko.

Our approach will be fairly elementary and no significant prior knowledge of algebraic geometry is assumed.

Our objects of study are spaces of configurations of n distinct, labelled points in a topological space X. Though of interest in various contexts of algebraic topology over a long time, some of the topological invariants of these configuration spaces remained undetermined even for basic instances of X.

We present a complete and explicit description of the cohomology algebras of configuration spaces of spheres with integer coefficients, thereby exhibiting 2-torsion for spheres of even dimension. Moreover, we determine integer cohomology of the space of configurations of three distinct points on the torus. Surprisingly, we find 2-torsion as well as 4-torsion.

Our tools are elementary. Using classical spectral sequence techniques, the building blocks for our investigations turn out to be of combinatorial nature, thus revealing combinatorial structure at the core of the problem.

(Joint work with Gunter M. Ziegler.)

Consider an arbitrary poset P with a minimal element 0. Fix an integer k. The construction of the k_th deleted join of P can be described as follows: (1) Choose all possible ordered k-tuples of pointwise disjoint elements of P (for x,y in P, x and y are called disjoint if P_{<=x}\cap P_{<=y} = 0), (2) form a partially ordered set by saying that one k-tuple is larger than another if every element of the first k-tuple is larger or equal to some element of the second k-tuple.

The poset so obtained is called k_th deleted join of P, denoted P^(k). The symmetric group S_k acts on the deleted join by permuting the k-tuples.

The main objects B_{n,k} that we study can be defined as follows: let B_n be an n-dimensional Boolean algebra; take its k_th deleted join and let B_{n,k} be the quotient of B_n^(k) under the action of the symmetric group S_k described above. For example for k=2 one obtains a face poset of a triangulation of the projective space of dimension n.

The rational homology groups of B_{n,k} are trivial: 0 except for the highest dimension, where it is a free group. However there is a lot of torsion. We compute the p-torsion of B_{n,k}, in other words, we compute homology groups of B_{n,k} with coefficients in Z_p using a mixture of currently available tools: shellability, classifying spaces of the symmetric group, diagrams of spaces, and spectral sequences.

This research is joint with Eric Babson.

Two players, Maker (red) and Breaker (blue) alternately color previously uncolored edges of K_N. Maker wins the game if there is a red K_n. Breaker wins if there is no red K_n after all N(N-1)/2 edges have been colored. Beck showed that, for every \epsilon >0, Maker has a winning strategy whenever N>=N_0:=(2+\epsilon)^n for n sufficiently large. However, Maker can claim a victory only after all edges of some K_{N_0} have been colored.

In this talk I'll present a winning strategy for Maker requiring at most (n-3)2^{n-1}+n+1 moves whenever N>=(n-1)2^{n-1}+2. Furthermore, unlike the most winning strategies based on the weight function method, the problem of determining a move according to this strategy is computationally trivial. A believer in symmetry would conjecture that this is an optimal winning strategy for the Ramsey graph game. If so, the startling improvement of the lower bound for Ramsey numbers would follow.

We present a new method based on the Regularity Lemma and the Blow-up Lemma for finding certain special spanning subgraphs of dense graphs. Two typical applications of this method:

1. (Bollobas Conjecture, 1978) We show that any constant degree tree on sufficiently many vertices can be embedded into any dense graph on the same number of vertices.

2. (Posa-Seymour Conjecture, 1962) We show that a graph on sufficiently many vertices and with minimum degree at least 2/3 n (where n is the number of vertices) contains the square of a Hamiltonian cycle.

Algorithmic implications of the method will also be discussed.

The Turan number ex(n,G) of a fixed graph G is the greatest integer m, such that there exists a graph on n vertices with m edges, containing NO subgraph isomorphic to G. In the case when G is the complete bipartite graph K_{t,s}, the determination of the Turan number is called the Zarankiewicz problem. For 3 < t < =s, the order of magnitude of ex(n, K_{t,s}) wasn't (partly isn't) known.

Using polynomials over finite fields, we give an explicit construction of K_{t,(t-1)!+1}-free graphs with high edge-density. This improves upon earlier probabilistic bounds. The validity of the construction depends on elementary facts from commutative algebra. The result is a joint work with J. Kollar and L. Ronyai.

Extending the result from s>=(t-1)! to s>=t or even to s>=poly(t) would represent major progress.

Multivariate splines are piecewise polynomial functions defined on a polyhedral subdivision of R^d. Splines have many uses in applied math and engineering, e.g., approximating solutions to partial differential equations and surface modeling for computer graphics.

We address a problem in approximation theory about finding bases and dimensions for spline spaces by studying the combinatorial properties of the subdivision. Using these methods, we can explain how varying the triangulation changes the types of splines that can occur. We can also use the technique of Groebner bases to compute bases for spline spaces and to construct splines with a given set of constraints.

This talk will be accessible to a general mathematical audience.

The classical identities between the q-binomial coefficients and factorials can be generalized to a context where numbers are replaced by braids. More precisely, for every pair (i,n) of natural numbers, there is defined an element b^{(n)}_i of the braid group algebra kB_n, and these satisfy analogs of the classical identities for the binomial coefficients. By choosing representations of the braid groups one obtains numerical or matrix realizations of these identities. In particular one recovers the $q$-identities through the simplest one dimensional representation. These binomial braids b^{(n)}_i play a crucial role in the definition of the quantum group U_q^+(C) presented in the author's thesis. They are also closely related to the "Varchenko matrix" associated to the hyperplane arrangement of the root system A_n.

I will talk about two applications of free resolutions:

• Computing the cohomology of the complement of a real diagonal subspace arrangement (joint work with V. Reiner and V. Welker), and
• computing some invariants of the fundamental group of the complement of a complex hyperplane arrangemant.

For a simplicial subdivison Delta of a region in R^n, we analyze the dimension of the vector space C^r_k(Delta) of C^r piecewise polynomial functions (splines) on Delta of degree at most k. This problem is closely related to the structure of the graded R[x_0 \ldots x_n]-module C^r(\hat{Delta}), where \hat{Delta} is the join of Delta with the origin in R^{n+1}.

I will define a chain complex such that C^r(\hat{Delta}) appears as the top homology module, and will prove that if n=2 (i.e., Delta is planar), then C^r(\hat{\Delta}) is free if and only if the first homology module of the complex vanishes. Finally, I will show that there is a short exact sequence which relates the behavior of C^r(\hat{Delta}) to the behavior of ideals of the form <(x+a_1 y)^{r+1},...,(x+a_k y)^{r+1}>, with a_i not equal to a_j if i is not equal j, and will analyze the structure of these ideals.

It is well known that the Eulerian polynomials are log-concave, but until recently no combinatorial proof was known. In the first part of the talk we will present such a proof and discuss some related results and open questions.

The W-polynomials of labelled posets generalize the Eulerian polynomials. It was conjectured by Neggers and Stanley that the W-polynomials have only real zeros. We will prove that the W-polynomials of naturally labeled graded posets of small rank are unimodal which provides further evidence in support of the Neggers-Stanley conjecture. In the process we will also obtain a combinatorial proof of the fact that the W-polynomials of such posets are symmetric. (It is known that the W-polynomial of any naturally labeled graded poset is symmetric, but no combinatorial proof is known for the general case.)

Solving the first nonmonotonic, longer-than-three instance of a classic enumeration problem, we obtain the generating function H(x) of all 1342-avoiding permutations of length n as well as an exact formula for their number S_n(1342). While achieving this, we bijectively prove that the number of indecomposable 1342-avoiding permutations of length n equals that of labeled plane trees of a certain type on n+1 vertices recently enumerated by Cori, Jacquard and Schaeffer, which is in turn known to be equal to the number of rooted bicubic maps enumerated by Tutte in 1963. Moreover, H(x) turns out to be algebraic, proving the first nonmonotonic, longer-than-three instance of a conjecture of Zeilberger and Noonan. We also prove that the nth root of S_n(1342) converges to 8, so in particular, the limit of S_n(1342)/S_n(1234) as n goes to infinity is 0. This disproves one of the oldest conjectures of the field.