Let (E,A) be a set system consisting of a finite collection A of subsets of a ground set E, and suppose that we have a function Φ which maps A into some set S. Now removing a subset K from E gives a restriction A(K) to those sets of A disjoint from K, and we have a corresponding restriction φ(A,K) of our function Φ. If the removal of K does not affect the image set of Φ, that is φ(A,X)= Im(φ), then we will say that K is a kernel set of A with respect to Φ. Such sets are potentially useful in optimisation problems defined in terms of Φ. We will call the set of all subsets of E that are kernel sets with respect to Φ a kernel system and denote it by Ker φ(A). Motivated by the optimisation theme, we ask which kernel systems are matroids. For instance, if A is the collection of forests in a graph G with coloured edges and Φ counts how many edges of each colour occurs in a forest then Kerφ(A) is isomorphic to the disjoint sum of the cocycle matroids of the differently coloured subgraphs; on the other hand, if A is the power set of a set of positive integers, and Φ is the function which takes the values 1 and 0 on subsets according to whether they are sum-free or not, then we show that Kerφ(A) is essentially never a matroid.
展开▼
