# Arrangements Of Minors In The Positive Grassmannian And a Triangulation of The Hypersimplex

Miriam Farber, Yelena Mandelshtam

► To cite this version:

Miriam Farber, Yelena Mandelshtam. Arrangements Of Minors In The Positive Grassmannian And a Triangulation of The Hypersimplex. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.499-510, 10.46298/dmtcs.2469 . hal-01337798

HAL Id: hal-01337798

https://hal.science/hal-01337798

Submitted on 27 Jun 2016

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Arrangements of minors in the positive Grassmannian and a triangulation of the hypersimplex

Miriam Farber<fnref n="1" />† and Yelena Mandelshtam<fnref n="2" />

**Abstract.** The structure of zero and nonzero minors in the Grassmannian leads to rich combinatorics of matroids. In this paper, we investigate even richer structure of possible equalities and inequalities between the minors in the positive Grassmannian. It was previously shown that arrangements of equal minor of largest value are in bijection with the simplices in a certain triangulation of the hypersimplex that was studied by Stanley, Sturmfels, Lam and Postnikov. Here we investigate the entire set of arrangements and its relations with this triangulation. First, we show that second largest minors correspond to the facets of the simplices. We then introduce the notion of cubical distance on the dual graph of the triangulation, and study its relations with arrangement of t-th largest minors. Finally, we show that arrangements of largest minors induce a structure of partially ordered set on the entire collection of minors. We use the Lam and Postnikov circuit triangulation of the hypersimplex to describe a 2-dimensional grid structure of this poset.

**Résumé.** La structure des mineurs nuls et non nuls dans la Grassmannienne amène à une combinatoire très riche de matroïdes. Dans cet article, nous examinons la structure encore plus riche des égalités et inégalités possibles entre les mineurs de la Grassmannienne positive. Il a été montré précédemment que les arrangements de mineurs égaux de valeur maximale sont en bijection avec les simplexes d'une certaine triangulation de l'hypersimplexe étudiée par Stanley, Sturmfels, Lam et Postnikov. Nous examinons ici l'ensemble total des arrangements et ses relations avec cette triangulation. Tout d'abord, nous montrons que les deuxièmes plus grands mineurs correspondent aux facettes des simplexes. Nous introduisons ensuite la notion de distance cubique sur le graphe dual de la triangulation, et nous étudions ses relations avec l'arrangement des t-ièmes plus grands mineurs. Enfin, nous montrons que les arrangements de mineurs maximaux induisent une structure d'ensemble partiellement ordonné sur la collection totale des mineurs. Nous utilisons la triangulation-circuit de Lam et Postnikov de l'hypersimplexe pour décrire une structure de réseau 2-dimensionnel sur ce poset.

**Keywords:** the positive Grassmannian, sorted sets, triangulations, alcoved polytope, positroid stratification

<footnote n="1">¹Massachusetts Institute of Technology, Department of mathematics.</footnote>

<footnote n="2">²University of California Irvine, Department of Mathematics.</footnote>

<footnote>†Email: mfarber@mit.edu</footnote>
# 1 Introduction

In this paper, we study the relations between equalities and inequalities of minors in the positive Grassmannian and the triangulation of the hypersimplex. This study is strongly tied to various combinatorial objects such as the positive Grassmannian and its stratification [Pos06], alcoved polytopes [LP07], sorted sets and Gröbner bases [Stu96], as well as many other objects in algebraic combinatorics and beyond.

The notion of total positivity was originally introduced by Schoenberg [Sch30] and Gantmacher and Krein [GK41] in the 1930s. The classical theory of total positivity deals with totally positive matrices—matrices in which all minors of all orders are positive. Later, the theory was extended by Lusztig in the general Lie theoretic setup through definition of the positive part for a reductive Lie group $G$ and a generalized partial flag manifold $G/P$. In [Pos06] it was shown that the space of totally positive matrices can be embedded in the positive Grassmannian, and this embedding unveils symmetries which are hidden on the level of matrices. Thus it is very natural to discuss equalities and inequalities of minors in the more general settings of the positive Grassmannian.

The number and positioning of equal minors in totally positive matrices was studied in several recent papers. In [FFJM14], it was shown that the number of equal entries in a totally positive $n \times n$ matrix is $O(n^{4/3})$. The authors also discussed positioning of equal entries and obtained relations to the Bruhat order of permutations. In [FRS14] it was shown, using incidences between points and hyperplanes, that the maximal number of equal $k \times k$ minors in a $k \times n$ totally positive matrix is $O(n^{k - \frac{k}{k+1}})$.

Inequalities between products of two minors in TP matrices have been widely studied as well [Ska04, RS05], and have close ties with Temperley-Lieb Immanants. Recently there has been also a study of products of three minors in such matrices [Lam14], that related such products with dimers. Despite all of the above, not much is known about the inequalities between the minors themselves. What is the full structure of all the possible equalities and inequalities between minors in TP matrices? The only part of this problem that has been solved discusses the structure of the minors with largest value and smallest value [FP14], while the rest of the problem remains open. The description in [FP14] involves rich combinatorial structure that relates arrangements of smallest minors with triangulations of the $n$-gon and the notion of weakly separated sets, while the structure of largest minors was related to thrackles and sorted collections. In this paper, we discuss the general case, and its tight relation with the triangulation of the hypersimplex.

# 2 Background

