An Introduction To Matroids And Its Invention English Language Essay

Published:

In 1930's, van der Waerden discovered the idea of a matroid in his "Moderne Algebra" paper, first attempt to formalize the definitions of linear and algebraic dependence. Another name well known for the discovery of matroid is Hassler Whitney. He mentioned it in his pioneering paper in 1935. This is a consequence from his previous work on graph theory where he had noticed that the idea of independence in graph theory and vector spaces do have something in common. Both of their works were left unnoticed until in 1958 by W. Tutte's work.

Ever since, matroid is being widely used in a lot of areas such as graph theory, projective geometry, switching theory, electrical network theory, linear programming, lattice theory and combinatorial theory. The latter is built on from the result of the discovery on a type of matroids named transversal matroids by J. Edmonds and D. R. Fulkerson and L. Mirsky and H.Perfect.

Lady using a tablet
Lady using a tablet

Professional

Essay Writers

Lady Using Tablet

Get your grade
or your money back

using our Essay Writing Service!

Essay Writing Service

Since matroid theory is quite fresh to the world, its name varies by authors and even rejected in some cases. As Welsh mentioned in his book, Mirsky and Perfect uses the term "independent space", Crapo and Rota use "pregeonometry" instead of "matroid", Rado works in terms of "independent functions" and Cohn uses the term "transitive dependence relation".

The name "matroid" gives us a hint that it is related to matrices which implies that the theory behind it will depend a lot on basic linear algebra knowledge. In general, matroid is a set of finite elements with linearly independent properties. Edges of a graph, vectors from a vector space and lots more are valid elements of a matroid which tells us that matroid can be pictured in various ways.

This paper will list out the different definitions of a matroid but correspond to the same meaning, illustrate some of the important types of matriod and a some problems with solutions in each section to help the reader grasp the knowledge on matroids. Sentences in italic font signify that they are taken from a source as referenced.

Before we move on, the reader must have sufficient background in linear algebra prior to understanding this paper. In addition, some knowledge from graph theory is also helpful but not really necessary since the concepts from this area will be revised when needed.

2 DEFINITIONS OF A MATROID

There are a lot of ways to define a matroid. Whitney, for instance, had defined a matroid with a couple of different definitions and proven that they are equivalent in his primary paper. This paper will state the three most common and important definitions with an extra definition at the end which is useful to know.

We will start by giving the definition of a matroid in terms of bases.

2.1 BASES

A matroid M = {E, ß} consists of a non-empty finite set E together with a non-empty collection ß of subsets of E, called bases, satisfying the following properties: [1] 

ß(i) No base properly contains another base

ß(ii) If B1 and B2 are bases and x is an element of B1, then there exists an element y of B2 with the property that (B1 - {x}) {f} is also a base.

Before we go further, we need to understand both of the properties. The first condition is easy to understand from previous knowledge of linear algebra but the second condition might be quite confusing after reading it for the first time. To make it clear for the reader, I will illustrate the second property with a simple example. Let E = {1, 2, 3, 4} and ß = {{1,2,3},{1,2,4},{1,3,4}}. Since no bases in ß are equal, property ß(i) is satisfied. Let B1 = {1,2,3} and B2 = {1,2,4}. To show ß(ii), say x = 2 in this case and choosing y = 4 from B2, (B1 - {2}) {4} = {1,3,4} which is the third base in ß. Hence, the second property holds. This tells us that this set E together with ß is a matroid.

We can relate this definition to both the areas of graph theory and linear algebra as mentioned before. From graph theory, if G is a graph, then the set E in this case would be the set of all the edges of graph G. ß would be the maximum sets of edges that do not include any cycle, ie; the edges of a spanning forest of G. A spanning forest of a graph G is attained from the spanning trees of each components of G. A spanning tree of a connected graph Gi (i is the ith component of G) is defined to be the subgraph of Gi which contains all the vertices of Gi and contains no cycles. This type of matroid is called the cycle matroid or sometimes known as circuit matroid of G denoted by M(G).

Lady using a tablet
Lady using a tablet

Comprehensive

Writing Services

Lady Using Tablet

Plagiarism-free
Always on Time

Marked to Standard

Order Now

In the field of linear algebra, a matroid can be defined to be a vector matroid. As the name suggests, this matroid does relate to vectors. By setting E to be the finite set of vectors in vector space V and ß to be the set of all the linearly independent subsets of E, then both of E and ß would form the vector matroid.

