In 1930 ‘s, van der Waerden discovered the thought of a matroid in his “ Moderne Algebra ” paper, first effort to formalise the definitions of additive and algebraic dependance. Another name good known for the find of matroid is Hassler Whitney. He mentioned it in his open uping paper in 1935. This is a effect from his old work on graph theory where he had noticed that the thought of independency in graph theory and vector infinites do hold something in common. Both of their plants were left unnoticed until in 1958 by W. Tutte ‘s work.
Ever since, matroid is being widely used in a batch of countries such as graph theory, projective geometry, exchanging theory, electrical web theory, additive scheduling, lattice theory and combinative theory. The latter is built on from the consequence of the find on a type of matroids named cross matroids by J. Edmonds and D. R. Fulkerson and L. Mirsky and H.Perfect.
Since matroid theory is rather fresh to the universe, its name varies by writers and even rejected in some instances. As Welsh mentioned in his book, Mirsky and Perfect uses the term “ independent infinite ” , Crapo and Rota use “ pregeonometry ” alternatively of “ matroid ” , Rado works in footings of “ independent maps ” and Cohn uses the term “ transitive dependance relation ” .
The name “ matroid ” gives us a intimation that it is related to matrices which implies that the theory behind it will depend a batch on basic additive algebra cognition. In general, matroid is a set of finite elements with linearly independent belongingss. Edges of a graph, vectors from a vector infinite and tonss more are valid elements of a matroid which tells us that matroid can be pictured in assorted ways.
This paper will name out the different definitions of a matroid but correspond to the same significance, exemplify some of the of import types of matriod and a some jobs with solutions in each subdivision to assist the reader grasp the cognition on matroids. Sentences in italic fount signify that they are taken from a beginning as referenced.
Before we move on, the reader must hold sufficient background in additive algebra prior to understanding this paper. In add-on, some cognition from graph theory is besides helpful but non truly necessary since the constructs from this country will be revised when needed.
2 DEFINITIONS OF A MATROID
There are a batch of ways to specify a matroid. Whitney, for case, had defined a matroid with a twosome of different definitions and proven that they are tantamount in his primary paper. This paper will province the three most common and of import definitions with an excess definition at the terminal which is utile to cognize.
We will get down by giving the definition of a matroid in footings of bases.
2.1 BASES
A matroid M = { E, ? } consists of a non-empty finite set E together with a non-empty aggregation ? of subsets of E, called bases, fulfilling the undermentioned belongingss:[ 1 ]
? ( I ) No base decently contains another base
? ( two ) If B1 and B2 are bases and x is an component of B1, so there exists an element Y of B2 with the belongings that ( B1 – { x } ) { f } is besides a base.
Before we go farther, we need to understand both of the belongingss. The first status is easy to understand from old cognition of additive algebra but the 2nd status might be rather confusing after reading it for the first clip. To do it clear for the reader, I will exemplify the 2nd belongings with a simple illustration. Let E = { 1, 2, 3, 4 } and ? = { { 1,2,3 } , { 1,2,4 } , { 1,3,4 } } . Since no bases in ? are equal, belongings ? ( I ) is satisfied. Let B1 = { 1,2,3 } and B2 = { 1,2,4 } . To demo ? ( two ) , say ten = 2 in this instance and taking Y = 4 from B2, ( B1 – { 2 } ) { 4 } = { 1,3,4 } which is the 3rd base in ? . Hence, the 2nd belongings holds. This tells us that this set E together with ? is a matroid.
We can associate this definition to both the countries of graph theory and additive algebra as mentioned before. From graph theory, if G is a graph, so the set Tocopherol in this instance would be the set of all the borders of graph G. ? would be the maximal sets of borders that do non include any rhythm, Internet Explorer ; the borders of a crossing wood of G. A crossing wood of a graph G is attained from the crossing trees of each constituents of G. A crossing tree of a affiliated graph Gi ( I is the ith constituent of G ) is defined to be the subgraph of Gi which contains all the vertices of Gi and contains no rhythms. This type of matroid is called the rhythm matroid or sometimes known as circuit matroid of G denoted by M ( G ) .
In the field of additive algebra, a matroid can be defined to be a vector matroid. As the name suggests, this matroid does associate to vectors. By puting E to be the finite set of vectors in vector infinite V and ? to be the set of all the linearly independent subsets of E, so both of E and ? would organize the vector matroid.
Another definition which is worth adverting here is the rank nomenclature. In additive algebra, theA rankA of aA matrixA AA is the maximum figure ofA linearly independentA rows or columns ofA A.[ 2 ]In this instance, the rank would be the figure of elements in ? . For illustration, ? = { { 1,0 } , { 0,1 } } has rank ( ) = 2. In graph theory, the rank of a graph G ( where G has n vertices and k constituents ) is the figure of borders in a spanning wood which is n-k borders.
We could easy see that all of the bases of a matroid will hold the same cardinality. Therefore, we measure the size of a matroid to be the figure of elements in any base of M. This is besides known as the rank of M.
Before we move on to the following subdivision, it is of import to observe that a subset S aS† E will be an independent set if S is contain in some base of a matroid M. The bases of a matroid are really the maximum independent sets, Internet Explorer ; there can non be any independent sets larger than the 1s in the bases. This gives us a unsmooth thought that a matroid could be defined in simpler footings 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 aggregation I of subsets of E ( called independent sets ) fulfilling the undermentioned belongingss:[ 3 ]
I ( I ) Any subset of an independent set is independent ;
I ( two ) If I and J are independent sets with |J| & gt ; |I| , so there is an element vitamin E, contained in J but non in I, such that I { vitamin E } is independent.
As pointed out before, a base is the maximal of independent sets. Let us look at the independent sets of a rhythm and vector matroid. The rhythm matroid M ( G ) of a graph G as we have mentioned earlier have bases to be the borders of a spanning woods of G. So, its independent sets, I, would be the sets of borders of G that contains no rhythm. For vector matroid, if every vector in the subset is linearly independent, so the subset will be independent, i.e. ; the subset I of E.
In Whitney ‘s “ On the abstract belongings of additive dependance ” paper, he used both I ( I ) and I ( two ) with the status that the set I is non-empty to obtain the important thought of dependance. A dependent set is defined to be the subset of E which does non belong to the set I, i.e. ; the subset which is non independent. We named a minimum dependant set to be a rhythm.
We know, as explained in subdivision 2.1, what the rank, R ( E ) of a base is. Now we need to see it in footings of independent sets. The rank of S aS‚ E is the cardinality of the biggest independent set in S besides denoted as R ( S ) . The relation between the rank map R and independent sets gives the thought that matroid could be defined in footings of its rank map r. In fact, this is the definition given by Whitney in his cardinal paper.
2.3 RANK FUNCTION
A matroid consists of a non-empty finite set E and an whole number valued map R defined on the set of subsets of E, satisfying:[ 4 ]
R ( I ) 0 a‰¤ R ( A ) a‰¤ |A| , for each subset A of Tocopherol ;
R ( two ) if A aS† B aS† E, so R ( A ) a‰¤ R ( B ) ;
R ( three ) for any A, B aS† E, so R ( A B ) + R ( A B ) a‰¤ R ( A ) + R ( B ) .
Note that the above is a theorem given by Wilson and the cogent evidence is omitted here but can be found in the same book. The last status is besides known as submodularity which is used in combinative optimisation. loop.png
Figure A cringle and a brace 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 map R ( { a } ) is zero, this tells us that a is a loop shown as an illustration in figure 1.
parallel 2.png
Figure If { a, B } is a brace of elements in E ( non loops ) , such that R ( { a, B } ) = 1, so they are a brace of elements as shown in figure 2.
As declared in subdivision 2.2, a rhythm is defined to be a minimum dependant set of a matroid M = ( E, I ) . The minimum dependent sets, i.e. ; rhythms, of the rhythm matroid of a graph G would be the rhythms of a graph G. A rhythm of aA graphA G, sometimes besides called a circuit, is a subset of theA border setA ofA GA that forms aA pathA such that the first node of the way corresponds to the last.[ 5 ]As cited antecedently, the independent set of a rhythm matroid is the set of borders of G that contains no rhythm. This suggests that a matroid can be defined in term of rhythms or besides known every bit circuits as given in the following subdivision.
2.4 Circuits
A matroid M = ( E, C ) consists of a non-empty finite set E, together with a aggregation C of non-empty subsets of E ( called circuits ) fulfilling the undermentioned belongingss:[ 6 ]
C ( I ) No circuit decently contains another circuit ;
C ( two ) If C1 and C2 are distinguishable circuits each incorporating an component ten, so there exists a circuit in C1 C2 which does non incorporate ten.
This is a really utile definition since we are traveling to cover more on graphs in this paper. By specifying a matroid by its rhythms, it is easier to visualize the matroids on graphs.
Take note that we will utilize both rhythms and circuits term since they have the same significance.
Following, we are traveling to use our cognition up till now to the jobs stated in the following subdivision.
2.5 PROBLEMS
2.5.1 PROBLEM 1
Let G1 and G2 be the graphs below. Write down the bases, rhythms and independent sets of the circuit matroids M ( G1 ) and M ( G2 ) .
G1.pngG2.png
G1 G2
Solution:
Recall that in subdivision 2.1, we have mentioned that the bases for a circuit matroid of graph G, M ( G ) are the borders of a crossing wood of G. In this instance, the bases would be the crossing trees of G1 and similar instance for G2.
The bases of M ( G1 ) are: { a, B, vitamin D } , { a, B, vitamin E } , { a, degree Celsius, vitamin D } , { a, degree Celsius, vitamin E } , { a, vitamin D, vitamin E } , { B, degree Celsius, vitamin D } , { B, degree Celsius, vitamin E } and { B, vitamin D, vitamin E }
The bases of M ( G2 ) are: { a, B, degree Celsius } , { a, B, vitamin D } , { a, B, vitamin E } , { a, degree Celsius, vitamin D } , { a, degree Celsius, degree Fahrenheit } , { a, vitamin D, vitamin E } , { a, vitamin D, degree Fahrenheit } , { B, degree Celsius, vitamin D } , { B, degree Celsius, vitamin E } , { B, degree Celsius, degree Fahrenheit } , { B, vitamin D, degree Fahrenheit } , and { degree Celsius, vitamin D, vitamin E } .
As stated in subdivision 2.2, the rhythms of M ( G ) would be the rhythms of the graph G. Hence, we merely necessitate to indentify the rhythms of both of the graphs.
The rhythms of M ( G1 ) are: { a, B, degree Celsius } , { degree Celsius, vitamin D, vitamin E } and { a, B, vitamin D, vitamin E } .
The rhythms of M ( G2 ) are: { a, B, degree Fahrenheit } , { a, degree Celsius, vitamin E } , { B, vitamin D, vitamin E } , { degree Celsius, vitamin D, degree Fahrenheit } and { a, B, degree Celsius, vitamin D } .
In 2.2, it is mentioned that the independent sets of M ( G ) consists of the borders of a graph G that contains no rhythm.
The independent sets of M ( G1 ) are: , { a } , { B } , { degree Celsius } , { vitamin D } , { vitamin E } , { a, B } , { a, degree Celsius } , { a, vitamin D } , { a, vitamin E } , { B, degree Celsius } , { B, vitamin D } , { B, vitamin E } , { degree Celsius, vitamin D } , { degree Celsius, vitamin E } , { vitamin D, vitamin E } , { a, B, vitamin D } , { a, B, vitamin E } , { a, degree Celsius, vitamin D } , { a, degree Celsius, vitamin E } , { a, vitamin D, vitamin E } , { B, degree Celsius, vitamin D } , { B, degree Celsius, vitamin E } and { B, vitamin D, vitamin E } .
The independent sets of M ( G2 ) are: a?… , { a } , { B } , { degree Celsius } , { vitamin D } , { vitamin E } , { degree Fahrenheit } , { a, B } , { a, degree Celsius } , { a, vitamin D } , { a, vitamin E } , { a, degree Fahrenheit } , { B, degree Celsius } , { B, vitamin D } , { B, vitamin E } , { B, degree Fahrenheit } , { degree Celsius, vitamin D } , { degree Celsius, vitamin E } , { degree Celsius, degree Fahrenheit } , { vitamin D, vitamin E } , { vitamin D, degree Fahrenheit } , { vitamin E, degree Fahrenheit } , { a, B, degree Celsius } , { a, B, vitamin D } , { a, B, vitamin E } , { a, degree Celsius, vitamin D } , { a, degree Celsius, degree Fahrenheit } , { a, vitamin D, vitamin E } , { a, vitamin D, degree Fahrenheit } , { B, degree Celsius, vitamin D } , { B, degree Celsius, vitamin E } , { B, degree Celsius, degree Fahrenheit } , { B, vitamin D, degree Fahrenheit } , and { degree Celsius, vitamin D, vitamin E } .
2.5.2 PROBLEM 2
Let M be the matroid on the set E = { a, B, degree Celsius, vitamin D } whose bases are { a, B } , { a, degree Celsius } , { a, vitamin D } , { B, degree Celsius } , { B, vitamin D } and { degree Celsius, vitamin D } . Write down the rhythms of M and infer that there is no graph G which has M as its circuit matroid.
Solution:
Section 2.2 had defined that a rhythm is a minimum dependant set. So the rhythms of M would be the minimum dependant set of M.
Independent sets
Bases
, { a } , { B } , { degree Celsius } , { vitamin D } ,
{ a, B } , { a, degree Celsius } , { a, vitamin D } , { B, degree Celsius } , { B, vitamin D } , { degree Celsius, vitamin D }
{ a, B } , { a, degree Celsius } , { a, vitamin D } , { B, degree Celsius } , { B, vitamin D } , { degree Celsius, vitamin D }
Cycles: { a, B, degree Celsius } , { a, B, vitamin D } , { a, degree Celsius, vitamin D } , { B, degree Celsius, vitamin D }
No graph G has such rhythms of the matroid M. The rhythms of a matroid M ( G ) are the rhythms of the graph G. Since no such graph G with those rhythms exists, so there is no graph G that has M as its circuit matroid.
3 TYPES OF MATROID
We will travel through some of the of import types of matroid in this subdivision. Before we go into deepness for each type, we need to cognize the definition of the isomorphy of a matroid.
Let M1 = ( E1, B1 ) and M2 = ( E2, B2 ) be two matroids. We say that M1 is isomorphous to M2 with isomorphy if:[ 7 ]
: E1 E2 is a bijection and
( B ) B2 if and merely if BB1. ( Note: ( B ) = { ( ten ) : xB } )
In other words, a subset Angstrom of E1 is an independent set in M1, if and merely if the corresponding subset B ( image A ) of E2 is an independent set in M2. Isomorphism does continue rhythms and of class the borders of the graphs but might non keep the figure of vertices degress and connection.
3.1 UNIFORM MATROIDS
A unvarying matroid, Uk, N is a matroid M = ( E, I ) with N as the figure of elements in set E and that the figure of elements in set I is at most thousand elements. Hence, every independent subsets A of E will hold at most thousand figure of elements with rank ( A ) = min ( |A| , K ) .
More specifically, a matroid that has bases with precisely thousand elements is called a k-uniform matroid.
0-uniform is besides known as the fiddling matroid on E where the empty set, is the lone independent set. Thus, the rank is zero.
|E|-uniform is the distinct matroid ( or free matroid ) where every subsets of E is independent. This besides means that bases of E contains no rhythms and that the rank of a subset Angstrom in E is the cardinality of A.
Problem 2 is a type of a 2-uniform matroid since it has bases with precisely 2 elements.
3.2 GRAPHIC MATROIDS
This is a critical type of matroids used in combinative optimisation.
We know from antecedently that the rhythms of M ( G ) are the rhythms of graph of G and that rank of a rhythm matroid M ( G ) is given by n-k where there are n vertices and thousand constituents. Give a matroid M, is at that place a graph G that have rhythms that corresponds to rhythms of M? Yes there is and it is called a in writing matroid. However, non every matroid is a in writing matroid as seen in job 2. It is an illustration of a non-graphic matroid.
Therefore, if there exists a graph G such that M M ( G ) , so M is a in writing matroid. Oxley had stated that every matroids that have three or fewer elements are in writing. Mention to his book to look at the matching graphs of these matroids.
From graph theory, a simple graph G is a graph without cringles and parallel borders. Therefore, if graph G is a simple graph, M ( G ) is a simple matroid.
3.3 COGRAPHIC MATROIDS
Besides the rhythm matroid, M ( G ) of graph G, we can besides specify on a set of borders of graph G the cutset matroid, M* ( G ) of graph G when its rhythms are chosen to be the cutset ( minimal set of borders that disconnects the graph ) of the graph G. Since the bases of M ( G ) are the borders of the crossing woods of G, so that of M* ( G ) would be the complement of the crossing woods of G.
Cographic and cutset matroid have similar relation as in writing and cyle matroids. This is because, if there exists a graph G such that M M* ( G ) so matroid M is a cographic matroid.
A matroid which is both in writing and cographic is known as a planar matroid. ( Revision from graph theory: a planar graph is a graph that can be drawn with no borders crossing 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 at that place exists a vector infinite V over F and a map from E to V, such that a subset Angstrom of E is independent in M if and merely 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, so 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 Angstrom with entries in F of M, for all field F, so 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 ) ( Internet Explorer ; the field of whole numbers of modulo 2 ) , so it they are called binary matroids. Ternary matroids would be the 1s representable over GF ( 3 ) . If a matroid is both binary and treble, it tells us that it is representable over every field F.
It is proven that every in writing matroid is a binary matroid in Oxley ‘s paper. However, Fano matroid ( will be seen in job 4 ) is the smallest binary matroid that is neither a in writing nor a cographic matroid.
3.5 EULERIAN MATROIDS
From old graph theory cognition, a affiliated graph is called Eulerian if it contains an Eulerian circuit. This is a circuit which contains every border merely one time.
In Wilson ‘s “ Introduction to Graph Theory ” book, there is a corollary stating that a affiliated graph is Eulerian if and merely if its set of borders can be split up into disjoint rhythms.
Generalizing this to the construct of matroids ; a matroid is called an Eulerian matroid if its non-empty finite set E is made up of the brotherhood of disjoint rhythms.
3.6 PROBLEMS
3.6.1 PROBLEM 3
Show that upto isomorphy, there are precisely 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 demo that it has precisely four matroids on E1 by naming out their aggregation 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 construction. In other words, the two such matroids are isomorphous which means, there are precisely four such matroids on a set of two elements. We could besides name the matroids in footings of bases and rhythms by mentioning back to the old definitions. To do it clearer, the four matroids will be shown in a tabular array in footings of its independent sets, bases and rhythms upto isomorphy.
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 demo that there are precisely eight matroids on this set by naming them out on a table upto isomorphy.
Independent sets
Bases
Cycles
{ a } , { B } , { degree Celsius }
, { a }
{ a }
{ B } , { degree Celsius }
, { a } , { B }
{ a } , { B }
{ degree Celsius } , { a, B }
, { a } , { B } , { degree Celsius }
{ a } , { B } , { degree Celsius }
{ a, B } , { B, degree Celsius } , { a, degree Celsius }
, { a } , { B } , { a, B }
{ a, B }
{ degree Celsius }
, { a } , { B } , { a, B } , { B, degree Celsius }
{ a, B } , { B, degree Celsius }
{ a, degree Celsius }
, { a } , { B } , { degree Celsius } , { a, B } , { B, degree Celsius } , { a, degree Celsius }
{ a, B } , { B, degree Celsius } , { a, degree Celsius }
{ a, B, degree Celsius }
, { a } , { B } , { degree Celsius } , { a, B } , { B, degree Celsius } , { a, degree Celsius } , { a, B, degree Celsius }
{ a, B, degree Celsius }
–
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 incorporating 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 exactly those sets of three elements which do non lie in a line.
Show that the Fano matroid is binary and Eulerian but neither in writing nor cographic.