For $n \ge k \ge 0$, let the *Grassmannian* $Gr(k, n)$ (over $\mathbb{R}$) be the manifold of $k$-dimensional subspaces $V \subset \mathbb{R}^n$. It can be identified with the space of real $k \times n$ matrices of rank $k$ modulo row operations. Here we assume that the subspace $V$ associated with a $k \times n$-matrix $A$ is spanned by the row vectors of $A$. For such a matrix $A$ and a $k$-element subset $I \subset [n] := \{1, 2, 3, \dots, n\}$, we denote by $A_I$ the $k \times k$-submatrix of $A$ in the column set $I$, and let $\Delta_I(A) := \det(A_I)$. The coordinates $\Delta_I$ form projective coordinates on the Grassmannian, called the *Plücker coordinates*. In [Pos06], the *positive (nonnegative) Grassmannian* $Gr^+(k, n)$ ($Gr^-(k, n)$) was defined to be the subset of $Gr(k, n)$ whose elements are represented by $k \times n$ matrices $A$ with strictly positive (nonnegative) Plücker coordinates: $\Delta_I > 0$ for all $I$.

We recall two classical stratifications of $Gr(k, n)$ [Pos06]. The first one is the cellular decomposition of $Gr(k, n)$ into a disjoint union of Schubert cells. The Grassmannian $Gr(k, n)$ also has a subdivision into matroid strata (or Gelfand-Serganova strata) $S_M$ labelled by matroids $M$. The nonnegative Grassmannian
can be decomposed into cells via the positroid stratification. This decomposition has been studied by Postnikov in [Pos06] and was described in terms of various combinatorial objects such as: decorated permutations, plabic graphs, L-diagrams, Grassmann necklaces, etc. The following stratification, which is finer than the positroid stratification, was suggested in [FP14], along with the problem below:

**Definition 2.1** Let $\mathbb{U} = (\mathbb{U}_0, \mathbb{U}_1, \dots, \mathbb{U}_t)$ be an ordered set-partition of the set $\binom{[n]}{k}$ of all $k$-element subsets in $[n]$. Let us subdivide the nonnegative Grassmannian $Gr^{\geq}(k, n)$ into the strata $S_{\mathbb{U}}$ labelled by such ordered set partitions $\mathbb{U}$ and given by the conditions:

1. $\Delta_I = 0$ for $I \in \mathbb{U}_0$,

2. $\Delta_I = \Delta_J$ if $I, J \in \mathbb{U}_i$,

3. $\Delta_I < \Delta_J$ if $I \in \mathbb{U}_i$ and $J \in \mathbb{U}_j$ with $i < j$.

An arrangement of minors is an ordered set-partition $\mathbb{U}$ such that the stratum $S_{\mathbb{U}}$ is not empty.

**Problem 2.2** Describe combinatorially all possible arrangements of minors in $Gr^{\geq}(k, n)$. Investigate the geometric and the combinatorial structure of the stratification $Gr^{\geq}(k, n) = \bigcup S_{\mathbb{U}}$.

**Example 2.3** Let $\mathbb{U}_0 = \emptyset, \mathbb{U}_1 = \{\{3, 4\}\}, \mathbb{U}_2 = \{\{1, 4\}\}, \mathbb{U}_3 = \{\{1, 2\}, \{2, 3\}, \{1, 3\}, \{2, 4\}\}$.

Then $\mathbb{U} = (\mathbb{U}_0, \mathbb{U}_1, \mathbb{U}_2, \mathbb{U}_3)$ is an ordered set partition of $\binom{[4]}{2}$. Consider the matrix $A = \begin{pmatrix} 1 & 2 & 1 & 1/3 \\ 1 & 3 & 2 & 1 \end{pmatrix}$.

The matrix $A$ satisfies $\Delta_{34} = 1/3, \Delta_{14} = 2/3, \Delta_{12} = \Delta_{23} = \Delta_{13} = \Delta_{24} = 1$. Therefore $S_{\mathbb{U}}$ is nonempty since $A \in S_{\mathbb{U}}$, and hence $\mathbb{U}$ is an arrangement of minors.

For the case $k = 1$, the stratification of $Gr^{\geq}(k, n)$ into the strata $S_{\mathbb{U}}$ is equivalent to Coxeter arrangement of type A (also known as braid arrangement). The classification of the possible options for $\mathbb{U}_0$ is equivalent to the positroid stratification described above. In this work we deal with the positive Grammarian, and thus restrict ourself to the case $\mathbb{U}_0 = \emptyset$. We extend the convention from [FP14]:

**Definition 2.4** We say that a subset $\mathcal{J} \subset \binom{[n]}{k}$ is an arrangement of $t^{th}$ largest (smallest) minors in $Gr^+(k, n)$, if there exists a nonempty stratum $S_{\mathbb{U}}$ such that $\mathbb{U}_0 = \emptyset$ and $\mathbb{U}_{l-t+1} = \mathcal{J}$ ($\mathbb{U}_t = \mathcal{J}$).

If $t = 1$ we say that such arrangement is the arrangement of largest (smallest) minors.

Arrangements of largest and smallest minors were studied in [FP14], where it was shown that they enjoy a rich combinatorial structure. Arrangements of smallest minors are related to weakly separated sets. Such sets originally introduced by Leclerc-Zelevinsky [LZ98] in the study of quasi-commuting quantum minors, and are closely related to the associated cluster algebra of the positive Grassmannian. Arrangement of largest minors were shown to be in bijection with simplices of Sturmfels' triangulation of the hypersimplex, which also appear in the context of Gröbner bases [LP07]. In this paper, we are interested in the combinatorial description of arrangements of $t^{th}$ largest minors for $t \geq 2$. For a stratum $S_{\mathbb{U}}$, the structure of $\mathbb{U}_t$ for $t < l$ depends on the structure of $\mathbb{U}_l$, as we will show later.

**Definition 2.5** Let $\mathcal{J} \subset \binom{[n]}{k}$ be an arrangement of largest minors. We say that $\mathcal{Y} \subset \binom{[n]}{k}$ is a $(t, \mathcal{J})$-largest arrangement ($t \geq 2$) if there exists a nonempty stratum $S_{\mathbb{U}}$ such that $\mathbb{U}_0 = \emptyset, \mathbb{U}_l = \mathcal{J}$ and $\mathbb{U}_{l-t+1} = \mathcal{Y}$.

We say that $W \in \binom{[n]}{k}$ can be $(t, \mathcal{J})$-largest minor if there exists a $(t, \mathcal{J})$-largest arrangement $\mathcal{Y}$ such that $W \in \mathcal{Y}$.
In particular, if $\mathcal{Y} \subset \binom{[n]}{k}$ is a $(t, \mathcal{J})$-largest arrangement, then $\mathcal{Y}$ is also an arrangement of $t^{th}$ largest minors. For example, the first part of Example 2.3 implies that $\{\{3, 4\}\}$ is a $(3, \{\{1, 2\}, \{2, 3\}, \{1, 3\}, \{2, 4\}\})$-largest arrangement, and that $\{1, 4\}$ can be $(2, \{\{1, 2\}, \{2, 3\}, \{1, 3\}, \{2, 4\}\})$-largest minor.

### 3 The Triangulation of the Hypersimplex

**Definition 3.1** The hypersimplex $\Delta_{k,n}$ is an $(n-1)$-dimensional polytope defined as follows:

$$ \Delta_{k,n} = \{(x_1, \dots, x_n) \mid 0 \le x_1, \dots, x_n \le 1; x_1 + x_2 + \dots + x_n = k\}. $$

It was shown in [Sta77, Stu96] that the normalized volume of $\Delta_{k,n}$ equals the Eulerian number $A(n-1, k-1)$, that is, the number of permutations $w$ of size $n-1$ with exactly $k-1$ descents. In [LP07] four different constructions of a triangulation of the hypersimplex into $A(n-1, k-1)$ unit simplices are presented: Stanley's triangulation [Sta77], Alcove triangulation, circuit triangulation and Sturmfels' triangulation [Stu96]. It was shown in [LP07] that these four triangulations coincide. The rest of the section is devoted to Sturmfels' construction following the notations of [LP07].

**Definition 3.2** For a multiset $S$ of elements from $[n]$, let $\text{Sort}(S)$ be the non-decreasing sequence obtained by ordering the elements of $S$. Let $I, J \subset \binom{[n]}{k}$ and let $\text{Sort}(I \cup J) = (a_1, a_2, \dots, a_{2k})$. Define

$$ \text{Sort}_1(I, J) := \{a_1, a_3, \dots, a_{2k-1}\}, \quad \text{Sort}_2(I, J) := \{a_2, a_4, \dots, a_{2k}\}. $$

A pair $\{I, J\}$ is called sorted if $\text{Sort}_1(I, J) = I$ and $\text{Sort}_2(I, J) = J$, or vise versa.

For example, $\{1, 3, 5\}, \{2, 4, 6\}$ are sorted, while $\{1, 4, 5\}, \{2, 3, 6\}$ are not sorted. The following Corollary follows from Skandera inequalities [Ska04].

**Corollary 3.3** Let $I, J \in \binom{[n]}{k}$ be a pair which is not sorted. Then $\Delta_{\text{sort}_1(I,J)} \Delta_{\text{sort}_2(I,J)} > \Delta_I \Delta_J$ for points of the positive Grassmannian $\text{Gr}^+(k, n)$.

A collection $\mathcal{I} = \{I_1, I_2, \dots, I_r\}$ of elements in $\binom{[n]}{k}$ is called sorted if $I_i, I_j$ are sorted, for any pair $1 \le i < j \le n$. Given $I \in \binom{[n]}{k}$, let $\epsilon_I$ be a 0,1-vector $\epsilon_I = (\epsilon_1, \epsilon_2, \dots, \epsilon_n)$ such that $\epsilon_i = 1$ iff $i \in I$, and otherwise $\epsilon_i = 0$. For a sorted collection $\mathcal{I}$, we denote by $\nabla_{\mathcal{I}}$ the $(r-1)$-dimensional simplex with the vertices $\epsilon_{I_1}, \dots, \epsilon_{I_r}$.

**Theorem 3.4** [Stu96] The collection of simplices $\nabla_{\mathcal{I}}$ where $\mathcal{I}$ varies over all sorted collections of $k$-element subsets in $[n]$, is a simplicial complex that forms a triangulation of the hypersimplex $\Delta_{k,n}$.

From Theorem 3.4, it follows that the maximal by inclusion sorted collections correspond to the maximal simplices in the triangulation, and they are known to be of size $n$. As an example, consider the case $k=2$. Let $I = \{a, b\}, J = \{c, d\} \subset \binom{[n]}{2}$ be a pair of sorted sets ($I \neq J$). Consider the graph $G$ of order $n$ whose vertices lie in clockwise order on a circle. Then we can think about $I$ and $J$ as edges in the graph, and since $I$ and $J$ are sorted, these two edges either share a common vertex or cross each other.

**Definition 3.5** A thrackle is a graph in which every pair of edges is either crossing or shares a common vertex. (i)

The maximal number of edges in a thrackle is $n$, and each such maximal thrackle corresponds to a maximal sorted set with $k=2$. Figure 1 describes all the thrackles of order up to 5.

<footnote>(i) Our thrackles are a special case of Conway's thrackles. The latter are not required to have vertices arranged on a circle.</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1: All maximal thrackles that have at most 5 vertices (up to rotations and reflections).</figcaption></figure>

**Definition 3.6** The dual graph $\Gamma_{(k,n)}$ of Sturmfels' triangulation of $\Delta_{k,n}$ is the graph whose vertices are the maximal simplices, and two maximal simplices are adjacent by an edge if they share a common facet.

Figure 2 depicts the graph $\Gamma_{(2,6)}$. This graph has $A(5, 1) = 26$ vertices, each corresponds to a maximal thrackle on 6 vertices. We also described explicitly 6 of the vertices. In particular, vertices $a$ and $b$ are connected since $b$ can be obtained from $a$ by removing the edge $\{1, 6\}$ and adding instead the edge $\{2, 5\}$. Therefore $\nabla_a$ and $\nabla_b$ share a common facet.

<figure><img src="image_3.png" /><figcaption>Fig. 2: The graph $\Gamma_{(2,6)}$</figcaption></figure>

# 4 Arrangements of minors and Sturmfels' triangulation

In this section, we describe necessary and sufficient conditions on arrangements of second largest minors, and also necessary conditions for arrangements of $t$-th largest minors for any $t \ge 2$. The case $t = 1$, i.e., arrangements of largest minors, was fully resolved in [FP14]:

**Theorem 4.1** A subset of $\mathcal{J} \subset \binom{[n]}{k}$ is an arrangement of largest minors in $Gr^+(k, n)$ if and only if it is a sorted subset. Equivalently, $\mathcal{J}$ is an arrangement of largest minors if and only if it corresponds to a simplex in Sturmfels' triangulation of the hypersimplex. Maximal arrangements of largest minors contain exactly $n$ minors. The number of maximal arrangements of largest minors in $Gr^+(k, n)$ equals the Eulerian number $A(n-1, k-1)$.
Theorem 4.1 implies that maximal arrangements of largest minors are in bijection with the vertices of $\Gamma_{(k,n)}$. In this section, we will show that the structure of arrangements of second largest minors is strongly related the structure of edges in $\Gamma_{(k,n)}$. As a warm-up, we start with the case $k = 2$.

## 4.1 The case $k = 2$: maximal thrackles

Consider the space $Gr^+(2, n)$, and let $\mathcal{J} \subset \binom{[n]}{2}$ be a maximal arrangement of largest minors (hence it corresponds to a maximal thrackle). Given $W \in \binom{[n]}{2}$, we ask whether $W$ can be $(2, \mathcal{J})$-largest minor. That is, whether there exists an element in $Gr^+(2, n)$ in which the collection of largest minors is $\mathcal{J}$ and $W$ is second largest. Our theorem bellow gives necessary and sufficient conditions on such $W$.

**Theorem 4.2** Let $W \in \binom{[n]}{2}$ and let $\mathcal{J} \subset \binom{[n]}{2}$ be some maximal arrangement of largest minors. The following four statements are equivalent.

1. $W$ can be $(2, \mathcal{J})$-largest minor.

2. There exist a vertex $Q$ in $\Gamma_{(2,n)}$ that is adjacent to $\mathcal{J}$, such that $W \in Q$.

3. There exist $J \in \mathcal{J}$ such that $(\mathcal{J} \setminus J) \cup W$ is an arrangement of largest minors.

4. There exist four distinct vertices labelled $a, a+1, b, b+1 \mod n$ such that $\{(a, b), (a-1, b), (b+1, a)\} \subset \mathcal{J}$ and $W = (a-1, b+1)$.

In particular, the minors that can be second largest are in bijection with the edges of $\Gamma_{(2,n)}$ that are connected to vertex $\mathcal{J}$, and the number of such minors is at most $n$.

We emphasize the relation, implied by our theorem, between arrangements of second largest minors and the structure of $\Gamma_{(2,n)}$. Let $\mathcal{J} \subset \binom{[n]}{2}$ be a maximal thrackle, and let

$$T = \{A \in Gr^+(2, n) \mid \text{the set of largest minors of } A \text{ is } \mathcal{J}\}.$$

Let $W \in \binom{[n]}{2}$. Theorem 4.2(2) implies that there exists $A \in T$ for which $W$ is the second largest minor if and only if there exists a vertex $Q$ in $\Gamma_{(2,n)}$ that is adjacent to $\mathcal{J}$ such that $W \in Q$.

**Example 4.3** Consider the maximal thrackle $\mathcal{J}$ in Figure 3 on the left. Using part (4) of Theorem 4.2, we identify the elements in $\binom{[n]}{2}$ that can be second largest minors, and denote them by red lines (and this is the second graph from the left). Then, in Figure 3 on the right, we describe the thrackle resulted in adding the red line and removing one of the edges of $\mathcal{J}$. Those three cases correspond to the three edges that are connected to $\mathcal{J}$ in $\Gamma_{(2,5)}$.