Another definition which is worth mentioning here is the rank terminology. In linear algebra, the rank of a matrix A is the maximal number of linearly independent rows or columns of A. [2] In this case, the rank would be the number of elements in ß. For example, ß = {{1,0},{0,1}} has rank () = 2. In graph theory, the rank of a graph G (where G has n vertices and k components) is the number of edges in a spanning forest which is n-k edges.

We could easily see that all of the bases of a matroid will have the same cardinality. Therefore, we measure the size of a matroid to be the number of elements in any base of M. This is also known as the rank of M.

Before we move on to the next section, it is important to note that a subset S ⊆ E will be an independent set if S is contain in some base of a matroid M. The bases of a matroid are actually the maximal independent sets, ie; there cannot be any independent sets larger than the ones in the bases. This gives us a rough idea that a matroid could be defined in simpler terms by its independent sets.

2.2 INDEPENDENT SETS

A matroid M = (E, I) consists of a non-empty finite set E and a non-empty collection I of subsets of E (called independent sets) satisfying the following properties: [3] 

I(i) Any subset of an independent set is independent;

I(ii) If I and J are independent sets with |J| > |I|, then there is an element e, contained in J but not in I, such that I {e} is independent.

As pointed out earlier, a base is the maximal of independent sets. Let us look at the independent sets of a cycle and vector matroid. The cycle matroid M(G) of a graph G as we have mentioned before have bases to be the edges of a spanning forests of G. So, its independent sets, I, would be the sets of edges of G that contains no cycle. For vector matroid, if every vector in the subset is linearly independent, then the subset will be independent, i.e.; the subset I of E.

In Whitney's "On the abstract property of linear dependence" paper, he used both I(i) and I(ii) with the condition that the set I is non-empty to obtain the crucial idea of dependence. A dependent set is defined to be the subset of E which does not belong to the set I, i.e.; the subset which is not independent. We named a minimal dependent set to be a cycle.

We know, as explained in section 2.1, what the rank, r(E) of a base is. Now we need to view it in terms of independent sets. The rank of S ⊂ E is the cardinality of the biggest independent set in S also denoted as r(S). The relation between the rank function r and independent sets gives the idea that matroid could be defined in terms of its rank function r. In fact, this is the definition given by Whitney in his fundamental paper.

2.3 RANK FUNCTION

A matroid consists of a non-empty finite set E and an integer valued function r defined on the set of subsets of E, satisfying: [4] 

r(i) 0 ≤ r(A) ≤ |A|, for each subset A of E;

r(ii) if A ⊆ B ⊆ E, then r(A) ≤ r(B);

Lady using a tablet
Lady using a tablet

This Essay is

a Student's Work

Lady Using Tablet

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Examples of our work

r(iii) for any A, B ⊆ E, then r(A B) + r(A B) ≤ r(A) + r(B).

Note that the above is a theorem given by Wilson and the proof is omitted here but can be found in the same book. The last condition is also known as submodularity which is used in combinatorial optimization. loop.png

Figure A loop and a pair of parallel elements of a matroid M can be defined by ranks. Let a and b be the elements in set E. If the rank function r({a}) is zero, this tells us that a is a loop shown as an example in figure 1.

parallel 2.png

Figure If {a,b} is a pair of elements in E (not loops), such that r({a,b}) = 1, then they are a pair of elements as shown in figure 2.

As declared in section 2.2, a cycle is defined to be a minimal dependent set of a matroid M = (E,I). The minimal dependent sets, i.e.; cycles, of the cycle matroid of a graph G would be the cycles of a graph G. A cycle of a graph G, sometimes also called a circuit, is a subset of the edge set of G that forms a path such that the first node of the path corresponds to the last. [5] As cited previously, the independent set of a cycle matroid is the set of edges of G that contains no cycle. This suggests that a matroid can be defined in term of cycles or also known as circuits as given in the next section.

2.4 CIRCUITS

A matroid M = (E, C) consists of a non-empty finite set E, together with a collection C of non-empty subsets of E (called circuits) satisfying the following properties: [6] 

C(i) No circuit properly contains another circuit;

C(ii) If C1 and C2 are distinct circuits each containing an element x, then there exists a circuit in C1 C2 which does not contain x.

This is a very useful definition since we are going to deal more on graphs in this paper. By defining a matroid by its cycles, it is easier to picture the matroids on graphs.

Take note that we will use both cycles and circuits term since they have the same meaning.

Next, we are going to apply our knowledge up till now to the problems stated in the next section.

2.5 PROBLEMS

2.5.1 PROBLEM 1

Let G1 and G2 be the graphs below. Write down the bases, cycles and independent sets of the circuit matroids M(G1) and M(G2).

G1.pngG2.png

