Is the following set system a matroid?

110 Views Asked by At

Suppose $\mathcal{M}=(E,\mathcal{I})$ is a matroid without any loop where $E$ is the ground set and $\mathcal{I}$ is the set of independent sets. Let $x,y$ be two distinct elements of $E$. Take set system $\mathcal{F}=(E\setminus \{x,y\}, \{S\subseteq E\setminus \{x,y\}\mid S\cup\{x\}, S\cup\{y\}\in \mathcal{I} \})$. Is $\mathcal{F}$ a matroid?

1

There are 1 best solutions below

1
On BEST ANSWER

The graphic matroid of the complete graph $K_{4}$ on four vertices provides a counterexample.

Consider the rank-$3$ matroid $M = ([6], \mathcal{B}) = M(K_{4})$ with $16$ bases

$$ \{134, 234, 135, 235, 136, 236, 156, 256, 124, 125, 126, 146, 245, 345, 346, 456\}.$$

Take $\{x,y\} = \{1,2\}$. Then the construction yields a set system with cardinality-maximal sets $\{34, 35, 36, 56\}$ which is not the set of bases of a matroid.

Edit: Using the Macaulay2 package Matroids one can verify that this example is minimal with respect to ground set size, rank, and number of bases (or circuits, or hyperplanes). Moreover while only three of the 98 (non-isomorphic) matroids on 6 elements have a pair of ground set elements for which the construction in the OP fails to yield a matroid, more than half of the 1724 matroids on 8 elements have such a pair.