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.     

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.     

A geometric characterization of Coxeter matroids

Coxeter matroids, introduced by Gelfand and Serganova, are combinatorial structures associated with any finite Coxeter group and its parabolic subgroup they include ordinary matroids as a specia case. A basic result in the subject is a geometric characterization of Coxeter matroids first stated by Gelfand and Serganova. This paper presents a self-contained, simple proof of a more general version of this geometric characterization.     

Recognizing graphic matroids

There is no polynomially bounded algorithm to test if a matroid (presented by an “independence oracle”) is binary. However, there is one to test graphicness. Finding this extends work of previous authors, who have given algorithms to test binary matroids for graphicness. Our main tool is a new result that ifM′ is the polygon matroid of a graphG, andM is a different matroid onE(G) with the same rank, then there is a vertex ofG whose star is not a cocircuit ofM.     

Counterexamples to conjectures on 4-connected matroids

Tutte characterized binary matroids to be those matroids without aU ₄ ² minor. Bixby strengthened Tutte’s result, proving that each element of a 2-connected non-binary matroid is in someU ₄ ² minor. Seymour proved that each pair of elements in a 3-connected non-binary matroid is in someU ₄ ² minor and conjectured that each triple of elements in a 4-connected non-binary matroid is in someU ₄ ² minor. A related conjecture of Robertson is that each triple of elements in a 4-connected non-graphic matroid is in some circuit. This paper provides counterexamples to these two conjectures.     

Boundaries of Coxeter Matroids

The purpose of this paper is to introduce, for a finite Coxeter groupW, the mod 2 boundary operator on the space of all Coxeter matroids (also known asWP-matroids) forWandP, wherePvaries through all the proper standard parabolic subgroups ofW(Theorem 3 of the paper). A remarkably simple interpretation of Coxeter matroids as certain sets of faces of the generalized permutahedron associated with the Coxeter groupW(Theorem 1) yields a natural definition of the boundary of a Coxeter matroid. The latter happens to be a union of Coxeter matroids for maximal standard parabolic subgroupsQ_iofP(Theorem 2). These results have very natural interpretations in the case of ordinary matroids and flag-matroids (Section 3).     

Quasi‐graphic matroids*

Frame matroids and lifted‐graphic matroids are two interesting generalizations of graphic matroids. Here, we introduce a new generalization, quasi‐graphic matroids, that unifies these two existing classes. Unlike frame matroids and lifted‐graphic matroids, it is easy to certify that a 3‐connected matroid is quasi‐graphic. The main result is that every 3‐connected representable quasi‐graphic matroid is either a lifted‐graphic matroid or a frame matroid.     

Matroid matching in pseudomodular lattices

The matroid matching problem (also known as matroid parity problem) has been intensively studied by several authors. Starting from very special problems, in particular the matching problem and the matroid intersection problem, good characterizations have been obtained for more and more general classes of matroids. The two most recent ones are the class of representable matroids and, later on, the class of algebraic matroids (cf. [4] and [2]). We present a further step of generalization, showing that a good characterization can also be obtained for the class of socalled pseudomodular matroids, introduced by Björner and Lovász (cf. [1]). A small counterexample is included to show that pseudomodularity still does not cover all matroids that behave well with respect to matroid matching.Supported by the German Research Association (Deutsche Forschungsgemeinschaft, SFB 303).     

On the cube problem of Las Vergnas

