Foundations of matroids
Part 1: Matroids without large uniform minors
Abstract.
The foundation of a matroid is a canonical algebraic invariant which classifies, in a certain precise sense, all representations of the matroid up to rescaling equivalence. Foundations of matroids are pastures, a simultaneous generalization of partial fields and hyperfields which are special cases of both tracts (as defined by the first author and Bowler) and ordered blue fields (as defined by the second author).
Using deep results due to Tutte, Dress–Wenzel, and Gelfand–Rybnikov–Stone, we give a presentation for the foundation of a matroid in terms of generators and relations. The generators are certain “cross-ratios” generalizing the cross-ratio of four points on a projective line, and the relations encode dependencies between cross-ratios in certain low-rank configurations arising in projective geometry.
Although the presentation of the foundation is valid for all matroids, it is simplest to apply in the case of matroids without large uniform minors. i.e., matroids having no minor corresponding to five points on a line or its dual configuration. For such matroids, we obtain a complete classification of all possible foundations.
We then give a number of applications of this classification theorem, for example:
-
(1)
We prove the following strengthening of a 1997 theorem of Lee and Scobee: every orientation of a matroid without large uniform minors comes from a dyadic representation, which is unique up to rescaling.
-
(2)
For a matroid without large uniform minors, we establish the following strengthening of a 2017 theorem of Ardila–Rincón–Williams: if is positively oriented then is representable over every field with at least 3 elements.
-
(3)
Two matroids are said to belong to the same representation class if they are representable over precisely the same pastures. We prove that there are precisely 12 possibilities for the representation class of a matroid without large uniform minors, exactly three of which are not representable over any field.
Introduction
Matroids are a combinatorial abstraction of the notion of linear independence in vector spaces. If is a field and is a positive integer, any linear subspace of gives rise to a matroid; such matroids are called representable over . The task of deciding whether or not certain families of matroids are representable over certain kinds of fields has occupied a plethora of papers in the matroid theory literature.
Dress and Wenzel [13, 14] introduced the Tutte group and the inner Tutte group of a matroid. These are abelian groups which, in a certain precise sense, can be used to understand representations of over all so-called fuzzy rings (which, in particular include fields). Dress and Wenzel gave several different presentations for these groups in terms of generators and relations, and Gelfand–Rybnikov–Stone [16] subsequently gave additional presentations for the inner Tutte group of . The Dress–Wenzel theory of Tutte groups, inner Tutte groups, and fuzzy rings is powerful but lacks simple definitions and characterizations in terms of universal properties.
In their 1996 paper [28], Semple and Whittle generalized the notion of matroid representations to partial fields (which are special cases of fuzzy rings); this allows one to consider certain families of matroids (e.g. regular or dyadic) as analogous to matroids over a field, and to prove new theorems in the spirit of Tutte’s theorem that a matroid is both binary and ternary if and only if it is regular. Pendavingh and van Zwam [23, 24] subsequently introduced the universal partial field of a matroid , which governs the representations of over all partial fields. Unfortunately, most matroids (asymptotically 100%, in fact, by a theorem of Nelson [20]) are not representable over any partial field, and in this case the universal partial field gives no information. One can view non-representable matroids as the “dark matter” of matroid theory: they are ubiquitous but somehow mysterious.
Using the theory of matroids over partial hyperstructures presented in [3] (which has been continued in [1], [9] and [22]), we introduced in [5] a generalization of the universal partial field which we call the foundation of a matroid. The foundation is a kind of algebraic object which we call a pasture; pastures include both hyperfields and partial fields and form a natural class of “field-like” objects within the second author’s theory of ordered blueprints in [18]. The category of pastures has various desirable categorical properties (e.g., the existence of products and co-products) which makes it a natural context in which to study algebraic invariants of matroids. Pastures are closely related to fuzzy rings, but they are axiomatically much simpler.
One advantage of the foundation over the universal partial field is that the foundation exists for every matroid , not just matroids that are representable over some field. Moreover, unlike the inner Tutte group, the foundation of a matroid is characterized by a universal property which immediately clarifies its importance and establishes its naturality.
More precisely, the foundation of a matroid represents the functor taking a pasture to the set of rescaling equivalence classes of -representations of ; in particular, is representable over a pasture if and only if there is a morphism from the foundation of to .
Our first main result (Theorem 4.20) gives a precise and useful description of the foundation of a matroid in terms of generators and relations. Although this theorem applies to all matroids, it is easiest to apply in the case of matroids without large uniform minors, by which we mean matroids which do not have minors isomorphic to either or .111Note that if has no minor of type or , then also has no uniform minor with and , hence the term “large”. For such matroids, we obtain a complete classification (Theorem 5.9) of all possible foundations, from which one can read off just about any desired representability property. This applies, notably, to the dark matter of matroid theory: we show, for example, that there are precisely three different representation classes of matroids without large uniform minors which are not representable over any field. The applications of Theorem 5.9 which we present in Section 6 are merely a representative sample of the kinds of things one can deduce from this structural result.
We now give a somewhat more precise introduction to the main concepts, definitions, and results in the present paper.
A quick introduction to pastures
A field can be thought of as an abelian group , a multiplicatively absorbing element , and a binary operation on which satisfies certain additional natural axioms (e.g. commutativity, associativity, distributivity, and the existence of additive inverses). Pastures are a generalization of the notion of field in which we still have a multiplicative abelian group , an absorbing element , and an “additive structure”, but we relax the requirement that the additive structure come from a binary operation. The following two examples are illustrative of the type of relaxations we have in mind.
Example (Krasner hyperfield).
As a pasture, the Krasner hyperfield consists of the multiplicative monoid with and and the additive relations , , and . Note, in particular, that both and are true, and in particular the additive structure is not derived from a binary operation. The fact that is equal to two different things may seem counterintuitive at first, but if we think of 1 as a symbol meaning “non-zero”, it is simply a reflection of the fact that the sum of two non-zero elements (in a field, say) can be either non-zero or zero.
Example (Regular partial field).
As a pasture, the regular partial field consists of the multiplicative monoid with , , , and , together with the additive relations and . Note, in particular, that there is no additive relation of the form or , so that once again the additive structure is not derived from a binary operation (but for a different reason: here, is undefined rather than being multi-valued). We think of as encoding the restriction of addition and multiplication in the ring to the multiplicative subset .
In general, we will require that a pasture has an involution (which is trivial in the case of ), and we can use this involution to rewrite additive relations of the form as . It turns out to be more convenient to define pastures using this formalism, and from now on we view the expression as shorthand for . For additional notational convenience, we identify relations of the form with triples ; the set of all such triples will be denoted and called the null set of the pasture.
More formally, a pasture is a multiplicative monoid-with-zero such that is an abelian group, an involution on fixing , and a subset of such that:
-
(1)
(Symmetry) is invariant under the natural action of on .
-
(2)
(Weak Distributivity) is invariant under the diagonal action of on .
-
(3)
(Unique Weak Inverses) if and only if .
If we set , then the pasture corresponds to a field if and only if is an associative binary operation. If contains at least one element for all and is associative (in the sense of set-wise addition), we call a hyperfield. If contains at most one element for all and satisfies a suitable associative law, we call a partial field. Pastures generalize (and simplify) both hyperfields and partial fields by imposing no conditions on the size of the sets and no associativity conditions.
Example (Hyperfields).
Let be a field and let be a multiplicative subgroup. Then the quotient monoid is naturally a hyperfield: the additive relations are all expressions of the form for which there exist such that . For example, is isomorphic to the Krasner hyperfield , is isomorphic to the sign hyperfield (cf. [3, Example 2.13]), and if is a prime number with then is isomorphic to the weak sign hyperfield (cf. [3, Example 2.13]). However, not every hyperfield arises in this way (cf. [4, 19]).
Example (Partial fields).
Let be a commutative ring and let be a subgroup of the unit group of containing . Then is naturally a partial field: the additive relations are all expressions of the form with such that in . Unlike the situation with hyperfields, every partial field arises from this construction (cf. [24, Theorem 2.16]).
Example (Partial fields, continued).
If is a commutative ring, let be the partial field corresponding to . In this paper, we will make extensive use of the following partial fields:
-
(1)
. We call this the regular partial field.
-
(2)
. We call this the dyadic partial field.
- (3)
-
(4)
, where is an indeterminate. We call this the near-regular partial field.
Example (Fields).
It is perhaps worth pointing out explicitly that fields are special cases of both hyperfields and partial fields; in fact, they are precisely the pastures which are both hyperfields and partial fields. Since we will be making extensive use of the finite fields and in this paper, here is how to explicitly realize these fields as pastures:
-
(1)
has as its underlying monoid with the usual multiplication. The involution is trivial, and the -term additive relations are and (and all permutations thereof).
-
(2)
has as its underlying monoid with the usual multiplication. The involution sends to and to . The -term additive relations are , (and all permutations thereof), and .
A morphism of pastures is a multiplicative map of monoids such that , and in whenever in . Pastures form a category whose initial object is and whose final object is .
Representations of matroids over pastures and the foundation of a matroid
Let be a matroid of rank on the finite set , and let be a pasture.
A -representation of is a function such that:
-
(1)
if and only if is a basis of .
-
(2)
for all permutations .
-
(3)
satisfies the 3-term Plücker relations: for all and all , the null set of contains the additive relation
where .
Definition.
-
(1)
is representable over if there is at least one -representation of .
-
(2)
Two -representations and are isomorphic if there exists such that for all .333An isomorphism class of -representations of is the same thing as a weak -matroid whose support is , in the terminology of [3].
-
(3)
and rescaling equivalent if there exist and a map such that for all .
-
(4)
We denote by (resp. ) the set of isomorphism classes (resp. rescaling classes) of -representations of .444In [5], these sets are denoted and , respectively.
Example.
By the results in [3] and [5], we have:
-
(1)
If is a field, the isomorphism classes of -representations of are naturally in bijection with -dimensional subspaces of (the -vector space of functions from to ) whose underlying matroid is .
-
(2)
Every matroid has a unique representation over the Krasner hyperfield .
-
(3)
If is a partial field, is representable over if and only if it is representable by a -matrix in the sense of [24]. In particular, a matroid is regular (i.e., representable over by a totally unimodular matrix) if and only if it is representable over the partial field . A regular matroid will in general have many different (non-isomorphic) representations over , but there is a unique rescaling class of such representations.
-
(4)
A matroid is orientable if and only if it is representable over the sign hyperfield . An orientation of is the same thing as an -representation, and in this case rescaling equivalence is usually called reorientation equivalence.
For fixed the map taking a pasture to the set (resp. ) is a functor. In particular, if is a morphism of pastures, there are natural maps and .
We now come to the key result from [5] motivating the present paper:
Theorem.
Given a matroid , the functor taking a pasture to the set is representable by a pasture which we call the universal pasture of . In other words, we have a natural isomorphism
(1) |
The functor taking a pasture to the set is representable by a subpasture of which we call the foundation of , i.e. there is a natural isomorphism
(2) |
For various reasons, including the fact that the foundation can be presented by generators and relations “induced from small minors”, we will mainly focus in this paper on studying the foundation of rather than the universal pasture. Note that both and have the property that is representable over a pasture if and only if there is a morphism from (resp. ) to .
Remark.
-
(1)
The universal partial field and foundation behave nicely with respect to various matroid operations. For example, the universal partial fields (resp. foundations) of and its dual matroid are canonically isomorphic. And there is a natural morphism from the universal partial field (resp. foundation) of a minor of to the universal partial field (resp. foundation) of .
-
(2)
The multiplicative group (resp. ) of the universal partial field (resp. foundation) of is isomorphic to the Tutte group (resp. inner Tutte group) of Dress and Wenzel [13, Definition 1.6].
If we take in (1), the identity map is a distinguished element of . It therefore corresponds to a distinguished element , which (by abuse of terminology) we call the universal representation of . (Technically speaking, the universal representation is actually an isomorphism class of representations.)
Remark.
When is a partial field, the foundation coincides with the universal partial field of [23]. However, when is not representable over any field, the universal partial field does not exist. On the other hand, the foundation of is always well-defined; this is one sense in which the theory of pastures helps us explore the “dark matter” of the matroid universe.
Products and coproducts
The category of pastures admits finite products and co-products (a.k.a. tensor products). This is a key advantage of pastures over the categories of fields, partial fields, and hyperfields, none of which admit both products and co-products. The relevance of such considerations to matroid theory is illustrated by the following observations:
-
(1)
is representable over both and if and only if is representable over the product pasture . (This is immediate from the universal property of the foundation and of categorical products.)
-
(2)
If and are matroids, the foundation of the direct sum is canonically isomorphic to the tensor product , and similarly for the -sum of and . (These facts, along with some applications, will be discussed in detail a follow-up paper.)
-
(3)
Tensor products of pastures are needed in order to state and apply the main theorem of this paper, the classification theorem for foundations of matroids without large uniform minors (Theorem 5.9 below).
In order to illustrate the utility of categorical considerations for studying matroid representations, we briefly discuss a couple of key examples.
Example.
The product of the fields and , considered as pastures, is isomorphic to the regular partial field . As an immediate consequence, we obtain Tutte’s celebrated result that a matroid is representable over every field if and only if is regular. (Proof: If is regular then since is an initial object in the category of pastures, is representable over every pasture, and in particular over every field. Conversely, if is representable over every field, then it is in particular representable over both and , hence over their product , and thus is regular.)
One can, in the same way, establish Whittle’s theorem that a matroid is representable over both and if and only if it is hexagonal, i.e., representable over the partial field .
These kind of arguments are well-known in the theory of partial fields; however, the theory of pastures is more flexible. For example, the product of the field and the hyperfield is also isomorphic to the partial field . In this way, we obtain a unified proof of the result of Tutte just mentioned and the theorem of Bland and Las Vergnas that a matroid is regular if and only if it is both binary and orientable [8].
Example.
If we try to extend this type of argument to more general pastures, we run into some intriguing complications. As an illuminating example, consider the theorem of Lee and Scobee [17] that a matroid is both ternary and orientable if and only if it is dyadic, i.e., representable over the partial field . In this case, the product of and is not isomorphic to ; there is merely a morphism from to . The theorem of Lee and Scobee therefore lies deeper than the theorems mentioned in the previous example; proving it requires establishing, in particular, that is not the foundation of any matroid.
To do this, one needs a structural understanding of foundations, which we obtain by utilizing highly non-trivial results of Tutte, Dress–Wenzel, and Gelfand–Rybnikov–Stone. The result of our analysis, in the context of matroids which are both ternary and orientable, is that every morphism from the foundation of some matroid to lifts uniquely to . More precisely, we prove that if is a matroid without large uniform minors (e.g. if is ternary), then the morphism induces a canonical bijection . This gives a new and non-trivial strengthening of the Lee–Scobee theorem. The proof goes roughly as follows: by Theorem B we have , where each belongs to an explicit finite set of pastures. By categorical considerations, the statement that a morphism lifts uniquely to is equivalent to the statement that for all , and this can be checked by concrete elementary computations.
Universal cross ratios
In order to explain why the “large” uniform minors and play a special role in the theory of foundations, we need to first explain the concept of a universal cross ratio, which is intimately related to -minors.
Let be a matroid of rank , let be a pasture, and let be a -representation of . Let have distinct coordinates and let be the corresponding unordered subset of of size . If and are both non-zero (i.e., if and are both bases of ), then we can rewrite the 3-term Plücker relation
as
Moreover, as one easily checks, the quantities and are invariant under rescaling equivalence and do not depend on the choice of ordering of elements of . In particular,
depends only on and on the rescaling class of in .
The cross ratio associated to the universal representation plays an especially important role in our theory. For notational convenience, we set
We will write instead of when is understood.
Using the fact that depends only on the rescaling class of , one sees easily that , which a priori is an element of the universal pasture , in fact belongs to the foundation .
We call elements of of the form universal cross ratios of . When we omit the subscript entirely. By [5, Lemma 7.7], we have:
Lemma.
The foundation of is generated by its universal cross ratios.
Remark.
-
(1)
When and is the uniform matroid of rank 2 on the 4-element set , the quantity can be viewed as a “universal” version of the usual cross-ratio of four points on a projective line. The fact that the cross-ratio is the only projective invariant of four points on a line corresponds to the fact that the foundation of is isomorphic to the partial field described above. The six different values of for correspond to the elements , and of .
-
(2)
More generally, we can associate a universal cross ratio to each -minor of (together with an ordering of the ground set of ) via the natural map from to , and every universal cross ratio arises from this construction.
The structure theorem for foundations of matroids without large uniform minors
In order to calculate and classify foundations of matroids, in addition to knowing that the universal cross ratios generate , we need to understand the relations between these generators.
Example.
The universal cross ratios of the uniform matroid on satisfy certain tip relations of the form
By duality, the universal cross ratios of satisfy similar identities which we call the cotip relations.
The theoretical tool which allows one to understand all relations between universal cross ratios is Tutte’s Homotopy Theorem [31, 32, 33] (or, more specifically, [16, Theorem 4], whose proof is based on Tutte’s Homotopy Theorem). We give an informal description here; a more precise version is given in Theorem 4.20 below. To state the result, we say that a relation between universal cross-ratios of is inherited from a minor if it is the image (with respect to the natural inclusion ) of a relation between universal cross ratios in .
Theorem A.
Every relation between universal cross ratios of a matroid is inherited from a minor on a -element set. The foundation of is generated as an -algebra by such generators and relations, together with the relation if has a minor isomorphic to either the Fano matroid or its dual.
The most complicated relations between universal cross ratios come from the tip and cotip relations in and , respectively (six-element minors and non-uniform five-element minors only contribute additional relations identifying certain cross ratios with one another). In the absence of such minors, we can completely classify all possible foundations. Roughly speaking, the conclusion is that the foundation of a matroid is the tensor product of copies of and quotients of (the foundation of ) by groups of automorphisms. By calculating all possible quotients of by automorphisms, we obtain the following result (Theorem 5.9):
Theorem B.
Let be a matroid without large uniform minors and its foundation. Then
for some and pastures .
Remark.
In a sequel paper, we will show that every pasture of the form with is the foundation of some matroid.
Consequences of the structure theorem
A matroid is representable over a pasture if and only if there is a morphism from the foundation of to . If is without large uniform minors (which is automatic if is binary or ternary), then by Theorem 5.9 its foundation is isomorphic to a tensor product of copies of , , , and . There is a morphism from to if and only if there is a morphism from each to , so one readily obtains various theorems about representability of such matroids.
We mention just a selection of sample applications from the more complete list of results in section 6. For instance, our method yields short proofs of the excluded minor characterizations of regular, binary and ternary matroids (Theorems 6.3 and 6.4). We find a similarly short proof for Brylawski-Lucas’s result that every matroid has at most one rescaling class over (Theorem 6.5 and Remark 6.6).
As already mentioned, we derive a strengthening of a theorem by Lee and Scobee ([17]) on lifts of oriented matroids. The lifting result assumes a particularly strong form in the case of positively oriented matroids, improving on a result by Ardila, Rincón and Williams ([2]). The following summarizes Theorems 6.9 and 6.15:
Theorem C.
Let be an oriented matroid whose underlying matroid is without large uniform minors. Then is uniquely dyadic up to rescaling. If is positively oriented, then is near-regular.
In Theorem 6.7, we derive similar statements for the weak hyperfield of signs and the phase hyperfield ; cf. section 2.1.2 for definitions. Namely, a matroid without large uniform minors is ternary if it is representable over , and is representable over if it is representable over .
We define the representation class of a matroid as the class of all pastures over which is representable. Two matroids and are representation equivalent if . The following is Theorem 6.20.
Theorem D.
Let be a matroid without large uniform minors. Then there are precisely 12 possibilities for the representation class of . Nine of these classes are representable over some field, and the other three are not.
The structure theorem also provides short proofs of various characterizations (some new, some previously known by other methods) of certain classes of matroids. The following summarizes Theorems 6.26–6.34:
Theorem E.
Let be a matroid without large uniform minors and its foundation. Then all conditions in a given row in Table 1 are equivalent, where the conditions should be read as follows:
-
(1)
The first column describes the class by name (cf. Definition 2.14 for any unfamiliar terms).
-
(2)
The second column characterizes the class in terms of the factors that may appear in a decomposition , as in Theorem B.
-
(3)
The third column lists various classifying pastures , separated by slashes, which means that is contained in the class in question if and only if it is representable over .
class | possible factors of | representable over |
---|---|---|
regular | – | with in |
binary | ||
ternary | any field extension of | |
quaternary | any field extension of | |
near-regular | ||
dyadic | ||
hexagonal | ||
-representable | ||
representable | either or |
Another consequence of the structure theorem for foundations of matroids without large uniform minors is the following result, which will be the theme of a forthcoming paper.
Theorem F.
Let be a ternary matroid. Then up to rescaling equivalence,
-
(1)
every quarternary representation of lifts uniquely to ;
-
(2)
every quinternary representation of lifts uniquely to ;
-
(3)
every septernary representation of lifts uniquely to ;
-
(4)
every octernary representation of lifts uniquely to .
Content overview
In section 1, we introduce embedded minors and review basic facts concerning the Tutte group of a matroid. In section 2, we discuss matroid representations over pastures and explain the concept of the universal pasture of a matroid. In section 3, we extend the concept of cross ratios to matroid representations over pastures and define universal cross ratios. In section 4, we introduce the foundation of a matroid and exhibit a complete set of relations between cross ratios, which culminates in Theorem A. In section 5, we focus on matroids without large uniform minors and prove Theorem B. In section 6, we explain several consequences of Theorem B, such as Theorems C, D and E.
Acknowledgements
The authors thank Nathan Bowler and Rudi Pendavingh for helpful discussions; in particular, we thank Rudi Pendavingh for suggesting that a result along the lines of Theorem 4.20 should follow from [16]. The authors also thank their respective muses Camille and Cecília for inspiring the name of the matroid .
1. Background
1.1. Notation
In this paper, we assume that the reader is familiar with basic concepts from matroid theory.
Typically, denotes a matroid of rank on the ground set . We denote its set of bases by and its set of hyperplanes by . We denote the closure of a subset of by . We denote the dual matroid of by .
Given two subsets and of , we denote by the complement of in . For an ordered tuple in , we denote by the subset of . Given elements , we denote by the -tuple . If is a subset of , then we denote by the subset of . In particular, we have for . inline]Reminder: we should point out discrepancies to the notation and terminology of [5].
1.2. The Tutte group
The Tutte group is an invariant of a matroid that was introduced and studied by Dress and Wenzel in [13]. We will review the parts of this theory that are relevant for the present text in the following.
Definition 1.1.
Let be a matroid of rank on with Grassmann-Plücker function . The multiplicatively written abelian group is generated by symbols and for every modulo the relations
for every permutation , where we consider as an element of ;
for and such that for all and but .
The group comes with a morphism that sends to for every . The Tutte group of is the kernel of this map.
By definition, the Tutte group is generated by ratios of generators of , of . Since the basis exchange graph of a matroid is connected, it follows that is generated by elements of the form , where and are such that both and are in the support of .
The Tutte group can equivalently be defined in terms of hyperplanes, as explained in the following.
Definition 1.2.
Let be a matroid and its set of hyperplanes. We define as the abelian group generated by symbols and for all and modulo the relations
where are pairwise distinct such that is a flat of rank and for .
This group comes with a map that sends an element to the characteristic function of , i.e. for .
The relation between and is explained in [13, Thms. 1.1 and 1.2], which is as follows.
Theorem 1.3 (Dress-Wenzel ’89).
Let be a matroid and its set of bases. Then the association and , where , with and , defines an injective group homomorphism whose image is .
1.3. Embedded minors
In this section, we review some basic facts about minors of a matroid and introduce the concept of an embedded minor.
Let and be matroids with respective ground sets and . An isomorphism of matroids is a bijection such that is a basis of if and only if is a basis of .
Definition 1.4.
Let be a matroid on . A minor of is a matroid isomorphic to , where and are disjoint subsets of , denotes the deletion of in and denotes the contraction of in .
Note that there are in general different pairs of subsets and as above that give rise to isomorphic minors . In particular, [21, Prop. 3.3.6] shows that there is a co-independent subset and an independent subset of for every minor of such that and . Still, such and are in general not uniquely determined by , cf. Example 1.8.
If we fix and as above, then we can identify the ground set of with , which yields an inclusion . Since is co-independent and is independent, the set of bases of is
where is the set of bases of . Consequently, the difference between the rank of and the rank of is . Moreover, the inclusion induces an inclusion
Definition 1.5.
An embedded minor of is a minor together with the pair , where is a co-independent subset and is an independent subset of such that . By abuse of notation, we say that is an embedded minor, where for fixed subsets and as above and where is the induced inclusion of the respective set of bases.
Let be a matroid. Then we say that an embedded minor is of type , or is an embedded -minor, if is isomorphic to .
Let and be matroids. A minor embedding of into is an isomorphism of together with an embedded minor of .
Given two minor embeddings and , we define the composition of with as the minor embedding .
Example 1.6 (Embedded minors of type ).
Let be a matroid and an embedded minor of type . Let and be as above. Then since the rank of is , and has elements . The set of bases of consists of all -subsets of , and thus
Remark 1.7.
Note that a composition of minor embeddings induces a composition of inclusions of sets of bases. On the other hand, a minor embedding decomposes into with and for every pair of partitions and .
Note further that it is slightly inaccurate to suppress the subsets and from the notation of an embedded minor since they are in general not uniquely determined by the isomorphism type of and the injection , cf. Example 1.9. However, there is always a maximal choice for and for a given injection .
More precisely, for two disjoint subsets and of and , let . If is not empty, then is co-independent and is independent and is the image for the embedded minor of . Tautologically,
are the maximal co-independent and independent subsets of such that .
Example 1.8.
In the following, we illustrate how different choices of disjoint subsets and of lead to different injections .
Let be the matroid on whose set of bases is . Let be the restriction of to , whose set of bases is . Since there is no canonical map , it is clear that not every pair of disjoint subsets and leads to an embedding .
The minor is isomorphic to both and , which are embedded minors with respect to the inclusions with and with , respectively.
Example 1.9.
The contrary effect to that illustrated in Example 1.8 can also happen: different embedded minors can give rise to the same inclusions of sets of bases.
For instance, consider the matroid on with and the embedded minor . Then and the induced embedding is a bijection. This is obviously also the case for the trivial minor . This shows that is not determined by .
2. Pastures
2.1. Definition and first properties
By a monoid with zero we mean a multiplicatively written commutative monoid with an element that satisfies for all . We denote the unit of by and write for the group of invertible elements in . We denote by all elements of the form in the monoid semiring , where .
Definition 2.1.
A pasture is a monoid with zero such that , together with a subset of such that for all
-
(P1)
if and only if ,
-
(P2)
if , then is in ,
-
(P3)
there is a unique element such that .
We call the nullset of , and say that is null, and write symbolically , if . For , we call the weak inverse of .
The element plays the role of an additive inverse of , and the relations express that certain sums of elements are zero, even though the multiplicative monoid does not carry an addition. For this reason, we will write frequently for and for . In particular, we have . Moreover, we shall write or for .
Remark 2.2.
As a word of warning, note that is not an additive inverse of if considered as elements in the semiring , i.e. as elements of . Psychologically, it is better to think of “” as an involution on .
Definition 2.3.
A morphism of pastures is a multiplicative map with and such that in whenever in . This defines the category .
Definition 2.4.
A subpasture of a pasture is a submonoid of together with a subset such that for every nonzero and for all with .
Given a subset of , the subpasture generated by is the submonoid , where denotes the subgroup of generated by , together with the nullset .
Lemma 2.5.
Let be a pasture. Then if and only if . In particular, we have . Let be a morphism of pastures. Then .
Proof.
Note that is uniquely determined by the relation . By (P2), this implies that and thus by (P3), we conclude that , or equivalently, .
Given a morphism be a morphism of pastures, the null relation in yields the relation in . Thus is the weak inverse of , which is . ∎
2.1.1. Free algebras and quotients
Let be a pasture with null set . We define the free -algebra in as the pasture whose unit group is , where is the free abelian group generated by the symbols , and whose null set is
where stands for if and for if . This pasture comes with a canonical morphism of pastures that sends to .
Let be a set of relations of the form with . We define the quotient of by as the following pasture. Let be the smallest subset of that is closed under property (P2) and that contains and . Since all elements in have at least two nonzero terms by assumption, also satisfies (P1). But it might fail to satisfy (P3), necessitating the following quotient construction for .
We define the unit group of as the quotient of the group by the subgroup generated by all elements for which . The underlying monoid of is, by definition, , and it comes with a surjection of monoids. We denote the image of by , and define the null set of as the subset
of . The quotient of by comes with a canonical map that sends to and is a morphism of pastures.
If is a subset of relations of the form with , then the composition of the canonical morphisms for the free algebra and for the quotient yields a canonical morphism
We denote by the map that sends to .
The following result describes the universal property of , which is analogous to the universal property of the quotient of the algebra of Laurent polynomials over a field by the ideal generated by a set of Laurent polynomials (each with only two or three terms). Note that the special case yields the universal property of the free algebra and the special case yields the universal property of the quotient .
Proposition 2.6.
Let be a pasture, and a subset of relations of the form with . Let be a morphism of pastures and a map with the property that with and for implies that
Then there is a unique morphism such that the diagrams
and |
commute.
Proof.
We claim that the association
is a morphism of pastures. Once we have proven this, it is clear that and . Since the unit group of is generated by , it follows that is uniquely determined by the conditions and .
We are left with the verification that is a morphism. As a first step, we show that the restriction defines a group homomorphism. Note that . Thus we have an equality in if and only if for some . By our assumptions, we have , and thus multiplying with yields . This verifies that is well-defined as a map. It is clear from the definition that it is a group homomorphism.
For showing that is a morphism of pastures, we need to verify that for every element in , the element is in . This can be done by a similar argument as before. We omit the details. ∎
2.1.2. Examples
The regular partial field is the pasture whose multiplication is determined by .
Let be a field and its multiplicative monoid. Then we can associate with the pasture . We can recover the addition of by the rule if . In particular, we can identify the finite field with elements with the pasture , which implies that , and the finite field with elements with the pasture .
Let be a hyperfield and its multiplicative monoid. Then we can associate with the pasture . In particular, we can realize the Krasner hyperfield as , and the sign hyperfield as .
The near-regular partial field is
The dyadic partial field is
The hexagonal partial field is
It is a straightforward exercise to verify that these descriptions of agree with the definitions given in the introduction.
As final examples, the weak sign hyperfield is the pasture
and the phase hyperfield is the pasture whose unit group is the subgroup of norm -elements in and whose null set is
where is the smallest cone in that contains , and . In fact, is isomorphic to the quotient of the pasture associated with by the action of by multiplication.
2.1.3. Initial and final objects
The category admits both initial and final objects. The initial object of is the regular partial field . Given a pasture , we denote by the unique initial morphism .
The final object of is the Krasner hyperfield . Given a pasture , we denote by the unique terminal morphism sending to and every nonzero element of to .
2.1.4. Products and coproducts
The category admits both a product and coproduct.
Let be pastures. The (categorical) product can be constructed explicitly as follows. As sets, we have , endowed with the coordinatewise multiplication on , extended by the rule , and the nullset is the subset
of .
The categorical coproduct is given by the tensor product defined as follows. As sets, we have , where denotes the Cartesian product (not the underlying set of the product in the category of pastures) and if and only if either:
-
•
At least one of is zero and at least one of is zero; or
-
•
and ; or
-
•
and .
Denoting the equivalence class of by , the additive relations are given by:
-
•
for and with .
-
•
for and with .
Lemma 2.7.
The tensor product of pastures satisfies the universal property of a coproduct with respect to the morphisms and given by and , respectively.
Proof.
Given a pasture and morphisms for , we must show that there is a unique morphism such that for .
Define by the formula . To see that this is well-defined, suppose . If and , then . Otherwise for with , and we have
Hence is well-defined.
It is straightforward to verify that for and that is a morphism.
To see that is unique, suppose is another such morphism. Then and , and since is a morphism we have
for all and . Thus . ∎
By comparison, the category of fields (which is a full subcategory of ) does not have an initial object, a final object, products, or coproducts.
Example 2.8.
We have and . The first isomorphism follows easily from our formula for the product of two pastures, and the second is an immediate consequence of the following lemma, which in turn follows easily from the universal property of the coproduct.
Lemma 2.9.
If , where , then .
Example 2.10.
We have and . For the first isomorphism, note that the underlying set of is while the underlying set of is . One checks easily that the map sending to and to is an isomorphism of pastures. The second isomorphism is a consequence of Lemma 2.9.
Example 2.11.
Here (without proof) are a few more examples of products and coproducts:
-
•
.
-
•
.
-
•
.
Remark 2.12.
More generally, one can show that the category is complete and co-complete, i.e., it admits all small limits and colimits. In particular, one can form arbitrary fiber products and fiber coproducts in . We omit the details since we will not need these more general statements in the present paper.
2.1.5. Comparison with partial fields, hyperfields, fuzzy rings, tracts and ordered blueprints
The definitions of partial fields, hyperfields, fuzzy rings, tracts and ordered blueprints, and a comparison thereof, can be found in [5]. We are not aiming at repeating all definitions, but we will explain how the category of pastures fits within the landscape of these types of algebraic objects.
We have already explained how partial fields and hyperfields give rise to pastures. The tract associated with a pasture is defined as , where is the ideal generated by in . The ordered blueprint associated to a pasture is defined as .
These associations yield fully faithful embeddings of the category of partial fields and the category of hyperfields into , and of into the category of tracts and into the category of ordered blueprints with unique weak inverses. This completes the diagram of [5, Thm. 2.21] to
where is the category of fuzzy rings. This diagram commutes and all functors are fully faithful, with exception of the adjunction between and . We omit the details of these claims.
Note that fuzzy rings, seen as objects in either or , are not pastures in general since the ideal of the fuzzy ring might not be generated by -term elements of . Conversely, not every pasture, seen as a tract or as an ordered blueprint, gives rise to a fuzzy ring since the axiom (FR2) (in the notation of [5, Section 2.4]) might not be satisfied. An example of a pasture for which (FR2) fails to hold is the pasture ; cf. [5, Ex. 2.11] for more details on this example.
2.2. Matroid representations
We recall the notion of weak matroids over pastures from [3]. Let be a pasture. A weak Grassmann–Plücker function of rank on with values in is a function such that:
-
(1)
The set of -element subsets such that is the set of bases of a matroid .
-
(2)
for all permutations .
-
(3)
satisfies the 3-term Plücker relations: for all and all ,
Two weak Grassmann–Plücker functions are isomorphic if there is a such that for all .
A weak -matroid of rank on is an isomorphism class of weak Grassmann–Plücker functions .
We call the underlying matroid of , and we refer to as a -representation of .
We say that a matroid is representable over a pasture if there is at least one -representation of .
Remark 2.13.
In [3] one also finds a definition of strong -matroids, but this will not play a role in the present paper. We therefore omit the adjective “weak” when talking about -representations.
With this terminology, we introduce the following subclasses of matroids:
Definition 2.14.
A matroid is
-
•
regular if it is representable over ;
-
•
binary if it is representable over ;
-
•
ternary if it is representable over ;
-
•
quaternary if it is representable over ;
-
•
near-regular if it is representable over ;
-
•
dyadic if it is representable over ;
-
•
hexagonal if it is representable over ;
-
•
-representable555In [24, p. 55], the partial field is denoted . if it is representable over ;
-
•
representable if it representable over some field;
-
•
orientable if it is representable over .
-
•
weakly orientable if it is representable over .
2.3. Matroid representations via hyperplane functions
There are various “cryptomorphic” descriptions of weak -matroids, for example in terms of “weak -circuits”, cf. [3]. For the purposes of the present paper, it will be more convenient to reformulate things in terms of hyperplanes rather than circuits.
Definition 2.15.
Let be a pasture and let be a matroid on the finite set . Let be the set of hyperplanes of .
-
(1)
Given , we say that is a -hyperplane function for if if and only if .
-
(2)
Two -hyperplane functions for are projectively equivalent if there exists such that for all .
-
(3)
A triple of hyperplanes is modular if is a flat of corank such that for all distinct .
-
(4)
A modular system of -hyperplane functions for is a collection of -hyperplane functions , one for each , such that whenever is a modular triple of hyperplanes in , the corresponding functions are linearly dependent, i.e., there exist constants in , not all zero, such that
for all .
-
(5)
Two modular systems of -hyperplane functions and are equivalent if and are projectively equivalent for all .
The following result can be viewed as a generalization of “Tutte’s representation theorem” [33, Theorem 5.1] (compare with [15, Theorem 3.5]). One can also view it as adding to the collection of cryptomorphisms for weak matroids established in [3].
Theorem 2.16.
Let be a pasture and let be a matroid of rank on . Let be the set of hyperplanes of . There is a canonical bijection
If is a -representation of and , then
for every , elements and such that is an independent set which spans .
Proof.
Let be a weak -matroid with underlying matroid . Let be a hyperplane of . The complement of in is a cocircuit of ; choose a -cocircuit of whose support is . Now define by . Then iff iff iff , so is a -hyperplane function for .
Suppose is a modular triple of hyperplanes of with intersection , a flat of corank 2. Let be an element of . Then by the covering axiom for flats [21, Exercise 1.4.11, Axiom (F3)]. Let and be the -cocircuits of corresponding to and , respectively, and let . Then , so by [3, Axiom ], there is a -cocircuit of such that and for all . By [3, Lemma 3.7], the support of is . By [3, Axiom (C2)], is a scalar multiple of , say . Then , so is a modular system of -hyperplane functions for .
Conversely, a similar argument shows that given a modular system of -hyperplane functions for , there is a corresponding family of -cocircuits defining a weak -matroid . These operations are inverse to one another by construction, and this establishes the desired bijection.
We turn to the second claim, which is obvious for , so we may assume that . Let and choose such that . Note that since is a basis of , the complement is a basis for . If and , we define a total order on by
By [3, Lemma 4.1], there is a dual Grassmann-Plücker function to that satisfies
and
where is the identity and is the transposition that exchanges with . This implies that
as desired, where we use [3, Def. 4.6 and Lemma 4.7] for the first equality. ∎
2.4. The universal pasture
The universal pasture of a matroid was introduced in [5] as a tool to control the representations of a matroid over other pastures. We review this in the following.
The symmetric group on elements acts by permutation of coefficients on . In the following, we understand the sign of a permutation as an element of .
Definition 2.17.
Let be a matroid with Grassmann-Plücker function . The extended universal pasture of is the pasture , where is the set of the relations for all and , together with the -term Plücker relations
for all and .
The pasture is naturally graded by the rule that has degree for every . The universal pasture of is the subpasture of degree -elements of .
The relevance of the universal pasture is that it represents the set of isomorphism classes of -representations of . This is derived in [5] by means of the algebraic geometry of the moduli space of matroids. We include an independent, and more elementary, proof in the following.
Theorem 2.18 ([5, Prop. 6.22]).
Let be a matroid of rank on and a pasture. Then there is a functorial bijection between the set of isomorphism classes of -representations of and . In particular, is representable over if and only if there is a morphism .
Proof.
Let be a -representation of and the extended universal pasture of . Define the map from the set of generators of to . Let be the set of -term Plücker relations
where and such that has elements. Applying to this relation, with the convention that if , yields
which is an element of since is a Grassmann-Plücker function. Thus, by Proposition 2.6, the map together with the unique morphism define a morphism
with for . We define as the composition of the inclusion with . Since every element of has degree , we have for every , which shows that depends only on the isomorphism class of .
This yields a canonical map
which turns out to be a bijection whose inverse can be described as follows. Let be a morphism. Choose an such that is a basis of and define the map
This is a Grassmann-Plücker function, since
is in the nullset of . Note that the isomorphism class of is independent of the choice of , since any two such choices yield Grassmann-Plücker functions that are constant multiples of each other.
It is straightforward to verify that the associations and are mutually inverse, and that both maps are functorial in ; we omit the details. ∎
Remark 2.19.
We call the morphism associated with the (isomorphism class of a) -representation the characteristic morphism.
The proof of Theorem 2.18 also shows that the set of -representations of are in functorial bijection with . Under this identification, the identity morphism defines a -representation of , which we call the universal Grassmann-Plücker function of . It satisfies if is a basis of and otherwise, and is a Grassmann-Plücker function for where is the terminal morphism, cf. section 2.1.3.
2.5. The Tutte group and the universal pasture
The connection between the Tutte group and the universal pasture is explained in Theorem 6.26 of [5], which is as follows:
Theorem 2.20.
Let be a matroid with Grassmann-Plücker function . The association and for defines an isomorphism of groups that restricts to an isomorphism .
Remark 2.21.
Dress and Wenzel show in [15, Thm. 3.7] that a matroid is representable over a fuzzy ring if and only if there is a group homomorphism that preserves the Plücker relations. This can be seen as an analogue of Theorem 2.18 in the formalism of Dress and Wenzel, but it also lets us explain the advantage of our formulation.
Namely, the foundation of a matroid is an object in the same category as the coefficient domains for matroid representations. We can thus use standard arguments from category theory to deduce results about the representability of a matroid. For example, if the foundation of a matroid is the tensor product of two pastures and , then is representable over a third pasture if and only if there exist morphisms and . We will make a frequent use of this observation in section 6.
3. Cross ratios
In this section, we review the theory of cross ratios for matroids from different angles, and explain the connection between these viewpoints, which are derived from cryptomorphic descriptions of a matroid in terms of bases and hyperplanes. There are two principally different types of cross ratios: cross ratios for -matroids, which are elements of , and universal cross ratios of a matroid , which are elements of the universal pasture of . It turns out that there is a close relation between these two types of cross ratios and their different incarnations in terms of bases and hyperplanes. In particular, we identify in a concluding subsection the set of universal cross ratios with the set of fundamental elements in .
3.1. Cross ratios of -matroids
Let and . Let be a pasture and a -matroid with Grassmann-Plücker function .
Define to be the set of tuples for which there exists a with underlying set such that
where .
Definition 3.1.
Let be a -matroid with Grassmann-Plücker function and . The cross ratio of in is the element
of for any with .
Note that the value of the cross ratio does not depend on the ordering of , nor on the choice of Grassmann-Plücker function for , which justifies our notation.
We find the following relations between cross ratios with permuted arguments. Let and be such that . We say that is non-degenerate if
or equivalently, if is defined and nonzero for every permutation of . We define to be the subset of consisting of all non-degenerate . We call a cross ratio non-degenerate if is non-degenerate. We call degenerate if it is not in .
One finds some relations that follow immediately from the definition, such as the fact that permuting rows and columns has no effect on the value of the cross ratio, i.e.
that permuting the last two entries inverts the cross ratio, i.e.
and that a cyclic rotation of the last three entries yields the relation
if is non-degenerate. We will discuss these relations and others in detail in Theorem 4.20.
The cross ratios keep track of the Plücker relations
(2) |
satisfied by the Grassmann-Plücker function . Namely, if and are such that , then dividing both sides of the Plücker relation (2) by yields the Plücker relation for cross ratios
where the notation in a pasture is short-hand for .
If is degenerate, then and dividing the Plücker relation by yields , and thus
by the uniqueness of additive inverses in .
Lemma 3.2.
Let be a pasture and a -matroid of rank on with dual . Let and . Then
as elements of .
Proof.
Let . Choose with and with . Choose a total order on . Let be a Grassmann-Plücker function for . Then by [3, Lemma 4.2], there is a Grassmann-Plücker function for such that for all identifications , we have
where is the permutation of such that
in the chosen total order of . Since for the transposition that exchanges and , we have . Thus we obtain
as claimed. ∎
3.2. Cross ratios for hyperplanes
There is a different, but closely related, notion of cross ratios associated to certain quadruples of hyperplanes.
Definition 3.3.
Let be a matroid of rank on and be its set of hyperplanes. A quadruple of hyperplanes is modular if is a flat of corank such that for all and . A modular quadruple is non-degenerate if for all distinct . Otherwise it is called degenerate.666Note that in some papers the term “modular quadruple” is used for what we call a non-degenerate quadruple; e.g. see [3], [7, Def. 5.1] and [25, Def. 3.18]. We denote the set of all modular quadruples of hyperplanes by and the subset of all non-degenerate modular quadruples by .
Definition 3.4.
Let be a pasture and a -matroid with underlying matroid . Let . The cross ratio of in is the element
of , where is a -hyperplane function for for (cf. Definition 2.15), and where for with .
Since and are determined by and up to a factor in , the definition of is independent of the choices of and . It follows from [3, Theorem 3.21, Lemma 4.5, and Definition 4.6] that it is also independent of the choices of and .
We continue with a comparison of the two notions of cross ratios.
Lemma 3.5.
Let be a matroid of rank on . The association with for defines a surjective map , which restricts to a surjective map .
Proof.
The flat is of rank since is an independent set of rank . We have for all and since and thus . This shows that is indeed a modular quadruple. By the same reasoning applied to arbitrary distinct , we conclude that restricts to a map .
Given and , choose an independent subset with elements and for . Since for and , the closure of is , i.e. is a basis of . Thus and , which establishes the surjectivity of . If , then and thus is a basis of for all distinct . Thus and , which establishes the surjectivity of . ∎
Proposition 3.6.
Let be a pasture and a -matroid with underlying matroid . Let and . Then we have
as elements of .
Proof.
Since is an -set that generates and for and , we can apply Theorem 2.16 to conclude that
as claimed. ∎
Our comparison of different notions of cross ratios has the following immediate consequence.
Corollary 3.7.
Let be a matroid and . If for , then .
Proof.
By Proposition 3.6, we have if for . ∎
3.3. Universal cross ratios
Let be a matroid of rank on with Grassmann-Plücker function .
Recall from section 2.4 the definition of the extended universal pasture
of , where contains the relations and the -term Plücker relations
for all and , where we use the convention if . The universal Grassmann-Plücker function for sends to if is a basis of , and to otherwise. The universal -matroid for is defined by the Grassmann-Plücker function , where is any -tuple with .
Definition 3.8.
Let be a matroid with universal -matroid . Let and . The universal cross ratio of is the element
of , and the universal cross ratio of is the element
of .
The relation between cross ratios of a -matroid and the universal cross ratio of the underlying matroid is explained in the following statement.
Proposition 3.9.
Let be a pasture and a -matroid with Grassmann Plücker function . Let be the underlying matroid and its universal pasture. Let be the universal morphism associated with , which maps to . Then
as elements of for every .
Proof.
This follows directly from the definitions of , and the (universal) cross ratios. ∎
3.4. Fundamental elements
Universal cross ratios can be characterized intrinsically as the fundamental elements of the universal pasture of a matroid. To the best of our knowledge, the importance of fundamental elements in the study of matroid representations goes back to Semple’s paper [26], where this concept was introduced in the context of partial fields. We extend the notion of fundamental elements to pastures and explain its relation to universal cross ratios in the following.
The property of cross ratios that lead to the definition of fundamental elements are the -term Plücker relations
for a Grassmann-Plücker function , where and . If for all distinct , then division by yields
for the non-degenerate cross ratios and in .
Definition 3.10.
Let be a pasture. A fundamental element of is an element such that for some .
Proposition 3.11.
Let be a matroid. For an element , the following are equivalent:
-
(1)
is a fundamental element of ;
-
(2)
for some ;
-
(3)
for some .
Proof.
Our preceding discussion shows that for . Thus (2)(1). The equivalence of (2) and (3) follows from Proposition 3.6.
We are left with (1)(2). Assume that is a fundamental element, i.e. for some . Since the nullset of the extended universal pasture is generated by the -terms Plücker relations, there must be an element such that is of the form
for some and such that is a basis of for all distinct , i.e. where . After a suitable permutation of , we can assume that and . Thus
is a cross ratio, as claimed. ∎
3.5. Compatibility with the Tutte group formulation of Dress and Wenzel
We provide a comparison of the different types of universal cross ratios, as introduced above, with the cross ratios introduced by Dress and Wenzel in [14, Def. 2.3].
The image of a universal cross ratio under the isomorphism from Theorem 2.20 appears implicitly already in [13, Prop. 2.2], and is as follows.
Lemma 3.12.
Let be a matroid with Grassmann-Plücker function , Tutte group and universal pasture . Let be the isomorphism of groups that sends to for . Then
for all and with .
Proof.
Note that the ratio does not depend on the ordering of . The rest follows immediately from the definitions. ∎
Let be a modular quadruple of hyperplanes of and the corank flat contained in all . Let and . The Dress–Wenzel universal cross ratio of is the element
of the group .
As shown in [14, Lemma 2.1], this definition is independent of the choices of and . Since , it follows from Theorem 1.3 that is contained in the image of the injection .
Lemma 3.13.
Let be the group homomorphism that maps to where , , , , and are bases of . Let be a modular quadruple of hyperplanes of . Then
4. Foundations
The foundation of a matroid is the subpasture of degree -elements of the universal pasture , and it represents the functor taking a pasture to the set of -rescaling classes of . In particular, just as with , the foundation can detect whether or not a matroid is representable over a given pasture in terms of the existence of a morphism from to .
One advantage of the foundation over the universal pasture is that, because of some deep theorems due to Tutte, Dress–Wenzel, and Gelfand–Rybnikov–Stone, there is an explicit presentation of in terms of generators and relations in which the relations are all inherited from “small” embedded minors. More precisely, the foundation of is generated by the universal cross ratios of , and all relations between these cross ratios are generated by a small list of relations stemming from embedded minors of having at most elements.
We begin our discussion of foundations by reviewing some facts which were proved in the authors’ previous paper [5]. Next we explain the role of embedded minors in the study of foundations. We then exhibit, through very explicit computations, the relations between universal cross ratios inherited from small minors which enter into the presentation by generators and relations alluded to above. Finally, we use the aforementioned result of Gelfand, Rybnikov and Stone to prove that these relations generate all relations in between universal cross ratios.
4.1. Definition and basic facts
Let be a matroid of rank on with extended universal pasture . For a subset of , let be the characteristic function of , which is an element of . The multidegree is the group homomorphism
where . It is easily verified that this map is well-defined, cf. [5, section 7.3]. The degree in is the function that is the composition of with the canonical projection to the -th component, i.e. if and if . The total degree is the function that is the sum over for all , i.e. .
Definition 4.1.
Let be a matroid with extended universal pasture . The foundation of is the subpasture of that consists of and all elements of multidegree .
Note that the universal pasture of is the subpasture of that is generated by all units of total degree . Since if , the foundation of is a subpasture of .
The relevance of the foundation of is the fact that it represents the rescaling class space
considered as a functor in .
Theorem 4.2 ([5, Cor. 7.26]).
Let be a matroid and a pasture. Then there is a functorial bijection . In particular, is representable over if and only if there is a morphism .
Recall from [13] that the inner Tutte group of a matroid is defined as the subgroup of the Tutte group of that consists of all elements of multidegree , where the multidegree is defined in the same way as the multidegree . This yields at once the following consequence of Theorem 2.20 (cf. [5, Cor. 7.11]).
Corollary 4.3.
The canonical isomorphism restricts to an isomorphism .
4.2. Universal cross ratios as generators of the foundation
Let be a matroid of rank on and its extended universal pasture. The simplest type of elements of with multidegree are universal cross ratios
where and such that . This formula shows that the universal cross ratios are elements of the foundation of . It is proven in [5, Cor. 7.11] that the foundation is generated by the universal cross ratios. To summarize, we have:
Theorem 4.5.
Let be a matroid. Then for every , and is generated by the collection of all such universal cross ratios.
Using Proposition 3.6, we obtain:
Corollary 4.6.
Let be a matroid. Then for every , and is generated by the collection of all such hyperplane universal cross ratios.
4.3. The foundation of the dual matroid
Let be a matroid of rank on and its universal pasture. By definition the identity morphism is the characteristic morphism of the universal -matroid ; cf. Theorem 2.18. The underlying matroid of is . The underlying matroid of the dual -matroid of is the dual of , cf. [3, Thm. 3.24]. Let be the characteristic morphism of .
Proposition 4.7.
Let be a matroid of rank on . Then is an isomorphism of pastures that restricts to an isomorphism between the respective foundations of and . Let . For every , and such that , we have
and for every and , we have and
where is the universal -matroid of and is the universal -matroid of .
Proof.
The construction of , applied to in place of , yields a morphism . Since , we have . The composition is the characteristic morphism of the double dual of , which is equal to by [3, Thm. 3.24], and thus is the identity of . Similarly, the composition is the identity of . This shows that and are mutually inverse isomorphisms.
Let be a Grassmann-Plücker function for . Endow with a total order and define as the sign of the permutation of such that if are pairwise distinct. Then by [3, Lemma 4.1], there is a Grassmann-Plücker function for that satisfies
for all pairwise distinct . Thus if , and are as in the hypothesis of the theorem, then
as claimed. If and , then is a basis for , and thus is a basis for for all and . Thus . The image of the corresponding cross ratio under is
where such that and where we use Lemma 3.2 for the last equality. Since the foundations of and are generated by cross ratios, it follows at once that restricts to an isomorphism . ∎
4.4. Foundations of embedded minors
Let be a matroid of rank on , and let be the universal -matroid associated with , whose characteristic function is the identity map on ; cf. Theorem 2.18. Let be a Grassmann-Plücker function for ; e.g. we can choose some such that is a basis of and define if is a basis of and if not.
Let be an embedded minor of . Let be its rank and its ground set. Choose an ordering of the elements of . By [3, Lemma 4.4], the function
is a Grassmann-Plücker function that represents and its isomorphism class is independent of the choice of ordering of . The characteristic function of the -matroid is a morphism ; once again cf. Theorem 2.18.
Proposition 4.8.
Let be a matroid of rank on and an embedded minor of rank on . Let . Then the morphism satisfies the following properties.
-
(1)
For all such that and are bases of , we have
-
(2)
The identification yields a commutative diagram
of pastures, where and are the isomorphisms from Proposition 4.7.
-
(3)
The morphism restricts to a morphism between the foundations of and . For , we have and
-
(4)
If every element in is a loop and if every element in is a coloop, then is an isomorphism. If every element in is a loop or parallel to an element in and if every element in is a coloop or coparallel to an element in , then is an isomorphism.
Proof.
Property (1) follows from the direct computation
We continue with (2). Let be the corank of and the corank of . Choose an ordering . Let , and be such that , which are the assumptions needed to apply Proposition 4.7 to . Since is generated by elements of the form , the commutativity of the diagram in question follows from
Note that we can apply Proposition 4.7 to since .
We continue with (3). If , then for all and , the set is a basis of and thus is a basis of . Thus . Let such that . Then
By Theorem 4.5, the foundation of a matroid is generated by its cross ratios. Thus the previous calculation shows that restricts to a morphism which maps to .
We continue with (4). By successively deleting or contracting one element at a time, it suffices to prove the claim for . Using (2), we can assume that and . If is a loop, then defines a bijection between the set of bases of and the set of bases of . Moreover, for every , we have , which provides an identification . Thus and have the same generators and the same -term Plücker relations, so is an isomorphism. This argument also shows that is an isomorphism.
If is parallel to an element , then for every subset of . Thus for and with either or and for , we have if and only if , and . This shows that is an isomorphism, which completes the proof. ∎
An immediate consequence of Proposition 4.8 is the following.
Corollary 4.9.
The foundation of a matroid is isomorphic to the foundation of its simplification and isomorphic to the foundation of its cosimplification.
Proof.
This follows at once from Proposition 4.8, since the simplification of a matroid is an embedded minor of of the form , where consists of all loops of and a choice of all but one element in each class of parallel elements. Similarly, the cosimplification of is an embedded minor of of the form , where consists of all coloops of and a choice of all but one element in each class of coparallel elements. ∎
Another consequence of Proposition 4.8, which we will utilize constantly in the upcoming sections, is the following observation. Since a universal cross ratio involves only bases that contain and have a trivial intersection with , we have
for the morphism from Proposition 4.8. Thus every universal cross ratio in is the image of a universal cross ratio of an embedded minor of rank on a -element set .
4.5. The foundation of
Let be the uniform minor of rank on the set , which is represented by the Grassmann-Plücker function with . The cross ratios of are of the form
for some permutation of . Since permuting columns and rows in does not change the cross ratio, as pointed out in section 3.1, we have
Thus we can assume that , and with this convention, we find that each of the 24 possible cross ratios is equal to one of the following six:
They satisfy the following two types of multiplicative relations
and the Plücker relations
These relations can be illustrated in the form of a hexagon, see Figure 1. The three edges with label refer to relations of type (4.5), the three edges with label refer to the Plücker relations (4.5), and the two inner triangles refer to the relations of type (4.5).
Note that we can rewrite the relations of type (4.5) as , and so forth, which highlights an analogy with the Plücker relations . This makes the meaning of the edge labels and easy to remember.
Proposition 4.10.
Let and . Then the foundation of is
In particular, we have
Proof.
By relation (4.5), is generated by the cross ratios
By relation (4.5), we have
Relation (4.5), paired with (4.5), yields
Applying (4.5) once again yields
By (4.5), we have . This shows that the foundation of is a quotient of .
There are several different ways to show that there are no further relations in aside from those already present in , for example:
-
(1)
One can work this out “by hand”.
-
(2)
One can utilize the fact that is near-regular, which implies that there is a morphism .
- (3)
We explain a fourth route, which uses a theorem of Dress and Wenzel determining the inner Tutte group of a uniform matroid. In the case of , [13, Thm. 8.1], paired with Corollary 4.3, shows that . We conclude that the quotient map is an isomorphism between the underlying monoids. We are left with showing that every relation in the nullset of comes from , which is the intersection of the nullset of with . Since is generated by the single term
where we use the short-hand notation , every term in is a multiple of . This shows that is an isomorphism. ∎
Morphisms from into another pasture can be studied in terms of pairs of fundamental elements:
Definition 4.11.
A pair of fundamental elements in is an ordered pair of elements such that .
Lemma 4.12.
Let be a pasture. Then there is a bijection between with the set of pairs of fundamental elements.
Proof.
Every morphism maps and to invertible elements in . Since , we have in , which shows that is a pair of fundamental elements. This defines a map , where is the set of pairs of fundamental elements in .
Since is determined by the images of and , we see that is injective. On the other hand, for every pair of fundamental elements in , the map and extends to a morphism . Thus is surjective as well. ∎
Recall that a reorientation class is a rescaling class over the sign hyperfield . The following corollary is well known:
Corollary 4.13.
The rescaling classes of over a field are in bijection with , and has reorientation classes.
Proof.
If is a field, then is uniquely determined by , and both belong to precisely when , which establishes the first claim. The second claim follows from the observation that in if and only if is one of the pairs , and . ∎
4.6. The tip and cotip relations
In this section, we exhibit two types of relations that occur for matroids of ranks and , respectively, on the five element set .
As in the case of the uniform matroid , we write for in the case of a rank -matroid . We also use the shorthand notation and .
Lemma 4.14.
Let be a matroid of rank on . Assume that is a basis of for all and all . Then
Proof.
Equation (4.14) follows from the direct computation
We call equation (4.14) the tip relation with tip and cyclic orientation . The reason for this terminology is that in the case of the uniform matroid , the three cross ratios in equation (4.14) stem from three octahedrons in the basis exchange graph of , which share exactly one common vertex, or tip, which is .
Note that if is not uniform, i.e. some -subsets of are not bases, then some of the cross ratios in equation (4.14) are trivial. We will examine this situation in more detail in section 5.1.
In the case of a matroid of rank , we write for .
Lemma 4.15.
Let be a matroid of rank on . Assume that is a basis of for all and all with . Then
Proof.
Equation (4.15) follows from the direct computation
We call equation (4.15) the cotip relation with cotip and cyclic orientation . Similar to the rank -case, we use this terminology since in the case of the uniform matroid , the three cross ratios in equation (4.15) stem from three octahedrons in the basis exchange graph of , which share exactly one common vertex, which is . Therefore we call the complement of this common vertex the cotip.
Note that the tip and cotip relations are both invariant under permuting and under cyclic permutations of . Any other permutation of will produce another tip or cotip relation, provided that all involved values of are nonzero.
4.7. Relations for parallel elements
In this section, we exhibit a type of relation between universal cross ratios that stems from parallel elements. As in the previous section, we write for .
Lemma 4.16.
Let be a matroid of rank on and assume that and are parallel elements, i.e. is a circuit of . If for , then
Proof.
By our assumptions, every subset of the form with , and is a basis of , but no basis contains both and . Thus and are degenerate tuples in , and thus . With this, equation (4.16) follows from the computation
4.8. The foundation of the Fano matroid and its dual
In this section, we show that the Fano matroid and its dual impose the relation on their foundation, which is . This already follows from [5, Thms. 7.30 and 7.33], using the fact that and are not regular. Here we offer a proof in terms of a direct calculation that does not rely on knowledge of the representability of .
The Fano matroid is the rank matroid on represented by the Grassmann-Plücker function with for , where we read and modulo , and otherwise. Thus the family of circuits is , together with all -element subsets that do not contain one of these, which can be illustrated as follows:
Lemma 4.17.
The foundation of both the Fano matroid and its dual is .
Proof.
Since the foundation of is isomorphic to the foundation of , it is enough to prove the lemma for the Fano matroid. Throughout the proof, we read expressions like and modulo for all .
Since the rank of is , the set of a tuple is a singleton, i.e. for some . The element is contained in the three circuits , and whose union is equal to . By the pigeonhole principle, we must have for some and . Since are pairwise distinct, is not a basis. This shows that every is degenerate, and thus . We conclude that is a quotient of .
We use the shorthand notations and in the following. Note that and for every permutation of . We calculate that
This shows that the foundation of is a quotient of . Since does not contain any -minors, all cross ratios are degenerate and thus the nullset of does not contain any -term relations. We conclude that . ∎
4.9. A presentation of the foundation by hyperplanes
Gelfand, Rybnikov and Stone exhibit in [16, Thm. 4] a complete set of multiplicative relations in the inner Tutte group of between the cross ratios of modular quadruples of circuits, which results in essence from Tutte’s homotopy theorem. Since hyperplanes are just complements of circuits of the dual matroid, this set of relations yields at once a complete set of relations for cross ratios of modular quadruples of hyperplanes.
Theorem 4.18.
Let be a matroid with foundation . Then
where is defined by the multiplicative relations
if the Fano matroid or its dual is a minor of ;
for all ;
for all degenerate ;
for all ;
for all ;
for all ; and
where for five pairwise distinct corank -flats that contain a common flat of corank such that and ,
as well as the additive Plücker relations
for all .
Proof.
The theorem follows by translating the relations between cross ratios in for modular quadruples of cycles of the dual matroid from [16, Thm. 4] to the hyperplane formulation by replacing a cocycle by the hyperplane . To pass from the inner Tutte group to the foundation, we employ Lemma 3.13, which identifies with under the canonical isomorphism .
Using this translation, relation (4.18) is equivalent to (TG0) and (CR5) in [16]. Relation (4.18) is equivalent to (CR3). Relation (4.18) is equivalent to (CR1). Relation (CR4) is equivalent to (4.18) (in the case that one cross ratio is degenerate) and (4.18) (in the case that all cross ratios are non-degenerate). Relation (4.18) is equivalent to (CR4). Relation (4.18) is equivalent to (CR6), where we observe that the degenerate case in [16] reduces (CR6) to (CR1). Finally note that the -term Plücker relations of are captured in (4.18). ∎
Remark 4.19.
We include a discussion of relation (4.18), which has the most complicated formulation among the relations of Theorem 4.18. Since all flats contain a common flat of corank , this constellation comes from a minor of rank , which has corank -flats corresponding to . In the non-degenerate situation where all hyperplanes are pairwise distinct, this minor is of type , and the containment relation of the and can be illustrated as on the right-hand side of Figure 2.
The original formulation of Gelfand, Rybnikov and Stone concerns points, which are circuits, and lines, which are unions of circuits having projective dimension 1. To pass from our formulation to that of Gelfand-Rybnikov-Stone, we take the complement of a hyperplane , which is a circuit of the dual matroid. Thus, in the non-degenerate case, axiom (CR6) expresses the point-line configuration of , which we illustrate on the left-hand side of Figure 2. The lines are the complements of the flats , and therefore the union of the circuits (with varying ).
Note that there are two degenerate situations that (CR6) allows for: (a) three lines, say , and , intersect in one point ; this case corresponds to the point-line arrangement of a parallel extension of , which we denote by in section 5.1.3; and (b) two lines agree; this case corresponds to the point-line arrangement of .
4.10. A presentation of the foundation by bases
Using the relation between cross ratios for modular quadruples of hyperplanes and universal cross ratios for , as exhibited in Proposition 3.6, we derive from Theorem 4.18 the following description of a complete set of relations between universal cross ratios. The possibility of such a deduction was observed and communicated to us by Rudi Pendavingh, who proves a similar result in the joint work [10] in progress with Brettell.
Theorem 4.20.
Let be a matroid with foundation . Then
where is defined by the multiplicative relations
if the Fano matroid or its dual is a minor of ;
for all ;
for all degenerate ;
for all ;
for all ;
for all and such that each of , and is in ;
for all and such that , and are in ;
for all and such that and such that and are in ;
as well as the additive Plücker relations
for all .
Proof.
By Proposition 3.6, we have for every and for . Thus (4.20)–(4.20) follow from (4.18)–(4.18). To see that (4.20) implies (4.18), define for given and as in (4.20) the corank -flats for , which are pairwise distinct and contain the common flat of corank , as required. For , we define hyperplanes . Then we have for all identifications that
which shows that (4.18) implies (4.20). The relation (4.20) follows from
where is -th coefficient of the common image of and under .
We are left to show that if , i.e. if for . We will prove this by replacing one element of by an element of at a time. Note that both and are bases of the restriction , where is the flat of rank generated by and . Since the basis exchange graph of is connected, we find a sequence of bases for such that and for and some and . Considered as subsets of , we have and thus for all . Thus we can apply (4.20), which yields
We conclude that .
Next we replace the by the , one at a time. After permuting rows and columns appropriately, which does not change the value of the cross ratio by (4.20), we are reduced to studying cross ratios of the forms and such that is a hyperplane. By (4.20), we have
Since is a hyperplane, the subset of has rank and is not a basis of . Thus by (4.20), which shows that
where we use (4.20) for the last equality. We conclude that
as desired. This completes the proof of the theorem. ∎
Corollary 4.21.
Proof.
By Theorem 4.20, the foundation is generated by the universal cross ratios of , which are the images of the universal cross ratios of minors on elements ; cf. Proposition 4.8. The morphisms testify that all relations of also hold in , and therefore we conclude that is of the form
for some set of -term relations , where denotes the ground set of . A priori, this holds if we include all relations (4.20)–(4.20) of Theorem 4.20 in . To reduce this to the assertion of the corollary, we observe the following.
If is a minor on elements that is not of type , then is regular and . Thus we can omit these factors from the tensor product. Note that (4.20) assures that the cross ratios coming from such a minor are trivial in . Therefore we can omit (4.20) from .
4.11. A presentation of the foundation by embedded minors
Let and be two embedded minors of a matroid . If and , then is an embedded minor of . We write for the inclusion as embedded minors and for the induced morphism between the respective foundations.
Theorem 4.22.
Let be a matroid with foundation . Let be the collection of all embedded minors of on at most elements with the following properties:
-
•
if has at most elements, then it contains a minor of type ;
-
•
if has exactly elements, then it contains two parallel elements;
-
•
if has elements, then it is isomorphic to or .
Then
where the set is generated by the relations for every inclusion of embedded minors and in .
Proof.
It is clear that the morphisms from Proposition 4.8 induce a canonical morphism , and since contains all embedded -minors of , this morphism is surjective. Thus we are left with showing that contains all defining relations of .
Let us define for where denotes the ground set of the embedded minor . Then . The set consists of the embedded -minors of , and thus
by Corollary 4.21, where contains all relations of types (4.20) (in the presence of an or -minor) and (4.20)–(4.20).
The relations (4.20) and (4.20) stem from embedded minors on elements, and these relations involve a nondegenerate cross ratio only if contains a -minor, i.e. . Thus (4.20) and (4.20) can be replaced by tensoring with and including the relations for every minor embedding with .
Similarly, (4.20) stems from embedded minors on elements with two parallel elements, and involves a nondegenerate cross ratio only if contains a -minor, i.e. . Thus (4.20) can be replaced by tensoring with and including the relations for every minor embedding with .
The set consists of all embedded minors of types and . Since and for every pasture , we can replace the relation (4.20) by if . This recovers all relations in and completes the proof. ∎
5. The structure theorem
In this section, we prove the central result of this paper, Theorem 5.9, which asserts that the foundation of a matroid without large uniform minors is isomorphic to a tensor product of finitely many copies of the pastures , , , and .
This is done by first showing that in the absence of large uniform minors, the tip and cotip relations are of a particularly simple form, which eventually leads to the conclusion that the foundation of is the tensor product of quotients of by automorphism groups, and possibly . The quotients of by automorphisms are precisely , , and .
5.1. Foundations of matroids on elements
By Theorem 4.22, the foundation of a matroid is determined completely by its minors on at most elements and the embedded minors on with two parallel elements.
In this section, we will determine the foundations of all matroids on at most elements. Most of these matroids are regular and have foundation by [5, Thm. 7.33]. There is only a small number of non-regular matroids on at most elements, which we will inspect in detail.
Let and be a matroid of rank on .
5.1.1. Regular matroids
A matroid is regular if and only if there is no nontrivial cross ratio, which is the case if and only if the matroid does not contain any minor of type .
This is the case in exactly one of the following situations: (a) ; (b) , and is not uniform; (c) , and is not uniform for every ; (d) , and is not uniform for every .
5.1.2. Matroids with exactly one embedded -minor
There are several isomorphism classes of matroids with exactly one -minor, which we list in the following.
Since the tip and cotip relations involve cross ratios from different embedded -minors, they do not appear for matroids with only one embedded -minor.
If , then there is exactly one such matroid, namely itself, which has foundation by Proposition 4.10.
Proposition 5.1.
Let be a matroid on elements with exactly one embedded -minor. Then is isomorphic to where is a matroid on element. The foundation of is isomorphic to .
Proof.
In order to have an -minor, must have rank or . Since the embedded minors of correspond bijectively to the embedded minors and since is self-dual, the matroids and have the same number of -minors. Once we have shown that every rank -matroid with exactly one embedded -minor is isomorphic to for a matroid on one element, which has to be of rank , then we can conclude that is isomorphic to . To complete this reduction to the rank -case, we note that the foundation of is canonically isomorphic to the foundation of , cf. Proposition 4.7.
Assume that the rank -matroid on has an embedded -minor. After a permutation of , we can assume that this embedded -minor is , i.e. that all of the following -subsets
of are bases. If these are all bases of , then is a loop and is isomorphic to , as claimed.
We indicate why cannot have more bases of the form . If has exactly one additional basis element, say , then the basis exchange property is violated by exchanging by an element of the basis . The same reason excludes the possibility that has exactly two additional basis elements, say and . If has or more basis elements, say all -subsets of but possibly , then both minors and are isomorphic to . Thus in this case, has at least two embedded -minors.
This shows that has to be isomorphic to . Since is a loop, the conditions for the tip relations are not satisfied, which means that all relations stem from the unique embedded -minor . This shows that the foundation of is isomorphic to , as claimed. ∎
5.1.3. Matroids with exactly two embedded -minors
If has two embedded -minors, then the ground set must be . As explained in Section 5.1.2, must have rank or if has an -minor. We will show that if has exactly two embedded -minors, then it must be isomorphic to the following matroid, or its dual.
Definition 5.2.
We denote by the rank -matroid on whose set of bases is .
Proposition 5.3.
A matroid on elements has exactly two embedded -minors if and only if is isomorphic to either or its dual. The cross ratios of satisfy
and the cross ratios of satisfy
for all identifications . The foundations of both and are isomorphic to .
We illustrate all non-degenerate cross ratios of and their relations in Figure 3.
Proof.
In the proof of Proposition 5.1, we saw that has at least two embedded -minors, which correspond to the -minors and . All other minors of rank on elements of are of the form for . But since is not a basis of , none of these minors is isomorphic to . This shows that has exactly two embedded -minors, as has every matroid that is isomorphic to .
Conversely, assume that is a matroid on elements with exactly two embedded -minors. Since duality preserves -minors, can assume that is of rank . After a permutation of , we can assume that these two embedded -minors are and . Thus all of the -subsets
are bases. If was also a basis of , then would be the uniform matroid , which has five minors for . Thus is isomorphic to . This proves our first claim.
Let us choose an identification . The tip relation (4.20) in Theorem 4.20 with tip and cyclic orientation for is
Since is degenerate, we obtain the claimed relation
where the second equality is relation (4.20). Similarly, the cotip relation (4.20) with cotip and cyclic orientation for is
Since is degenerate, we obtain the claimed relation
Since is a parallel extension of , the foundation of is by Proposition 4.8, which concludes the proof. ∎
5.1.4. Matroids with five embedded -minors
The only matroids on at most five elements that do not appear among the previous cases with at most two embedded -minors are the uniform matroids and , which have five embedded -minors.
For completeness, we describe their foundations. However, we postpone the proof to a sequel to this paper where we develop more sophisticated methods to calculate the foundations of matroids. Note that the results of this first part are independent from the following result since we consider matroids without large uniform minors.
Proposition 5.4.
The foundations of and are isomorphic to
where and .
5.2. Symmetry quotients
The classification of foundations of matroids on up to five elements in section 5.1 shows that in a matroid without large uniform minors, all relations between cross ratios of different embedded -minors arise from minors of type or . Proposition 5.3 shows that these types of minors identify the two hexagons of cross ratios, which implies an identification of two copies of the near-regular partial field ; cf. Figure 3. The same happens for relations of type 4.20: they identify two copies of .
It can, and it will, happen that a matroid contains a chain of such minors, which creates a self-identification of the cross ratios belonging to an embedded -minor of . By Proposition 5.3, this self-identification must respect the relations between the cross ratios in each hexagon, and induces an automorphism of . Therefore we are led to study the quotients of by such automorphisms.
5.2.1. Automorphisms of the near-regular partial field
In the following, we determine all automorphisms of the near-regular partial field . By Lemma 4.12, it suffices to determine the images of and to describe an automorphism of . A result equivalent to the following is also proved in [24, Lemma 4.4].
Lemma 5.5.
The elements of the form in the nullset of with are
Thus the fundamental elements of are .
Proof.
Note that the only element with is . Thus to find all fundamental elements, it suffices to search for relations of the form with . Since is generated by and , and since all terms have to be nonzero and at least one term has to be equal to to find a relation for fundamental elements, we find exactly three relations of the form , which are
Thus the claim of the lemma. ∎
Proposition 5.6.
The associations
define automorphisms of that generate the automorphism group of and satisfy the relations . In particular, .
Proof.
By Lemma 5.5, both and are pairs of fundamental elements in . Thus, by Lemma 4.12, and define morphisms from to . Since and , we conclude that defines a group automorphism of of order . Similarly, defines a group automorphism of of order . The relation can be easily verified by evaluation on and .
We conclude that the automorphism group of contains as a subgroup. By Lemma 5.5, contains precisely fundamental elements, which implies easily that is generated by and . ∎
Remark 5.7.
It follows from Lemma 5.5 that the isomorphism from Proposition 4.10 maps the cross ratios of bijectively to the fundamental elements of . We can arrange these fundamental elements in a hexagon
in the same way as we arrange the cross ratios in Figure 1. It follows from Proposition 5.6 that the automorphisms of correspond bijectively to the symmetries of this hexagon that preserve the edge labels and the inner triangles.
5.2.2. Classification of the symmetry quotients of
A symmetry quotient of is the quotient of by a group of automorphisms. More precisely, if is a subgroup of , then the quotient of by is
In fact, we have if is a set of generators of .
Proposition 5.8.
The symmetry quotients of are, up to isomorphism,
Proof.
In the following, we show that the quotients of by different subgroups of are exactly the pastures , , and , up to isomorphism. Clearly is the quotient of by the trivial subgroup.
Note that if is a subgroup conjugate to , i.e. for some , then the quotient of by equals the quotient of by . This means that it suffices to determine the isomorphism classes of the quotients of by the groups , and , which represent all conjugacy classes of nontrivial subgroups of .
Let . We denote the residue classes of and in by and , respectively. We claim that the association
defines an isomorphism of pastures. We begin with the verification that defines a morphism. The map with is a morphism, since the generator of the nullset of is mapped to , which is in the nullset of . Since and , the morphism induces a morphism by the universal property of the quotient , cf. Proposition 2.6.
We define the inverse to as the association . This defines a multiplicative map since is freely generated by . Since
is null in , this defines a morphism . It is obvious that is an inverse to , which shows that is an isomorphism.
We continue with the automorphism group . We claim that the association
defines an isomorphism of pastures. We begin with the verification that defines a morphism. The map with and is a morphism, since the generator of the nullset of is mapped to , which is in the nullset of . Since and , the morphism induces a morphism by the universal property of the quotient .
We define the inverse of as follows. Let be the morphism that maps to . The defining relations of are and . Thus
which is in the nullset of . Since in , we have and thus
which is also in the nullset of . This shows that the morphism defines a morphism , which is obviously inverse to .
Finally we show that is isomorphic to . Since , it suffices to show that the association
is an isomorphism. Since and , and since , the assignment extends to a multiplicative map. Since and are null in , the map is a morphism. Note that in , we have and , and thus . We conclude that the assignment defines a morphism , since
is null in . It is clear that is an inverse of , which shows that is an isomorphism. This concludes the proof of the proposition. ∎
5.3. The structure theorem for matroids without large uniform minors
We are prepared to prove the central result of this paper. In the following, the empty tensor product stands for the initial object in , which is .
Theorem 5.9.
Let be a matroid without large uniform minors and its foundation. Then
for some and pastures .
Proof.
Let be the collection of embedded minors of from Theorem 4.22. Then
where the set is generated by the relations for every inclusion of embedded minors and in .
From the analysis in section 5.1, it follows that the foundation of every embedded minor of with at most elements is either or , where we use the assumption that is without minors of types and . A matroid with foundation is regular and has thus no minor of type . We conclude that every embedded minor in on at most elements has foundation .
If an embedded minor in has elements, and thus two of them are parallel, then deleting one of these parallel elements yields an embedded minor of , and the induced morphism is an isomorphism. Thus also every embedded minor in with elements has foundation .
Since neither nor contains a minor of type , an embedded minor in with elements cannot contain another embedded minor in . Consequently the isomorphism of Theorem 4.22 implies that
where is the subset of that contains all embedded minors with elements, is the subset of that contains all embedded minors with at most elements and is the set generated by the relations for every inclusion of embedded minors and in .
By what we have seen, an inclusion of embedded minors in is an isomorphism, and either foundation is isomorphic to . Thus all identifications in stem from isomorphisms between some factors of the tensor product. What can, and does, happen is that a chain of such isomorphisms imposes a self-identification of a factor with itself by a non-trivial automorphism. This leads to a symmetry quotient of , which is one of , , and . Thus
is a tensor product of copies of , , and .
This leaves us with the factors for . By Theorem 4.20, we have , and all cross ratios are trivial since there are no -minors. Thus . This concludes the proof of the theorem. ∎
Theorem 5.9 can be reformulated as follows, which expresses the dependencies of the factors on .
Corollary 5.10.
Let be a matroid without large uniform minors, its foundation. Then
for a uniquely determined and uniquely determined pastures and , up to a permutation of the indices . We have or if and only if contains a minor of type or .
Proof.
By Theorem 5.9, the foundation of a matroid without large uniform minors is isomorphic to a tensor product of copies of , , , and .
Since morphisms from and into other pastures are uniquely determined, if they exist, we conclude that and . Thus the pasture
is isomorphic to
cf. Example 2.8 for the equality . This explains the list of possible isomorphism types for . Since appears as a factor of if and only if has a minor of type or , this verifies the last claim of the corollary.
It follows that is isomorphic to a tensor product of with pastures .
We are left with establishing the uniqueness claims. To begin with, is uniquely determined by the presence or absence of the relations and , which correspond to the relations and , respectively, in our previous case consideration. Thus is uniquely determined.
The factors are determined by the fundamental elements of , as we explain in the following. Let be the canonical inclusion. By the construction of the tensor product, the nullset of consists of all terms of the form for some , and such that is in the nullset of . The fundamental elements of stem from such equations for which and are nonzero and . Thus is in the image of , and therefore and . Since is in the nullset of , we conclude that all fundamental elements in are of the form for some and some fundamental element of .
To make a distinction between the different isomorphism types of the factors, we note that every fundamental element with relation gives rise to a set of fundamental elements. If these six fundamental elements come from a factor , then they are pairwise different. If they come from a factor , then
is a set with three distinct elements. If they come from a factor , then
is a set with two distinct elements. Note that if or , then is also a fundamental element, and in this case are all equal. This shows that the number of factors of types , and are determined by the fundamental elements of , which completes the proof of our uniqueness claims. ∎
Remark 5.11.
In a sequel to this paper, we will show that for all and , there is a matroid without large uniform minors whose foundation is isomorphic to the tensor product .
6. Applications
In this concluding part of the paper, we explain various applications of our central result Theorem 5.9. Along with some new results and strengthenings of known facts, we also present short conceptual proofs for a number of established theorems which illustrate the versatility of our structure theory for foundations.
The main technique in most of the upcoming proofs is the following. A matroid is representable over a pasture if and only there is a morphism from the foundation of to . If is without large uniform minors, then we know by Theorem 5.9 that is isomorphic to the tensor product of copies of , , , and . Thus a morphism from to exists if and only there is a morphism from each to , which in practice is quite easy to determine.
For reference in the later sections, we will provide some general criteria for such morphisms in the following result, and list the outcome for a series of prominent pastures in Table 2.
Lemma 6.1.
Let be a pasture.
-
(1)
There is a morphism if and only if contains a fundamental element. For a field , this is the case if and only if .
-
(2)
There is a morphism if and only if there is an element such that . For a field , this is the case if and only if .
-
(3)
There is a morphism if and only if there is an element such that and . For a field , this is the case if and only if or if contains a primitive third root of unity.
-
(4)
There is a morphism if and only if in . For a field , this is the case if and only if .
-
(5)
There is a morphism if and only if in . For a field , this is the case if and only if .
There exist morphisms from , , , and into the pastures , , , for , , , , and where Table 2 contains a check mark—a dash indicates that there is no morphism.
Proof.
We briefly indicate the reasons for claims (1)–(5). We begin with claim (1). The universal property from Proposition 2.6 implies that there is a morphism from to if and only if there are such that . By definition, such elements are fundamental elements of . If is a field, then a pair of fundamental elements is a point of the line in . Since contains precisely two points and with vanishing coordinates, the elements of are in bijection with . Thus has a fundamental element if and only if .
We continue with claim (2). The first assertion follows at once from the universal property for . A field contains an element with if and only if is invertible in , which is the case if and only if is of characteristic different from .
We continue with claim (3). The first assertion follows at once from the universal property for . In a field of characteristic , the element satisfies and . If has characteristic different from , then satisfies the equation , which characterizes a primitive third root of unity. Note that we have automatically in a field if is a third root of unity.
6.1. Forbidden minors for regular, binary and ternary matroids
The techniques of this paper allow for short arguments to re-establish the known characterizations of regular, binary and ternary matroids in terms of forbidden minors, as they have been proven by Tutte in [31] and [32] for regular and binary matroids, and independently by Bixby in [6] and by Seymour in [29] for ternary matroids.
We spell out the following basic fact for its importance for many of the upcoming theorems.
Lemma 6.2.
Binary matroids and ternary matroids are without large uniform minors.
Proof.
All minors of a binary or ternary matroid are binary or ternary, respectively. Since and are neither binary nor ternary, the result follows. ∎
Next we turn to the proofs of the excluded minor characterizations of regular, binary and ternary matroids.
Theorem 6.3 (Tutte ’58).
A matroid is regular if and only if it contains no minor of types , or . A matroid is binary if and only if it contains no minor of type .
Proof.
By Corollary 4.13, is not binary and therefore also not regular. It follows from Theorem 4.20 that the foundations of and contain the relation , which means that they do not admit a morphism to . Thus and are not regular.
We are left with showing that the respective lists of forbidden minors are complete. If a matroid does not contain a minor of type , then Corollary 4.21 implies that the foundation of is equal to or . In either case, there is a morphism from to , which shows that is binary if it has no minor of type .
If, in addition, has no minor of types or , then Corollary 4.21 implies that , and thus is regular. ∎
Theorem 6.4 (Bixby ’79, Seymour ’79).
A matroid is ternary if and only if it does not contain a minor of type , , or .
Proof.
If is ternary, then it does not have a minor of type or by Lemma 6.2. Thus Theorem 4.20 applies, and since in , does not have a minor of type or . This establishes all forbidden minors as listed in the theorem.
To show that the list of forbidden minors is complete, we assume that contains no minors of these types. Then Corollary 5.10 implies that the foundation of is isomorphic to with . Since each of , , , admits a morphism to , there is a morphism , which shows that is ternary. ∎
6.2. Uniqueness of the rescaling class over
Brylawski and Lucas show in [11] that a representation of a matroid over is uniquely determined up to rescaling. Our method yields a short proof of the following generalization.
Theorem 6.5.
Let be a pasture with at most one fundamental element. Then every matroid has at most one rescaling class over .
Proof.
Let be a matroid with foundation . Since the rescaling classes of over are in bijective correspondence with the morphisms , it suffices to show that there is at most one such morphism.
By Proposition 3.11, every cross ratio of is a fundamental element of , and thus must be mapped to a fundamental element of . By the uniqueness of (if it exists), the image of every cross ratio is uniquely determined. Since is generated over by cross ratios, the result follows. ∎
Remark 6.6.
Examples of pastures with at most one fundamental element are , , and . In fact it is not hard to prove that every pasture with at most one fundamental element contains one of these pastures as a subpasture, and that the fundamental element is (if it exists). Note that Brylawski and Lucas’s theorem concerns the case .
6.3. Criteria for representability over certain fields
Our theory allows us to deduce at once that matroids without large minors that are representable over certain pastures are automatically representable over certain (partial) fields. For instance, we find such criteria in the cases of the sign hyperfield , the phase hyperfield and the weak sign hyperfield .
Note that the proof of Criterion (1) in the following theorem strengthens Lee and Scobee’s result that every ternary and orientable matroid is dyadic; see [17, Cor. 1]. In fact, we further improve on this result in Theorem 6.9 where we show that every orientation is uniquely liftable to up to rescaling.
In the statement of the following theorem, recall that a matroid is said to be weakly orientable if it is representable over .
Theorem 6.7.
Let be a matroid without large uniform minors.
-
(1)
If is orientable, then it is representable over every field of characteristic different from .
-
(2)
If is representable over , then it is representable over fields of every characteristic except possibly .
-
(3)
If is weakly orientable, then it is ternary.
Proof.
Let be the foundation of and the decomposition from Theorem 5.9 into factors . If is representable over a pasture , then there is a morphism , and thus there is a morphism for every . Conversely, if one of the building blocks , , , and does not map to , we conclude that this building block does not occur among the .
Claim (1) follows since there are no morphisms from , or to , and both and map to every field of characteristic different from . Claim (2) follows since there are no morphisms from or to , and since each of , and maps to a field if its characteristic is or if it is different from and if contains a primitive third root of unity. Claim (3) follows since there is no morphism from to , and each of , , and maps to . ∎
Remark 6.8.
The proof of Theorem 6.7 shows that similar conclusions can be formulated for other pastures that do not receive morphisms from some of the building blocks of the foundation of a matroid without large uniform minors. If is representable over , then we can conclude the following, for instance:
-
•
if there is no morphism from to , then is quaternary;
-
•
if there is no morphism from either or to , then is hexagonal.
6.4. Oriented matroids without large minors are uniquely dyadic
Our techniques allow us to strengthen the result of Lee and Scobee ([17, Thm. 1]) that an oriented matroid is dyadic if its underlying matroid is ternary. At the end of this section, we deduce Lee and Scobee’s result from ours.
An oriented matroid is an -matroid, i.e. the class of a Grassmann-Plücker function , where is the rank of and its ground set. The underlying matroid of is the matroid , where is the terminal morphism, cf. section 2.1.3. Recall that a reorientation class is a rescaling class over .
Let be the morphism from the dyadic partial field to that maps to . An oriented matroid is dyadic if there is a -matroid such that . We call a lift of along .
Theorem 6.9.
Let be an oriented matroid whose underlying matroid is without large uniform minors. Then there is a unique rescaling class of dyadic matroids such that .
Proof.
Let be the foundation of . The oriented matroid determines a reorientation class and thus a morphism . Since rescaling classes of over correspond bijectively to morphisms , we need to show that the morphism lifts uniquely to , i.e. that there is a unique morphism such that the diagram
commutes.
Note that this implies only that there is a unique rescaling class such that the reorientation classes and are equal. In order to conclude that we can choose such that , we note that the morphism is surjective, and thus any reorientation of can be inverted by a rescaling of over . This shows that we have proven everything, once we show that lifts uniquely to .
Since is without large uniform minors, Theorem 5.9 implies that is isomorphic to for some . Composing with the canonical inclusions yields morphisms for . As visible in Table 2, there are no morphisms from , or to . This means that .
By the universal property of the tensor product, the morphisms correspond bijectively to the tuples of morphisms . Thus there is a unique lift of to if and only if for every , there is a unique lift of to . This reduces our task to an inspection of the two cases and .
Consider the case . Since in , we must have in , which is only possible if . Thus , which means that the identity morphism lifts , i.e.
commutes. This lift is unique since is only satisfied by , and thus is determined.
We are left with the case , for which we inspect the possible images of the fundamental elements and of in and . The relations of the form in are and . Thus maps to one of , and . This means that there are precisely morphisms , and has to be one of them.
The relations of the form in are and . Thus the morphisms correspond to a choice of mapping to one of , and . Considering the respective images and in , we conclude that every morphism lifts uniquely to a morphism , i.e.
commutes. This completes the proof of the theorem. ∎
Theorem 6.10 (Lee–Scobee ’99).
An oriented matroid is dyadic if and only if its underlying matroid is ternary.
Proof.
Let be an oriented matroid and let be its underlying matroid. If is ternary, then it is without large uniform minors. Thus is dyadic by Theorem 6.9.
Conversely, assume that is dyadic, i.e. it has a lift along . Since there is a morphism , and since , the -matroid is a representation of over . Thus is ternary. ∎
6.5. Positively oriented matroids without large uniform minors are near-regular
In their 2017 paper [2], Ardila, Rincón and Williams prove that every positively oriented matroid can be represented over (and a posteriori, by a theorem of Postnikov, over ), which solves a conjecture from da Silva’s thesis [12] from 1987. A second proof has recently been obtained by Speyer and Williams in [30]. Neither of these proofs yields information about the structure of the lifts of positive orientations to or .
With our techniques, we can recover and strengthen the result for positively oriented matroids whose underlying matroid is without large uniform minors. To begin with, let us recall the definition of positively oriented matroids.
Definition 6.11.
Let be a matroid of rank on the ground set . A positive orientation of (with respect to ) is a Grassmann-Plücker function such that and such that for every with .
An oriented matroid of rank on is positively oriented if its underlying matroid has a positive orientation with respect to some identification such that .
A key tool for proof of Theorem 6.15 is the following notion.
Definition 6.12.
Let be a matroid of rank on the ground set . Let be the Klein -group, considered as a subgroup of . The -signature of (with respect to ) is the map
that sends to the class of the uniquely determined permutation that
is an order-preserving bijection.
Example 6.13.
The key example to understand the relevance of the -signature is the uniform matroid , whose foundation is . In this case, consists of the tuples for which is a permutation of . Since the cross ratio determines up to a permutation in , which corresponds to a permutation of the rows and the columns of the cross ratio, the -signature induces a well-defined bijection
Lemma 6.14.
Let be a matroid of rank on the ground set and let be a positive orientation of . Let and be such that . Then
Proof.
Choose so that . Since is a positive orientation, we have for all and that , where is the unique permutation such that
Since the cross ratio is invariant under permutations of , we can assume that . Thus we can write as the composition of with the permutation of that fixes and satisfies . A minimal decomposition of into transpositions is
where is such that . Thus
and
Since the parity of is even for every , we can assume that is the representative that occurs in the definition of , i.e. we can assume that defines an order preserving bijection . Then is the identity if and if . Thus if and if .
Since is invariant under exchanging rows and columns, we can assume that is the minimal element in , i.e. and for . We verify the claim of the lemma by a case consideration for the value of .
If , then is minimal in and for all . Thus
If , then or . Thus and
If , then is maximal in and for all . Thus
which completes the proof. ∎
Let be a morphism of pastures. A lift of to (along ) is a -matroid such that . In the following result, we will implicitly understand that a subfield of comes with the sign map .
As explained in Corollary 4.13, the near-regular partial field admits three morphisms to . Since the automorphism group acts transitively on these three morphisms, we can fix one of them without restricting the generality of our results. Thus we will implicitly understand that comes with the morphism given by .
Theorem 6.15.
Let be a positively oriented matroid whose underlying matroid is without large uniform minors. Then is near-regular and for some . Up to rescaling equivalence, there are precisely lifts of to , and for every subfield of , the lifts of to modulo rescaling equivalence correspond bijectively to .
Proof.
By Theorem 5.9, the foundation is isomorphic to a tensor product of copies of and symmetry quotients of . The rescaling class of induces a morphism . Since there is no morphism from to , each of the factors has to be a symmetry quotient of .
From the proof of Theorem 5.9, it follows that each symmetry quotient of is the image of the induced morphism of foundations for an embedded -minor of . This means that for every and every , we have an identity of universal cross ratios
We claim that if then , where is the -signature. We verify this in the following for all the defining relations of that involve non-degenerate cross ratios, as they appear in Theorem 4.20.
The relations (4.20) and (4.20) do not involve non-degenerate cross ratios (and (4.20) does not occur in our case since neither the Fano matroid not its dual are orientable). The relations (4.20), (4.20), (4.20) and (4.20) are already incorporated in and can thus be ignored. For relation (4.20), it is obvious that both involved cross ratios have the same -signature.
Thus we are left the relations (4.20) and (4.20). Since is without large uniform minors, each of these relations reduces to an identity of two universal cross ratios. We begin with the tip relation (4.20), which is of the form
in our case, where we use (4.20) to express as . After a permutation of , we can assume that , and thus
by Lemma 6.14. Therefore also , which means that the unique order preserving bijection must satisfy according to Lemma 6.14. Since by our assumptions, this implies that . Thus .
The cotip relations (4.20) are in our case of the form
As before, we can assume that and thus . By the same reasoning, this implies that and thus . This establishes our claim that whenever .
In particular, if then , which means that is in . These are precisely the relations in (4.20), which are already satisfied in . We conclude that is the identity on .
This shows that every factor of is a trivial quotient of and thus , as claimed in the theorem. It also implies at once that is near-regular.
Let be the morphism of pastures induced by the rescaling class of . The lifts of to and , up to rescaling, correspond to the lifts of to and , respectively. We can study this question for each factor of individually.
A lift of to is a morphism such that . This determines up to a permutation of and , which shows that there are precisely two lifts of to . Thus there are precisely lifts of to up to rescaling equivalence.
A lift of to is a morphism such that . Since , this means that and, conversely, every choice of image determines a lift of to . Thus the lifts of to up to rescaling equivalence correspond bijectively to . This completes the proof of the theorem. ∎
6.6. Representation classes of matroids without large uniform minors
Given a matroid , we can ask over which pastures is representable. This defines a class of pastures that we call the representation class of .
For cardinality reasons, it is clear that not every class of pastures can be the representation class of a matroid. The theorems in Section 6.7 make clear that this fails in an even more drastic way—for example, a matroid that is representable over and is representable over all pastures; cf. Theorem 6.26.
In this section, we determine the representation classes that are defined by matroids without large uniform minors. It turns out that there are only twelve of them; see Table 3 for a characterization.
Definition 6.16.
Let be a matroid. The representation class of is the class of all pastures over which is representable. Two matroids and are representation equivalent if .
Note that the representation class of a matroid consists of precisely those pastures for which there is a morphism from the foundation of to . This means that the representation class of a matroid is determined by its foundation. Evidently, if and are representation equivalent, which justifies the notation where is the representation class of .
Often there are simpler pastures than the foundation that characterize representation classes in the same way, which leads to the following notion.
Definition 6.17.
Let be a matroid with representation class . A characteristic pasture for is a pasture for which a pasture is in if and only if there is a morphism . A matroid is strictly representable over a pasture if is a characteristic pasture for .
By the existence of the identity morphism , strictly representable implies representable. And the foundation of a matroid is clearly a characteristic pasture for . The following result characterizes all characteristic pastures:
Lemma 6.18.
Let be a matroid with foundation . A pasture is a characteristic pasture of if and only if there exist morphisms and .
Proof.
Assume that is a characteristic pasture for . Since also is a characteristic pasture, we have , and by the defining property of characteristic pastures, there are morphisms and .
Conversely, assume that there are morphisms and . If , then there is a morphism , which yields a morphism . If there is a morphism , then there is a morphism , and thus . This shows that is a characteristic pasture for . ∎
The next result describes an explicit condition for representation equivalent matroids.
Lemma 6.19.
Let and be two matroids with respective representation classes and and respective characteristic pastures and . Then is contained in if and only if there is a morphism . In particular, and are representation equivalent if and only if there exist morphisms and .
Proof.
If there is a morphism , then we can compose every morphism with , which implies that . Assume conversely that . Then , which means that there is a morphism . The additional claim of the lemma is obvious. ∎
In the following, we say that a matroid is
-
•
strictly binary if is a characteristic pasture for ;
-
•
strictly ternary if is a characteristic pasture for ;
-
•
strictly near-regular if is a characteristic pasture for ;
-
•
strictly dyadic if is a characteristic pasture for ;
-
•
strictly hexagonal if is a characteristic pasture for ;
-
•
strictly -representable if is a characteristic pasture for ;
-
•
idempotent if is a characteristic pasture for .
Note that an idempotent matroid is representable over a pasture if and only if is idempotent, by which we mean that both and hold in .
Theorem 6.20.
Let be a matroid without large uniform minors. Then belongs to precisely one of the classes that are described in Table 3. The six columns of Table 3 describe the following information:
-
(1)
a label for each class ;
-
(2)
a name (as far as we have introduced one);
-
(3)
a characteristic pasture that is minimal in the sense that the foundation of every matroid in the class is of isomorphism type for some and ;
-
(4)
the type of factors that can occur in the expression for in ;
-
(5)
a characterization of the pastures in the representation class ;
-
(6)
whether the matroids in this class are representable over some field.
The left diagram in Figure 4 illustrates the existence of morphisms between the different characteristic pastures in Table 3. The right diagram illustrates the inclusion relation between the representation classes (for )—an edge indicates that the class on the bottom end of the edge is contained in the class at the top end of the edge.
Name | minimal | add. | iff. s.t. | field? | |
---|---|---|---|---|---|
regular | yes | ||||
str. near-regular | yes | ||||
strictly dyadic | , | yes | |||
str. hexagonal | , | yes | |||
str. -repr. | , , | yes | |||
strictly ternary | , , | yes | |||
strictly binary | yes | ||||
yes | |||||
, | no | ||||
, | yes | ||||
, , | no | ||||
idempotent | , , | no |
Proof.
For the sake of this proof, we say that two pastures and are equivalent, and write , if there are morphisms and .
If there is a morphism , then there are morphisms and , which means that . This applies in particular to . This shows that for and pastures if, for every , there is a and a morphism .
Let be a matroid without large uniform minors and its foundation. By Theorem 5.9, for some , where we can assume that appears at most once as a factor. By the previous considerations, for pairwise distinct . Since there are morphisms
we have , and for . Thus we can assume that in the expression at most one of , , and appears, with the exception of .
Thus we are limited to the twelve different expressions for that appear in Figure 4. We conclude that is equivalent to one of those and that is a characteristic pasture for .
An easy case-by-case verification based on Table 2, which we shall not carry out, shows that there is a morphism between two pastures if and only if there is a directed path between these pastures in the diagram on the left hand side of Figure 4. By Lemma 6.19, this diagram determines at once the inclusion behaviour of the associated representation classes – as illustrated on the right hand side of Figure 4.
Note that the way we found the twelve characteristic pastures shows that they are minimal in the sense of part (3) of the theorem, and it shows that the types of additional factors displayed in the forth column of Table 3 are correct. The conditions in the fifth column of Table 3 follows at once from Lemma 6.1.
For the verification of the last column, note that there is a morphism for the classes and that there is a morphism for . Thus the matroids in the classes – and are representable over a field. There is no morphism from to any field since in a field only one of and for some can hold. Thus matroids in the classes , and are not representable over any field, which concludes the proof of the theorem. ∎
As a sample application, we formulate the following strengthening of the result [37, Thm. 3.3] by Whittle. Recall that a matroid is called representable if it is representable over some field.
Theorem 6.21.
Let . Then two representable matroids and without large uniform minors are representation equivalent if and only if . More precisely, for and and as in Table 4, the class is the intersection of the representation classes of all matroids without large uniform minors that are representable over and .
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 10 | |
---|---|---|---|---|---|---|---|---|---|
2 | 3 | 3 | 3 | 3 | 3 | 2 | 8 | 4 | |
3 | 8 | 5 | 4 | 7 | 3 | 2 | 8 | 4 |
Proof.
For and in , let be the subset of such that is a characteristic pasture for , cf. Table 3. Then we can read off from Table 2 that there are morphisms and for all , and that for all that are not in , there is either no morphism from to or no morphism from to . This shows that the existence of morphisms into and characterize the factors of the characteristic pasture and establishes the claims of the theorem. ∎
Remark 6.22.
Note that the representation class of regular matroids contains all pastures and is therefore the largest possible representation class. The representation class of idempotent pastures is the smallest representation class, since every matroid is by definition representable over and thus over every idempotent pasture. (Recall that a pasture is called idempotent if there is a morphism from to .) Every other representation class thus lies between and .
Remark 6.23.
We will show in a sequel to this paper that every tensor product of copies of the pastures , , , and occurs as the foundation of a matroid. Consequently each of the classes – is nonempty.
Alternatively, we can use known results to deduce this. Since there are matroids that are regular, strictly near-regular (e.g. ), strictly dyadic (e.g. the non-Fano matroid ), strictly hexagonal (e.g. the ternary affine plane ), strictly ternary (e.g. the matroid from Oxley’s book [21]) and strictly binary (e.g. the Fano matroid ), the classes , , , , and are nonempty.
Since the characteristic pastures of the remaining classes in Table 3 are tensor products of characteristic pastures of one of the aforementioned matroids, we can deduce that the other classes are also nonempty by observing that
for two matroids and .
Remark 6.24.
Since all binary and ternary matroids are without large uniform minors, all matroids in the classes – are without large uniform minors. This is not true for all classes though. For instance the direct sum of an idempotent matroid with is also idempotent and thus in , but has a minor of type ; cf. Remark 6.23 for the existence of idempotent matroids.
In fact, a similar construction yield matroids with -minors in the classes and . By contrast, all matroids in and are without large uniform minors. This latter fact can be proven as follows: a class contains a matroid with a - or a -minor if and only if there is morphism from the foundation of (cf. Proposition 5.4) to the minimal characteristic pasture for . There is no morphism from the foundation of to or to , but there are morphisms to and .
6.7. Characterization of classes of matroids
In this section, we use our results to provide different characterizations of some prominent classes of matroids, such as regular, near-regular, binary, ternary, quaternary, dyadic, and hexagonal matroids. In particular, we find new proofs for results by Tutte, Bland and Las Vergnas, and Whittle, which we refer to in detail at the beginnings of the appropriate sections. Moreover, we obtain new characterizations, which often involve the pastures , and .
All these characterizations are immediate applications of Theorem 5.9 in combination with Table 2. It is possible to work out additional descriptions for the classes of matroids under consideration, or to study other classes with the same techniques. For example, our technique allows for an easy proof of the following results found in Theorems 5.1 and 5.2 of Semple and Whittle’s paper [27].
Theorem 6.25 (Semple–Whittle ’96).
Let denote the class of matroids without large uniform minors that are representable over a pasture . Then the following hold true.
-
(1)
for odd .
-
(2)
for even .
-
(3)
for every field of characteristic different from , and if, in addition, does not contain a primitive sixth root of unity.
6.7.1. Regular matroids
The following theorem extends a number of classical results that characterize regular matroids, namely as binary matroids that are representable over a field with by Tutte in [31] and [32] (use in (5)) and as binary and orientable matroids by Bland and Las Vergnas in [8] (use in (5)). Up to the characterization (3), the authors of this paper have proven Theorem 6.26 in its full generality in [5, Thm. 7.33] with a slightly different proof.
Theorem 6.26.
Let be a matroid with foundation . Then the following assertions are equivalent:
-
(1)
is regular.
-
(2)
.
-
(3)
belongs to .
-
(4)
is representable over all pastures.
-
(5)
is representable over and a pasture with .
6.7.2. Binary matroids
We find the following equivalent characterizations of binary matroids.
Theorem 6.27.
Let be a matroid with foundation . Then the following assertions are equivalent:
-
(1)
is binary.
-
(2)
or .
-
(3)
belongs to or .
-
(4)
is representable over every pasture for which .
-
(5)
All fundamental elements of are trivial.
6.7.3. Ternary matroids
We find the following equivalent characterizations of ternary matroids.
Theorem 6.28.
Let be a matroid with foundation . Then the following assertions are equivalent:
-
(1)
is ternary.
-
(2)
for and .
-
(3)
belongs to one of –.
-
(4)
is representable over every pasture for which .
-
(5)
is without large uniform minors and representable over a field of characteristic .
-
(6)
is without large uniform minors and weakly orientable.
-
(7)
is without large uniform minors and there is no morphism from to .
Proof.
We show (2)(3), (1)(4) and (2)(1)(5) / (6) / (7)(2). The implications (2)(1)(4) are trivial. The equivalence (2)(3) follows from Theorem 6.20.
6.7.4. Quaternary matroids without large uniform minors
We find the following equivalent characterizations of quaternary matroids without large uniform minors.
Theorem 6.29.
Let be a matroid without large uniform minors and its foundation. Then the following assertions are equivalent:
-
(1)
is quaternary.
-
(2)
for and .
-
(3)
belongs to , , , , or .
-
(4)
is representable over every pasture for which and that contains an element for which .
-
(5)
is representable over all field extensions of .
-
(6)
There is no morphism from to .
Proof.
We show (2)(3) and (2)(4)(1)(5)(6)(2). The equivalence (2)(3) follows from Theorem 6.20. The implications (2)(4)(1)(5) are trivial. The implication (5)(6) follows since there is no morphism from to by Lemma 6.1. The implication (6)(2) follows by Theorem 5.9, together with the fact that there is a morphism but not to , and , and thus only the latter three pastures can occur as factors of . ∎
6.7.5. Near-regular matroids
In this section, we provide several characterizations of near-regular matroids. The descriptions (5) and (6) appear in Whittle’s paper [36, Thm. 1.4].
Theorem 6.30.
Let be a matroid with foundation . Then the following assertions are equivalent:
-
(1)
is near-regular.
-
(2)
for and .
-
(3)
belongs to or .
-
(4)
is representable over all pastures with a fundamental element.
-
(5)
is representable over fields with at least elements.
-
(6)
is representable over and .
-
(7)
is without large uniform minors and representable over and .
-
(8)
is without large uniform minors and representable over and .
-
(9)
is without large uniform minors and representable over and .
-
(10)
is dyadic and hexagonal.
-
(11)
is without large uniform minors and there are no morphisms , , or .
Proof.
We show (2)(3), (2)(1)(4)(5)(2) and the equivalence of (2) with each of (6)–(11). The equivalence (2)(3) follows from Theorem 6.20, (2)(1) and (4)(5) are trivial and (1)(4) follows from Lemma 6.1. That (2) implies (6)–(11) can be read off from Table 2. Conversely, each of (5)–(11) implies that is without large uniform minors and thus Theorem 5.9 applies. In turn, each of (5)–(11) excludes that any of , , and occur as a factor , and thus (2). ∎
6.7.6. Dyadic matroids
In this section, we provide several characterizations of dyadic matroids. Description (6) has been given by Whittle in [35, Thm. 7.1]. Descriptions (4) and (5) have been given by Whittle in [36, Thm. 1.1].
Theorem 6.31.
Let be a matroid with foundation . Then the following assertions are equivalent:
-
(1)
is dyadic.
-
(2)
for and .
-
(3)
belongs to , or .
-
(4)
is representable over every pasture such that for some .
-
(5)
is representable over every field of characteristic different from .
-
(6)
is representable over and , where is an odd prime power such that is not divisible by .
-
(7)
is representable over and .
-
(8)
is representable over and .
-
(9)
is without large uniform minors and there are no morphisms or .
Proof.
We show (2)(3), (2)(1)(4)(5)(2) and the equivalence of (2) with each of (6)–(9). The equivalence (2)(3) follows from Theorem 6.20, (2)(1) and (4)(5) are trivial and (1)(4) follows from Lemma 6.1. That (2) implies (6)–(9) follows from Lemma 6.1 and Table 2. Conversely, each of (5)–(9) implies that is without large uniform minors and thus Theorem 5.9 applies. In turn, each of (5)–(9) excludes that any of , and occur as a factor , and thus (2). ∎
6.7.7. Hexagonal matroids
In this section, we provide several characterizations of hexagonal matroids. Description (5) has been given by Whittle in [36, Thm. 1.2].
Theorem 6.32.
Let be a matroid with foundation . Then the following assertions are equivalent:
-
(1)
is hexagonal.
-
(2)
for and .
-
(3)
belongs to , or .
-
(4)
is representable over every pasture that contains an element with and .
-
(5)
is representable over every field that is of characteristic or contains a primitive sixth root of unity.
-
(6)
is representable over and .
-
(7)
is without large uniform minors, weakly orientable, and representable over .
-
(8)
is without large uniform minors and there are no morphisms or .
Proof.
We show (2)(3), (2)(1)(4)(5)(2) and the equivalence of (2) with each of (6)–(8). The equivalence (2)(3) follows from Theorem 6.20, (2)(1) and (4)(5) are trivial and (1)(4) follows from Lemma 6.1. That (2) implies (6)–(8) follows from Lemma 6.1 and Table 2. Conversely, each of (5)–(8) implies that is without large uniform minors and thus Theorem 5.9 applies. In turn, each of (5)–(8) excludes that any of , and occur as a factor , and thus (2). ∎
6.7.8. -representable matroids
Whittle describes in [36, Thm. 1.3] equivalent conditions that are satisfied by -representable matroids, which are conditions (4) and (5) below. We augment Whittle’s result with the following theorem.
Theorem 6.33.
Let be a matroid with foundation . Then the following assertions are equivalent:
-
(1)
is -representable.
-
(2)
for and .
-
(3)
belongs to one of –.
-
(4)
is representable over and .
-
(5)
is representable over and , where is an odd prime power congruent to modulo .
-
(6)
is representable over and .
Proof.
We show (1)(2)(3)(1) and the equivalence of (2) with each of (4)–(6). The implications (1)(2)(3)(1) follow from Theorem 6.20. That (2) implies (4)–(6) follows from Lemma 6.1 and Table 2. Conversely, each of (4)–(6) implies that is without large uniform minors by Lemma 6.2, and thus Theorem 5.9 applies. In turn, each of (4)–(6) excludes the possibility that either or occurs as a factor , and thus (2). ∎
6.7.9. Representable matroids without large uniform minors
As a final application, we find the following equivalent characterization of matroids without large uniform minors which are representable over some field.
Theorem 6.34.
Let be a matroid without large uniform minors and its foundation. Then the following assertions are equivalent:
-
(1)
is representable over some field.
-
(2)
for and either or .
-
(3)
belongs to one of – or .
-
(4)
is ternary or quaternary.
-
(5)
There is no morphism from to .
References
- [1] Laura Anderson. Vectors of matroids over tracts. J. Combin. Theory Ser. A, 161:236–270, 2019.
- [2] Federico Ardila, Felipe Rincón, and Lauren Williams. Positively oriented matroids are realizable. J. Eur. Math. Soc. (JEMS), 19(3):815–833, 2017.
- [3] Matthew Baker and Nathan Bowler. Matroids over partial hyperstructures. Adv. Math., 343:821–863, 2019.
- [4] Matthew Baker and Tong Jin. On the structure of hyperfields obtained as quotients of fields. To appear in Proc. Amer. Math. Soc., arXiv:1912.11496, 2019.
- [5] Matthew Baker and Oliver Lorscheid. The moduli space of matroids. Preprint, arXiv:1809.03542, 2018.
- [6] Robert E. Bixby. On Reid’s characterization of the ternary matroids. J. Combin. Theory Ser. B, 26(2):174–204, 1979.
- [7] Robert G. Bland and David L. Jensen. Weakly oriented matroids. Cornell University School of OR/IE Technical Report No. 732, 1987.
- [8] Robert G. Bland and Michel Las Vergnas. Orientability of matroids. J. Combinatorial Theory Ser. B, 24(1):94–123, 1978.
- [9] Nathan Bowler and Rudi Pendavingh. Perfect matroids over hyperfields. Preprint, arXiv:1908.03420, 2019.
- [10] Nick Brettell and Rudi Pendavingh. Computing excluded minors for classes of matroids representable over partial fields. In preparation.
- [11] Tom Brylawski and Dean Lucas. Uniquely representable combinatorial geometries. In Proceedings of the International Colloquium on Combinatorial Theory. Rome, 1973.
- [12] Ilda P.F. da Silva. Quelques propriétés des matroides orientés. PhD thesis, Université Paris VI, 1987.
- [13] Andreas W. M. Dress and Walter Wenzel. Geometric algebra for combinatorial geometries. Adv. Math., 77(1):1–36, 1989.
- [14] Andreas W. M. Dress and Walter Wenzel. On combinatorial and projective geometry. Geom. Dedicata, 34(2):161–197, 1990.
- [15] Andreas W. M. Dress and Walter Wenzel. Perfect matroids. Adv. Math., 91(2):158–208, 1992.
- [16] Israel M. Gelfand, Grigori L. Rybnikov, and David A. Stone. Projective orientations of matroids. Adv. Math., 113(1):118–150, 1995.
- [17] Jon Lee and Matt Scobee. A characterization of the orientations of ternary matroids. J. Combin. Theory Ser. B, 77(2):263–291, 1999.
- [18] Oliver Lorscheid. Scheme theoretic tropicalization. Preprint, arXiv:1508.07949v2, 2015.
- [19] Ch. G. Massouros. Methods of constructing hyperfields. Internat. J. Math. Math. Sci., 8(4):725–728, 1985.
- [20] Peter Nelson. Almost all matroids are nonrepresentable. Bull. Lond. Math. Soc., 50(2):245–248, 2018.
- [21] James G. Oxley. Matroid theory. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1992.
- [22] Rudi Pendavingh. Field extensions, derivations, and matroids over skew hyperfields. Preprint, arXiv:1802.02447, 2018.
- [23] Rudi A. Pendavingh and Stefan H. M. van Zwam. Confinement of matroid representations to subsets of partial fields. J. Combin. Theory Ser. B, 100(6):510–545, 2010.
- [24] Rudi A. Pendavingh and Stefan H. M. van Zwam. Lifts of matroid representations over partial fields. J. Combin. Theory Ser. B, 100(1):36–67, 2010.
- [25] Rudi A. Pendavingh and Stefan H. M. van Zwam. Representing some non-representable matroids. Preprint, arXiv:1106.3088, 2011.
- [26] Charles Semple. -regular matroids. In Combinatorics, complexity, & logic (Auckland, 1996), Springer Ser. Discrete Math. Theor. Comput. Sci., pages 376–386. Springer, Singapore, 1997.
- [27] Charles Semple and Geoff Whittle. On representable matroids having neither - nor -minors. In Matroid theory (Seattle, WA, 1995), volume 197 of Contemp. Math., pages 377–386. Amer. Math. Soc., Providence, RI, 1996.
- [28] Charles Semple and Geoff Whittle. Partial fields and matroid representation. Adv. in Appl. Math., 17(2):184–208, 1996.
- [29] P. D. Seymour. Matroid representation over . J. Combin. Theory Ser. B, 26(2):159–173, 1979.
- [30] David Speyer and Lauren K. Williams. The positive Dressian equals the positive tropical Grassmannian. Preprint, arXiv:2003.10231, 2020.
- [31] William T. Tutte. A homotopy theorem for matroids, I. Trans. Amer. Math. Soc., 88:144–160, 1958.
- [32] William T. Tutte. A homotopy theorem for matroids, II. Trans. Amer. Math. Soc., 88:161–174, 1958.
- [33] William T. Tutte. Lectures on matroids. J. Res. Nat. Bur. Standards Sect. B, 69B:1–47, 1965.
- [34] Walter Wenzel. Projective equivalence of matroids with coefficients. J. Combin. Theory Ser. A, 57(1):15–45, 1991.
- [35] Geoff Whittle. A characterisation of the matroids representable over and the rationals. J. Combin. Theory Ser. B, 65(2):222–261, 1995.
- [36] Geoff Whittle. On matroids representable over and other fields. Trans. Amer. Math. Soc., 349(2):579–603, 1997.
- [37] Geoff Whittle. Recent work in matroid representation theory. Discrete Math., 302(1-3):285–296, 2005.