Combinatorial Foundations of Tropical and Oriented Matroids

This direction is split into other directions: matroid representability. Its last version stays readable and citable here.

Version 1 of 129 papers38 conceptsfrozen 2026-10-04

Matroid theory has long served as the abstract language of linear independence. Traditionally, we think of matroids as collections of vectors in a coordinate space, where "independence" is defined by linear combinations. However, a significant portion of the matroid universe is "non-realizable"—meaning these structures satisfy the combinatorial axioms of independence but cannot be represented by any matrix over any field.

Recent research is bridging this gap by moving away from classical coordinates and toward tropical geometry and oriented matroids. This shift allows researchers to treat complex geometric and optimization problems as purely combinatorial objects, revealing the deep structural rules that govern everything from secret sharing to auction design.

The Tropical Bridge to Independence

Tropical geometry replaces standard addition and multiplication with the "min-plus" algebra. In this setting, the "lines" and "planes" of classical geometry become polyhedral fans and piecewise-linear structures. Georg Loho and Raman Sanyal have demonstrated that this is not just an algebraic curiosity; it provides a new home for matroid theory.

By proving a tropical version of the Matroid Carathéodory Theorem, Loho and Sanyal showed that the convex hulls of tropical points are fundamentally governed by matroid rank conditions. Unlike classical geometry, where these theorems rely on topological continuity, the tropical versions are driven by covector graphs—combinatorial maps that track how points sit relative to one another. This framework allows us to analyze "monomial" tropical polyhedra as algebraic objects, specifically encoding the properties of monomial ideals in commutative algebra Loho and Smith.

Constructing Matroids from Triangulations

One of the most difficult challenges in the field is finding a systematic way to generate non-realizable matroids—those "pathological" cases that linear algebra cannot reach. Marcel Celaya and Chi Ho Yuen discovered a surprising source for these objects: triangulations of products of simplices.

The intuition is that the way we subdivide a high-dimensional shape (a product of simplices) into smaller pieces (triangles or simplices) implicitly defines a set of "orientation" rules. Celaya proved that by selecting specific terms from the combinatorial data of these triangulations—a method called "polyhedral matching fields"—one can satisfy the complex axioms of oriented matroids. This construction is powerful enough to produce famous non-realizable examples like Ringel’s matroid, suggesting that the boundary between "matrix-based" geometry and "abstract" combinatorics is thinner than previously thought.

Valuations and the Limits of Construction

In discrete convex analysis, the focus shifts to valuated matroids, where independence is paired with a weight or "valuation" function. This is critical for mathematical economics, particularly in modeling stable matchings and auctions. For years, the Matroid Based Valuation (MBV) Conjecture suggested that all such structures could be built from a single universal block: weighted bipartite matchings.

However, Edin Husic, Georg Loho, and László A. Végh recently refuted this conjecture. By showing that some valuated matroids cannot be represented as "R-minors" of matchings, they proved that the world of discrete convexity is more diverse than our current constructive frameworks can capture. This result has immediate implications for the study of Lorentzian polynomials, which are used to prove the log-concavity of sequences in combinatorics.

The Computational Hardness of Being Realizable

If non-realizable matroids are so prevalent, why not just check if a given matroid has a matrix representation? Arnaud de Mesmay, Eun Jung Kim, and Tillmann Miltzow have provided a sobering answer: the problem is $\exists\mathbb{R}$-complete.

This means that deciding if an abstract matroid can be represented by real vectors is as difficult as finding the real roots of a system of high-degree multivariate polynomials. It places matroid representability in the same complexity class as the "Art Gallery Problem" or "Graph Drawing," confirming that the gap between combinatorial independence and geometric realization is a fundamental computational barrier.

Structural Guarantees and Girth

Despite these complexity hurdles, certain classes of matroids behave predictably. Nisheeth K. Vishnoi and Rohit Gurjar showed that for regular matroids (those representable over every field), the number of "near-minimum" circuits is polynomially bounded. This provides a structural "safety net" for algorithms working with linear codes and lattices.

Furthermore, James Davies and Rose McCarty recently settled a long-standing conjecture regarding girth in matroids representable over finite fields. They proved that if a representable matroid has a sufficiently large girth (the size of its smallest dependent set), it must contain a specific structural "clique" as a minor. This links the density of the matroid to its unavoidable internal structures, though extending this from finite fields to all matroids remains a major open frontier.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_combinatorial_foundations_of_tropical_an_f1eec8e7,
  title = {Combinatorial Foundations of Tropical and Oriented Matroids},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/combinatorial-foundations-of-tropical-and-oriented-matroids/rdr_f1eec8e752674f94ae5b983690d98a46},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_combinatorial_foundations_of_tropical_an_f1eec8e7_v1,
  title = {Combinatorial Foundations of Tropical and Oriented Matroids},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/combinatorial-foundations-of-tropical-and-oriented-matroids/rdr_f1eec8e752674f94ae5b983690d98a46/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}