We prove a conjecture of Las Vergnas in dimensions d7: The matroid of the d-dimensional cube C ^d has a unique reorientation class. This extends a result of Las Vergnas, Roudneff and Salaün in dimension 4. Moreover, we determine the automorphism group G ^d of the matroid of the d-cube C ^d for arbitrary dimension d, and we discuss its relation to the Coxeter group of C ^d . We introduce matroid facets of the matroid of the d-cube in order to evaluate the order of G ^d . These matroid facets turn out to be arbitrary pairs of parallel subfacets of the cube. We show that the Euclidean automorphism group W ^d is a proper subgroup of the group G ^d of all matroid symmetries of the d-cube by describing genuine matroid symmetries for each Euclidean facet. A main theorem asserts that any one of these matroid symmetries together with the Euclidean Coxeter symmetries generate the full automorphism group G ^d . For the proof of Las Vergnas' conjecture we use essentially these symmetry results together with the fact that the reorientation class of an oriented matroid is determined by the labeled lower rank contractions of the oriented matroid. We also describe the Folkman-Lawrence representation of the vertex figure of the d-cube and a contraction of it. Finally, we apply our method of proof to show a result of Las Vergnas, Roudneff, and Salaün that the matroid of the 24-cell has a unique reorientation class, too.     

Two Remarks Concerning Balanced Matroids

The property of balance (in the sense of Feder and Mihail) is investigated in the context of paving matroids. The following examples are exhibited: (a) a class of “sparse” paving matroids that are balanced, but at the same time rich enough combinatorially to permit the encoding of hard counting problems; and (b) a paving matroid that is not balanced. The computational significance of (a) is the following. As a consequence of balance, there is an efficient algorithm for approximating the number of bases of a sparse paving matroid within specified relative error. On the other hand, determining the number of bases exactly is likely to be computationally intractable. * The work described here was supported by the grant “Sharper analysis of randomised algorithms” from the UK Engineering and Physical Sciences Research Council.     

Facial structures of lattice path matroid polytopes

A lattice path matroid is a transversal matroid corresponding to a pair of lattice paths on the plane. A matroid base polytope is the polytope whose vertices are the incidence vectors of the bases of the given matroid. In this paper, we study the facial structures of matroid base polytopes corresponding to lattice path matroids. In the case of a border strip, we show that all faces of a lattice path matroid polytope can be described by certain subsets of deletions, contractions, and direct sums. In particular, we express them in terms of the lattice path obtained from the border strip. Subsequently, the facial structures of a lattice path matroid polytope for a general case are explained in terms of certain tilings of skew shapes inside the given region.     

On some combinatorial properties of algebraic matroids

It was proved implicitly by Ingleton and Main and explicitly by Lindström that if three lines in the algebraic matroid consisting of all elements of an algebraically closed field are not coplanar, but any two of them are, then they pass through one point. This theorem is extended to a more general result about the intersection of subspaces in full algebraic matroids. This result is used to show that the minimax theorem for matroid matching, proved for linear matroids by Lovász, remains valid for algebraic matroids.     

Matroids and quotients of spheres

For any linear quotient of a sphere, where is an elementary abelian p–group, there is a corresponding representable matroid which only depends on the isometry class of X. When p is 2 or 3 this correspondence induces a bijection between isometry classes of linear quotients of spheres by elementary abelian p–groups, and matroids representable over Not only do the matroids give a great deal of information about the geometry and topology of the quotient spaces, but the topology of the quotient spaces point to new insights into some familiar matroid invariants. These include a generalization of the Crapo–Rota critical problem inequality and an unexpected relationship between and whether or not the matroid is affine. Received: 7 February 2001; in final form: 30 October 2001/ Published online: 29 April 2002     

Permutahedra and generalized associahedra

Given a finite Coxeter system (W,S) and a Coxeter element c, or equivalently an orientation of the Coxeter graph of W, we construct a simple polytope whose outer normal fan is N. Reading's Cambrian fan Fc, settling a conjecture of Reading that this is possible. We call this polytope the c-generalized associahedron. Our approach generalizes Loday's realization of the associahedron (a type A c-generalized associahedron whose outer normal fan is not the cluster fan but a coarsening of the Coxeter fan arising from the Tamari lattice) to any finite Coxeter group. A crucial role in the construction is played by the c-singleton cones, the cones in the c-Cambrian fan which consist of a single maximal cone from the Coxeter fan.Moreover, if W is a Weyl group and the vertices of the permutahedron are chosen in a lattice associated to W, then we show that our realizations have integer coordinates in this lattice.     

