On the intersection of infinite matroids

We show that the infinite matroid intersection conjecture of Nash-Williams implies the infinite Menger theorem proved by Aharoni and Berger in 2009.We prove that this conjecture is true whenever one matroid is nearly finitary and the second is the dual of a nearly finitary matroid, where the nearly finitary matroids form a superclass of the finitary matroids.In particular, this proves the infinite matroid intersection conjecture for finite-cycle matroids of 2-connected, locally finite graphs with only a finite number of vertex-disjoint rays.     

A constrained independent set problem for matroids

In this note, we study a constrained independent set problem for matroids. The problem can be regarded as an ordered version of the matroid parity problem. By a reduction of this problem to matroid intersection, we prove a min-max formula. We show how earlier results of Hefner and Kleinschmidt on the so-called MS-matchings fit in our framework.     

Persistency in combinatorial optimization problems on matroids

Optimization problems on matroids are generalizations of such important combinatorial optimization problems like the problem of minimum spanning tree of a graph, the bipartite matching problem, flow problems, etc. We analyze algorithms for finding the maximum weight independent set of a matroid and for finding a maximum cardinality intersection of two matroids and extend them to obtain the so-called “persistency” partition of the basic set of the matroid, where contain elements belonging to all optimum solutions; contain elements not belonging to any optimum solution; contain elements that belong to some but not to all optimum solutions.     

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.     

On the regularity of orientable matroids

We present two characterizations of regular matroids among orientable matroids and use them to give a measure of “how far” an orientable matroid is from being regular.     

Removing circuits in 3-connected binary matroids

For a k-connected graph or matroid M, where k is a fixed positive integer, we say that a subset X of E(M) is k-removable provided M?X is k-connected. In this paper, we obtain a sharp condition on the size of a 3-connected binary matroid to have a 3-removable circuit.     

On partitioning two matroids into common independent subsets

Let M₁ and M₂ be two matroids on the same ground set S. We conjecture that if there do not exist disjoint subsets A₁,A₂,…,A_k+1 of S, such that _isp_M1(A_i)≠Ø, and similarly for M₂, then S is partitioned into k sets, each independent in both M₁ and M₂. This is a possible generalization of König's edge-coloring theorem. We prove the conjecture for the case k=2 and for a regular case, in which both matroids have the same rank d, and S consists of k·d elements. Finally, we prove another special case related to a conjecture of Rota.     

Ore-type and Dirac-type theorems for matroids

Let M be a connected binary matroid having no -minor. Let be a collection of cocircuits of M. We prove there is a circuit intersecting all cocircuits of if either one of two things hold:

(i) For any two disjoint cocircuits and in it holds that .

(ii) For any two disjoint cocircuits and in it holds that .

Part (ii) implies Ore's Theorem, a well-known theorem giving sufficient conditions for the existence of a hamilton cycle in a graph. As an application of part (i), it is shown that if M is a k-connected regular matroid and has cocircumference c^*2k, then there is a circuit which intersects each cocircuit of size c^*−k+2 or greater.We also extend a theorem of Dirac for graphs by showing that for any k-connected binary matroid M having no -minor, it holds that for any k cocircuits of M there is a circuit which intersects them.     

On the reliability roots of simplicial complexes and matroids

Assume that the vertices of a graph $G$ are always operational, but the edges of $G$ fail independently with probability $q\in [0,1]$. The all-terminal reliability of $G$ is the probability that the resulting subgraph is connected. The all-terminal reliability can be formulated into a polynomial in $q$, and it was conjectured that all the roots of (nonzero) reliability polynomials fall inside the closed unit disk. It has since been shown that there exist some connected graphs which have their reliability roots outside the closed unit disk, but these examples seem to be few and far between, and the roots are only barely outside the disk. In this paper we generalize the notion of reliability to simplicial complexes and matroids and investigate when the roots fall inside the closed unit disk. We show that such is the case for matroids of rank 3 and paving matroids of rank 4. We also prove that the reliability roots of shellable complexes are dense in the complex plane, and that the real reliability roots of any matroid lie in $[?1,0)\cup \left\{1\right\}$. Finally, we also show that the reliability roots of thickenings of the Fano matroid can lie outside the unit disk.     

Axioms for infinite matroids

We give axiomatic foundations for infinite matroids with duality, in terms of independent sets, bases, circuits, closure and rank. Continuing work of Higgs and Oxley, this completes the solution to a problem of Rado of 1966.     

Some heterochromatic theorems for matroids

The anti-Ramsey number of Erdös, Simonovits and Sós from 1973 has become a classic invariant in Graph Theory. To extend this invariant to Matroid Theory, we use the heterochromatic number $hc\left(H\right)$ of a non-empty hypergraph $H$. The heterochromatic number of $H$ is the smallest integer $k$ such that for every colouring of the vertices of $H$ with exactly $k$ colours, there is a totally multicoloured hyperedge of $H$.Given a matroid $M$, there are several hypergraphs over the ground set of $M$ we can consider, for example, $C\left(M\right)$, whose hyperedges are the circuits of $M$, or $B\left(M\right)$, whose hyperedges are the bases of $M$. We determine $hc\left(C\left(M\right)\right)$ for general matroids and characterise the matroids with the property that $hc\left(B\left(M\right)\right)$ equals the rank of the matroid. We also consider the case when the hyperedges are the Hamiltonian circuits of the matroid. Finally, we extend the known result about the anti-Ramsey number of 3-cycles in complete graphs to the heterochromatic number of 3-circuits in projective geometries over finite fields, and we propose a problem very similar to the famous problem on the anti-Ramsey number of the $p$-cycles.     

On combinatorial optimization problems on matroids with uncertain weights

In this paper the combinatorial optimization problem on weighted matroid is considered. It is assumed that the weights in the problem are ill-known and they are modeled as fuzzy intervals. The optimality of solutions and the optimality of elements are characterized. This characterization is performed in the setting of possibility theory. A method of choosing a solution under uncertainty is also proposed.     

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.     

Unipancyclic matroids

Analogous to the concept of uniquely pancyclic graphs, we define a uniquely pancyclic (UPC) matroid of rank $r$ to be a (simple) rank-$r$ matroid containing exactly one circuit of each length $?$ for $3\le ?\le r+1$. Our discussion addresses the existence of graphic, binary, and transversal representations of UPC matroids. Using Shi’s results, which catalogued exactly seven non-isomorphic UPC graphs, we produce a nongraphic binary UPC matroid of rank 24. We consider properties of binary UPC matroids in general, and prove that all binary UPC matroids have a connectivity of $2$.     

The 3-connected matroids with circumference 6

We construct all 3-connected matroids with circumference equal to 6 having rank at least 8. A matroid belongs to this family if and only if it is a generalized parallel connection of a set of planes along a common line (which may have some virtual points).     

Topological representations of matroids

There is a one-to-one correspondence between geometric lattices and the intersection lattices of arrangements of homotopy spheres. When the arrangements are essential and fully partitioned, Zaslavsky's enumeration of the cells of the arrangement still holds. Bounded subcomplexes of an arrangement of homotopy spheres correspond to minimal cellular resolutions of the dual matroid Steiner ideal. As a result, the Betti numbers of the ideal are computed and seen to be equivalent to Stanley's formula in the special case of face ideals of independence complexes of matroids.

     

Thin sums matroids and duality

Building on the recent axiomatisation of infinite matroids with duality, we present a theory of representability for infinite matroids. This notion of representability allows for infinite sums, and is preserved under duality.