The Las Vergnas polynomial for embedded graphs

The Las Vergnas polynomial is an extension of the Tutte polynomial to cellularly embedded graphs. It was introduced by Michel Las Vergnas in 1978 as special case of his Tutte polynomial of a morphism of matroids. While the general Tutte polynomial of a morphism of matroids has a complete set of deletion–contraction relations, its specialisation to cellularly embedded graphs does not. Here we extend the Las Vergnas polynomial to graphs in pseudo-surfaces. We show that in this setting we can define deletion and contraction for embedded graphs consistently with the deletion and contraction of the underlying matroid perspective, thus yielding a version of the Las Vergnas polynomial with complete recursive definition. This also enables us to obtain a deeper understanding of the relationships among the Las Vergnas polynomial, the Bollobás–Riordan polynomial, and the Krushkal polynomial. We also take this opportunity to extend some of Las Vergnas’ results on Eulerian circuits from graphs in surfaces of low genus to graphs in surfaces of arbitrary genus.     

Latroids and their representation by codes over modules

It has been known for some time that there is a connection between linear codes over fields and matroids represented over fields. In fact a generator matrix for a linear code over a field is also a representation of a matroid over that field. There are intimately related operations of deletion, contraction, minors and duality on both the code and the matroid. The weight enumerator of the code is an evaluation of the Tutte polynomial of the matroid, and a standard identity relating the Tutte polynomials of dual matroids gives rise to a MacWilliams identity relating the weight enumerators of dual codes. More recently, codes over rings and modules have been considered, and MacWilliams type identities have been found in certain cases.

In this paper we consider codes over rings and modules with code duality based on a Morita duality of categories of modules. To these we associate latroids, defined here. We generalize notions of deletion, contraction, minors and duality, on both codes and latroids, and examine all natural relations among these.

We define generating functions associated with codes and latroids, and prove identities relating them, generalizing above-mentioned generating functions and identities.

     

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].     

Splitting Formulas for Tutte Polynomials

We present two splitting formulas for calculating the Tutte polynomial of a matroid. The first one is for a generalized parallel connection across a 3-point line of two matroids and the second one is applicable to a 3-sum of two matroids. An important tool used is the bipointed Tutte polynomial of a matroid, an extension of the pointed Tutte polynomial introduced by Brylawski.     

Orientability of matroids

In this paper we define oriented matroids and develop their fundamental properties, which lead to generalizations of known results concerning directed graphs, convex polytopes, and linear programming. Duals and minors of oriented matroids are defined. It is shown that every coordinatization (representation) of a matroid over an ordered field induces an orientation of the matroid. Examples of matroids that are orientable but not coordinatizable and of matroids that are not orientable are presented. We show that a binary matroid is orientable if and only if it is unimodular (regular), and that every unimodular matroid has an orientation that is induced by a coordinatization and is unique in a certain straightforward sense.     

Separating cocircuits in binary matroids

A cocircuit of a matroid is separating if deleting it leaves a separable matroid. We give an effecient algorithm which finds a separating cocircuit or a Fano minor in a binary matroid, thus proving constructively a theorem of Tutte. Using this algorithm and a new recursive characterization of bond matroids, we give a new method for testing binary matroids for graphicness. We also give an efficient algorithm for finding a special kind of separating cocircuit: one whose deletion leaves a matroid having a coloop.     

Minors of simplicial complexes

We extend the notion of a minor from matroids to simplicial complexes. We show that the class of matroids, as well as the class of independence complexes, is characterized by a single forbidden minor. Inspired by a recent result of Aharoni and Berger, we investigate possible ways to extend the matroid intersection theorem to simplicial complexes.     

Strongly inequivalent representations and Tutte polynomials of matroids

We develop constructive techniques to show that non-isomorphic 3-connected matroids that are representable over a fixed finite field and that have the same Tutte polynomial abound. In particular, for most prime powers q, we construct infinite families of sets of 3-connected matroids for which the matroids in a given set are non-isomorphic, are representable over GF(q), and have the same Tutte polynomial. Furthermore, the cardinalities of the sets of matroids in a given family grow exponentially as a function of rank, and there are many such families.In Memory of Gian-Carlo Rota     

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.     

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     

