0

Let $S = \{s_1,s_2,\ldots,s_n\} $ denote a ground set of $n$ elements.

Define:

  • a k-uniform matroid: $\mathcal{M} = (S, \mathcal{I}),$ where $\mathcal{I} = \{I: I \subseteq S, |I| \leq k \}$ for some positive integer $k$.

  • a partition matroid: $\mathcal{P} = (S, \mathcal{J})$, where $\mathcal{J} = \{I: I \subseteq S, |I \cap B_i| \leq d_i \}$ and the $B_i$ are disjoint subsets that form a partition of $S$

I am wondering if the intersection of these two matroids, defined as: $$\mathcal{M} \cap \mathcal{P} :=(S,\mathcal{I}\cap\mathcal{J})$$ is also considered a matroid?

Asaf Karagila
  • 393,674
Elements
  • 2,638

1 Answers1

4

The answer to your question is YES.

If you consider the properties defining a matroid, the only one which must be checked is the augmentation property (the empty set and hereditary property always hold for an intersection) and this is quite simply done.

Let $A, B \in \mathcal{I}\cap\mathcal{J}$ with $|A|>|B|$. As $\mathcal{P}$ is a matroid, $\exists x \in A\setminus B$, $B\cup\{x\}\in\mathcal{J}$. But $k\geq |A| > |B|$, hence $k\geq B\cup\{x\}$. Therefore, $ B\cup\{x\}\in\mathcal{I}$. And you're done.

We have even shown that, more generally, the intersection of a $k$-uniform matroid with any matroid defined on the same ground set is a matroid.

Thomas Delacroix
  • 332