15
$\begingroup$

Let $M$ be a matroid with set of basis $\mathcal{B}$. The basis graph of $M$ is a graph with set of vertices $\mathcal{B}$ and edges $(B,B')$ always that $B$ and $B'$ differ (as sets) by exactly one element.

It is easy to see that this graph can be thought as the $1$-skeleton of the basis polytope of $M$.

My question is if it is indeed true that the isomorphism class of $M$ is determined by its basis graph. To avoid trivialities, we ask $M$ to be loopless and bridgeless (it is $M^*$ is also loopless), because otherwise there are simple counterexamples.

My intuition says the answer is no, but I couldn't find a counterexample so far.

EDIT: As pointed out in the answers and comments, since duality preserves the basis graph, it is reasonable to ask if there is a pair of indecomposable non isomorphic non dual matroids (loopless and bridgeless) such that they induce isomorphic basis graphs.

$\endgroup$

2 Answers 2

12
$\begingroup$

I think this question is answered in the paper A Graphical Representation of Matroids by C. A. Holzmann, P. G. Norton, and M. D. Tobey. From the abstract:

"A base graph of a matroid is the graph whose points are the bases of the matroid. Two bases are adjacent if they differ by exactly one element. A definition of equivalence of matroids is given and it is shown that two matroids are equivalent if and only if their base graphs are isomorphic. In particular, if M and $M_1 $ are nonseparable matroids with isomorphic base graphs, then M is isomorphic to either $M_1 $ or its dual..."

The notion of equivalence is $M = \sum_i M_i$ and $M' = \sum_i M'_i$ are equivalent if and only if $M'_i$ is isomorphic to $M_i$ or its dual for each $i$ (and some reordering if needed).

$\endgroup$
4
  • 2
    $\begingroup$ Wow, not the answer I expected! $\endgroup$ Dec 12, 2019 at 23:59
  • $\begingroup$ I will give a careful look at this paper, because I think it has some strong implications on some invariants of matroids. Thank you very much. $\endgroup$ Dec 13, 2019 at 0:10
  • $\begingroup$ @SamHopkins yes I vaguely remember hearing nice things about these graphs at some point in the past. When I looked it up I was a bit surprised it gives you almost everything since it's only the 1-skeleton of the polytope. $\endgroup$ Dec 14, 2019 at 2:31
  • $\begingroup$ @LuisFerroni you can also see the papers "Matroid basis graphs. I" and "Matroid basis graphs. II" both published in JCTB (free online now since they are older papers). Maybe you are already aware of these. They give lots of info about the graph, like what a neighborhood can look like, etc. $\endgroup$ Dec 14, 2019 at 2:33
9
$\begingroup$

Let $M$ be the matroid corresponding to the cycle graph $C_3$ with edges $\{a,b,c\}$, so that the bases of $M$ are $\{a,b\}$, $\{a,b\}$, $\{b,c\}$; let $M'$ be the matroid corresponding to the multigraph with two vertices and three edges $\{a,b,c\}$ between them, so that the bases of $M'$ are $\{a\}$, $\{b\}$, $\{c\}$. Then $M$ and $M'$ are not isomorphic (they don't even have the same rank), but they both have $C_3$ as their basis graph. (Note that $M$ and $M'$ are however dual.)

$\endgroup$
4
  • $\begingroup$ Maybe you want to fix the rank (and size of ground set $E$?); even then I doubt the basis graph determines the matroid. $\endgroup$ Dec 12, 2019 at 17:36
  • $\begingroup$ Yes, this example works for the question as originally stated, and indeed it is true that essentially duality preserves the basis graph. However, what I'm now wondering is if "duality" is the only obstacle here. As you point out, it seems plausible that there is a pair of non dual loopless and bridgeless matroids with the same basis graph, and actually that is what I've been looking for until now, without any example. $\endgroup$ Dec 12, 2019 at 17:44
  • 1
    $\begingroup$ You probably also want to assume $M$ is indecomposable then, otherwise you can set $M= M_1 \oplus M_2$ and $M' = M_1^{*} \oplus M_2$. $\endgroup$ Dec 12, 2019 at 17:58
  • $\begingroup$ Yes, exactly. I will add these remarks to the questions. $\endgroup$ Dec 12, 2019 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.