# Why do combinatorial abstractions of geometric objects behave so well?

This question is inspired by a talk of June Huh from the recent "Current Developments in Mathematics" conference: http://www.math.harvard.edu/cdm/.

Here are two examples of the kind of combinatorial abstractions of geometric objects referred to in the title of this question:

• Coxeter groups. These are abstractions of Weyl groups. Weyl groups have geometry coming from Lie theory: they are finite reflection groups associated to a crystallographic root system. Weyl groups (or perhaps finite reflection groups, or including Weyl groups associated to affine lie algebras, etc.) are then the "realizable" Coxeter groups.
• Matroids. These are abstractions of collections of vectors in some vector space. The matroids coming from collections of vectors in some vector space (over some field, say) are again the "realizable" matroids.

Here is what I mean by "behave so well":

Often it happens that we can associate some interesting polynomial invariant to the combinatorial object in question. Some examples are:

• The Kazhdan-Lusztig (KL) polynomial associated to a Coxeter system.
• The characteristic polynomial associated to a matroid.
• The recent KL polynomial associated to a matroid (see https://arxiv.org/abs/1412.7408).

And these polynomials have surprising and deep properties (positivity or unimodality/log-concavity of coefficients) that are not at all obvious from their definitions. A recurring theme is that these properties can be established in the "realizable" cases by appealing to algebraic geometry, specifically, to some suitable cohomology theory. However, the properties continue to hold for the general, nonrealizable objects for which there is no underlying geometry. The proofs of the general result are usually more "elementary" in so far as they avoid any algebraic geometry; but chronologically they come after the realizable results.

For instance, the coefficients of KL polynomials associated to a Coxeter system are positive. This was a famous conjecture of Kazhdan-Lusztig, proved a few years ago by Elias and Williamson (https://arxiv.org/abs/1212.0791). However, positivity was known for realizable Coxeter groups much earlier by interpreting the polynomials as Poincaré polynomials for the intersection cohomology of certain Schubert varieties.

Similarly, it is conjectured that the KL polynomial of a matroid has positive coefficients (see https://arxiv.org/abs/1611.07474); and this conjecture is known to be true when the matroid is realizable, again by interpreting the coefficients as dimensions of intersection cohomology spaces on certain varieties.

Or for the characteristic polynomial of a matroid: we know that the coefficients of this polynomial are log-concave, as was recently proved in the remarkable work of Adiprasito-Huh-Katz (https://arxiv.org/abs/1511.02888). Again, this result was preceded by the same result for the realizable case, due to Huh-Katz (https://arxiv.org/abs/1104.2519), interpreting the coefficients as intersection numbers for some toric variety.

So we come to my question:

Why do combinatorial abstractions of geometric objects behave so well, even in the absence of any underlying geometry?

EDIT: At around the 50 minute mark of his plenary talk at ICM 2018 (on Youtube here: https://www.youtube.com/watch?v=-3q6C558yog), Geordie Williamson asks a roughly similar question, and suggests that it may be a "mystery for the 21st century."

EDIT 2: As mentioned in the answers of Gil Kalai and Karim Adiprasito, another good example of "combinatorial abstraction of geometric object" is the notion of simplicial sphere, where the realizable case is a boundary of a polytope. Here the realizable case is connected to algebraic geometry via the theory of toric varieties, and as always this connection enables one to prove deep positivity results (e.g. the g-theorem of Stanley); whereas again the same results for the nonrealizable case are apparently much harder and the subject of intense, current research.

EDIT 3: I'm including a very relevant passage from a preprint of Braden-Huh-Matherne-Proudfoot-Wang (https://arxiv.org/abs/2010.06088).

Remark 1.13 It is reasonable to ask to what extent these three nonnegativity results can be unified. [The three results here are the nonnegativity of the coefficients of the KL polynomial of an arbitrary Coxeter group, the $$g$$-polynomial of an arbitrary polytope, and the KL polynomial of an arbitrary matroid.] In the geometric setting (Weyl groups, rational polytopes, realizable matroids), it is possible to write down a general theorem that has each of these results as a special case. However, the problem of finding algebraic or combinatorial replacements for the intersection cohomology groups of stratified algebraic varieties is not one for which we have a general solution. Each of the three theories described above involves numerous details that are unique to that specific case. The one insight that we can take away is that, while the hard Lefschetz theorem is typically the main statement needed for applications, it is always necessary to prove Poincaré duality, the hard Lefschetz theorem, and the Hodge–Riemann relations together as a single package.

• Remarkable question! My hope is that cohomology theories used for the realizable structures are in fact partial cases of more general theories, which work in the same way for more general combinatorial structures. Nov 27, 2016 at 19:23
• I disagree with the claim that general Coxeter groups are "objects for which there is no underlying geometry". I recommend reading the book "The Geometry and Topology of Coxeter Groups" by Mike Davis. Nov 27, 2016 at 22:05
• @UriBader: it's a fair response. Perhaps one answer could be exactly that all these objects are "realizable" in some generalized sense (e.g., all matroids are realizable over hyperfields, see: arxiv.org/abs/1601.01204). But still, in the general case, the geometry is far from clearly explaining why these deep properties of the associated polynomials hold. Nov 27, 2016 at 22:11
• Is there anything wrong with the following point of view? What we are learning is that the correct "explanation" of positivity and log-concavity is combinatorial, rather than geometric. We tend to think of geometry as "explaining" these things only because that's the familiar, easier case, but once we get more familiar with combinatorics, we'll come to see the combinatorial proof as the natural one. Nov 28, 2016 at 16:38
• I'm not an expert on this by any means, but in the Adiprasito-Huh-Katz paper that proves some log-concavity conjectures for general matroids, what's roughly happening (and this is not really discussed in the paper, the terminology is more combinatorial) is that there is in fact underlying geometry. In this case, the geometry is tropical. Matroids in some sense are exactly the tropical varieties of degree 1. (This can be seen as the generalized sense 'of "realizable" you mentioned). Sep 19, 2017 at 17:07

Perhaps this, for now, is more an issue of perspective. Yes, for matroids, spheres and Coxeter groups the realizable cases were known before using results in algebraic geometry, but this is natural as our understanding of the cohomology of algebraic varietes was much better, historically. And so we think of this as strange because we are used to think of this in terms of algebraic varieties.

However, matroids, for instance, are perhaps more naturally thought of in the context of valuations, and there, it suddenly becomes more natural to consider McMullen's argument for the Lefschetz theorem and the Hodge-Riemann relations (and this is ultimately what is used).

Similarly, spheres are rarely ever polytopal, and even for those that are, the realization as a polytope is an unnatural straightjacket. We do, however, understand them well in terms of cobordisms, and we do know general position tricks from when we define intersection products in cohomology. And this ultimately leads to the Lefschetz theorem there.

As Uri Bader remarked one has to be careful with the term "combinatorial abstraction". In the cases mentioned by Sam and in other cases the geometric objects are certain algebraic varieties but the abstractions often refers to other geometric or topological objects. Let me give three examples. (I will add links later.)

A) The $$g$$-theorem and KL-polynomials For example: convex polytopes which are geometric objects leads in the special case of rational polytopes to toric varieties. The standard conjectures for those translate back to some combinatorial statements on the so called g-polynomials (The "g-theorem") which extends to general polytops and, in fact, to much much more general cellular decompositions of spheres. (Very recently Adiprasito proved the "g-conjecture" to general homology spheres.) June Huh videotapes lecture also from ICM 2018 suggests that the standard package of conjectures ((PD) Poincare duality, (HL) Hard Lefschetz, and (HR) Hodge Riemann) extends to many contexts where the algebraic varieties do not exist. Adiprasito's work asserts that positivity of Hodge Riemann relations can be replaced by "genericity" in even greater generality.

One can note that the combinatorial consequences of Poincare duality follows combinatorially from Euler-Poincare relations and thus extends to arbitrary Eulerian graded posets which are indeed very large class of combinatorial objects.

Here an ultimate fantasy would be to extend KL-polynomials to arbitrary regular CW spheres and perhaps even to cellular objects beyond that.

I should mention that there is even another level of combinatorial extensions (with geometric flavor). We expect that certain combinatorial objects (like KL polynomials) extend "on the nose" to much greater generality beyond cases where the algebraic varieties exist, and we also expect that certain combinatorial consequences extend qualitatively to even much more general objects.

Closely related is the remarkable extensions of the intersection homology of toric vrieties (Described by the toric h-vector) from the case of rational polytopes (where toric varieties exist) to the case of general polytopes. Also here some of the combinatorics requires only the Euler relatio. In series of works by Barthel, Brasselet, Fieseler and Kaup, Bressler and Lunts and Karu. Extending this apparatus to polyhedral spheres is an open conjecture.

B) The Upper bound theorem Let me demonstrate these relations with another example: The upper bound theorem (UBT).

The UBT asserts that among all $$d$$-polytopes with $$n$$ vertices the number of $$k$$-faces is maximized by the cyclic $$d$$-polytope with $$n$$ vertices.

1) For Eulerian simplicial complexes Klee proved that UBT holds when $$n>Cd^2$$. (It is not known if the conjecture holds for every $$n$$ in this generality.)

2) McMullen proved the UBT for polytopes based on shellability. (Thus the proof extends to a large class of strongly shellable simplicial spheres.

3) Stanley proved the UBT for all simplicial spheres using the connection to Cohen Macaulay rings.

4) There are large classes of geometric objects where the qualitative statement: the number of facets is $$\le Cn^{[d/2]}$$ can be proved.

5) The UBT was proved for all Eulerian manifolds by Novik

