# Finding the vertices of a polyhedral complex coming from a GIT wall and chamber decomposition

I am interested in a polyhedral/combinatorics problem that arises in algebraic geometry in the context of geometric invariant theory (GIT).

Algebro-geometric background: Consider the natural diagonal action of $\text{SL}_{d+1}$ on $(\mathbb{P}^d)^n$. For each linearization $L$ one can consider the GIT quotient $(\mathbb{P}^d)^n//_L\text{SL}_{d+1}$. By the general theory known as "variation of GIT" developed by Thaddeus and Dolgachev-Hu, the space of linearizations $L$ is divided into a finite number of chambers such that as the linearization varies within the interior of a fixed chamber the corresponding GIT quotients do not change. The walls determining these chambers are the loci where there are strictly semistable points.

In the particular situation mentioned above this can be made quite explicit. Every ample divisor comes with a unique linearization for this $\text{SL}_{d+1}$ action, so the choice of a linearization is equivalent to the choice of an ample divisor on $(\mathbb{P}^d)^n$. This space has Picard group $\mathbb{Z}^n$, but it is convenient to tensor with $\mathbb{Q}$ and consider fractional linearizations. Moreover, taking tensor powers of the linearization does not affect stability, so one may normalize by assuming $L=(l_1,\ldots,l_n)\in\mathbb{Q}_{>0}^n$ satisfies $\sum_1^n l_i = d+1$. In this case the space of linearizations with nonempty GIT quotient is identified with the hypersimplex $\Delta(d+1,n)=\{(l_1,\ldots,l_n)\in\mathbb{Q}_{>0}^n\cap[0,1]^n~|~\sum_1^n l_i=d+1\}$, namely the intersection of a scaled standard simplex with the unit hypercube. The walls for this GIT problem are then all hyperplanes of the form $\sum_{i\in I}l_i = k$ where $I\subseteq\{1,\ldots,n\}$ and $1\le k \le d$.

Combinatorics problem: What are the vertices for this GIT decomposition? In other words, the walls $\sum_{i\in I}l_i = k$ (again, $I\subseteq\{1,\ldots,n\}$ and $1\le k \le d$) induce a polyhedral decomposition of the hypersimplex $\Delta(d+1,n)$ and I would like to know the vertices for this. The ideal answer would be a systematic way to describe all vertices, though I'm worried this may not be feasible. Another useful result would be an upper-bound on the number of vertices as a function of $n$ and $d$. There are algorithmic approaches that could compute the vertices for a fixed value of $n,d$, but I'm more interested in what kinds of general statements one could make about this set of vertices.

-
I don't know the answer, but I would like to mention the principal trick of my first paper: undivide each ${\mathbb P}^d$ by ${\mathbb G}_m$, resulting in a $GL(d+1) \times T^n$ action, then divide by the $GL(d+1)$ to get a Grassmannian $Gr(d+1,n)$, whose $T^n$-moment polytope is the hypersimplex you mention. This is a slight variant of the Gel$'$fand-MacPherson correspondence. –  Allen Knutson Apr 18 '11 at 1:43
This procedure identifies the space of linearizations for the SL action on projective space with the space of linearizations for the torus action on the Grassmannian. Moreover, the stability conditions carry over without modification, so that not only are the GIT quotients identified by this Gelfand-MacPherson type correspondence, but the entire VGIT pictures are identified, so finding the vertices in the torus case seems equivalent (in particular, no simpler) than for the SL action. But you think there's a way using toric or symplectic geometry for which this helps? –  Noah Giansiracusa Apr 18 '11 at 2:53
No, not really. The principal problem, as I'm sure you know, is that the vertices you're looking for "downstairs" don't correspond to anything "upstairs". For example, in Gr(2,4) the moment polytope is an octahedron, bisected by three equatorial planes. The planes mean something upstairs (e.g. the pencil of lines in $P^3$ touching the xy line and the zw line), but don't actually intersect there; they only intersect after one applies the moment map. –  Allen Knutson Apr 20 '11 at 0:46
Noah, interesting question! do you know the situation for small values of d? –  Gil Kalai Apr 20 '11 at 19:15
Thanks, Gil. The only cases I've seen people compute are small n and d=1. This question came up for d=1 in the paper of Alexeev and Swinarski called "Nef divisors on $\overline{M}_{0,n}$ from GIT." In fact, the reason I asked my question is in a direct attempt to generalize the main construction and technique from that paper to d>1. Dave Swinarski and Boris Alexeev (Valery's son!) have some nice computer software for computing the vertices (what they call "0-cells of the GIT complex") in a few cases: math.uga.edu/~davids/n456780cells.txt –  Noah Giansiracusa Apr 26 '11 at 13:52

This is not a real answer. However, I'd seen something closely related to this before, but they were tangential to what I cared about and I didn't sit and think about it. This question made me stop and think about it again (for way to long now), and I'm posting some of what I've learned as it may help, and that so I can get back to what I should have been doing the last few days -- though I really enjoyed thinking about this and would be happy to think more about it later.

So, all I really have is a slight reformulation that "reduces" your question to something I had seen before, that this has prompted me to ask MO about myself. You can see a tiny bit more structure after this reduction. Reduce is in quotes because I'm not sure it's any easier, or that the reduction is particularly effective computationally, but I did find it pleasing conceptually.

The way my previous experience has connections with your question is if we forget some of the structure you have, and simply consider the following central hyperplane arrangement in $\mathbb{R}^n$. Let the $x_i$ be the coordinate functions on $\mathbb{R}^n$. The hyperplane arrangement has one hyperplane for each of the $2^n-1$ nonempty subset $I\subset [n]$, with the corresponding equation given by: $$\sum_{i\in I} x_i=0.$$

Another description of the hypersimplex is to slice the unit $n$-cube by the $n-1$ hyperplanes $\sum x_i=k, 1\leq k \leq n$. Then the $n$-pieces that result are hypersimplices. So, rather than consider your problem one at a time, I'm going to stack up all the hypersimplices for fixed $n$ and varying $k$, and get a decomposition of the unit cube, and discuss the vertices of this decomposition. In a way this will give slightly more structure than you had looking at one hypersimplex at a time.

One could connect your problem to the hyperplane arrangement I've described above by also adding translations of the hyperplanes above and restricting to the unit cube, but here's a more pleasing way: let's take the quotient of $\mathbb{R}^n$ by the usual lattice $\mathbb{Z}^n$, and consider the same set of hyperplanes. The hyperplanes will now wrap around and give the translations of the hyperplanes as you ask above, giving a polyhedral decomposition of the $n$-torus -- you're asking for the vertices of this decomposition.

I should say that this trick of viewing this on the torus is in my head in part from skimming Alexeev's paper "Compactified Jacobians and the Torelli map", and that I first saw this hyperplane arrangement in my work on double Hurwitz numbers, which are piecewise polynomial, with walls given by this hyperplane arrangement, and which are rather conjecturally related to wall crossing behavior for some kind of universal compactified Jacobian.

One way to describe a vertex would be a set $J$ of $n$ hyperplanes in that arrangement intersecting transversally. Note that the same set of $n$ hyperplanes, as they wrap around, will in general intersect multiple times on the torus, so that the set $J$ will in general label some set $G_J$ of vertices of the decomposition. I have called this set $G_J$, because in fact they form a finite subgroup of the torus: the definition of $G_J$ essentially makes it the kernel of a surjective homomorphism from $T^n$ to $T^n$. And it is easy to figure out what this group $G_J$ is from the set $J$ of hyperplanes -- it's the usual way to get a finite abelian group from a cone from toric geometry.

So, though I found all of that pleasing, and at least some more can be done with it, I'm not sure it's actually helpful -- the hyperplane arrangement is huge and a mess, and I'm not saying we can just take the cones that correspond to chambers of the hyperplane arrangement -- I'd be surprised of that arrangement is simplicial, and even if it I see no reason that we could just consider the cones of regions of the arrangement anyway, and not arbitrary sets of transverse hyperplanes.

I will mention something else I learned, that you may already know and that Allen was pointing at and that I found out only in trying to understanding what Allen was saying. There's a rather natural decomposition of the hypersimplex into simplices, with vertices only the vertices of the hypersimplices, but it is not $S_n$ invariant, and your decomposition is what you get by acting by the $S_n$ action. I learned this just recently from the first few pages of Lam and Postnikov, Alcoved Polytopes I -- and rather than write it out I'll just send you there, though I'll note that I found it more convenient to imagine this happening on the torus rather than on the unit cube.

This naturally relates to Allen's comment connecting this to the moment map from the Grassmannian -- you're probably more aware of this than I am, but I found the introduction to his paper with Lam and Speyer on Positroid Varieties pertinent, as it talks about what this story means upstairs in the Grassmannian corresponds to, and that it's a huge mess, although perhaps it's somehow cleaner downstairs.

-