<figure><img src="image_4.png" /><figcaption>Fig. 3</figcaption></figure>
## 4.2 The general case

In the previous section, we considered the space $Gr^+(2, n)$ and discussed arrangements of second largest minors. In this section we consider the space $Gr^+(k, n)$, and discuss arrangements of $t^{th}$ largest minors ($t \ge 2$). Our discussion covers the general case (that is, we will make no assumption on the arrangements of largest minors). We start with the case $t = 2$.

**Theorem 4.4** Let $W \in \binom{[n]}{k}$ and let $\mathcal{J} \subset \binom{[n]}{k}$ be some arrangement of largest minors. Denote $|\mathcal{J}| = c$. If $W$ can be $(2, \mathcal{J})$-largest minor, then one of 1,2 holds, or equivalently, one of 3,4 holds:

1. The collection $\{W\} \cup \mathcal{J}$ is sorted

2. There exists $J \in \mathcal{J}$ such that $W$ and $J$ are not sorted, and $(\mathcal{J} \setminus J) \cup \{W\}$ is a sorted collection.

3. $\nabla_{\{W\}} \cup \mathcal{J}$ is a $c$-dimensional simplex in Sturmfels triangulation of the hypersimplex $\Delta_{k,n}$.

4. There exists a $c-1$-dimensional simplex $\nabla_Y$ in Sturmfels triangulation such that $\epsilon_W$ is a vertex in $\nabla_Y$, and the simplices $\nabla_Y, \nabla_{\mathcal{J}}$ share a common facet.

The proof idea is to show that if there exist two elements $J_1, J_2 \in \mathcal{J}$ that are not sorted with $W$, then the collection $\{J_1, J_2, \text{Sort}_1(W, J_1), \text{Sort}_2(W, J_1), \text{Sort}_1(W, J_2), \text{Sort}_2(W, J_2)\}$ cannot be sorted. Therefore, not all the elements in the collection can be in the arrangement of largest minors. From here we can use Skandera inequalities and deduce that $W$ cannot be second largest. The theorem above gives a necessary condition on second largest minors. If $\mathcal{J}$ from Theorem 4.4 is maximal, we obtain sufficient conditions as well. The following generalize Theorem 4.2.

**Theorem 4.5** Let $W \in \binom{[n]}{k}$ and let $\mathcal{J} \subset \binom{[n]}{k}$ be some maximal arrangement of largest minors. The following two statements are equivalent.

1. $W$ can be $(2, \mathcal{J})$-largest minor.

2. There exist a vertex $Q$ in $\Gamma_{(k,n)}$ that is adjacent to $\mathcal{J}$, such that $W \in Q$.

In particular, the minors that can be second largest are in bijection with the edges of $\Gamma_{(k,n)}$ that connected to vertex $\mathcal{J}$, and the number of such minors is at most $n$.

In one direction the proof follows from Theorem 4.4. The second direction is proven using properties of the torus action on the positive Grassmannian. Theorem 4.5 states that when $\mathcal{J}$ is a maximal sorted set, the second largest minor must appear in one of the neighbors of $\mathcal{J}$ in $\Gamma_{(k,n)}$. In order to discuss $t^{th}$ largest minors for $t > 2$, we will introduce the notion of cubical distance in the graph $\Gamma_{(k,n)}$. Consider the blue edges in Figure 2, and note that they form a square, while the red edges form a 3-dimensional cube. We say that two vertices $\mathcal{J}_1, \mathcal{J}_2$ in $\Gamma_{(k,n)}$ are of cubical distance 1 if both of them lie in certain cube (of any dimension). For example, vertices $a$ and $b$ from Figure 2 are of cubical distance 1 since both of them lie in a 1-dimensional cube (which is just an edge). Similarly, $a$ and $c$ are of cubical distance 1 (both of them lie in a square), as well as $c$ and $d$ (both of them lie in a 3-dimensional cube).

**Definition 4.6** Let $\mathcal{J}_1, \mathcal{J}_2 \subset \binom{[n]}{k}$ be maximal sorted collections, and let $W \in \binom{[n]}{k}$. We say that $\mathcal{J}_1, \mathcal{J}_2$ are of cubical distance $D$, and denote it by $\text{cube}_d(\mathcal{J}_1, \mathcal{J}_2) = D$, if one can arrive from $\mathcal{J}_1$ to $\mathcal{J}_2$ by moving along $D$ cubes in $\Gamma_{(k,n)}$, and $D$ is minimal with respect to this property. We say that $W$ is of cubical distance $D$ from $\mathcal{J}_1$, and denote it by $\text{cube}_d(\mathcal{J}_1, W) = D$, if for any vertex $\mathcal{J}_2$ in $\Gamma_{(k,n)}$ that contains $W$, $\text{cube}_d(\mathcal{J}_1, \mathcal{J}_2) \ge D$, and for at least one such $\mathcal{J}_2$ this inequality becomes equality.
For example, using the notations of Figure 2, $cube_d(a, d) = 2$, $cube_d(b, d) = 2$, $cube_d(a, e) = 3$. We also have $cube_d(a, \{1, 4\}) = 1$ since $\{1, 4\} \in f$, and $cube_d(a, \{2, 4\}) = 2$ since $\{2, 4\} \notin b, f, c, \{2, 4\} \in d$. It can also be shown that $cube_d(a, \{2, 3\}) = 3$.