6) The UBT (and a much stronger statement called the generalized UBT) is conjectured for all subcimplexes of cellular Witt spaces (with the lattice property) with vanishing middle intersecion homology.

We see here all sort of geometric and combinatorial abstractions. For rational simplicial polytopes the cohomology ring of the toric variety (that leads to Stanley's g-theorem) also "explains" the UBT. Toric varieties extends to general rational polytopes but there we do not know to derive the GUBT from information on their (intersection) homology.

C) The Erdos-Moser conjecture. Stanley used the Hard Lefschetz theorem to prove the Erdos-Moser theorem giving a Sperner property for a certain Poset. Also here the underlying algebraic reason (this time via representation theory) could be proved directly (without using algebraic varieties) but I am not sure to what extent this proof extends to more general objects where varieties do not exist (Ill try to check it). The combinatorial phenomenon behind Erdos-Moser conjecture (which goes back to Sarkozy and Szemeredi) extends in various ways related to combinatorics, probability, and additive number theory. A crucial related theory is by Halasz.

I'm not exactly addressing your question about combinatorial abstractions of geometric objects, but you seem to be taking Lie theory as a given natural geometric arena.

On the contrary, the development of Lie theory itself is an awesome abstraction from even more concrete geometric notions. Some early avatars are given by the identification of $$\mathfrak{so}(3)$$ with $$\mathbb{R}^{3}$$ equipped with the cross product, or the Heisenberg Lie algebra popping out of considerations in the early days of quantum mechanics, both examples having their origins in physics. In this case, I would wager that the abstraction to the general definition of a Lie algebra works so well because the way you prove anything about these concrete examples is by using their apparent algebraic properties, which is exactly what is being codified in passing to an abstract Lie algebra.

Furthermore, I'm not so sure I'd say that abstractions of geometric objects necessarily behave so well. Using my above example again, the theory of general Lie algebras is kind of a mess (we'll never classify nilpotent Lie algebras for example), but it's an extremely rich mess that has various alleyways which are amenable to a deep analysis and classification scheme (e.g semi-simple Lie algebras).

In my opinion, the idea that abstractions of geometric objects don't have an underlying geometric companion is an ode to a romantic sense that there is some mystical quality about certain geometric objects. While I would count myself as a mystic in this sense, maybe at the end of the day the reason things "behave well" is because the abstractions aren't really any less geometric than the original objects of study, as others have mentioned above.