WorksMathematics
Maximum number of cells in a matroid subdivision of hypersimplex
Abstract
David Speyer proved that the maximum number of cells in a regular matroid subdivision of the hypersimplex is , using the language of tropical geometry and properties of the Tutte polynomial of a matroid \cite[Theorem 6.1]{Speyer}. In this paper, we prove this result in general, i.e. for arbitrary matroid subdivisions including the non-regular ones. We perform a different combinatorial way using our results in \cite{HHH} and independent of tropical language.
Introduction
Triangulations and subdivisions are among the most important notions in convex geometry as well as in algebraic geometry and topology. For example in toric geometry, we can associate an algebraic variety to a triangulation of a special polytope. More generally we can consider face-fitting decompositions, in which we do not need the smaller polytopes to be simplices anymore. One of the most important special cases is a subdivision of hypersimplex
by matroid polytopes. In fact, the hypersimplex is itself the polytope of the uniform matroid and its subdivision is also considered in matroid theory [12]. On the other hand one can construct toric varieties from matroid polytopes involved in a matroid subdivision and attach them to get the so called stable varieties or ”shas”(stable hyperplane arrangements) as explained in [7]. A natural question is what is the maximum number of irreducible components in a ”shas” obtained by a matroid subdivision of hypersimplex ? Or, in another words, what is the maximum number of polytopes in a matroid subdivision of the hypersimplex? We will recall some definitions from matroid theory:
Definition 1.1. A matroid is a pair , where is a collection of subsets of satisfying the properties below:
If and , then
If and , there exists such that .
We also denote the matroid simply by .
Definition 1.2. If the pair is a matroid, the elements of are called independent sets of the matroid.
Matroids can also be defined via their bases:
Definition 1.3. Let the pair be a matroid, a subset is called a basis if it is a maximal independent set. We denote the set of all bases by or .
Definition 1.4. The matroid polytope of a matroid is the convex hull of the points with . It is a polytope in and is denoted by or .
Two operations can be performed on matroids, one is deletion and the other is contraction:
Definition 1.5. Let be a matroid and . Put
Then the pair is also a matroid, called the deletion of and is denoted by .
Definition 1.6. Let be a matroid and . Put
Then the pair is also a matroid, called the contraction of and is denoted by .
The notion of rank function for a matroid is essential in our study:
Definition 1.7. Let be a matroid and . The rank of , denoted by , is defined to be the cardinality of a basis of .
We will work with two kinds of matroids:
Definition 1.8. A matroid of rank is linear if there are vectors in such that a subset is independent if and only if the set is linearly independent over .
There is a notion of connectedness in matroid theory which is useful for our aim.
Definition 1.9. A matroid is connected if one cannot decompose the ground set
such that a subset is independent if and only if
where , and are independent.
Definition 1.10. A collection of maximal matroid polytopes in is a matroid decomposition of if and they intersect face-fittingly; i.e., for each pair and , is either empty or a face of both and .
It is proven by Herrmann, Jensen, Joswig, and Sturmfels that the maximum number of cells in a matroid subdivision of the hypersimplex is not bounded by a constant [10]. Valery Alexeev also proved that this number is bounded by for [7]. Finally, David Speyer proved that for all the maximum number of cells in a regular matroid subdivision of is . In this article we extend this result to all arbitrary (including non-regular) matroid subdivisions of via the ideas written in [13]. We hope our new approach also helps us to answer a question about the Dressian fan in tropical geometry, denoted by . We briefly state the question below:
Every element in the Dressian fan determines a matroid subdivision for . The number, spread of an element in the Dressian, is the number of maximal cells in the corresponding matroid subdivision of hypersimplex. Question 35 in [11] states:
What is the maximal spread of a ray of (at least for )?
In the question above, rays correspond to subdivisions that cannot be coarsened, i.e. if you want to coarsen it, you will only get the whole hypersimplex . We hope that the recursive process that we used for the previous problem can also be used to solve the problem above.
Relation to inverse limit of point configurations
The notion of inverse limit for an action of an algebraic group on an algebraic variety was studied in [5] using Geometric Invariant Theory [9] and its variation [4, 3]. For a reference concerning this matter and the special case of point configurations see [2].
Definition 2.1. A point configuration with parameters is a tuple such that for every . We also assume that we have at least general points in this configuration.
One can consider finitely many quotients of the natural action of on , provided by Geometric Invariant Theory, and consider their inverse limit. In fact, for every weight , we have a corresponding moduli space parametrizing -semistable representations up to -equivalence. Based on the Geometric Invariant Theory literature, they form an inverse system and we denote this inverse limit by .
In fact, the walls for , decompose the hypersimplex into finitely many chambers. For each chamber in this decomposition, we have a distinct moduli space. We can specify a representative for each chamber; this representative determines the corresponding moduli space . The inverse limit is a closed subvariety of , where is the set which has exactly one weight as a representative from each chamber. In this way, we can denote each element of the inverse limit as such that .
We need to establish some notations:
Notation 2.1. Let be the standard basis vectors of . Suppose , and .
In the above notations, the particular case is of interest to us. In this case we have
We will work with both of them multiple times.
In the paper [13], we construct algebraic morphisms
for every which are called deletion and contraction maps. They are analogous to the well-known maps of the Kapranov-Chow quotients of Grassmannians [6]. One can combine the deletion and contraction maps for a fixed simultaneously to get the natural morphism
If we have a point of the inverse limit , this gives us a matroid decomposition of the hypersimplex for by [13 Theorem 1.14], we can apply the morphisms above to get elements in and and decompositions for and respectively.
In fact these morphisms are derived from natural maps:
where and are obtained from the representation by applying the deletion and contraction process over point for each as explained in [13 Definition 3.14,Definition 3.15]. In this definition, chambers of the hypersimplices and are obtained with intersecting of chambers of with respectively. So if we have a point of the inverse limit in the images would be tuples of the form and respectively.
For a point inside the inverse limit , we denote the maximum number of cells in the corresponding subdivision of hypersimplex by . Then we can get a recursive formula if we prove the items below:
Every component of and is obtained from one component of .
Every component of the initial element of in appears in at least one(or both) of the components of the images and in and respectively.
If we prove these two facts, then we have:
To see why this is true, take a tuple with maximal cells which is a point of the inverse limit , the items (1), (2) in the previous paragraph show that we can decompose the cells of this tuple into union of two sets such that and are the maximal cells of the images in and respectively, so
Thus using induction on and Pascal identity, we get
for and and the bound is achieved. The base of induction is also clear .
It is quite easy to see that both of (1), (2) are satisfied for point configurations or linear matroids. With this motivation we prove (1),(2) for general matroids in theorem 3.5 and state this bound for every matroid decomposition of hypersimplex independent of inverse limit and regularity concept.
Proof that the bound is working
We first establish some notation and lemmas, specially the lemma below, which is well-known in matroid theory.
Lemma 3.1. Let be an abstract matroid, the matroid polytope is of maximal dimension if and only if the matroid is connected.
Proof. Dimension of the matroid polytope can be computed using [14 Proposition 2.4], i.e
where is the number of connected components of the matroid . Notice that a matroid is connected if and only of . Since the matroid polytope is a sub-polytope of the hypersimplex and the result is driven.
Notation 3.1. If is a matroid and , we can operate the Deletion and Contraction process, over point and get two new matroids and with indices .
We also need the definition of isomorphism between matroids:
Definition 3.2. Two abstract matroids and are isomorphic if there is a bijective map such that for every subset , if and only if .
Definition 3.3. We say two matroid subdivisions
and
are isomorphic if there is a bijection between their cells, i.e there are isomorphisms of matroids for .
Let be the set of all matroid subdivisions of the hypersimplex up to the notion of isomorphism defined in the above. We will construct the map below analogous the inverse limit one:
Here we should notice that since the decomposition is face-fitting, after intersecting with and , it will remain face-fitting. We should also prove that both of the components and are matroid polytopes. We will prove this in the proposition below:
Proposition 3.4. If is an abstract matroid such that is of maximal dimension and , then
Proof. Definition of matroid polytope says:
Based on the assumption the matroid polytope is of maximal dimension. Thus lemma 3.1 implies that the matroid is connected and the element is neither loop nor coloop. So we have
:::
Now it is easy to see the isomporphisms. □
Now if we prove items (1), (2) of the theorem below, then we get the required bound by the same way as before.
Theorem 3.5. With the notations above, we have:
(1) Every maximal component of and is obtained from one component of .
(2) Every component of the initial decomposition in appears in at least one of the maximal components of the images and in and respectively.
Proof. Item (1) is clear. For (2) notice that the intersection and could be non-maximal, in this case they are not computed as a maximal component. We should prove that for every component at least one of or is maximal. This is proven in the next proposition. □
Proposition 3.6. At least one of the polytopes or is maximal dimensional.
Proof. Based of proposition 3.4 we have to prove at least one of the polytopes or is of maximal dimensional. By lemma 3.1 we should prove that either or is connected. Since , the matroid polytope is of maximal dimension, so is connected. As known in matroid theory, Theorem 4.3.1 in Oxley book [8] implies that either or is connected. □
Corollary 3.7. Maximum number of maximal cells in an arbitrary matroid decomposition of hypersimplex is .
Acknowledgement
I would like to express my gratitude to my advisors, Prof. Lutz Hille and Prof. S. Mohammad Hadi Hedayatzadeh, for their constant support and invaluable guidance. In particular, I am grateful to Prof. Lutz Hille for introducing me to this interesting problem and the concept of inverse limit, which played a key role in shaping my research.
3 Department of Mathematics, IPM - Institute for Research in Fundamental Sciences, Tehran, Iran
Email address: [email protected]
References
- [2]M. Blume and L. Hille. Quivers and moduli spaces of pointed curves of genus zero, Algebr. Comb., 4(1):89–124, 2021 https://doi.org/10.5802/alco.152
- [3]I. Dolgachev, Y. Hu, Variation of geometric invariant theory quotients, Publ. Math. IHES 87 (1998), 5–51 https://doi.org/10.1007/BF02698859
- [4]M. Thaddeus, Geometric invariant theory and flips. Journal of the American Mathematical Society, vol. 9, no. 3, pp. 691–723, 1996. https://arxiv.org/pdf/alg-geom/9405004
- [5]M. Thaddeus, Complete collineations revisited. Math. Ann. 315 (1999), 469–495, https://doi.org/10.1007/s002080050324
- [6]M. Kapranov, Chow quotients of Grassmannians I, Adv. Soviet Math. 16 (1993), 29–110, https://arxiv.org/abs/alg-geom/9210002
- [7]Valery Alexeev, Moduli of Weighted Hyperplane Arrangements, Advanced Courses in Mathematics. CRM Barcelona, Springer , Basel, 2015. https://doi.org/10.1007/978-3-0348-0915-3
- [8]James Oxley. Matroid theory, Oxford University Press, 2011. https://www.math.ens.psl.eu/~benoist/refs/Oxley.pdf.
- [9]D. Mumford, J. Fogarty, F. Kirwan: Geometric invariant theory. Third edition. Ergebnisse der Mathematik und ihrer Grenzgebiete (2), 34. Springer-Verlag, Berlin, 1994. https://link.springer.com/book/9783540569633
- [10]Herrmann, Jensen, Joswig, Sturmfels, How to draw tropical planes, Electron. J. Combin. 16 (2009), no. 2, Special volume in honor of Anders Bjorner, Research Paper 6, 26. https://arxiv.org/pdf/0808.2383
- [11]S.Herrmann, M.Joswig, D.Speyer, Dressians, tropical Grassmannians, and their rays. Forum Math. 26(6), 2014. https://arxiv.org/pdf/1112.1278
- [12]M. Cleya, G.Loho, C. Yuen, Oriented matroids of triangulations of products of simplices, Selecta Mathematical, 2024, Springer. https://arxiv.org/pdf/2005.01787
- [13]M. Hedayatzadeh, M. Hasani, Inverse limit and Chow quotient of point configurations in projective spaces are not isomorphic, preprint, 2026.
- [14]E. Feichtner, B. Sturmfels, Matroid polytopes, nested sets and Bergman fans, Port. Math. (N.S.), 62 (2005), pp. 437–468.