On Tutte polynomial expansion formulas in perspectives of matroids and oriented matroids

We introduce the active partition of the ground set of an oriented matroid perspective (or morphism, or quotient, or strong map) on a linearly ordered ground set. The reorientations obtained by arbitrarily reorienting parts of the active partition share the same active partition. This yields an equivalence relation for the set of reorientations of an oriented matroid perspective, whose classes are enumerated by coefficients of the Tutte polynomial, and a remarkable partition of the set of reorientations into Boolean lattices, from which we get a short direct proof of a 4-variable expansion formula for the Tutte polynomial in terms of orientation activities. This formula was given in the last unpublished preprint by Michel Las Vergnas; the above equivalence relation and notion of active partition generalize a former construction in oriented matroids by Michel Las Vergnas and the author; and the possibility of such a proof technique in perspectives was announced in the aforementioned preprint. We also briefly highlight how the 5-variable expansion of the Tutte polynomial in terms of subset activities in matroid perspectives comes in a similar way from the known partition of the power set of the ground set into Boolean lattices related to subset activities (and we complete the proof with a property which was missing in the literature). In particular, the paper applies to matroids and oriented matroids on a linearly ordered ground set, and applies to graph and directed graph homomorphisms on a linearly ordered edge-set.     

Extreme point axioms for closure spaces

A pair (X,τ) of a finite set X and a closure operator τ:2^X→2^X is called a closure space. The class of closure spaces includes matroids as well as antimatroids. Associated with a closure space (X,τ), the extreme point operator ex:2^X→2^X is defined as ex(A)={p|p∈A,p∉τ(A-{p})}. We give characterizations of extreme point operators of closure spaces, matroids and antimatroids, respectively.     

On the evaluation at (<Emphasis Type="Italic">j</Emphasis>, <Emphasis Type="Italic">j</Emphasis><Superscript>2</Superscript>) of the Tutte polynomial of a ternary matroid

F. Jaeger has shown that up to a ± sign the evaluation at (j, j ²) of the Tutte polynomial of a ternary matroid can be expressed in terms of the dimension of the bicycle space of a representation over GF(3). We give a short algebraic proof of this result, which moreover yields the exact value of ±, a problem left open in Jaeger's paper. It follows that the computation of t(j, j ²) is of polynomial complexity for a ternary matroid.E. Gioan: C.N.R.S., MontpellierM. Las Vergnas: C.N.R.S., Paris     

Cohen–Macaulayness of monomial ideals and symbolic powers of Stanley–Reisner ideals

We present criteria for the Cohen–Macaulayness of a monomial ideal in terms of its primary decomposition. These criteria allow us to use tools of graph theory and of linear programming to study the Cohen–Macaulayness of monomial ideals which are intersections of prime ideal powers. We can characterize the Cohen–Macaulayness of the second symbolic power or of all symbolic powers of a Stanley–Reisner ideal in terms of the simplicial complex. These characterizations show that the simplicial complex must be very compact if some symbolic power is Cohen–Macaulay. In particular, all symbolic powers are Cohen–Macaulay if and only if the simplicial complex is a matroid complex. We also prove that the Cohen–Macaulayness can pass from a symbolic power to another symbolic powers in different ways.     

Envy-free matchings with one-sided preferences and matroid constraints

In this paper, we consider the problem of checking the existence of an envy-free matching in a many-to-one matching model with one-sided preferences and matroid constraints. For this problem, we propose a polynomial-time algorithm which is a generalization of the algorithm proposed by Gan, Suksompong, and Voudouris for the one-to-one setting. Furthermore, we consider a stronger variant of envy-freeness.     

About a new class of matroid-inducing packing families

Let T be a family of graphs. A T-packing of a graph G is a subgraph of G, components of which are isomorphic to members of T. We are concerned with families T, such that in every graph G, the subsets of vertices that can be saturated by some T-packing form a collection of independent sets of a matroid. The main purpose of this paper is to introduce a new class of families with this property.     

Facets of the independent path-matching polytope

Cunningham and Geelen introduced the independent path-matching problem as a common generalization of the weighted matching problem and the weighted matroid intersection problem. Associated with an independent path-matching is an independent path-matching vector. The independent path-matching polytope of an instance of the independent path-matching problem is the convex hull of all the independent path-matching vectors. Cunningham and Geelen described a system of linear inequalities defining the independent path-matching polytope. In this paper, we characterize which inequalities in this system induce facets of the independent path-matching polytope, generalizing previous results on the matching polytope and the common independent set polytope.