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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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).

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Wow, not the answer I expected! $\endgroup$
    – Sam Hopkins
    Commented 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$
    – Luis Ferroni
    Commented 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$
    – John Machacek
    Commented 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$
    – John Machacek
    Commented 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.)

Improve this answer
$\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$
    – Sam Hopkins
    Commented 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$
    – Luis Ferroni
    Commented 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$
    – Sam Hopkins
    Commented Dec 12, 2019 at 17:58
  • $\begingroup$ Yes, exactly. I will add these remarks to the questions. $\endgroup$
    – Luis Ferroni
    Commented Dec 12, 2019 at 18:07

You must log in to answer this question.

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