**Definition 4.7** Let $\mathcal{J} \subset \binom{[n]}{k}$ be an arrangement of largest minors, and let $W \in \binom{[n]}{k}$. We say that $W$ is $(\ge t, \mathcal{J})$-largest minor if for any arrangement of minors $U = (U_0, U_1, \dots, U_l)$ such that $U_l = \mathcal{J}$ the following holds: $W \notin U_l, U_{l-1}, \dots, U_{l-t+2}$.

For example, let $\mathcal{J}$ be the maximal sorted collection that corresponds to vertex $a$ in Figure 2, and let $A \in Gr^+(2, 6)$ in which the collection of maximal minors is $\mathcal{J}$. Using Skandera's inequalities, it is possible to show that for such $A$, $\Delta_{16} > \Delta_{14} > \Delta_{24} > \Delta_{23}$. Therefore, $\{2, 3\}$ is $(\ge 4, U_l)$-largest minor, since $\{2, 3\} \notin U_l, U_{l-1}, U_{l-2}$.

**Conjecture 4.8** Let $W \in \binom{[n]}{k}$ and let $\mathcal{J} \subset \binom{[n]}{k}$ be some maximal arrangement of largest minors. If $cube_d(W, \mathcal{J}) = t$, then $W$ is $(\ge t + 1, U_l)$-largest minor.

Note that the examples we gave earlier are special cases of this conjecture. For example, $cube_d(a, \{2, 3\}) = 3$, and indeed $\{2, 3\}$ is $(\ge 4, U_l)$-largest minor.

**Theorem 4.9** Conjecture 4.8 holds for $t = 2, 3$ (and any $n, k$), and also for $k = 2$ (and any $n, t$).

At first glance, it may seem like Theorem 4.9 contradicts Theorem 4.5 since a vertex $\mathcal{J}_2$ of cubical distance 1 from $\mathcal{J}$ doesn't have to be connected to $\mathcal{J}$. However, it can be shown that if $W \in \mathcal{J}_2$ then $W$ also appears in one of the neighbors of $\mathcal{J}$. In the next section, we will prove additional cases of the conjecture. Conjecture 4.8 deals with the case in which $\mathcal{J}$ is maximal. We will now discuss general case, in which $\mathcal{J}$ can be any sorted collection. Theorem 4.4 implies that if $W \in \binom{[n]}{k}$ is a second largest minor, then $\epsilon_W$ is "close" to $\nabla_{\mathcal{J}}$. This notion of distance is formally defined in the following definition. This definition allows us to generalize this property for arrangements of $t^{th}$ largest minors ($t \ge 2$).

**Definition 4.10** Let $r$ be an integer, $1 \le i \le j \le n$, and denote by $H_{i,j,r}$ the affine hyperplane $\{x_i + x_{i+1} + \dots + x_j = r\} \subset \mathbb{R}^n$. Fix a point $x \in \mathbb{R}^n$. For $y \in \mathbb{R}^n$, we say that $H_{i,j,r}$ separates $y$ from $x$ if one of the following holds:

* $x$ and $y$ lie in the two disjoint halfspaces formed by $H_{i,j,r}$.

* $y$ lies on $H_{i,j,r}$ and $x$ does not.

*Define* $d_{ij}(x, y) = |\{r \mid \text{the hyperplane } H_{i,j,r} \text{ separates } y \text{ from } x\}|$.

*Finally, let* $B_r(x) = \{y \mid d_{ij}(x, y) \le r \text{ for all } 1 \le i \le j \le n\}$.

The notion $d_{ij}$ arises naturally in the discussion of sorted sets. In particular, by [LP07, section 2.4], $I$ and $J$ are sorted if and only if $d_{ij}(\epsilon_I, \epsilon_J) \le 1$ for every $1 \le i \le j \le n$.

**Theorem 4.11** Let $\mathcal{J} \subset \binom{[n]}{k}$ be some arrangement of largest minors, and let $\mathcal{Y}$ be a $(t, \mathcal{J})$-largest arrangement. Then the following holds:

* If $t = 2$, then $\epsilon_Y \in B_2(\mathcal{J})$ for any $Y \in \mathcal{Y}, J \in \mathcal{J}$.

* If $t \ge 3$, then $\epsilon_Y \in B_{2+2^{t-3}}(\mathcal{J})$ for any $Y \in \mathcal{Y}, J \in \mathcal{J}$.

Thus, we get that if $W$ can be $(t, \mathcal{J})$-largest minor, then $W$ must lie within a ball of certain bounded radius around $\mathcal{J}$. We conclude this section with the following corollary.
**Corollary 4.12** Let $\mathcal{Y}$ be an arrangement of $t^{th}$ largest minor, $t \ge 2$. Then all the elements $\epsilon_Y, Y \in \mathcal{Y}$ lie within a ball of radius $2 + 2^{t-3}$.

# 5 Circuit triangulation and partially ordered set of minors

In this section, we show that arrangements of largest minors induces a structure of partially ordered set on the entire collection of minors. We investigate this poset, and its relations to arrangements of minors.

