Ir al contenido

Documat

Oriented matroids from triangulations of products of simplices

  • Marcel Celaya [1] ; Georg Loho [2] ; Chi Ho Yuen [3]
    1. [1] Cardiff University

      Cardiff University

      Castle, Reino Unido

    2. [2] University of Twente

      University of Twente

      Países Bajos

    3. [3] Department of Applied Mathematics, National Yang Ming Chiao Tung University, Hsinchu City, Taiwan
    Mostrar afiliaciones +
  • Localización: Selecta Mathematica, New Series, ISSN 1022-1824, Vol. 30, Nº. 3, 2024, págs. 1-32
  • Idioma: inglés
  • DOI: 10.1007/s00029-024-00938-2
  • Enlaces
  • Resumen

    • We introduce a construction of oriented matroids from a triangulation of a product of two simplices. For this, we use the structure of such a triangulation in terms of polyhedral matching fields. The oriented matroid is composed of compatible chirotopes on the cells in a matroid subdivision of the hypersimplex, which might be of independent interest. In particular, we generalize this using the language of matroids over hyperfields, which gives a new approach to construct matroids over hyperfields. A recurring theme in our work is that various tropical constructions can be extended beyond tropicalization with new formulations and proof methods.

  • Referencias bibliográficas
    • Akian, M., Gaubert, S., Guterman, A.: Tropical polyhedra are equivalent to mean payoff games. Int. J. Algebra Comput. 22(1), 1250001 (2012).
    • Allamigeon, X., Benchimol, P., Gaubert, S., Joswig, M.: Tropicalizing the simplex algorithm. SIAM J. Discrete Math. 29(2), 751–795 (2015).
    • Allamigeon, X., Benchimol, P., Gaubert, S., Joswig, M.: Log-barrier interior point methods are not strongly polynomial. SIAM J. Appl. Algebra...
    • Anderson, L.: Representing weak maps of oriented matroids. Eur. J. Comb. 22(5), 579–586 (2001).
    • Anderson, L.: Vectors of matroids over tracts. J. Comb. Theory Ser. A 161, 236–270 (2019).
    • Anderson, L., Davis, J.F.: Hyperfield grassmannians. Adv. Math. 341, 336–366 (2019).
    • Ardila, F., Billey, S.: Flag arrangements and triangulations of products of simplices. Adv. Math. 214(2), 495–524 (2007).
    • Ardila, F., Ceballos, C.: Acyclic systems of permutations and fine mixed subdivisions of simplices. Discrete Comput. Geom. 49(3), 485–510...
    • Ardila, F., Develin, M.: Tropical hyperplane arrangements and oriented matroids. Math. Z. 262(4), 795–816 (2009).
    • Arkani-Hamed, N., Lam, T., Spradlin, M.: Positive configuration space. Commun. Math. Phys. 384(2), 909–954 (2021).
    • Baker, M., Bowler, N.: Matroids over partial hyperstructures. Adv. Math. 343, 821–863 (2019).
    • Benchimol, P.: Tropical aspects of linear programming. Theses, École Polytechnique (2014).
    • Bernstein, D., Zelevinsky, A.: Combinatorics of maximal minors. J. Algebraic Comb. 2(2), 111–121 (1993).
    • Björner, A., Vergnas, M.L., Sturmfels, B., White, N., Ziegler, G.M.: Oriented matroids. Encyclopedia of Mathematics and its Applications,...
    • Bokowski, J., Mock, S., Streinu, I.: On the Folkman-Lawrence topological representation theorem for oriented matroids of rank 3. Eur. J. Comb....
    • Celaya, M., Loho, G., Yuen, C.H.: Patchworking oriented matroids. J. Lond. Math. Soc. (2) 106(4), 3545–3576 (2022).
    • De Loera, J.A., Rambau, J., Santos, F.: Triangulations, Algorithms and Computation in Mathematics, vol. 25. Springer, Berlin (2010). Structures...
    • Develin, M., Sturmfels, B.: Tropical convexity. Doc. Math. 9, 1–27 (2004) (electronic), erratum ibid., pp. 205–206.
    • Dress, A.W.M., Wenzel, W.: Valuated matroids. Adv. Math. 93(2), 214–250 (1992).
    • Fink, A., Rincón, F.: Stiefel tropical linear spaces. J. Comb. Theory Ser. A 135, 291–331 (2015).
    • Folkman, J., Lawrence, J.: Oriented matroids. J. Comb. Theory Ser. B 25(2), 199–236 (1978).
    • Fukuda, K.: Oriented matroid programming. ProQuest LLC, Ann Arbor, MI, 1982, Thesis (Ph.D.)– University of Waterloo (Canada).
    • Gawrilow, E., Joswig, M.: polymake: A framework for analyzing convex polytopes. In Polytopes—combinatorics and computation (Oberwolfach, 1997),...
    • Gelfand, I.M., Kapranov, M.M., Zelevinsky, A.V.: Discriminants, Resultants, and Multidimensional Determinants, Mathematics: Theory & Applications....
    • Goodman, J.E., O’Rourke, J. (eds.): Handbook of Discrete and Computational Geometry, 2nd edn. Chapman & Hall/CRC, Boca Raton (2004).
    • Grünbaum, B.: Conference Board of the Mathematical Sciences. Arrangements and spreads. Regional conference series in mathematics, Conference...
    • Gurvich, V.A., Karzanov, A.V., Khachiyan, L.G.: Cyclic games and finding minimax mean cycles in digraphs. Zh. Vychisl. Mat. i Mat. Fiz. 28(9),...
    • Herrmann, S., Joswig, M., Speyer, D.E.: Dressians, tropical Grassmannians, and their rays. Forum Math. 26(6), 1853–1881 (2014).
    • Horn, S.: A topological representation theorem for tropical oriented matroids. J. Comb. Theory Ser. A 142, 77–112 (2016).
    • Kapranov, M.M.: Chow quotients of Grassmannians. I. In I. M. Gelfand seminar. Part 2: Papers of the Gelfand seminar in functional analysis...
    • Loho, G.: Abstract tropical linear programming. Electron. J. Comb. 27(2), research paper p2.51, 68 (2020).
    • Loho, G., Smith, B.: Matching fields and lattice points of simplices. Adv. Math. 370, 107232 (2020).
    • Lorscheid, O.: Categories of matroids and matroid bundles (2023). https://www.birs.ca/events/2023/5-day-workshops/23w5149/videos/watch/202303131033-Lorscheid.html...
    • Lukowski, T., Parisi, M., Williams, L.K.: The Positive Tropical Grassmannian, the Hypersimplex, and the m = 2 Amplituhedron. Int. Math....
    • Massouros, C.G.: Constructions of hyperfields. Math. Balkanica (N.S.) 5(3), 250–257 (1991).
    • Murota, K.: Discrete Convex Analysis. SIAM Society for Industrial and Applied Mathematics, Philadelphia, PA (2003).
    • Postnikov, A.: Permutohedra, associahedra, and beyond. Int. Math. Res. Not. 6, 1026–1106 (2009).
    • Rincón, F.: Local tropical linear spaces. Discrete Comput. Geom. 50(3), 700–713 (2013).
    • Santos, F.: The Cayley trick and triangulations of products of simplices. In Integer points in polyhedra—geometry, number theory, algebra,...
    • Schrijver, A.: Matroids and linking systems. J. Comb. Theory Ser. B 26(3), 349–369 (1979).
    • Speyer, D., Sturmfels, B.: The tropical Grassmannian. Adv. Geom. 4(3), 389–411 (2004).
    • Speyer, D., Williams, L.K.: The positive Dressian equals the positive tropical Grassmannian. Trans. Am. Math. Soc. Ser. B 8, 330–353 (2021).
    • Speyer, D.E.: Tropical linear spaces. SIAM J. Discrete Math. 22(4), 1527–1558 (2008).
    • Speyer, D.E.: A matroid invariant via the K-theory of the Grassmannian. Adv. Math. 221(3), 882–913 (2009).
    • Sturmfels, B., Zelevinsky, A.: Maximal minors and their leading terms. Adv. Math. 98(1), 65–112 (1993).
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno