Louis Billera<billera@math.cornell.edu>

Geometric Enumeration, Quasisymmetric Functions and a Construction of Provan

Abstract: The idea of encoding the chain enumeration information for a graded partially ordered set as a formal power series has proved to be extremely useful in unifying several basic results concerning enumeration in polytopes and hyperplane arrangements. These power series, proposed by Ehrenborg several years ago, generate the algebra of quasisymmetric functions, a generalization of the ordinary symmetric functions that arise in representation theory. Natural considerations in this algebraic setting lead to the known connection between enumeration in a hyperplane arrangement and in its associated intersection lattice. Similar relationships appear to hold for other posets of geometric interest. An old construction of Provan proves useful in making these relationships explicit

Manoj Chari <Manoj.Chari@sas.com>

On the number of faces of matroid complexes

The number of faces of the abstract simplicial complex formed by independent sets of a matroid is a combinatorial invariant of theoretical and practical interest. There has been some progress towards the problem of completely characterizing this invariant in recent years and this talk will highlight some of the major results. Though it is a numerical invariant associated with an abstract and purely combinatorial object, we will show that it can be studied in a very geometric/topological manner. In particular, we will highlight the very close analogy between results for the number of faces of matroid complexes and the corresponding results for number of faces of simplicial convex polytopes. The talk will assume knowledge of some basic facts about graphs, polytopes and topology but will not assume any prior knowledge of matroid theory.

Craig Falls <cfalls@cs.unc.edu>

An extremal graph related algorithm for a problem arising in genetics.

Clusters of Orthologous Groups (COGs) are a popular tool for identifying groups of genes in different genomes that may be related by evolution. In a graph whose edges represent mutually best-fit genes, one forms COGs of stringency $m$ by merging $m$-cliques that overlap in $m-1$-cliques, and reporting the resulting sets of vertices. The presence of paralogs produces large Turan-type graphs, which makes straightforward enumeration of cliques infeasible -- there are simply too many. By recognizing and exploiting these extremal graphs, however, we obtain an algorithm to compute COGs that is orders of magnitude faster than clique enumeration.

Martin Groetschel <groetschel@zib.de>

LP-Approaches to Cycles in Matroids

Eulerian subgraphs are, e. g., of interest, if one wants to find optimal garbage collection tours; the maximum cut problem is employed to minimize the number of vias in a printed circuit board or to determine a ground state of a spin glass. All these quite different combinatorial optimization problems from practice can be viewed as special cases of the task to find, in a matroid M with weights on the elements of M, a cycle of maximum weight. (A cycle is the disjoint union of circuits of M.)

A typical approach to solve maximum weight cycle problems is to consider the polytope P(M), the convex hull of all incidence vectors of cycles in a matroid M, and to optimize the given linear weight function over P(M). To do this one needs a description of P(M) be means of linear inequalities.

In this talk I will review properties of P(M). E. g., one can describe P(M) completeley if M is a binary matroid with the sum of circuits property, and one can optimize LPs over P(M) in polynomial time. For the class of uniform matroids M (a class of quite trivial matroids), the complete description of P(M) is surprisingly complicated. It can be shown to arise as a special case of the linear description of the polytopes that are associated with cardinality homogeneous set systems.

Outside these classes of matroids not much is known. There is not even a "decent" integer programming formulation for the maximum weight cycle problem available.

Andrea Mantler <mantler@cs.unc.edu>

From Combinatorial Rigidity to Protein Allostery

Combinatorial rigidity studies the distribution of edges in a graph to determine the rigidity and flexibility of a corresponding bar and joint framework, where the bars have fixed lengths, and the joints at the ends of the bars are completely flexible. An allosteric transition is a conformational change in a protein that occurs when a ligand is bound at the effector site, and the change in the protein's structure affects the protein's ability to bind a second ligand at the active site. We are currently investigating whether changes in rigidity are the cause of certain allosteric transitions. I will review the relevant background in combinatorial rigidity, how we can model proteins as bar and joint frameworks, and the algorithm currently being used to compute rigidity in proteins. I will then explain how \emph{transmission cores} can propagate changes in rigidity from one site to another, and discuss the problems related to applying this model to actual proteins.

This work in progress is in collaboration with Jack Snoeyink, Walter Whiteley, Leslie Kuhn, Ileana Streinu, and others.

Gabor Pataki <gabor@unc.edu>

Column basis reduction and hard knapsack problems

We present a very simple preconditioning method applicable to any integer program with integral data. It works by replacing the feasibility problem

by the equivalent problem

where U is a unimodular matrix chosen to make the columns of AU "relatively" short and orthogonal. In practice, U is found by lattice basis reduction, utilizing the algorithm of Lovasz, or some of its followers. Our reformulation method -- termed column basis reduction -- is a generalization and simplification of a reformulation technique proposed by Aardal, Lenstra and others for equality constrained problems.

The performance of column basis reduction is quite striking on some classes of problems: in one prominent example, a 0-1 knapsack problem with only 100 variables that could not be solved by a state-of-the-art commercial solver after enumerating 2 BILLION nodes, was solved at the rootnode after the reformulation was applied.

We present an analysis of this method for several classes of hard knapsack problems. We prove that on these problems branch-and-bound must take an exponential number of nodes to solve it, while after reformulation it solves after a constant number of nodes are enumerated.

Joint work with Bala Krishnamoorthy at UNC Chapel Hill.

Lindsay Piechnik <lcp7@math.duke.edu>

Smooth reflexive 4-polytopes have quadratic triangulations

Bernd Sturmfels asked whether the homogenous toric ideal coming from a smooth polytope (unimodular normal fan) is generated by quadrics. We show that all smooth reflexive 4-polytopes (as classified by Batyrev) have regular unimodular triangulations whose minimal non-faces are edges (clique complex). So these ideals even have a quadratic Groebner basis.

J.Scott Provan <Scott_Provan@UNC.edu>

The 2-Connected Steiner Network Problem in the Plane

Carla Savage <savage@unity.ncsu.edu>

Venn Diagrams and Symmetric Chain Decompositions in the Boolean Lattice