G1 G2

Solution:

Recall that in section 2.1, we have mentioned that the bases for a circuit matroid of graph G, M(G) are the edges of a spanning forest of G. In this case, the bases would be the spanning trees of G1 and similar case for G2.

The bases of M(G1) are: {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e} and {b, d, e}

The bases of M(G2) are: {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, f}, {a, d, e}, {a, d, f}, {b, c, d}, {b, c, e}, {b, c, f}, {b, d, f}, and {c, d, e}.

As stated in section 2.2, the cycles of M(G) would be the cycles of the graph G. Hence, we just need to indentify the cycles of both of the graphs.

The cycles of M(G1) are: {a, b, c}, {c, d, e} and {a, b, d, e}.

The cycles of M(G2) are: {a, b, f}, {a, c, e}, {b, d, e}, {c, d, f} and {a, b, c, d}.

In 2.2, it is mentioned that the independent sets of M(G) consists of the edges of a graph G that contains no cycle.

The independent sets of M(G1) are: , {a}, {b}, {c}, {d}, {e}, {a, b}, {a, c}, {a, d}, {a, e}, {b, c}, {b, d}, {b, e}, {c, d}, {c, e}, {d, e}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e} and {b, d, e}.

The independent sets of M(G2) are: ∅, {a}, {b}, {c}, {d}, {e}, {f}, {a, b}, {a, c}, {a, d}, {a, e}, {a, f}, {b, c}, {b, d}, {b, e}, {b, f}, {c, d}, {c, e}, {c, f}, {d, e}, {d, f}, {e, f}, {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, f}, {a, d, e}, {a, d, f}, {b, c, d}, {b, c, e}, {b, c, f}, {b, d, f}, and {c, d, e}.

2.5.2 PROBLEM 2

Let M be the matroid on the set E = {a, b, c, d} whose bases are {a, b}, {a, c}, {a, d}, {b, c}, {b, d} and {c, d}. Write down the cycles of M and deduce that there is no graph G which has M as its circuit matroid.

Solution:

Section 2.2 had defined that a cycle is a minimal dependent set. So the cycles of M would be the minimal dependent set of M.

Independent sets

Bases

, {a}, {b}, {c}, {d},

{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}

{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}

Cycles: {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}

No graph G has such cycles of the matroid M. The cycles of a matroid M(G) are the cycles of the graph G. Since no such graph G with those cycles exists, then there is no graph G that has M as its circuit matroid.

3 TYPES OF MATROID

We will go through some of the important types of matroid in this section. Before we go into depth for each type, we need to know the definition of the isomorphism of a matroid.

Let M1 = (E1, B1) and M2 = (E2, B2) be two matroids. We say that M1 is isomorphic to M2 with isomorphism if: [7] 

:E1 E2 is a bijection and

(B) B2 if and only if BB1. (Note:(B)= {(x): xB})

In other words, a subset A of E1 is an independent set in M1, if and only if the corresponding subset B (image A) of E2 is an independent set in M2. Isomorphism does preserve cycles and of course the edges of the graphs but might not maintain the number of vertices degress and connectedness.

3.1 UNIFORM MATROIDS

A uniform matroid, Uk,n is a matroid M = (E, I) with n as the number of elements in set E and that the number of elements in set I is at most k elements. Hence, every independent subsets A of E will have at most k number of elements with rank(A) = min(|A|, k).

More specifically, a matroid that has bases with exactly k elements is called a k-uniform matroid.

0-uniform is also known as the trivial matroid on E where the empty set, is the only independent set. Thus, the rank is zero.

|E|-uniform is the discrete matroid (or free matroid) where every subsets of E is independent. This also means that bases of E contains no cycles and that the rank of a subset A in E is the cardinality of A.

Problem 2 is a type of a 2-uniform matroid since it has bases with exactly 2 elements.

3.2 GRAPHIC MATROIDS

This is a vital type of matroids used in combinatorial optimization.

We know from previously that the cycles of M(G) are the cycles of graph of G and that rank of a cycle matroid M(G) is given by n-k where there are n vertices and k components. Given a matroid M, is there a graph G that have cycles that corresponds to cycles of M? Yes there is and it is called a graphic matroid. However, not every matroid is a graphic matroid as seen in problem 2. It is an example of a non-graphic matroid.

Therefore, if there exists a graph G such that M M(G), then M is a graphic matroid. Oxley had stated that every matroids that have three or fewer elements are graphic. Refer to his book to look at the corresponding graphs of these matroids.

From graph theory, a simple graph G is a graph without loops and parallel edges. Thus, if graph G is a simple graph, M(G) is a simple matroid.

