Matroid - Additional Terminology

Additional Terminology

Let M be a matroid with an underlying set of elements E.

• E may be called the ground set of M. Its elements may be called the points of M.
• A subset of E spans M if its closure is E. A set is said to span a closed set K if its closure is K.
• An element that forms a single-element circuit of M is called a loop. Equivalently, an element is a loop if it belongs to no basis.
• An element that belongs to no circuit is called a coloop. Equivalently, an element is a coloop if it belongs to every basis.
• If a two-element set {f, g} is a circuit of M, then f and g are parallel in M.
• A matroid is called simple if it has no circuits consisting of 1 or 2 elements. That is, it has no loops and no parallel elements. A simple matroid obtained from another matroid M by deleting all loops and deleting one element from each 2-element circuit until no 2-element circuits remain is called a simplification of M. A matroid is co-simple if its dual matroid is simple.
• A union of circuits is sometimes called a cycle of M. A cycle is therefore the complement of a flat of the dual matroid. (This usage conflicts with the common meaning of "cycle" in graph theory.)
• A separator of M is a subset S of E such that A proper separator is a separator that is neither E nor the empty set. An irreducible separator is a separator that contains no other non-empty separator. The irreducible separators partition the ground set E.
• A matroid which cannot be written as the direct sum of two nonempty matroids, or equivalently which has no proper separators, is called connected or irreducible.
• A maximal irreducible submatroid of M is called a component of M. A component is the restriction of M to an irreducible separator, and contrariwise, the restriction of M to an irreducible separator is a component.
• A matroid M is called a frame matroid if it, or a matroid that contains it, has a basis such that all the points of M are contained in the lines that join pairs of basis elements.
• A matroid is called a paving matroid if all of its circuits have size at least equal to its rank.