Circuits Through Cocircuits In A Graph With Extensions To Matroids

We show that for any k-connected graph having cocircumference c*, there is a cycle which intersects every cocycle of size c*-k + 2 or greater. We use this to show that in a 2-connected graph, there is a family of at most c* cycles for which each edge of the graph belongs to at least two cycles in the family. This settles a question raised by Oxley. A certain result known for cycles and cocycles in graphs is extended to matroids. It is shown that for a k-connected regular matroid having circumference c ≥ 2k if C₁ and C₂ are disjoint circuits satisfying r(C₁)+r(C₂)=r(C₁∪C₂), then |C₁|+|C₂|≤2(c-k + 1).     

The Greedy Algorithm and Coxeter Matroids

The notion of matroid has been generalized to Coxeter matroid by Gelfand and Serganova. To each pair (W, P) consisting of a finite irreducible Coxeter group W and parabolic subgroup P is associated a collection of objects called Coxeter matroids. The (ordinary) matroids are a special case, the case W = A (isomorphic to the symmetric group Sym_{_n+1}) and P a maximal parabolic subgroup. The main result of this paper is that for Coxeter matroids, just as for ordinary matroids, the greedy algorithm provides a solution to a naturally associated combinatorial optimization problem. Indeed, in many important cases, Coxeter matroids are characterized by this property. This result generalizes the classical Rado-Edmonds and Gale theorems.A corollary of our theorem is that, for Coxeter matroids L, the greedy algorithm solves the L-assignment problem. Let W be a finite group acting as linear transformations on a Euclidean space , and let

Recipe theorem for the Tutte polynomial for matroids,renormalization group-like approach

Using a quantum field theory renormalization group-like differential equation, we give a new proof of the recipe theorem for the Tutte polynomial for matroids. The solution of such an equation is in fact given by some appropriate characters of the Hopf algebra of isomorphic classes of matroids, characters which are then related to the Tutte polynomial for matroids. This Hopf algebraic approach also allows to prove, in a new way, a matroid Tutte polynomial convolution formula appearing in [W. Kook, V. Reiner, D. Stanton, A convolution formula for the Tutte polynomial, J. Combin. Theory Ser. B 76 (1999) 297–300] and [G. Etienne, M. Las Vergnas, External and internal elements of a matroid basis, Discrete Math. 179 (1998) 111–119].     

On matroid intersections

This paper exploits and extends results of Edmonds, Cunningham, Cruse and McDiarmid on matroid intersections. Letr ₁ andr ₂ be rank functions of two matroids defined on the same setE. For everyS ⊂E, letr ₁₂(S) be the largest cardinality of a subset ofS independent in both matroids, 0≦k≦r ₁₂(E)−1. It is shown that, ifc is nonnegative and integral, there is ay: 2 ^E →Z ⁺ which maximizes and , subject toy≧0, ∀j∈E, .     

Symplectic Matroids

A symplectic matroid is a collection B of k-element subsets of J = {1, 2, ..., n, 1*, 2*, ...; n*}, each of which contains not both of i and i* for every i n, and which has the additional property that for any linear ordering of J such that i j implies j* i* and i j* implies j i* for all i, j n, B has a member which dominates element-wise every other member of B. Symplectic matroids are a special case of Coxeter matroids, namely the case where the Coxeter group is the hyperoctahedral group, the group of symmetries of the n-cube. In this paper we develop the basic properties of symplectic matroids in a largely self-contained and elementary fashion. Many of these results are analogous to results for ordinary matroids (which are Coxeter matroids for the symmetric group), yet most are not generalizable to arbitrary Coxeter matroids. For example, representable symplectic matroids arise from totally isotropic subspaces of a symplectic space very similarly to the way in which representable ordinary matroids arise from a subspace of a vector space. We also examine Lagrangian matroids, which are the special case of symplectic matroids where k = n, and which are equivalent to Bouchet's symmetric matroids or 2-matroids.