Algebraic matroid

Last updated

In mathematics, an algebraic matroid is a matroid, a combinatorial structure, that expresses an abstraction of the relation of algebraic independence.

Contents

Definition

Given a field extension L/K, Zorn's lemma can be used to show that there always exists a maximal algebraically independent subset of L over K. Further, all the maximal algebraically independent subsets have the same cardinality, known as the transcendence degree of the extension.

For every finite set S of elements of L, the algebraically independent subsets of S satisfy the axioms that define the independent sets of a matroid. In this matroid, the rank of a set of elements is its transcendence degree, and the flat generated by a set T of elements is the intersection of L with the field K[T]. [1] A matroid that can be generated in this way is called algebraic or algebraically representable. [2] No good characterization of algebraic matroids is known, [3] but certain matroids are known to be non-algebraic; the smallest is the Vámos matroid. [4] [5]

Relation to linear matroids

Many finite matroids may be represented by a matrix over a field K, in which the matroid elements correspond to matrix columns, and a set of elements is independent if the corresponding set of columns is linearly independent. Every matroid with a linear representation of this type over a field F may also be represented as an algebraic matroid over F, [6] [7] by choosing an indeterminate for each row of the matrix, and by using the matrix coefficients within each column to assign each matroid element a linear combination of these transcendentals. For fields of characteristic zero (such as the real numbers) linear and algebraic matroids coincide, but for other fields there may exist algebraic matroids that are not linear; [8] [9] indeed the non-Pappus matroid is algebraic over any finite field, but not linear and not algebraic over any field of characteristic zero. [7] However, if a matroid is algebraic over a field F of characteristic zero then it is linear over F(T) for some finite set of transcendentals T over F [5] and over the algebraic closure of F. [7]

Closure properties

If a matroid is algebraic over a simple extension F(t) then it is algebraic over F. It follows that the class of algebraic matroids is closed under contraction, [10] and that a matroid algebraic over F is algebraic over the prime field of F. [11]

The class of algebraic matroids is closed under truncation and matroid union. [12] It is not known whether the dual of an algebraic matroid is always algebraic [13] and there is no excluded minor characterisation of the class. [12]

Characteristic set

The (algebraic) characteristic setK(M) of a matroid M is the set of possible characteristics of fields over which M is algebraically representable. [7]

Notes

  1. ↑ Oxley (1992) p.216
  2. ↑ Oxley (1992) p.218
  3. ↑ Oxley (1992) p.215
  4. ↑ Ingleton, A. W.; Main, R. A. (1975). "Non-algebraic matroids exist". Bulletin of the London Mathematical Society . 7 (2): 144–146. doi:10.1112/blms/7.2.144. MR   0369110. Zbl   0315.05018..
  5. 1 2 Oxley (1992) p.221
  6. ↑ Oxley (1992) p.220
  7. 1 2 3 4 5 6 White (1987) p.24
  8. ↑ Ingleton, A. W. (1971). "Representation of matroids". Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969). London: Academic Press. pp. 149–167. MR   0278974. Zbl   0222.05025.
  9. ↑ Joshi, K. D. (1997), Applied Discrete Structures, New Age International, p. 909, ISBN   9788122408263 .
  10. ↑ Oxley (1992) p.222
  11. ↑ Oxley (1992) p.224
  12. 1 2 3 White (1987) p.25
  13. ↑ Oxley (1992) p.223
  14. ↑ Lindström, Bernt (1985). "On the algebraic characteristic set for a class of matroids". Proceedings of the American Mathematical Society . 95 (1): 147–151. doi:10.2307/2045591. JSTOR   2045591. Zbl   0572.05019.

Related Research Articles

In mathematics, particularly in algebra, a field extension is a pair of fields such that the operations of E are those of F restricted to E. In this case, F is an extension field of E and E is a subfield of F. For example, under the usual notions of addition and multiplication, the complex numbers are an extension field of the real numbers; the real numbers are a subfield of the complex numbers.

In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite matroid is equivalent to a geometric lattice.

Transcendence degree Size of largest algebraically independent subset

In abstract algebra, the transcendence degree of a field extension L / K is a certain rather coarse measure of the "size" of the extension. Specifically, it is defined as the largest cardinality of an algebraically independent subset of L over K.

Algebraic independence Set without nontrivial polynomial equalities

In abstract algebra, a subset of a field is algebraically independent over a subfield if the elements of do not satisfy any non-trivial polynomial equation with coefficients in .

Field theory is the branch of mathematics in which fields are studied. This is a glossary of some terms of the subject.

In field theory, a branch of algebra, an algebraic field extension is called a separable extension if for every , the minimal polynomial of over F is a separable polynomial. There is also a more general definition that applies when E is not necessarily algebraic over F. An extension that is not separable is said to be inseparable.

In combinatorics, a greedoid is a type of set system. It arises from the notion of the matroid, which was originally introduced by Whitney in 1935 to study planar graphs and was later used by Edmonds to characterize a class of optimization problems that can be solved by greedy algorithms. Around 1980, Korte and Lovász introduced the greedoid to further generalize this characterization of greedy algorithms; hence the name greedoid. Besides mathematical optimization, greedoids have also been connected to graph theory, language theory, order theory, and other areas of mathematics.

Transcendental number theory Study of numbers that are not solutions of polynomials with rational coefficients

Transcendental number theory is a branch of number theory that investigates transcendental numbers, in both qualitative and quantitative ways.

Pregeometry, and in full combinatorial pregeometry, are essentially synonyms for "matroid". They were introduced by Gian-Carlo Rota with the intention of providing a less "ineffably cacophonous" alternative term. Also, the term combinatorial geometry, sometimes abbreviated to geometry, was intended to replace "simple matroid". These terms are now infrequently used in the study of matroids.

In mathematics, a regular matroid is a matroid that can be represented over all fields.

Algebraic combinatorics Area of combinatorics

Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra, notably group theory and representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in algebra.

In matroid theory, a field within mathematics, a gammoid is a certain kind of matroid, describing sets of vertices that can be reached by vertex-disjoint paths in a directed graph.

In mathematics, a uniform matroid is a matroid in which the independent sets are exactly the sets containing at most r elements, for some fixed integer r. An alternative definition is that every permutation of the elements is a symmetry.

In the mathematical theory of matroids, a minor of a matroid M is another matroid N that is obtained from M by a sequence of restriction and contraction operations. Matroid minors are closely related to graph minors, and the restriction and contraction operations by which they are formed correspond to edge deletion and edge contraction operations in graphs. The theory of matroid minors leads to structural decompositions of matroids, and characterizations of matroid families by forbidden minors, analogous to the corresponding theory in graphs.

Vámos matroid Matroid with no linear representation

In mathematics, the Vámos matroid or Vámos cube is a matroid over a set of eight elements that cannot be represented as a matrix over any field. It is named after English mathematician Peter Vámos, who first described it in an unpublished manuscript in 1968.

In the mathematical theory of matroids, the rank of a matroid is the maximum size of an independent set in the matroid. The rank of a subset S of elements of the matroid is, similarly, the maximum size of an independent subset of S, and the rank function of the matroid maps sets of elements to their ranks.

In the mathematical theory of matroids, a matroid representation is a family of vectors whose linear independence relation is the same as that of a given matroid. Matroid representations are analogous to group representations; both types of representation provide abstract algebraic structures with concrete descriptions in terms of linear algebra.

Paving matroid Matroid without short circuits

In the mathematical theory of matroids, a paving matroid is a matroid in which every circuit has size at least as large as the matroid's rank. In a matroid of rank every circuit has size at most , so it is equivalent to define paving matroids as the matroids in which the size of every circuit belongs to the set . It has been conjectured that almost all matroids are paving matroids.

In mathematics, Ingleton's inequality is an inequality that is satisfied by the rank function of any representable matroid. In this sense it is a necessary condition for representability of a matroid over a finite field. Let M be a matroid and let ρ be its rank function, Ingleton's inequality states that for any subsets X1, X2, X3 and X4 in the support of M, the inequality

In mathematics, a basis of a matroid is a maximal independent set of the matroid—that is, an independent set that is not contained in any other independent set.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.