Is the following a matroid?

193 Views Asked by At

If I have a bipartite graph $G = (L \cup R, E)$, then there is a matroid on ground set $L$ whose independent sets are the matchable subsets of $L$. That is, $A \subseteq L$ is independent if there is a matching incident on the vertices $A$. This is often a called transversal matroid.

I am consideing a meager extension of the above, but for $b$-matchings. What if I have an integer vector $b \in \mathbb{Z}^n$, and a bipartite graph as above. Again, my set system will have ground set $L$.

A subset $A \subseteq L$ is independent if there is a valid $b$-perfect matching incident on the vertices in $A$. Formally, let $A \subseteq L$ and $b'$ be the restriction of $b$ to $A \cup Neighbors(A)$. Then $A$ is independent if there is a $b'$-perfect matching on the induced subgarph on $A \cup Neighbors(A)$.

If $b = \mathbb{1}$, then the above set system yields standard transversal matroid, but I am wondering if this also yields a matroid. Could it even also be a transversal matroid on some augmented graph? If anyone has any insight or knows a reference, it would be appreciated. Thank you.

1

There are 1 best solutions below

1
On BEST ANSWER

Take $K_{3,3}$ with vertices $\{x_1,x_2,x_3\}$ on one side and $\{y_1, y_2, y_3\}$ on the other side; let $b = 1$ except $b(x_3) = 3$.

Then $\{x_1,x_2\}$ is an independent set and so is $\{x_3\}$. However, we cannot add either element of $\{x_1,x_2\}$ to $\{x_3\}$ to get a larger independent set. So this is not a matroid.