The Tutte group of projective planes

Dress and Wenzel have codified the notion of the Tutte group of a matroid and have determined the Tutte group of projective spaces over skew fields and of finite projective planes. In this note we shall examine the Tutte group of arbitrary projective planes.     

Coboundaries, Flows, and Tutte Polynomials of Matrices

Using matroid duality and the critical problem, we show that certain evaluations of the Tutte polynomial of a matroid represented as a matrix over a finite field GF(q) can be interpreted as weighted sums over pairs f , g of functions defined from the ground set to GF(q) whose difference f – g is the restriction of a linear functional on the column space of the matrix. Similar interpretations are given for the characteristic polynomial evaluated at q. These interpretations extend and elaborate interpretations for Tutte and chromatic polynomials of graphs due to Goodall and Matiyasevich. Received July 14, 2006     

Higher support matroids

The purpose of this paper is to provide links between matroid theory and the theory of subcode weights and supports in linear codes. We describe such weights and supports in terms of certain matroids arising from the vector matroids associated to the linear codes. Our results generalize classical results by Whitney, Tutte, Crapo and Rota, Greene, and other authors. As an application of our results, we obtain a new and elegant dual correspondence between the bond union and cycle union cardinalities of a graph.     

On critical exponents of Dowling matroids

The critical problem in matroid theory is the problem to determine the critical exponent of a given representable matroid over a finite field. In this paper, we study the critical exponents of a class of representable matroids over finite fields, called Dowling matroids. Then the critical problem for a Dowling matroid is corresponding to the classical problem in coding theory to determine the maximum dimension k such that there exists an \([n,k,d]_q\) code for given n, d and q. We give a necessary and sufficient condition on the critical exponents of Dowling matroids by using a coding theoretical approach.     

On Brylawski’s Generalized Duality

We introduce a notion of duality??due to Brylawski??that generalizes matroid duality to arbitrary rank functions. This allows us to define a generalization of the matroid Tutte polynomial. This polynomial satisfies a deletion-contraction recursion, where deletion and contraction are defined in this more general setting. We explore this notion of duality for greedoids, antimatroids and demi-matroids, proving that matroids correspond precisely to objects that are simultaneously greedoids and ??dual?? greedoids.     

Chords and disjoint paths in matroids

A chord of a circuit C of a matroid M on E is a cell e ? S\C such that C spans e. Menger's theorem gives necessary and sufficient conditions for a cell of a graphic matroid to be a chord of some circuit. We extend this result to a large class of matroids and find all minimal counterexamples. The theorem is used to obtain results on disjoint paths and to characterize a class of matroid sums.     

On the representations of projective geometries in algebraic combinatorial geometries

In this paper, we show that the full algebraic combinatorial geometry is not a projective geometry, it is only semimodular, but the p-polynomial points give a projective subgeometry. Also, we show that the subgeometry can be coordinatized by a skew field, which is quotient ring of an Ore domain. As a corollary, we prove the existence of algebraic representations over fields of prime characteristic of the non-Pappus matroid and its dual matroid. Regarding the existence of algebraic representations of the non-Pappus matroid, this result was earlier proved by Lindström [7] for finite fields.     

Matroid representation over GF(3)

We show that a matroid is representable over GF(3) if and only if no minor is the five-point line or the Fano matroid, or their duals. Tutte's famous characterization of the regular matroids is a corollary. A key lemma states that two representations of the same matroid in the same vector space over GF(3) may be transformed one into the other by inverting some points through the origin and taking a linear transformation; no result of this kind holds in larger fields.     

A Representation of a Family of Secret Sharing Matroids

Deciding whether a matroid is secret sharing or not is a well-known open problem. In Ng and Walker [6] it was shown that a matroid decomposes into uniform matroids under strong connectivity. The question then becomes as follows: when is a matroid m with N uniform components secret sharing? When N = 1, m corresponds to a uniform matroid and hence is secret sharing. In this paper we show, by constructing a representation using projective geometry, that all connected matroids with two uniform components are secret sharing     

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.