3

I am looking for the definition of the "euclidian representation" of a matroid. I guess it is used for graphic matroids but impossible to find the construction for this representation. Thank you for your help.

Fundamentalistic
  • 312

2 Answers2

3

sorry for my english because I am French. I can answer your question in the case of a matroid of rank 3 (I don't know in different rank, but I think you are interested in this case). Indeed in the case of a graphic matroid M, a theorem claims that M is euclidean and so you are sure to have an euclidean representation. You construct it as follow :

  • let E be the edges of M with #E=k (and V its vertices)

  • you call e(1), ..., e(k) those edges

  • at each edge e(i) in your matroid M corresponds a vertex in your euclidean representation
  • then you link three points in the euclidean representation iff the three associated edges form a loop in M

Then, the rule to interpret and euclidean representation is that 3 vertices in the representation form a base in M iff they are not linked in the representation (remember that M is of rank 3)

Your description is complete because :

  • a set of 3 points is a loop iff it is linked in the representation
  • a set of 3 points is a base iff those 3 points are not in a same line
  • a set of more than 3 points is a loop iff if you delete points you don't obtain three points linked by a line (because it would says you that there is a loop in this set of points and then it is not minimal)

I hope I have answered your question (not easy without a drawing ...)

Anaïs
  • 66
  • Salut Anaïs, de Montpellier ?^^ – Fundamentalistic Jan 11 '15 at 13:57
  • Fundamentalistic de Montpellier alors toi aussi ? ^^ – Anaïs Jan 11 '15 at 14:07
  • Yes ! Tu tires ça du cours du bon Jorge ? Car j'ai dû pas bien noter à ce moment-là et je trouve ça nulle part ailleurs. Par contre, il donne des représentations euclidiennes de matroïdes qui ne sont pas graphiques... – Fundamentalistic Jan 11 '15 at 14:10
  • ton vrai prénom au passage ? que je t'ai pas reconnu ! j'étais absente moi ce jour là, mais on m'a ré-éexpliqué ! oui en effet tant que ton matroïde est linéaire c'est bon, tu peux, il n'est pas forcément graphique, la condition est plus forte dans ce cas – Anaïs Jan 11 '15 at 14:13
  • Jonathan, ok d'acc je vais avoir avec ce que tu m'as dit du coup, merci en tout cas ah ah – Fundamentalistic Jan 11 '15 at 14:14
  • 1
    je t'en prie ! assez drôle cette petite rencontre sur une plate-forme à l'autre bout du monde. Have a good luck comme on dit ! – Anaïs Jan 11 '15 at 14:15
0

Let $M$ be a matrix over a field $\mathbb{F}$. It is easy to show that the set $\mathcal{I}$ consisting of all linearly independent subsets of columns of $M$ form the independent sets of a matroid $\mathcal{M}$. This matroid is called the vector matroid of the matrix $M$ over $\mathbb{F}$.

An arbitrary matroid $\mathcal{M}$ is representable (a.k.a. realizable) over a field $\mathbb{F}$ if it is the vector matroid of some matrix with entries in $\mathbb{F}$. If $\mathbb{F} = \mathbb{E}$ is euclidean space and $\mathcal{M}$ is representable over $\mathbb{E}$, then any matrix $M$ whose vector matroid is $\mathcal{M}$ (there are many of them) is a euclidean representation of $\mathcal{M}$.

Aaron Dall
  • 1,182