About matroids

For a soon to come paper about the injective norm of tensors, I learnt and use as technical devices, some elements of matroid theory. Learning about matroids also inspired me to try exploring, in an unrelated way, a presumably new question about matroids. This will hopefully lead to some interesting concepts later. Still I am not a matroid expert, and don’t intend to really become one. So I will give a try at presenting matroids elements to non-experts as a way to keep the building blocks in mind.

So first, in words what are matroids? In my understanding, it’s a very small theory, in the sense that the definition of matroids is based on very little. In fact it’s fully (finite) set theoretic. One of the goal is to abstract and combinatorialize the familiar concept of linear independence of linear algebra while generalizing concepts of graph theory. This is where lies part of their usefulness. Many problems in graph theory can be re-expressed in terms of matroids so that work that has been done for graph theory can be pushed forward to more general context with (hopefully) minimal effort. And of course, that’s the point of generalization, demonstrating new statements for matroids also proves them for all objects that matroids encompass.

A matroid is based on a finite set $X$ . This can be thought as a set of vectors of a vector space (but it is of course not in general). Then one defines the independents of this finite set by declaring that a family of subsets of $X$ are idependents. Of course, one cannot define independent in fully arbitrary ways, as one wants to recover the familiar properties of linear indepedence when $X$ is indeed a set of vectors of a vector space.

Definition (Matroid)

A matroid based on $X$ is the data $I\subseteq 2^X$ of a set of subsets of $X$ satisfying

$\emptyset \in I$
for all $a\in I, b\subseteq a\Rightarrow b\in I$
$a,b\in I, \lvert a\rvert<\lvert b \rvert \Rightarrow \exists x \in b\backslash a$ such that $a\cup\{x\}\in I.$

Coming back to our set of vectors heuristic, the second property is saying that any subset of a family of linearly independent vectors should also form a linearly independent family. The third one says one can augment a linearly independent family of vectors provided the family does not form a basis (i.e. is a largest family of linearly independent vectors).

The link to graph theory is easily recovered as every graph provides a matroid structure:

Let $G$ be a graph. The set of subforests $F$ of $G$ is a set of independents $I$ for the matroid based on the edges of $G$ . In fact, the forest without edges is in $I$ . If $f_1$ is a subforest and $f_2$ is a subgraph of $f_1$ , $f_2$ is a subforest of $G$ . Finally, given two subforests $f_1,f_2$ , $f_1$ being smaller than $f_2$ there exists an edge of $f_2$ that is not in $f_1$ but that can be added to $f_1$ without closing a cycle. In fact, $f_1$ must have more connected components than $f_2$ . Therefore, there must be at least two connected components of $f_1$ included in one connected component of $f_2$ . So there exist an edge in $f_2$ connecting these two components. This edge cannot form a cycle, therefore we’ve shown the last property.

We can give a small example of matroid. For instance consider $X=\{1,2,3,4\}$ and $I=\{\emptyset,\{1\},\{2\},\{3\},\{4\}\}$ form a matroid. A non example is $X=\{1,2,3,4\}, I=\{\emptyset,\{1\},\{2\},\{3\},\{4\},\{1,2\}\}$ as the third property is violated.

One also imports the concept of basis from linear algebra. A basis is a maximal independent set. In fact, one can define matroids from their bases set $B$ .

$B$ is a non empty set of subset of $X$
If $M\neq N\in B$ , and $m\in M\backslash N$ , then there exists $n\in N\backslash M$ such that $\{n\}\cup(M\backslash N)\in B$ .

The concept of basis allows us to introduce, in analogy to the vector space case, the dual of a matroid. The dual of a matroid $(X,I)$ is the matroid $(X,I^*)$ whose independents are all subsets of $I\subset X$ whose complement $\bar I$ contain a basis of $(X,I)$ .

In the previous small example, $I=\{\emptyset,\{1\},\{2\},\{3\},\{4\}\}$ and $B=\{\{1\},\{2\},\{3\},\{4\}\}$ . In the graph case described above, the bases are the spanning trees.

Finally a last piece of vocabulary. The circuits of a matroid are the minimally dependent sets, that is subsets of $X$ whose proper subsets are all independents.

We summarize those terms in the following animation, illustrating them on the edge matroid of a graph.

Rank and an important theorem

We can also define matroids through a rank function. A rank function is a function $r:2^X\rightarrow \mathbb{N}$ such that

The value of $r$ on a subset $S$ of X is bounded by the cardinal of $S$ .
The submodular property: let $S,T\in 2^X$ then $r(S\cup T)+r(S\cap T)\le r(S)+r(T)$ .
The rank is monotonous, that is $\forall S\subseteq X, x\in X$ , one has $r(A)\le r(A\cup\{x\})\le r(A)+1$ .

Matroids can be defined solely through their rank function by declaring that the independent sets are the set whose rank is their cardinal.

There is an important theorem in matroid theory, which I learnt about for my paper. This theorem is called Edmond Intersection theorem.

Theorem (Edmond’s Intersection Theorem): Let $(X,I_1),(X,I_2)$ be two matroids with the same base set and their own rank functions, $\text{rk}_1, \text{rk}_2$ , then

$\max_{S\in I_1\cap I_2} \lvert I\rvert =\min_{A\subseteq X} \text{rk}_1(A)+\text{rk}_2(\overline{A})$ .

More to come when the paper is out.

About matroids

Definition (Matroid)

Partager :