1
$\begingroup$

Consider the following definition of matroid.

A matroid over a set $X$ is a family $\mathcal B\subseteq\mathcal P(X)$ of subsets of $X$ (the set of bases) with the following properties:

  1. $\mathcal B$ is non-empty.
  2. (base exchange property) For any two $A,B\in \mathcal B$ and $a\in A\setminus B$, there is a $b\in B\setminus A$, so that $$A\setminus\{a\}\cup\{b\}\in \mathcal B\qquad\text{and}\qquad B\setminus\{b\}\cup\{a\}\in \mathcal B $$

I am interested in a generalization, lets call it $k$-matroids, in which I replace the second axiom by the following:

  1. For any two $A,B\in \mathcal B$ and distinct $a_1,...,a_k\in A\setminus B$, there is are distinct $b_1,...,b_k\in B\setminus A$, so that $$A\setminus\{a_1,...,a_k\}\cup\{b_1,...,b_k\}\in \mathcal B\qquad\text{and}\qquad B\setminus\{b_1,...,b_k\}\cup\{a_1,...,a_k\}\in \mathcal B $$

Is this generalization known and if so, where to read about it. If not, are there some obvious connections to classical matroids (which are 1-matroids).

$\endgroup$
3
  • $\begingroup$ Isn't your original definition of matroid the definition of a $\delta$-matroid, which is already a generalization of matroids? $\endgroup$
    – quarague
    Aug 8, 2019 at 6:43
  • $\begingroup$ @quarague I was under the impression that this was one of the equivalent definitions of matroids (from Wikipedia). What exactly is a $\delta$-matroid? Is it because the exchange property is symmetric, that is it makes a statement about $A\setminus\{a\}\cup\{b\}$ and $B\setminus \{b\}\cup\{a\}$ instead of just one? I learned that this is equivalent to just one direction. But actually, I do not need the symmetry. If this is the problem I would rather edit the question. $\endgroup$
    – M. Winter
    Aug 8, 2019 at 7:01
  • $\begingroup$ You are correct, you defined a matroid. Your definition is the one that is generalized when defining $\delta$-matroids, that's why I got confused. In a $\delta$-matroid one uses symmetric difference and not all bases need to have the same cardinality. See en.wikipedia.org/wiki/Delta-matroid $\endgroup$
    – quarague
    Aug 8, 2019 at 7:12

1 Answer 1

0
$\begingroup$

Your second condition still defines a matroid, no? By a repeated application of the standard basis exchange you can obtain your "stronger" k exchange property on all matroids I think:

Apply basis exchange to get another base B' = B1 - a_1 + b_1 for some b_1. Then apply basis exchange on B' and B2 to replace a2 with something from B2 again, etc.

$\endgroup$
2
  • 1
    $\begingroup$ Note that $k$ is a fixed number, so for example, in a 2-matroid the usual base exchange property does not necessarily hold. But yes, every $k$-matroid is also a $dk$-matroid for every $d\ge 1$. $\endgroup$
    – M. Winter
    Aug 20, 2021 at 9:20
  • $\begingroup$ Oh ok I see now thanks $\endgroup$ Aug 25, 2021 at 4:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .