1

I'm struggling with the definition of a graphical matroid.

Let $ G = (V, E)$ be an undirected graph. Matroid $M = ( E,I ),$ where $I= \{ F ⊆ E : F$ is acyclic $\}$ ; ie, forests in G. So if $M$ follows this rule than we can state that $M$ is a graphical matroid.

Example:

$M = (E, I) = (\{1,2,3\}, \{\{\emptyset, \{1\}, \{2\}, \{3\}, \{2, 3\}, \{1, 2\}\}$

Bases = $\{\{2,3\}, \{1,2\}\}$ and Circuits = $\{\{1,3\}\}$ also $\{1,2,3\}$ but it's not minimal.

Should I interpret the $I$ as labeled edges between vertices ? edges $ \{1\}, \{2\}, \{3\}$ alone don't make much sense to me.

(wrong) attempt to draw

enter image description here

Oleg
  • 499
  • The given $M$ is not a matroid because, for example, it doesn't satisfy the basis exchange axiom. Also, your picture is hard to interpret. You say ${1,3}$ should be a circuit. But a two element circuit in a graph is a pair of parallel edges and $1$ and $3$ sure don't look parallel. Is the picture of $K_3$ (i.e., a triangle)? or of a path of length three? In the former case the bases are all two element subsets. In the latter, there is a single basis corresponding to the graph itself. – Aaron Dall Mar 24 '18 at 11:33
  • 1
    @AaronDall the definition of Indepentent Sets from wiki : https://en.wikipedia.org/wiki/Matroid there are 3 properties ($I$ set is no empty, hereditary and augmentation property) and my example satisfies them. Isn't that enough for my $M$ to be called a matroid ? The picture is wrong on many levels because I don't know how to draw my $I$ set. – Oleg Mar 24 '18 at 12:01
  • You're right of course and @Andreas Blass's answer below clears the situation up for everybody. Also, this serves as a reminder to me that commenting around here after a long night out doesn't do anyone any good. Sorry for the confusion. Good luck! – Aaron Dall Mar 24 '18 at 23:26

1 Answers1

2

The matroid $M$ in the question is graphical, because it arises from the following graph: There are three vertices, which I'll call $a$, $b$, and $c$. There are three edges. Two of them, which I'll call $1$ and $3$, join vertex $a$ to $b$. (So they are what are often called "parallel" edges.) The remaining edge, which I'll call $2$, joins $a$ to $c$. For this graph, the associated graphical matroid has, as its underlying set $E$, the set $\{1,2,3\}$ of edges. Any single edge constitutes an independent (i.e., acyclic) set, because none of the edges are loops (joining a vertex to itself). Of course, the empty set is also independent. The set $\{1,2\}$ is also independent, as the edges $1$ and $2$ make a path $b-a-c$ and that's acyclic. The same goes for $\{2,3\}$. But $\{1,3\}$ and $\{1,2,3\}$ are dependent, because $\{1,3\}$ is a cycle. So the independent sets in this graph are exactly what you listed as $I$.

Andreas Blass
  • 71,833
  • One more question though, how should my edge set be such that when I will try to draw it, I'll see a self loop ? – Oleg Mar 24 '18 at 15:39
  • 1
    A self-loop in the graph is a one-element dependent set in the associated matroid. So the simplest example would be a graph with one vertex and one edge, where the edge, which I'll call $1$, joins the one vertex to itself. In this case, the matroid would have $E={1}$ and $I={\emptyset}$. – Andreas Blass Mar 24 '18 at 15:47
  • Why can't I just choose my $E ={1,2}$ as opposed to $E={1,2,3}$ ? – Oleg Mar 24 '18 at 16:21
  • 1
    If you delete edge $3$ from the graph in my answer, you have a new graph and therefore a new matroid. The new matroid would have as its underlying set just $E={1,2}$, and all four subsets of this would be independent. – Andreas Blass Mar 24 '18 at 16:30