Matroid - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

Matroids

  

Matroid

  

construct a matroid

 

Calling Sequence

Parameters

Description

Constructing a matroid from another mathematical object

Constructing a matroid directly

Constructing a matroid from a gallery of examples

Examples

References

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:

• 

(B1)  is non-empty.

• 

(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:

• 

(F1)  is a flat.

• 

(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.

(1)

(2)

(3)

The matroid of a matrix may differ depending on if independence is considered modulo a prime.

(4)

(5)

(6)

Create a matroid from a graph.

(7)

(8)

(9)

Create a matroid from an ideal.

(10)

(11)

(12)

Create a matroid directly from bases.

(13)

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.

(14)

References

  

James G. Oxley. Matroid Theory (Oxford Graduate Texts in Mathematics). New York: Oxford University Press. 2006.

See Also

Matroids[AreIsomorphic]

Matroids[Bases]

Matroids[CharacteristicPolynomial]

Matroids[Circuits]

Matroids[Contraction]

Matroids[Deletion]

Matroids[DependentSets]

Matroids[Dual]

Matroids[ExampleMatroids]

Matroids[Flats]

Matroids[GroundSet]

Matroids[Hyperplanes]

Matroids[IndependentSets]

Matroids[IsMinorOf]

Matroids[Rank]

Matroids[SetDisplayStyle]

Matroids[TuttePolynomial]

 


Download Help Document