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.     

On the Circuit-cocircuit Intersection Conjecture

Oxley has conjectured that for k≥4, if a matroid M has a k-element set that is the intersection of a circuit and a cocircuit, then M has a (k−2)-element set that is the intersection of a circuit and a cocircuit. In this paper we prove a stronger version of this conjecture for regular matroids. We also show that the stronger result does not hold for binary matroids. The second author was partially supported by CNPq (grant no 302195/02-5) and the ProNEx/CNPq (grant no 664107/97-4).     

On the unique representability of spikes over prime fields

For an integer n?3, a rank-n matroid is called an n-spike if it consists of n three-point lines through a common point such that, for all k in {1,2,…,n-1}, the union of every set of k of these lines has rank k+1. Spikes are very special and important in matroid theory. Wu [On the number of spikes over finite fields, Discrete Math. 265 (2003) 261-296] found the exact numbers of n-spikes over fields with 2, 3, 4, 5, 7 elements, and the asymptotic values for larger finite fields. In this paper, we prove that, for each prime number p, a GF(p) representable n-spike is only representable on fields with characteristic p provided that n?2p-1. Moreover, M is uniquely representable over GF(p).     

A unique factorization theorem for matroids

We study the combinatorial, algebraic and geometric properties of the free product operation on matroids. After giving cryptomorphic definitions of free product in terms of independent sets, bases, circuits, closure, flats and rank function, we show that free product, which is a noncommutative operation, is associative and respects matroid duality. The free product of matroids M and N is maximal with respect to the weak order among matroids having M as a submatroid, with complementary contraction equal to N. Any minor of the free product of M and N is a free product of a repeated truncation of the corresponding minor of M with a repeated Higgs lift of the corresponding minor of N. We characterize, in terms of their cyclic flats, matroids that are irreducible with respect to free product, and prove that the factorization of a matroid into a free product of irreducibles is unique up to isomorphism. We use these results to determine, for K a field of characteristic zero, the structure of the minor coalgebra of a family of matroids that is closed under formation of minors and free products: namely, is cofree, cogenerated by the set of irreducible matroids belonging to .     

The entropic discriminant

The entropic discriminant is a non-negative polynomial associated to a matrix. It arises in contexts ranging from statistics and linear programming to singularity theory and algebraic geometry. It describes the complex branch locus of the polar map of a real hyperplane arrangement, and it vanishes when the equations defining the analytic center of a linear program have a complex double root. We study the geometry of the entropic discriminant, and we express its degree in terms of the characteristic polynomial of the underlying matroid. Singularities of reciprocal linear spaces play a key role. In the corank-one case, the entropic discriminant admits a sum of squares representation derived from the discriminant of a characteristic polynomial of a symmetric matrix.     

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.