**Example 5.1** Let $k = 2, n = 6$, and let $A \in Gr^+(2, 6)$ be an element for which the minors that appear in Figure 4 on the left are maximal. Thus, without loss of generality, we can assume that

$$ \Delta_{12} = \Delta_{13} = \Delta_{14} = \Delta_{15} = \Delta_{25} = \Delta_{26} = 1. $$

<figure><img src="image_5.png" /><figcaption>Fig. 4: A maximal thrackle and the corresponding poset of minors</figcaption></figure>

By Theorem 4.1, all the other minors are strictly smaller than 1. However, there is much more information that we can obtain on the order of the minors. For example, using 3-term Plücker relation, we get $\Delta_{46}\Delta_{13} < \Delta_{14}\Delta_{36}$, and hence $\Delta_{46} < \Delta_{36}$. Once the set of largest minors is fixed, it induces a structure of partially ordered set on the collection of minors. Figure 4 depicts the Hasse diagram that corresponds to the example above (and the relation $\Delta_{46} < \Delta_{36}$ is one of the covering relations in this diagram).

In order to discuss these partially ordered set more systematically, we will use the circuit triangulation of the hypersimplex. It was introduced in [LP07], and was shown to be isomorphic to Sturmfels triangulation.

**Definition 5.2** We define $G_{k,n}$ to be the directed graph whose vertices are $\{\epsilon_I\}_{I \in (\binom{[n]}{k})}$, and two vertices $\epsilon = (\epsilon_1, \epsilon_2, \dots, \epsilon_n)$ and $\epsilon' = (\epsilon'_1, \epsilon'_2, \dots, \epsilon'_n)$ are connected by an edge oriented from $\epsilon$ to $\epsilon'$ if there exists some $i \in [n]$ such that $(\epsilon_i, \epsilon_{i+1}) = (1, 0)$ and the vector $\epsilon'$ is obtained from $\epsilon$ by switching $\epsilon_i, \epsilon_{i+1}$ (and leaving all the other coordinates unchanged, so the 1 is “shifted” one place to the right). We label such edge by $i$. When considering $i \in [n]$ we refer to $i$ as $i \mod n$, and thus if $i = n$, we have $i + 1 = 1$.

A circuit in $G_{k,n}$ of minimal possible length must be of length $n$. The left part of Figure 5 is an example of a minimal circuit in $G_{3,8}$. For convenience, we label the vertices by $I$ instead of $\epsilon_I$. The sequence of labels of edges in a minimal circuit forms a permutation $\omega = \omega_1\omega_2\dots\omega_n \in S_n$, and two permutations that obtained from each other by cyclic shifts correspond to the same circuit. Thus, we can label each minimal circuit in $G_{k,n}$ by its permutation modulo cyclic shifts. For example, the permutation corresponding to the minimal circuit in Figure 5 is $\omega = 56178243$, and we label this circuit by $C_\omega$.
**Theorem 5.3** [LP07] Each minimal circuit $C_\omega$ in $G_{k,n}$ determines the simplex $\Delta_\omega$ inside the hypersimplex $\Delta_{k,n}$ with the vertex set $C_\omega$. The collection of simplices $\Delta_\omega$ corresponding to all minimal circuits in $G_{k,n}$ forms a triangulation of the hypersimplex, which is called the circuit triangulation. The vertices of $C_\omega$ form a maximal sorted collection, and every maximal sorted collection can be realized via a minimal circuit in the graph $G_{k,n}$.

The structure of $G_{k,n}$ is quite complicated in general. Yet, we found an algorithm that recognizes certain planar subgraphs of $G_{k,n}$ - these subgraphs induce a structure of partial order on the set of minors.

**Definition 5.4** An oriented Young graph is the graph that is obtained from a Young diagram after orienting each horizontal edge from right to left and each vertical edge from top to bottom. We call the vertex that is in the upper left corner the origin vertex, and denote the upper right (lower left) vertex by $v_0$ ($v_1$). There are two paths that start at $v_0$, walk along the border end at $v_1$. The path that passes through the origin vertex is called inner path, and the second path is called outer path. From now on, we denote the set of the vertices appear in the outer path by $V$. See the right part of Figure 5 for example.

<figure><img src="image_6.png" /><figcaption>Fig. 5: The figure on the left is a circuit in $G_{3,8}$. The right figure is an oriented Young graph. It's inner boundary path formed by the edges labeled from 1' through 8'. Its outer boundary path formed by the edges labeled from 1 through 8, and all the vertices that appear along the latter path form the collection $V$.</figcaption></figure>

**Lemma 5.5** Let $H$ be an oriented Young subgraph of $G_{k,n}$, and let $A \in Gr^+(k, n)$ for which all the minors indexed by $V$ are equal and have largest value. Then for any vertex $I$ of $H$ such that $I \notin V$, we have $\Delta_I < \Delta_J$, $\Delta_I < \Delta_Z$ where $J$ is the vertex right below $I$ and $Z$ is the vertex to the right of $I$ in $H$ (see Figure 5).

**Definition 5.6** Let $H$ be an oriented Young subgraph of $G_{k,n}$, and let $u$ be the origin vertex. The swapping distance between $u$ and $V$ is $\max\{i + j - 1 | (i, j) \in H\}$.

For example, the swapping distance of $u$ from $V$ in Figure 5 is 5.

