Some heterochromatic theorems for matroids

Abstract

The anti-Ramsey number of Erdös, Simonovits and Sós from 1973 has become a classic invariant in Graph Theory. To study this invariant in Matroid Theory, we use a related invariant introduce by Arocha, Bracho and Neumann-Lara. The heterochromatic number $hc(H)$ of a non-empty hypergraph $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 rank-$r$ matroid $M$, there are several hypergraphs associated to the matroid that we can consider. One is $C(M)$, the hypergraph where the points are the elements of the matroid and the hyperedges are the circuits of $M$. The other one is $B(M)$, where here the points are the elements and the hyperedges are the bases of the matroid. We prove that $hc(C(M))$ equals $r+1$ when $M$ is not the free matroid $U_{n,n}$, and that if $M$ is a paving matroid, then $hc(B(M))$ equals $r$. Then we explore the case when the hypergraph has the Hamiltonian circuits of the matroid as hyperedges, if any, for a class of paving matroids. We also extend the trivial observation of Erdös, Simonovits and Sós for the anti-Ramsey number for 3-cycles to 3-circuits in projective geometries over finite fields.

Version 1.2, 15 pages, no figures