An Adjacency Criterion for Coxeter Matroids

A Coxeter matroid is a generalization of matroid, ordinary matroid being the case corresponding to the family of Coxeter groups A _n , which are isomorphic to the symmetric groups. A basic result in the subject is a geometric characterization of Coxeter matroid in terms of the matroid polytope, a result first stated by Gelfand and Serganova. This paper concerns properties of the matroid polytope. In particular, a criterion is given for adjacency of vertices in the matroid polytope.     

Zonotopes whose cellular strings are all coherent

A cellular string of a polytope is a sequence of faces stacked on top of each other in a given direction. The poset of cellular strings, ordered by refinement, is known to be homotopy equivalent to a sphere. The subposet of coherent cellular strings is the face lattice of the fiber polytope, hence is homeomorphic to a sphere. In some special cases, every cellular string is coherent. Such polytopes are said to be all-coherent. We give a complete classification of zonotopes with the all-coherence property in terms of their oriented matroid structure. Although the face lattice of the fiber polytope in this case is not an oriented matroid invariant, we prove that the all-coherence property is invariant.     

Flag enumerations of matroid base polytopes

In this paper, we study flag structures of matroid base polytopes. We describe faces of matroid base polytopes in terms of matroid data, and give conditions for hyperplane splits of matroid base polytopes. Also, we show how the cd-index of a polytope can be expressed when a polytope is split by a hyperplane, and apply these to the cd-index of a matroid base polytope of a rank 2 matroid.     

The Lattice of Cyclic Flats of a Matroid

A flat of a matroid is cyclic if it is a union of circuits. The cyclic flats of a matroid form a lattice under inclusion. We study these lattices and explore matroids from the perspective of cyclic flats. In particular, we show that every lattice is isomorphic to the lattice of cyclic flats of a matroid. We give a necessary and sufficient condition for a lattice of sets and a function to be the lattice of cyclic flats of a matroid and the restriction of the corresponding rank function to . We apply this perspective to give an alternative view of the free product of matroids and we show how to compute the Tutte polynomial of the free product in terms of the Tutte polynomials of the constituent matroids. We define cyclic width and show that this concept gives rise to minor-closed, dual-closed classes of matroids, two of which contain only transversal matroids. Received May 29, 2005     

A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs

The theta bodies of a polynomial ideal are a series of semidefinite programming relaxations of the convex hull of the real variety of the ideal. In this paper we construct the theta bodies of the vanishing ideal of cycles in a binary matroid. Applied to cuts in graphs, this yields a new hierarchy of semidefinite programming relaxations of the cut polytope of the graph. If the binary matroid avoids certain minors we can characterize when the first theta body in the hierarchy equals the cycle polytope of the matroid. Specialized to cuts in graphs, this result solves a problem posed by Lovász.     

Coxeter matroid polytopes

If Δ is a polytope in real affine space, each edge of Δ determines a reflection in the perpendicular bisector of the edge. The exchange groupW (Δ) is the group generated by these reflections, and Δ is a (Coxeter) matroid polytope if this group is finite. This simple concept of matroid polytope turns out to be an equivalent way to define Coxeter matroids. The Gelfand-Serganova Theorem and the structure of the exchange group both give us information about the matroid polytope. We then specialize this information to the case of ordinary matroids; the matroid polytope by our definition in this case turns out to be a facet of the classical matroid polytope familiar to matroid theorists. This work was supported in part by NSA grant MDA904-95-1-1056.     

On the facets of the secondary polytope

The secondary polytope of a point configuration A is a polytope whose face poset is isomorphic to the poset of all regular subdivisions of A. While the vertices of the secondary polytope - corresponding to the triangulations of A - are very well studied, there is not much known about the facets of the secondary polytope.The splits of a polytope, subdivisions with exactly two maximal faces, are the simplest examples of such facets and the first that were systematically investigated. The present paper can be seen as a continuation of these studies and as a starting point of an examination of the subdivisions corresponding to the facets of the secondary polytope in general. As a special case, the notion of k-split is introduced as a possibility to classify polytopes in accordance to the complexity of the facets of their secondary polytopes. An application to matroid subdivisions of hypersimplices and tropical geometry is given.     

Concerning the shape of a geometric lattice

