Ph.D. Recipients and their Thesis Abstracts

Combinatorics

Algebra, Analysis, Combinatorics, Differential Equations / Dynamical Systems, Differential Geometry, Geometry, Interdisciplinary, Lie Groups, Logic, Mathematical Physics, PDE / Numerical Analysis, Probability, Statistics, Topology

Quasisymmetric Functions and Flag Enumeration in Eulerian Posets

Abstract: We study the algebraic and enumerative combinatorial aspects of Eulerian posets and their quasisymmetric generating functions. These generating functions span the so-called peak algebra Pi, which originated with Stembridge's theory of enriched P-partitions. Remarkably, many constructs in the peak algebra that are natural in the context of enriched P-partitions are also important from the viewpoint of flag enumeration. For example, we show that the fundamental basis of peak functions arising from enriched P-partitions of chains is precisely the basis that is needed to properly encode the cd-index, a common invariant in the study of convex polytopes and Eulerian posets. As another example, the descents-to-peaks map, which relates the ordinary and enriched theories of P-partitions, turns out to be important for computing the flag-enumerative information of an oriented matroid based on that of the underlying matroid.

We introduce a family of Eulerian posets, called posets of signed order ideals. Each of these posets is defined by appropriately "signing" a distributive lattice. We establish that the flag-enumerative relationship between a poset of signed order ideals and its underlying distributive lattice is completely analogous to that between an oriented matroid and its underlying matroid. Furthermore, we show that these posets are EL-shellable, they have non-negative cd-indices, and their quasisymmetric generating functions enumerate the enriched P-partitions of certain labeled posets.

We analyze the (external) Hopf algebra structure on Pi, showing it to be dual to the concatenation Hopf algebra on letters of odd degree. Consequently, Pi is freely generated as a commutative algebra. Upon closer inspection of the generators, we find that Pi is free as a module over the ring of Schur Q-functions. Much of our analysis builds on basic properties of a monomial-like basis for the peak algebra, as well as a recursively defined basis of eigenvectors for the descents-to-peaks map. We give a simple criterion, in terms of this monomial basis, for determining when an element of Pi is symmetric.

Enumeration in Geometric Lattices and the
Symmetric Group

Abstract: This work primarily deals with questions relating to the enumeration of chains in geometric lattices. The study of geometric lattices arose in the process of characterizing the lattices of subspaces formed by a finite set of points in projective or affine space, and ordered by inclusion. More generally geometric lattices encode the structure of matroids (or combinatorial geometries), which take an axiomatic approach to the concept of dependence.

The flag Whitney numbers of a geometric lattice count the number of chains of the lattice with elements having specified ranks. We are interested in the linear inequalities satisfied by the flag Whitney numbers.

We present a lower bond on the flag Whitney numbers of a lattice in terms of its rank and number of atoms. We also show that all flag Whitney numbers are simultaneously minimized by the lattice corresponding to the near pencil arrangement of points in R^n. Next we focus on rank 3 geometric lattices and give a collection of inequalities which imply all the linear inequalities satisfied by the flag Whitney numbers of rank 3 geometric lattices. We further describe the smallest closed convex set containing the flag Whitney numbers of rank 3 lattices corresponding to oriented matroids.

The ab-index is a polynomial associated to a lattice which contains all of the information regarding the flag Whitney numbers. We give a recurrence relation for the ab-index of families of lattices satisfying a particular set of conditions. We also give a collection of inequalities for the ab-index of geometric lattices.

Finally, we turn our attention to the group algebra of the symmetric group. The peak set of a permutation $\sigma$ is the set $\{i:\sigma(i–1)<\sigma(i)>\sigma(i+1)\}$. We prove the existence of a subalgebra of Solomon's descent algebra in which elements are sums of permutations that share a common peak set.

Linear Inequalities for Flag f-Vectors of Polytopes

Abstract: Here we study the combinatorics of polytopes. A polytope P is the convex hull of a finite set of points in R^d, and its boundary is a collection of lower-dimensional polytopes known as the faces of P. The flag f-vector of P counts the faces of each dimension and their incidences with one another. We would like to know what linear inequalities the entries of the flag f-vector satisfy.

First we present some of the history of this problem, along with the necessary mathematical background. We discuss several special classes of polytopes, including simplicials, simples, cubicals and zonotopes, whose flag f-vectors satisfy inequalities not satisfied by all polytopes.

Then we define Stanley's toric g-vector, which can be used to generate many linear inequalities for flag f-vectors. We prove Meisinger's conjecture that some of these inequalities are implied by others. In addition, we consider the CD-index, another source of many inequalities. We show that not all of these are consequences of the non-negativity of the toric g-vector.

We then use linear inequalities satisfied by lower-dimensional polytopes to generate linear relations satisfied by simplicial, simple, k-simplicial and k-simple polytopes, and cubical zonotopes. We also examine a g-vector for cubical polytopes proposed by Adin and give evidence that supports the conjecture g_2 <= 0. In particular, we show this to hold for the class of almost simple cubical polytopes, where one might expect it is most likely to fail. Next we improve upon previously known linear inequalities satisfied by zonotopes. Finally, we construct examples of another special class of polytopes, the self-dual polytopes.

Solving Sparse Polynomial Systems

