|
Calling Sequence
|
|
Matroid(A)
Matroid(A,p)
Matroid(G)
Matroid(G,gsopt)
Matroid(I)
Matroid(E,opts)
|
|
Parameters
|
|
A
|
-
|
Matrix
|
p
|
-
|
prime number
|
G
|
-
|
graph
|
|
-
|
(optional) equation of the form , where is one of the names , , or , or a function of the form , where is a variable name
|
|
-
|
a polynomial ideal
|
|
-
|
a list containing the elements of the ground set of a matroid
|
|
-
|
one or more equations of the form , , , , , , , where is a list of subsets of and is a function mapping subsets of to nonnegative integers
|
|
|
|
|
Description
|
|
•
|
A matroid is an object which encodes independence structure on a set . Familiar examples include linear independence, or algebraic independence. Every matroid has a collection of subsets of which are called independent sets. These subsets must satisfy several axioms (see Matroid from Independent Sets). Given , we have the following definitions:
|
–
|
Bases : a subset of is a basis if it is a maximal independent set.
|
–
|
Dependent Sets : a subset of is a dependent set if it is not an independent set.
|
–
|
Circuits : a subset of is a circuit if it is a minimal dependent set.
|
–
|
Rank : a subset of has rank equal to the size of its largest independent subset.
|
–
|
Flats : a subset of is a flat if it is inclusionwise maximal among sets with the same rank.
|
–
|
Hyperplanes : a subset of is a hyperplane if it is a flat of rank one less than the rank of the matroid.
|
•
|
The information encoded in any of the above properties of a matroid defines the matroid. To construct a matroid explicitly from this information, certain axioms must hold, as detailed in the sections below. Alternatively, one may construct a matroid from a collection of other mathematical objects - in these cases, the axioms always hold.
|
|
|
Constructing a matroid from another mathematical object
|
|
•
|
Currently, there are three mathematical objects from which you can directly construct a matroid.
|
|
Representable (or linear) matroids - Matroids from matrices
|
|
•
|
Given a matrix with columns, the ground set of its matroid is the set,{1,2,..,n}, of indices of the columns. The independent sets are those subsets of which index independent columns. If is given, independence is considered modulo .
|
|
|
Graphic matroids - Matroids from graphs
|
|
•
|
Given a graph , let be the matroid defined by . Then the ground set of is the set of edges of , and its dependent sets are those subsets of which contain a cycle.
|
•
|
How exactly the ground set of is represented is controlled by the option:
|
–
|
If (the default), then the ground set consists of strings. The string for an edge is obtained by joining its two vertices by an underscore. A self-loop on a vertex is represented by the string . If two edges have the same string representation, an error is raised.
|
–
|
If , then the ground set consists of variable names. The names are constructed in the same way as with . If two edges have the same name representation, an error is raised.
|
–
|
If and there are edges in , the edges are assigned the numbers . The order of the edges is determined by Maple's set ordering, which does not necessarily correspond to the order in which the edges were specified when constructing .
|
–
|
If , the ground set is determined the same way as with , and the list of edges is assigned to the variable . If is already assigned a value prior to constructing the matroid, you will need to quote it to prevent evaluation, like .
|
|
|
Algebraic matroids - Matroids from ideals
|
|
•
|
Given an ideal in a polynomial ring with variables, the ground set of its matroid is the set of indices of the variables. The ideal defines a variety as its zero set, and the bases are those subsets of variables such that the projection of onto those variables is finite-to-one and dominant.
|
|
|
|
Constructing a matroid directly
|
|
•
|
To define a matroid directly, you provides a ground set, , and one or more of the independent sets, bases, dependent sets, circuits, rank, flats, and hyperplanes. If you provide the rank function, you specify it as a procedure that maps a subset of to a nonnegative integer. The other items are provided as a list of subsets of .
|
•
|
If you know more than one way to define the same matroid, you can provide them all. This may allow Maple to more efficiently do subsequent computations.
|
•
|
For each direct construction of a matroid, certain axioms on (or ) must hold; a different set of axioms for each of the types of information you can provide. For completeness, we give these axioms below. See [OXL] for more details.
|
•
|
Warning: Currently, the Matroid constructor does not validate these axioms. It is the responsibility of the user to verify that the input is valid, and that, if more than one item is provided, they define the same matroid.
|
|
Constructing a matroid from independent sets
|
|
•
|
A matroid is a pair where is the ground set and is a collection of subsets of called independent sets. The set must satisfy the following three axioms:
|
•
|
(I1) The empty set is an independent set.
|
•
|
(I2) Every subset of an independent set is an independent set.
|
•
|
(I3) If and are independent sets and has more elements than , then there exists an element of which when added to , results in an independent set.
|
|
|
Constructing a matroid from bases
|
|
•
|
A matroid is a pair where is the ground set and is a collection of subsets of called bases. The set must satisfy two axioms to define a matroid:
|
•
|
(B2) If and are bases, and is an element in but not , then there exists in so that replacing with in produces a basis.
|
|
|
Constructing a matroid from dependent sets
|
|
•
|
A matroid is a pair where is the ground set and is a collection of subsets of called dependent sets. The complement of in the power set of must form a collection of subsets which satisfy the independent set axioms.
|
|
|
Constructing a matroid from circuits
|
|
•
|
A matroid is a pair where is the ground set and is a collection of subsets of called circuits. The set must satisfy the following three axioms:
|
•
|
(C1) The empty set is not a circuit.
|
•
|
(C2) If and are circuits and is contained in , then is equal to .
|
•
|
(C3) If and are distinct circuits and is an element of their intersection, then there is a circuit contained in the union of and which does not contain .
|
|
|
Constructing a matroid from a rank function
|
|
•
|
A matroid is a pair where is the ground set and is a function from the power set of to the non-negative integers. The function must satisfy the following axioms:
|
•
|
(R1) For all , if then .
|
•
|
(R2) For all , we have .
|
•
|
(R3) For all and , we have .
|
|
|
Constructing a matroid from flats
|
|
•
|
A matroid is a pair where is the ground set and is a collection of subsets of called flats. The set must satisfy the following axioms:
|
•
|
(F2) The intersection of two flats is a flat.
|
•
|
(F3) If is a flat, then every element in its complement belongs to exactly one flat which minimally and properly contains (i.e. to exactly one flat which covers ).
|
|
|
Constructing a matroid from hyperplanes
|
|
•
|
A matroid is a pair where is the ground set and is a collection of subsets of called hyperplanes. The set must satisfy the following axioms:
|
•
|
(H1) For any hyperplane , the only hyperplane contained in is itself.
|
•
|
(H2) Given two distinct hyperplanes and and an element of the ground set not contained in their union, there exists a hyperplane containing and the intersection of and .
|
|
|
|
Constructing a matroid from a gallery of examples
|
|
•
|
A gallery of example matroids can be loaded using the command with(ExampleMatroids).
|
|
|
Examples
|
|
Create a matroid from a matrix.
The matroid of a matrix may differ depending on if independence is considered modulo a prime.
Create a matroid from a graph.
Create a matroid from an ideal.
Create a matroid directly from bases.
If you know more than one way to define the same matroid, you can provide them all. This may allow Maple to more efficiently do subsequent computations. For example, if you know the circuits of this same matroid (it has only one), you can provide them as follows.
|
|
References
|
|
|
James G. Oxley. Matroid Theory (Oxford Graduate Texts in Mathematics). New York: Oxford University Press. 2006.
|
|
|
|