On minor-minimally 3-connected binary matroids

A matroid M is called minor-minimally 3-connected if M is 3-connected and, for each e∈E(M), either M?e or M/e is not 3-connected. In this paper, we prove a chain theorem for the class of minor-minimally 3-connected binary matroids. As a consequence, we obtain a chain theorem for the class of minor-minimally 3-connected graphs.     

A note on nongraphic matroids

Tutte found an excluded minor characterization of graphic matroids with five excluded minors. A variation on Tutte's result is presented here. Let {e, f, g} be a circuit of a 3-connected nongraphic matroid M. Then M has a minor using e, f, g isomorphic to either the 4-point line, the Fano matroid, or the bond matroid of K_3,3.     

The max-flow min-cut property of two-dimensional affine convex geometries

In a matroid, (X,e) is a rooted circuit if X is a set not containing element e and X∪{e} is a circuit. We call X a broken circuit of e. A broken circuit clutter is the collection of broken circuits of a fixed element. Seymour [The matroids with the max-flow min-cut property, J. Combinatorial Theory B 23 (1977) 189-222] proved that a broken circuit clutter of a binary matroid has the max-flow min-cut property if and only if it does not contain a minor isomorphic to Q₆. We shall present an analogue of this result in affine convex geometries. Precisely, we shall show that a broken circuit clutter of an element e in a convex geometry arising from two-dimensional point configuration has the max-flow min-cut property if and only if the configuration has no subset forming a ‘Pentagon’ configuration with center e.Firstly we introduce the notion of closed set systems. This leads to a common generalization of rooted circuits both of matroids and convex geometries (antimatroids). We further study some properties of affine convex geometries and their broken circuit clutters.     

A quantifier for matroid duality

A quantifier is introduced on the elements of a matroid which, given an element e, says “for all elements (except possibly e) of some circuit containing e,…”. The matroid dual of this quantifier is shown to be identical with its logical dual, and this provides an elegant reformulation of Minty's self-dual axiomatization of matroids.This approach also provides a practical, and in a sense optimal, means of taking a statement in terms of circuits and constructing its dual, still in terms of circuits.     

Infinite subgraphs as matroid circuits

A matroidal family $\text{C}$ is defined to be a collection of graphs such that, for any given graph G, the subgraphs of G isomorphic to a graph in $\text{C}$ satisfy the matroid circuit-axioms. Here matroidal families closed under homeomorphism are considered. A theorem of Simöes-Pereira shows that when only finite connected graphs are allowed as members of $\text{C}$, two matroids arise: the cycle matroid and bicircular matroid. Here this theorem is generalized in two directions: the graphs are allowed to be infinite, and they are allowed to be disconnected. In the first case four structures result and in the second case two infinite families of matroids are obtained. The main theorem concerns the structures resulting when both restrictions are relaxed simultaneously.     

Almost-Graphic Matroids

A nongraphic matroid M is said to be almost-graphic if, for all elements e, either M\e or M/e is graphic. We determine completely the class of almost-graphic matroids, thereby answering a question posed by Oxley in his book “Matroid Theory.” A nonregular matroid is said to be almost-regular if, for all elements e, either M\e or M/e is regular. An element e for which both M\e and M/e are regular is called a regular element. We also determine the almost-regular matroids with at least one regular element.     

Independence and port oracles for matroids,with an application to computational learning theory

Given a matroidM with distinguished elemente, aport oracie with respect toe reports whether or not a given subset contains a circuit that containse. The first main result of this paper is an algorithm for computing ane-based ear decomposition (that is, an ear decomposition every circuit of which contains elemente) of a matroid using only a polynomial number of elementary operations and port oracle calls. In the case thatM is binary, the incidence vectors of the circuits in the ear decomposition form a matrix representation forM. Thus, this algorithm solves a problem in computational learning theory; it learns the class ofbinary matroid port (BMP) functions with membership queries in polynomial time. In this context, the algorithm generalizes results of Angluin, Hellerstein, and Karpinski [1], and Raghavan and Schach [17], who showed that certain subclasses of the BMP functions are learnable in polynomial time using membership queries. The second main result of this paper is an algorithm for testing independence of a given input set of the matroidM. This algorithm, which uses the ear decomposition algorithm as a subroutine, uses only a polynomial number of elementary operations and port oracle calls. The algorithm proves a constructive version of an early theorem of Lehman [13], which states that the port of a connected matroid uniquely determines the matroid.Research partially funded by NSF PYI Grant No. DDM-91-96083.Research partially funded by NSF Grant No CCR-92-10957.     

Elements belonging to triangles in 3-connected matroids

An element e of a 3-connected matroid M is said to be superfluous provided M/e is 3-connected. In this paper, we show that a 3-connected matroid M with exactly k superfluous elements has at least

     

The Euler circuit theorem for binary matroids

It is proved that, if M is a binary matroid, then every cocircuit of M has even cardinality if and only if M can be obtained by contracting some other binary matroid M⁺ onto a single circuit. This is the natural analog of the Euler circuit theorem for graphs. It is also proved that every coloop-free matroid can be obtained by contracting some other matroid (not in general binary) onto a single circuit.     