Abstract: The computation of all solutions of a system of polynomial equations is a basic and in general hard problem. The main techniques for accomplishing this task in an algorithmic manner, Gröbner bases, multivariate resultants and continuation methods have received a great deal of attention recently. This thesis describes continuation methods for numerically determining all complex solutions of a system of polynomial equations. The emphasis is on the set up of continuation problems which require as few paths as possible, rather than on the numerical process of path following.

The key to efficient continuation methods is to realize the system to be solved as a generic element in a one dimensional parameterized family. Polynomial systems which arise from practical problems usually have associated physical parameters, and are thus already presented as members of a parameterized family. In the first chapter we discuss the total space of such a parameterized family and its implications for continuation methods.

The main body of the thesis deals with the application of toric deformations, and polyhedral subdivisions to produce continuation methods which are optimal for systems with a given collection of support sets {\Cal A} = {{\Cal A}_1,...,{\Cal A}_n}. We identify monomials x^q=x_1^{q_1}... x_n^{q_n} with lattice points q=(q_1,...,q_n)\in Z^n and allow polynomials of the form

f_i(x)=\sum_{q\in{\Cal A}_i} c_{i,q}x^q

where i=1,...,n and the coefficients c_{i,q} are complex. A famous result of Bernstein sates that, for generic choices of coefficients, the mixed volume of the Newton polytopes {\Cal Q}_i= conv({\Cal A}_i) is equal to the number of isolated solutions in (C*)^n. In Chapter 2, the concepts of Minkowski addition, mixed volume, and fine mixed subdivisions are presented. The use of fine mixed subdivisions of the Minkowski sum {\Cal Q}_i+...+{\Cal Q}_n in computing mixed volumes generalizes the use of triangulations in volume computation. Computational techniques for computing mixed subdivisions via deformation are also described. In Chapter 3, these techniques are adapted to provide a constructive proof of Bernstein's theorem, as well as a generalization of Bernstein's theorem to counting roots in C^n. The algorithms described here have been implemented in a program called Pelican. Chapter 4 describes Pelican and provides a tutorial and reference manual.

Geometry and Combinatorics of Chow Forms

Abstract: The Chow form of a variety is similar to a resultant. Given d+1 linear forms on a d-dimensional projective variety, the Chow form is a polynomial in the coefficients of the linear forms (unique up to multiplication by a nonzero constant) which is zero if and only if the linear forms have a common zero on the variety. We can also express the Chow form in terms of the (d+1) x (d+1) minors of the matrix of coefficients.

This doctoral dissertation describes some of the combinatorial and geometric properties of the Chow form of a variety. In chapter 1, we give an introduction to Chow forms and describe how to perform some basic geometric operations on varieties by manipulating their Chow forms. In chapter 2, we study the combinatorics of Chow forms of point sets in projective spaces and compare and contrast this theory with the theory of binary forms (which are Chow forms of point sets in P^1). We also consider the inhomogeneous version of this theory, the theory of multisymmetric functions. We give proofs for many of the assertions made in this paper, and also a counterexample to one of them. In chapter 3, we consider the Chow polytope as a combinatorial invariant of the Chow form. We show that the Chow polytope of the ruled join of two varieties (a construction used in intersection theory) is the Cartesian product of the Chow polytopes after a change of scale. We also investigate the stratification of the Chow variety of plane conics (whose points are the coefficient vectors of their Chow forms) induced by the different Chow polytopes. In chapter 4, we present a geometric algorithm for computing the Chow form of a ruled join in stages, and give examples of its use. Chapter 5 is somewhat disconnected from the remainder of the thesis; it proves that all connected complexes of coordinate lines in P^3 are initial complexes of space curves. This is a partial converse to the cited result of Kalkbrener and Sturmfels that all initial complexes of irreducible varieties are connected. Appendix A describes some MAPLE code written by the author to implement the algorithms of Section 2.1.3 and to make it easier to execute the algorithm of Section 4.2.

Algebraic and Combinatorial Methods for Face Enumeration in Polytopes

Abstract: Let P be a d-dimensional polytope and S a subset of {0, 1, ... , d–1}. We denote by f_S(P) the number of chains of faces whose dimensions make up S. The flag f-vector is the vector made up of all such flag numbers. This thesis studies linear and nonlinear conditions on the flag f-vectors of several classes of polytopes.

We define a noncommutative algebra whose elements can be viewed as linear forms of flag numbers of polytopes. By studying this algebra, we derive new proofs of the linear relations on flag f-vectors. We also obtain results about the CD-index and symmetric linear forms having same value on any polytope and its dual. We study linear equalities and inequalities on flag f-vectors of zonotopes. The method is to construct a class of zonotopes to establish a lower bound for the span of flag f-vectors. We also find a class of inequalities on flag numbers of zonotopes; some of the inequalities from this class do not hold for general polytopes. In the case of the cube, we prove the g-conjecture in a stronger form, i.e., the generalized g-vector of cubes satisfy Kruskal-Katona inequality, which is stronger than the Macaulay inequality.

Combinatorial Structure on the Hilbert Scheme

Abstract: In this thesis, the component structure of the Hilbert scheme is investigated. The techniques used to carry out this investigation include Gröbner bases, state polytopes, Hartshorne's fans, normal bundles, Borel-fixed ideals, and methods from deformation theory.

Last modified: February 10, 2004