A well-known conjecture states that the Whitney numbers of the second kind of a geometric lattice (simple matroid) are logarithmically concave. We show this conjecture to be equivalent to proving an upper bound on the number of new copoints in the free erection of the associated simple matroid M. A bound on the number of these new copoints is given in terms of the copoints and colines of M. Also, the points-lines-planes conjecture is shown to be equivalent to a problem concerning the number of subgraphs of a certain bipartite graph whose vertices are the points and lines of a geometric lattice.     

On open questions in the geometric approach to structural learning Bayesian nets

The basic idea of an algebraic approach to learning Bayesian network (BN) structures is to represent every BN structure by a certain uniquely determined vector, called the standard imset. In a recent paper [18], it was shown that the set S of standard imsets is the set of vertices (=extreme points) of a certain polytope P and natural geometric neighborhood for standard imsets, and, consequently, for BN structures, was introduced.The new geometric view led to a series of open mathematical questions. In this paper, we try to answer some of them. First, we introduce a class of necessary linear constraints on standard imsets and formulate a conjecture that these constraints characterize the polytope P. The conjecture has been confirmed in the case of (at most) 4 variables. Second, we confirm a former hypothesis by Raymond Hemmecke that the only lattice points (=vectors having integers as components) within P are standard imsets. Third, we give a partial analysis of the geometric neighborhood in the case of 4 variables.     

A note on node packing polytopes on hypergraphs

A facial structure of the node packing polytope, i.e., of the convex hull of integer solutions of the node packing problem, on hypergraphs is studied. First, the results extracted by Chvàtal and by Balas and Zemel on canonical facets of the node packing polytopes on graphs are generalized to derive some specific hypergraphs having canonical facets. Second, it is shown that the facial structure of the node packing polytope on a hypergraph, named a fat graph, has a very close relationship to the facial structures of the node packing polytope and also of the convex hull of integer solutions of an integer linear program, which are defined on a specific graph corresponding to the fat graph.     

Toric ideals of lattice path matroids and polymatroids

White has conjectured that the toric ideal of a matroid is generated by quadric binomials corresponding to symmetric basis exchanges. We prove a stronger version of this conjecture for lattice path polymatroids by constructing a monomial order under which these sets of quadrics form Gröbner bases. We then introduce a larger class of polymatroids for which an analogous theorem holds. Finally, we obtain the same result for lattice path matroids as a corollary.     

Systems of Polynomials for Detecting Orientable Matroids

We study systems of polynomial equations that correspond to a matroid M. Each of these systems has a zero solution if and only if M is orientable. Since determining if a matroid is orientable is NP-complete with respect to the size of the input data, determining if these systems have solutions is also NP-complete. However, we show that one of the associated polynomial systems corresponding to M is linear if M is a binary matroid and thus it may be determined if binary matroids are orientable in polynomial time given the circuits and cocircuits of said matroid as the input. In the case when M is not binary, we consider the associated system of non-linear polynomials. In this case Hilbertʼs Nullstellensatz gives us that M is non-orientable if and only if a certain certificate to the given polynomials system exists. We wish to place bounds on the degree of these certificates in future research.     

Extended formulations for matroid polytopes through randomized protocols

The hitting number of a polytope P is the smallest size of a subset of vertices of P such that every facet of P has a vertex in the subset. We show that, if P is the base polytope of any matroid, then P admits an extended formulation of linear size on the hitting number of P. Our results generalize those of the spanning tree polytope given by Martin and Wong, and extend to polymatroids.     

The lattice of flats and its underlying flag matroid polytope

LetM be a matroid andF the collection of all linear orderings of bases ofM, orflags ofM. We define the flag matroid polytope Δ(F). We determine when two vertices of Δ(F) are adjacent, and provide a bijection between maximal chains in the lattice of flats ofM and certain maximal faces of Δ(F). Supported in part by NSA grant MDA904-95-1-1056.     

The brick polytope of a sorting network

The associahedron is a polytope whose graph is the graph of flips on triangulations of a convex polygon. Pseudotriangulations and multitriangulations generalize triangulations in two different ways, which have been unified by Pilaud & Pocchiola in their study of flip graphs on pseudoline arrangements with contacts supported by a given sorting network.In this paper, we construct the brick polytope of a sorting network, obtained as the convex hull of the brick vectors associated to each pseudoline arrangement supported by the network. We combinatorially characterize the vertices of this polytope, describe its faces, and decompose it as a Minkowski sum of matroid polytopes.Our brick polytopes include Hohlweg & Lange’s many realizations of the associahedron, which arise as brick polytopes for certain well-chosen sorting networks. We furthermore discuss the brick polytopes of sorting networks supporting pseudoline arrangements which correspond to multitriangulations of convex polygons: our polytopes only realize subgraphs of the flip graphs on multitriangulations and they cannot appear as projections of a hypothetical multiassociahedron.     