3.3 COGRAPHIC MATROIDS

Besides the cycle matroid, M(G) of graph G, we can also define on a set of edges of graph G the cutset matroid, M*(G) of graph G when its cycles are chosen to be the cutset (minimum set of edges that disconnects the graph) of the graph G. Since the bases of M(G) are the edges of the spanning forests of G, then that of M*(G) would be the complement of the spanning forests of G.

Cographic and cutset matroid have similar relation as graphic and cyle matroids. This is because, if there exists a graph G such that M M*(G) then matroid M is a cographic matroid.

A matroid which is both graphic and cographic is known as a planar matroid. (Revision from graph theory: a planar graph is a graph that can be drawn with no edges intersecting each other)

3.4 REPRESENTABLE MATROIDS

Given a matroid M on a set E, we say that M is representable over a field F is there exists a vector space V over F and a map from E to V, such that a subset A of E is independent in M if and only if is one to one on A and (A) is linearly independent in V. [8] 

In other words, if a simple matroid M can be represented over F for some field F, then M is a representable matroid.

We call the matroids that are representable over every field F to be the regular matroids. If there exists a matrix A with entries in F of M, for all field F, then it is called a regular matroid. Willamson showed in his book that the matroid M(G) of graph G is regular for any graph G.

If matroids are representable over GF(2) (ie; the field of integers of modulo 2), then it they are called binary matroids. Ternary matroids would be the ones representable over GF(3). If a matroid is both binary and ternary, it tells us that it is representable over every field F.

It is proven that every graphic matroid is a binary matroid in Oxley's paper. However, Fano matroid (will be seen in problem 4) is the smallest binary matroid that is neither a graphic nor a cographic matroid.

3.5 EULERIAN MATROIDS

From previous graph theory knowledge, a connected graph is called Eulerian if it contains an Eulerian circuit. This is a circuit which contains every edge only once.

In Wilson's "Introduction to Graph Theory" book, there is a corollary stating that a connected graph is Eulerian if and only if its set of edges can be split up into disjoint cycles.

Generalizing this to the concept of matroids; a matroid is called an Eulerian matroid if its non-empty finite set E is made up of the union of disjoint cycles.

3.6 PROBLEMS

3.6.1 PROBLEM 3

Show that upto isomorphism, there are exactly four matroids on a set of two elements and eight on a set of three elements.

Solution:

Let E1 = {a, b} be the set of two elements. Now, we will show that it has exactly four matroids on E1 by listing out their collection of independent sets.

Independent sets of E1: , {, {a}}, {, {b}}, {, {a}, {b}} and {, {a}, {b}, {a, b}}.

There are 5 independent sets of E1. But as you can see, both {, {a}} and {, {b}} have the same structure. In other words, the two such matroids are isomorphic which means, there are exactly four such matroids on a set of two elements. We could also list the matroids in terms of bases and cycles by referring back to the previous definitions. To make it clearer, the four matroids will be shown in a table in terms of its independent sets, bases and cycles upto isomorphism.

Independent sets

Bases

Cycles

{a}, {b}

, {a}

{a}

{b}

, {a}, {b}

{a}, {b}

{a, b}

, {a}, {b}, {a, b}

{a, b}

-

Let E2 = {a, b, c} be the set of three elements. We will show that there are exactly eight matroids on this set by listing them out on a table upto isomorphism.

Independent sets

Bases

Cycles

{a}, {b}, {c}

, {a}

{a}

{b}, {c}

, {a}, {b}

{a}, {b}

{c}, {a, b}

, {a}, {b}, {c}

{a}, {b}, {c}

{a, b}, {b, c}, {a, c}

, {a}, {b}, {a, b}

{a, b}

{c}

, {a}, {b}, {a, b}, {b, c}

{a, b}, {b, c}

{a, c}

, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}

{a, b}, {b, c}, {a, c}

{a, b, c}

, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}, {a, b, c}

{a, b, c}

-

3.2.2 PROBLEM 4

The Fano matroid F is the matroid defined on the set E = {1, 2, 3, 4, 5, 6, 7} whose bases are all those subsets of E containing three elements except {1, 2, 3}, {1, 4, 5}, {1, 6, 7}, {2, 4, 7}, {2, 5, 6}, {3, 4, 6} and {3, 5, 7}. F may be drawn

fano.png

the bases being precisely those sets of three elements which do not lie in a line.

Show that the Fano matroid is binary and Eulerian but neither graphic nor cographic.

Solution:

4 DISCUSSION

5 CONCLUSION