**Corollary 5.7** Let $H, V$, $u$ be as in Lemma 5.5, and denote by $t$ the swapping distance of $u$ from $V$. Let $U_l \subset \binom{[n]}{k}$ such that $V \subset U_l$. Then $u$ is $(\ge t + 1, U_l)$-largest minor.

**Lemma 5.8** Let $\mathcal{J} \subset \binom{[n]}{k}$ be a maximal sorted collection, and suppose that there exists an oriented Young subgraph $H$ of $G_{k,n}$ such that $V \subset \mathcal{J}$. Let $u$ be the origin vertex in $H$. Then $\mathrm{cube}_d(\mathcal{J}, u)$ is bounded from above by the swapping distance of $u$ from $V$.

**Theorem 5.9** If $W$ is sorted with at least one element in $\mathcal{J}$, then the claim in Conjecture 4.8 holds.
<figure><img src="image_7.png" /><figcaption>Fig. 6</figcaption></figure>

The proof idea of Theorem 5.9 is that under the conditions of the theorem, one can find an oriented Young subgraph of $G_{k,n}$ such that $W$ is the origin vertex and $V \subset \mathcal{J}$. Then we apply Lemma 5.5. The existence of such subgraph not only implies Theorem 5.9, but also induces a poset on the collection of minors, as each minor in the Young subgraph (that is not in $\mathcal{J}$) is smaller than the minor to the right of it and the minor below it. Let us show an example. Suppose that the minors corresponding to the circuit $C_\omega$ in Figure 5 form a collection $\mathcal{J}$ of largest minors, and let $W = (3, 5, 6)$. Among the vertices of $C_\omega$, $W$ is sorted with $\{1, 3, 5\}$, $\{1, 4, 5\}$, $\{1, 4, 6\}$, and not sorted with the rest. So the set of vertices that are not sorted with $W$ form a path in $C_\omega$, and this property also holds in the general case. We would like to construct an alternative path in $G_{3,8}$ that starts at $\{1, 4, 6\}$, ends at $\{1, 3, 5\}$ and contains only vertices that are sorted with $W$. Consider the left graph $G_1$ that appears in Figure 6. $G_1$ is a subgraph of the graph $G_{3,8}$, and the edges that correspond to the circuit $C_\omega$ appear as dotted lines. The part of $\omega$ that corresponds to the dotted lines is 617824 (we ignore the vertex $\{1, 4, 5\}$, as it is sorted with $W$). Let us instead start at $\{1, 4, 6\}$ and walk along the path 124678. Note that after 3 steps in this path, we arrive to the vertex $W$. The bottom right graph in Figure 6 is the oriented Young subgraph (in the figure it appears rotated) of $G_{3,8}$ in which the set $V$ is consisted of vertices from $C_\omega$ and $W$ is the origin vertex. One can check that this is indeed a subgraph of $G_1$. Similar claim holds in the case $W = (2, 5, 6)$, with the corresponding
oriented Young subgraph which appears in the top right part of the figure.

## Acknowledgements

We would like to thank Alexander Postnikov for useful discussions.

## References

[FFJM14] Miriam Farber, Mitchell Faulk, Charles R Johnson, and Evan Marzion. Equal entries in totally positive matrices. *Linear Algebra and its Applications*, 454:91–106, 2014.

[FJ11] S. Fallat and C.R. Johnson. *Totally Nonnegative Matrices*. Princeton University Press, 2011.

[FP14] M. Farber and A. Postnikov. Arrangements of equal minors in the positive grassmannian. In *DMTCS Proceedings*, pages 777–788, 2014.

[FRS14] Miriam Farber, Saurabh Ray, and Shakhar Smorodinsky. On totally positive matrices and geometric incidences. *Journal of Combinatorial Theory, Series A*, 128:149–161, 2014.

[GK41] F. R. Gantmacher and M. G. Krein. Oscillation matrices and small oscillations of mechanical systems. *Gostekhizdat*, Moscow-Leningrad, 1941.

[GM10] M. Gasca and C.A. Micchelli. *Total Positivity and Its Applications*. Kluwer Academic Publishers, 2010.

[Lam14] Thomas Lam. Dimers, webs, and positroids. arXiv:1404.3317, 2014.

[LP07] T. Lam and A. Postnikov. Alcoved polytopes i. *Discrete & Computational Geometry*, 38:453–478, 2007.

[LZ98] B. Leclerc and A. Zelevinsky. Quasicommuting families of quantum plücker coordinates. *American Mathematical Society Translations*, Ser. 2 **181**, 1998.

[Pos06] Alexander Postnikov. Total positivity, grassmannians, and networks. arXiv preprint math/0609764, 2006.

[RS05] B. Rhoades and M. Skandera. Temperley-lieb immanants. *Annals of Combinatorics*, 9:451–494, 2005.

[Sch30] Isac Schoenberg. Über variationsvermindernde lineare transformationen. *Mathematische Zeitschrift*, 32(1):321–328, 1930.

[Ska04] Mark Skandera. Inequalities in products of minors of totally nonnegative matrices. *Journal of Algebraic Combinatorics*, 20(2):195–211, 2004.

[Sta77] R. Stanley. *Eulerian partitions of a unit hypercube, in Higher Combinatorics*. (M. Aigner, ed.), Reidel, Dordrecht/Boston, 1977.

[Stu96] B. Sturmfels. *Gröbner bases and convex polytopes*. University Lecture Series, 8. American Mathematical Society, Providence, RI, 1996.