DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME Twenty Four:
TITLE: "Formal Power Series and Algebraic Combinatorics"
EDITORS: Louis J. Billera, Curtis Greene, Rodica Simion, Richard P.Stanley
Published by the American Mathematical Society


Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.



PREFACE


This volume is devoted to the invited lectures presented at the Sixth International Conference on Formal Power Series and Algebraic Combinatorics/ Series Formelles et Combinatoire Algebrique, held at DIMACS during May 23-27, 1994, and organized by the editors.

The conference, made possible by funding provided by DIMACS, the National Science Foundation, and the Ministere des Affaires Etrangeres of France, attracted an audience of approximately 180 attendees, consisting of graduate students, junior researchers and senior researchers from Austria, Canada, Croatia, France, Germany, India, Isreal, Italy, Japan, Mexico, The Netherlands, Russia, Sweden, and the United States. Originally planned as a small workshop to highlight the vitality of current research in algebraic combinatorics, it was later merged into the FPSAC/SFCA series of annual conferences, becoming the 1994 meeting of this series. It focused on algebraic combinatorics and its connections with enumeration topology, geometry, and theoretical computer science.

The conference program included nine invited hour lectures as well as fory-two contributed presentation. The invited lectures were given by Louis Billera, Anders Bjorner, Ruth Charney, Maylis Delest, Philip Hanlon, David Jackson, Sergei Kerov, Christophe Reutenauer, and Sheila Sundaram. (One of the original invited speakers was forced to cancel just prior to the conference, and his spot was filled by one of the organizers.)

All of these lectures appear in this volume. Articles related to the contributed presentations appear separately in a special issue of the journal Discrete Mathematics, edited by Rodica Simion.

Loosely speaking, algebraic combinatorics involves the use of the techniques from algebra, algebraic topology, and algebraic geometry in the solution of combinatorial problems, or the use of combinatorial methods to attack problems in these areas. The combinatorial problems amenable to algebraic methods can arise in these or other areas of mathematics, or from areas such as computer science, operations research, physics, chemistry and, more recently, biology, Because of this interplay with many fields of mathematics and science, algebraic combinatorics is an area in which a wide variety of ideas and methods come together. We hope the papers that follow give some indication of this rich interaction.


TABLE OF CONTENTS



Preface                                                         ix 

The Combinatorics of Permutation Polytopes                  
            Louis J. Billera and A. Sarangarajan                 1

Nonpure Shellability, f-Vectors, Subspace Arrangements and 
  Complexity
            Anders Bjorner                                      25

Metric Geometry: Connections with Combinatorics
            Ruth Charney                                        55

Algebraic Languages:  A Bridge between Combinatorics and 
Computer Science
            Maylis Delest                                       71

A Survey of Combinatorial Problems in Lie Algebra Homolgy
            Phil Hanlon                                         89

Algebraic and Analytic Approaches for the Genus Series for
  2-Cell Embeddings on Orientable and Nonorientable Surfaces
             D.M. Jackson                                       115

The Boundary of Young Lattice and Random Young Tableaux
             S. Kerov                                           133

A Survey of Noncommutative Rational Series
             Christophe Reutenauer                              159

Plethysm, Partitions with an Even Number of Blocks and Euler 
  Numbers 
             Shelia Sundaram                                    171



Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.