Hyperplane arrangements with a lattice of regions

A hyperplane arrangement is a finite set of hyperplanes through the origin in a finite-dimensional real vector space. Such an arrangement divides the vector space into a finite set of regions. Every such region determines a partial order on the set of all regions in which these are ordered according to their combinatorial distance from the fixed base region.We show that the base region is simplicial whenever the poset of regions is a lattice and that conversely this condition is sufficient for the lattice property for three-dimensional arrangements, but not in higher dimensions. For simplicial arrangements, the poset of regions is always a lattice.In the case of supersolvable arrangements (arrangements for which the lattice of intersections of hyperplanes is supersolvable), the poset of regions is a lattice if the base region is suitably chosen. We describe the geometric structure of such arrangements and derive an expression for the rank-generating function similar to a known one for Coxeter arrangements. For arrangements with a lattice of regions we give a geometric interpretation of the lattice property in terms of a closure operator defined on the set of hyperplanes.The results generalize to oriented matroids. We show that the adjacency graph (and poset of regions) of an arrangement determines the associated oriented matroid and hence in particular the lattice of intersections.The work of Anders Björner was supported in part by a grant from the NSF. Paul Edelman's work was supported in part by NSF Grants DMS-8612446 and DMS-8700995. The work of Günter Ziegler was done while he held a Norman Levinson Graduate Fellowship at MIT.     

Coproducts and the cd-Index

The linear span of isomorphism classes of posets, P, has a Newtonian coalgebra structure. We observe that the ab-index is a Newtonian coalgebra map from the vector space P to the algebra of polynomials in the noncommutative variables a and b. This enables us to obtain explicit formulas showing how the cd-index of the face lattice of a convex polytope changes when taking the pyramid and the prism of the polytope and the corresponding operations on posets. As a corollary, we have new recursion formulas for the cd-index of the Boolean algebra and the cubical lattice. Moreover, these operations also have interpretations for certain classes of permutations, including simsun and signed simsun permutations. We prove an identity for the shelling components of the simplex. Lastly, we show how to compute the ab-index of the Cartesian product of two posets given the ab-indexes of each poset.     

Face numbers of Engström representations of matroids

A classic problem in the theory of matroids is to find a subspace arrangement, such as a hyperplane or pseudosphere arrangement, whose intersection poset is isomorphic to a prescribed geometric lattice. Engström gave an explicit construction for an infinite family of such arrangements, indexed by the set of finite regular CW complexes. In this paper, we compute the face numbers of these topological representations in terms of the face numbers of the indexing complexes and give upper bounds on the total number of faces in these objects. Moreover, for a fixed rank, we show that the total number of faces in the Engström representation corresponding to a codimension one homotopy sphere arrangement is bounded above by a polynomial in the number of elements of the matroid, whose degree is one less than the matroid’s rank.     

Higher integrality conditions, volumes and Ehrhart polynomials

A polytope is integral if all of its vertices are lattice points. The constant term of the Ehrhart polynomial of an integral polytope is known to be 1. In previous work, we showed that the coefficients of the Ehrhart polynomial of a lattice-face polytope are volumes of projections of the polytope. We generalize both results by introducing a notion of k-integral polytopes, where 0-integral is equivalent to integral. We show that the Ehrhart polynomial of a k-integral polytope P has the properties that the coefficients in degrees less than or equal to k are determined by a projection of P, and the coefficients in higher degrees are determined by slices of P. A key step of the proof is that under certain generality conditions, the volume of a polytope is equal to the sum of volumes of slices of the polytope.     

The number of extreme points of tropical polyhedra

The celebrated upper bound theorem of McMullen determines the maximal number of extreme points of a polyhedron in terms of its dimension and the number of constraints which define it, showing that the maximum is attained by the polar of the cyclic polytope. We show that the same bound is valid in the tropical setting, up to a trivial modification. Then, we study the tropical analogues of the polars of a family of cyclic polytopes equipped with a sign pattern. We construct bijections between the extreme points of these polars and lattice paths depending on the sign pattern, from which we deduce explicit bounds for the number of extreme points, showing in particular that the upper bound is asymptotically tight as the dimension tends to infinity, keeping the number of constraints fixed. When transposed to the classical case, the previous constructions yield some lattice path generalizations of Gale's evenness criterion.