Connected matroids with a small circumference

Lemos and Oxley proved that if M is a connected matroid with |E(M)|⩾3r(M), then M has a circuit C such that M⧹C is connected. In this paper, we shall improve this result proving that for a simple and connected matroid M, if r(M)⩾7 and |E(M)|⩾3r(M)−3, then M has a circuit C such that M⧹C is connected. To prove this result, we shall construct all the connected matroids having circumference at most five, with the exception of those which are 3-connected and have rank five.     

Galois groups of multivariate Tutte polynomials

The multivariate Tutte polynomial $\hat{Z}_{M}$ of a matroid M is a generalization of the standard two-variable version, obtained by assigning a separate variable v _e to each element e of the ground set E. It encodes the full structure of M. Let v={v _e } _e??E , let K be an arbitrary field, and suppose M is connected. We show that $\hat{Z}_{M}$ is irreducible over K(v), and give three self-contained proofs that the Galois group of $\hat{Z}_{M}$ over K(v) is the symmetric group of degree n, where n is the rank of M. An immediate consequence of this result is that the Galois group of the multivariate Tutte polynomial of any matroid is a direct product of symmetric groups. Finally, we conjecture a similar result for the standard Tutte polynomial of a connected matroid.     

Properties of Hamilton cycles of circuit graphs of matroids

Let G be a circuit graph of a connected matroid. P. Li and G. Liu [Comput. Math. Appl., 2008, 55: 654–659] proved that G has a Hamilton cycle including e and another Hamilton cycle excluding e for any edge e of G if G has at least four vertices. This paper proves that G has a Hamilton cycle including e and excluding e′ for any two edges e and e′ of G if G has at least five vertices. This result is best possible in some sense. An open problem is proposed in the end of this paper.     

The Connectivity and Diameter of Second Order Circuit Graphs of Matroids

Let C ₂(M) be the second order circuit graph of a simple connected matroid M, then C ₂(M) is 2-connected if M has more than one circuit and M is not a line. Moreover, C ₂(M) has diameter at most two if and only if M does not have any restriction isomorphic to U _2,6.     

On minor-minimally-connected matroids

By a well-known result of Tutte, if e is an element of a connected matroid M, then either the deletion or the contraction of e from M is connected. If, for every element of M, exactly one of these minors is connected, then we call M minor-minimally-connected. This paper characterizes such matroids and shows that they must contain a number of two-element circuits or cocircuits. In addition, a new bound is proved on the number of 2-cocircuits in a minimally connected matroid.     

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.     

A matroid generalization of a result of Dirac

This paper generalizes a theorem of Dirac for graphs by proving that ifM is a 3-connected matroid, then, for all pairs {a,b} of distinct elements ofM and all cocircuitsC ^* ofM, there is a circuit that contains {a,b} and meetsC ^*. It is also shown that, although the converse of this result fails, the specified condition can be used to characterize 3-connected matroids.The author's research was partially supported by a grant from the National Security Agency.     

Matroids,generalized networks,and electric network synthesis

Matroid theory has been applied to solve problems in generalized assignment, operations research, control theory, network theory, flow theory, generalized flow theory or linear programming, coding theory, and telecommunication network design. The operations of matroid union, matroid partitioning, matroid intersection, and the theorem on the greedy algorithm, Rado's theorem, and Brualdi's symmetric version of Rado's theorem have been important for some of these applications. In this paper we consider the application of matroids to solve problems in network synthesis. Previously Bruno and Weinberg defined a generalized network, which is a network based on a matroid rather than a graph; for a generalized network the duality principle holds whereas it does not hold for a network based on a graph. We use the concept of the generalized network to formulate a solution to the following problem: What are the necessary and sufficient conditions for a singular matrix of real numbers, of order p and rank s, to be realizable as the open-circuit resistance matrix of a resistance p-port network. A simple algorithm is given for carriyng out the synthesis. We then present a number of unsolved problems, included among which is what could be called the four-color problem of network synthesis, namely, the resistance n-port problem.     

Oriented matroids and Ky Fan’s theorem

L. Lovász (Matroids and Sperner’s Lemma, Europ. J. Comb. 1 (1980), 65–66) has shown that Sperner’s combinatorial lemma admits a generalization involving a matroid defined on the set of vertices of the associated triangulation. We prove that Ky Fan’s theorem admits an oriented matroid generalization of similar nature. Classical Ky Fan’s theorem is obtained as a corollary if the underlying oriented matroid is chosen to be the alternating matroid C ^m,r .     

Primitive elements in the matroid-minor Hopf algebra

We introduce the matroid-minor coalgebra C, which has labeled matroids as distinguished basis and coproduct given by splitting a matroid into a submatroid and complementary contraction in all possible ways. We introduce two new bases for C; the first of these is related to the distinguished basis by Möbius inversion over the rank-preserving weak order on matroids, the second by Möbius inversion over the suborder excluding matroids that are irreducible with respect to the free product operation. We show that the subset of each of these bases corresponding to the set of irreducible matroids is a basis for the subspace of primitive elements of C. Projecting C onto the matroid-minor Hopf algebra H, we obtain bases for the subspace of primitive elements of H.