Research on this project involves the use of algebraic, geometric and combinatorial methods to attack fundamental questions involving enumeration in partially ordered sets arising as face lattices of convex polytopes and as Bruhat intervals in Coxeter groups. The basic algebraic structure underlying these questions is the algebra of quasisymmetric functions, which generalizes the classical algebra of symmetric functions. Early results have shown that a generalization of a fundamental enumerative invariant for counting faces in convex polytopes - the cd-index - also provides a convenient way of representing the Kazhdan-Lusztig polynomial of a Bruhat interval in terms of classical polynomials arising in the enumeration of lattice paths. A focus of the project is to study the behavior of this generalized cd-index over the class of Bruhat intervals. An unrelated area of interest is the geometry of the space of phylogenetic trees. A goal here is to determine an efficient scheme to compute distances between trees in this space.
The study of the basic properties of polyhedra has been with us since the Greeks. One fundamental question, studied for hundreds of years, has to do with the relationship between the numbers of sides, edges and corners in such an object. Similar questions exist for high-dimensional analogs of polyhedra, which occur naturally in the analysis of methods to solve optimization problems arising in diverse areas such as resource allocation, industrial production and the design of communication networks. This project is focusing on techniques to analyze these counting problems. Recently it has been shown that these techniques are also useful in the study of fundamental properties of objects arising in the study of symmetry, for example, in theoretical physics. An unrelated direction is the study of phylogenetic trees, which are of basic interest in evolutionary biology. Here the aim is to develop methods to compute the distance between two such trees, a basic step in recently developed techniques to apply statistical methods to the profusion of tree data now being derived from the study of the structure of DNA in various species. Research on this project will also continue the investigator's training of graduate students and postdoctoral associates, all of whom have gone on to positions as college or university faculty or as research staff in industrial or government laboratories.
This project involved the study of connections between algebra, geometry and combinatorics, in particular combinatorial properties of the algebraic objects (groups) describing the symmetries of the regular convex solids. One major outcome of this project has been the extension of the methods successfully used to study the face counts (numbers of vertices, edges, etc.) of general convex solids (polytopes) in all dimensions to these groups of symmetries, leading to the hope that open problems about these groups may now be attacked using the methods that have been successful in the study of face counts. Previous results obtained under this ongoing project involved the development of a notion of distance between evolutionary trees, with the object of being able to deal with the multiplicity of such trees that arise from the analysis of DNA data. Recently, in a breakthrough result by a former graduate student whose thesis research had been supported by this project, an efficient (polynomially bounded) algorithm to compute this distance was developed. This now enables these calculations to be performed routinely for trees involving as many as 500 different species. One interesting development is an ongoing study by this former student and others to determine whether this tree distance can be useful in the analysis of trees describing the airways in human lungs (as determined by CAT scans), with the aim of determining whether changes in the structure of these trees might be an early marker of a disease process. During the course of the current project, four Ph.D. students were supervised by the principal investigator. Three of these currently hold university positions in the US and Canada. The fourth is currently employed by the NSA.
