Algorithm 2.2 [Reference Agarwala and Fryer4, Algorithm 2]

Let (I ₁, …, I _n ) be a Grassmann necklace of type (k, n). Within a k × (n − k) square, draw the Young diagram whose rows are labeled by I ₁ (as per the convention above).

For each i, 2 ≤ i ≤ n, perform the following steps.

• • Write

  $$ \begin{align*}I_1 \setminus I_i = \{a_1> a_2 > \dots > a_r\}, \ \ \ I_i \setminus I_1 = \{b_1 < b_2 < \dots < b_r\},\end{align*} $$
  where the inequalities denote the <₁ order (subscripts suppressed for clarity).

• • For 1 ≤ j ≤ r, place a + in square (a _j , b _j ) of the diagram. (We will refer to this + as being in the a _j → b _j position.)

After performing the above, for 2 ≤ i ≤ n, place a 0 in any remaining unfilled boxes.

Proof This follows as a corollary of the previous theorem by induction in one direction and the pigeonhole principle in the other direction.

Alternatively, we can simply think about the condition of linear independence in the matrix $C(W)$ , and so the corollary can also be proved directly by linear algebra and the definition of $C(W)$ as follows.

Because the nonzero entries of $C(W)$ are independent indeterminates, J is an independent set if and only if there is some choice of $|J|$ nonzero entries of $C(W)$ , one in each row associated to an element of J and each in different columns. Each entry in $C(W)$ identifies a propagator by the row of the entry and a vertex by the column of the entry. The entry is nonzero if and only if the propagator is supported on that vertex. Consequently, take a choice of $|J|$ nonzero entries of $C(W)$ , one in each row associated to an element of J and each in different columns. Such a choice is equivalent to an assignment of the propagators of J to supporting vertices, so that no two are assigned to the same vertex. Such an assignment of the propagators of J to supporting vertices is exactly a map f as described in the statement, hence proving the result.▪

Proof Suppose first that W has a propagator of length $3$ , say $p=(i, i+3)$ . By Remark 3.2 and the fact that every vertex of W supports at least one propagator, we have that $i+2$ supports exactly one propagator, and this propagator must have length 2 by noncrossingness. This gives us an instance of configuration 1 from the statement.

Now, suppose W has no propagators of length $3$ .

We will inductively construct sequences of propagators $(p_r)$ and $(q_r)$ , with $\ell (p_r) = 2$ for each r and such that either of the following are true:

• • the propagator $p_r$ forms part of configuration 1 or 2 from the statement, at which point the induction terminates, or

• • there is a propagator $q_r$ satisfying $\ell (q_r) \geq 4$ , and $\{p_1, \ldots , p_r, q_1, \ldots , q_{r-1}\}$ are all on the same side of $q_r$ .

We can choose the orientation of $q_r$ , so that the previous $p_i$ and $q_i$ are all on the outside of $q_r$ , and restrict our attention to the subdiagram $(\mathcal {P}_{in}(q_r),[n])$ . By the finiteness of W, this must eventually terminate in one of the desired configurations.

Start by choosing a propagator $p_1 = (j_1,j_1+2)$ of length 2 in W (which exists by Remark 3.2). If it is part of one of the configurations we are looking for, we are done, so suppose otherwise.

From our existing assumptions, we know the following facts: $p_1$ is not in configuration 2, there are no propagators of length $3$ , and every vertex supports at least one propagator. Therefore, there must be a propagator of length at least 4 with one end on edge $j_1$ or on edge $j_1-1$ or on edge $j_1-2$ . Let $q_1 = (i_1, k_1)$ be this propagator, oriented such that $p_1 \in \mathcal {P}_{out}(q_1,<_{i_1})$ ; see Figure 4. This completes the base case.

Figure 4:

The base case of the induction in Lemma 3.3.

Now, suppose $q_{r} = (i_r, k_r)$ exists by the induction hypothesis and is oriented $(q_r, <_{i_r})$ , so that the previous $p_i$ and $q_i$ are on the outside. For the rest of this proof, we assume this orientation and drop the $<_{i_r}$ from the notation.

Let $W_r := (\mathcal {P}_{in}(q_r),[n])$ be the subdiagram of W consisting of those propagators inside $q_r$ (including $q_r$ itself); in particular, $W_r$ contains none of the previous $p_i$ or $q_i$ . By the original hypotheses on W, every vertex in $[i_r,k_{r+1}]$ (of which there are at least 4, because $\ell (q_r) \geq 4$ ) must support at least one propagator. Therefore, $W_r$ admits at least one propagator of length 2 (by Remark 3.2) and no propagators of length $3$ (by our assumption on W).

Let $p_{r+1} = (j_{r+1}, j_{r+1}+2)$ be a propagator of length 2 in $W_r$ . If it forms part of configuration 1 or 2, we are done, so assume otherwise.

Note that we could replace $q_r$ by another propagator $q^{\prime }_{r}$ in $W_r = (\mathcal {P}_{in}(q_r), [n])$ , as long as $p_{r+1}$ and $q_r$ are on opposite sides of $q_r^{\prime }$ . Such a new $q^{\prime }_{r}$ would still satisfy all of the induction hypotheses. (See Figure 5.) Therefore, without loss of generality, we may assume that $\mathcal {P}_{in}(q_r)$ does not contain any propagators (other than $q_r$ itself) which satisfy the induction hypotheses, i.e., we assume that there are no other propagators with $p_{r+1}$ on one side and $q_r$ on the other.

Figure 5:

We can replace $q_r$ with $q^{\prime }_r$ as long as $q_r$ and $p_{r+1}$ are on opposite sides of $q^{\prime }_r$ .

There are two cases to consider.

The first case is that $i_r \leq j_{r+1} \leq i_r+2$ and $k_r-2 \leq j_{r+1}+2 \leq k_{r}$ (so $p_{r+1}$ has one end before $i_{r} + 3$ and the other after $k_{r} - 2$ , i.e., there are at most two vertices between an endpoint of $p_{r+1}$ and an endpoint of $q_r$ ). Because $p_{r+1}$ has length 2, it must be that $(i_r+3)+1 \geq k_r-2$ , and so $q_r$ has length at most 6. By the minimality assumption on $q_r$ , no propagator in $W_r$ has $q_r$ on one side and $p_{r+1}$ on the other side. Therefore, any propagator in $W_r$ other than $q_r$ and $p_{r+1}$ must be of the form $(i,j)$ with $i_r\leq i < j\leq i_r+2$ or $k_r-2 \leq i < j\leq k_r$ . Both of these require that $(i,j)$ has length 2, and so we have configuration 2 which we have already assumed does not occur. Consequently, $W_r$ contains only the two propagators $q_r$ and $p_{r+1}$ , yielding configuration 1 from the lemma statement and again contradicting our assumption. Therefore, this first case cannot occur.

The second case is that there are at least three vertices between one endpoint of $p_{r+1}$ and the nearest endpoint of $q_r$ . In other words, at least one of the following four statements are true:

• • $i_r+3 \leq j_{r+1}\leq k_r-3$ (one endpoint of $p_{r+1}$ has at least three vertices between it and the nearest endpoint of $q_r$ ), or

• • $i_r+3 \leq j_{r+1}+2\leq k_r-3$ (the other endpoint of $p_{r+1}$ has at least three vertices between it and the nearest endpoint of $q_r$ ), or

• • $i_r = j_{r+1}$ ( $p_{r+1}$ and $q_r$ both have an end on edge $i_r$ ), or

• • $k_r = j_{r+1} +2$ ( $p_{r+1}$ and $q_r$ both have an end on edge $k_r$ ).

In other words, at least one end of $p_{r+1}$ is supported entirely by vertices in the interval $[i_r+3,k_r+2]$ (the first two bullet points) or both ends lie in $[i_r, i_r+3]$ (third point) or both ends lie in $[k_r-2, k_r+1]$ (fourth point). These situations all behave similarly, and by symmetry, it suffices to only consider the second and third possibilities.

We have $j_{r+1}+4 \leq k_r-1$ in both of these cases. In the situation of the second bullet point, this follows directly from the inequality, whereas in the third case, it follows from the fact that $\ell (p_{r+1}) = 2$ and $\ell (q_r) \geq 4$ . Therefore, the vertex $j_{r+1}+4$ is in the interval $[i_r, k_r+1]$ but does not support either $q_r$ or $p_{r+1}$ , and must therefore support some other propagator t. Because $p_{r+1}$ is not part of configuration 2 and $W_r$ has no propagators of length 3, it follows that $\ell (t) \geq 4$ . If $q_r$ and $p_{r+1}$ were on different sides of t, this would contradict the minimality of $q_r$ . Therefore, we can orient t, so that all previous $q_i$ and $p_i$ belong to $\mathcal {P}_{out}(t)$ , and set $q_{r+1} = t$ to continue the induction.

The overall result follows by induction.▪

Algorithm 3.5 Let W = (P, [n]) be an admissible Wilson loop diagram. In order to construct the set I _i ^W for i ∈ [n], perform the following steps.

1. (1) Fix a vertex i ∈ [n], the starting vertex. Set j:= i and I _i ^W = ∅.

2. (2) While P≠∅, perform the following steps.

   1. (a) Step j for starting vertex i: If Prop(j) = ∅, do nothing. Else, let p ∈Prop(j) be the clockwise-most propagator supported on j. Write I _i ^W = I _i ^W ∪{j}, and delete propagator p from the diagram.

   2. (b) Increment j by 1 and repeat from (a).

Proof Suppose, by way of contradiction, that we have $i \in [n]$ and $p \in \mathcal {P}$ such that $I_i(p)$ is $<_i$ -maximal in $V(p)$ . There are two possibilities, which are illustrated in Figure 7: either $p = (i-1,b)$ for some b (so i and $I_i(p) = i-1$ are the two ends of a single edge), or $p = (a,b)$ with $i\leq _i a <_i b$ and $I_i(p) = b+1$ .

Figure 7:

The two types of configuration that would (in theory) allow the propagator p to contribute its $<_i$ -maximal support vertex to $I_i$ .

When the first possibility occurs, observe that we must have another propagator $q = (c,b)$ with $c<_i b$ and $I_i(q) = b+1$ , because otherwise $I_i$ would assign p to $b+1$ . Now, q also contributes the $<_i$ -maximal vertex in its support to $I_i$ and is an instance of the second possibility. Therefore, it suffices to show that no admissible Wilson loop diagram admits the configuration illustrated in Case 2 of Figure 7.

So let $p = (a,b)$ with $a<_ib$ and $I_i(p) = b+1$ , and choose p such that $\big |[a+1,b]\big |$ is minimal among propagators of W which contribute their last vertex and are in Case 2.

Because $I_i(p) \neq b$ , there must exist a propagator q inside $(p,<_i)$ with $I_i(q) = b$ . The propagator q cannot end on the edge $b-1$ , as this would contradict the minimality of p, so we have $q = (d,b)$ with $a <_i d <_i b$ , and $I_i(q) = b$ .

In order for q to remain unassigned until the algorithm reaches vertex b, there must be another propagator r with an end on edge d and $I_i(r) = d+1$ ; the only way this can occur is if r is outside $(q,<_i)$ but inside $(p,<_i)$ . But now, r contributes its fourth vertex to $I_i$ , again contradicting the minimality of p.▪

Proof Fix $i \in [n]$ . It follows from the proof of Lemma 3.10 that in applying Algorithm 3.5 to construct the set $I_i$ , the algorithm can never reach the fourth vertex of a propagator’s support (ordered with respect to $<_i$ ) without having already assigned that propagator. Therefore, if the algorithm starts at vertex i, all propagators must have been eliminated by the time it gets to vertex $i-1$ , ensuring that the algorithm is completed in at most one full circumnavigation of the diagram and that $I_i$ contains exactly k distinct elements.▪

Proof We will prove the result by induction on the number of propagators. If W has one propagator, then the result is immediate. Now, suppose W has more than one propagator. Because nonsupporting vertices have no effect on Algorithm 3.5, it suffices to prove the result for W (possibly weakly admissible) with no nonsupporting vertices. Then, by Lemma 3.3, W has at least one of the four situations illustrated in Figure 8.

Figure 8:

Four cases for admissible Wilson loop diagrams with no nonsupporting vertices. The gray half-propagators illustrate where propagators may occur, but are not required to exist.

In each of the four cases, when we remove the propagator labeled p, we obtain a diagram which satisfies the statement of the theorem by the induction hypothesis, and contains a propagator ${q = (i,j)}$ with no other propagators inside it (with respect to the $<_i$ orientation). Note that this region may or may not contain nonsupporting vertices, which we will call $l, l+1, \ldots $ as necessary. Let V be the diagram obtained by removing the propagator p from W (Figure 9). The diagram V is guaranteed to be admissible, because it was formed by removing a propagator from a diagram that was at least weakly admissible.

Figure 9:

Diagram V is W with p removed; there are no propagators inside $q = (i,j)$ , though there may be up to 4 non-supporting vertices labeled $l, l+1, \ldots , l+3$ .

Consider Case 4 of Figure 8 first, as it is the easiest. In this case, the vertices ${\{l,l+1,l+2,l+3\}}$ which support p in W are nonsupporting in V, so for every propagator r in V (including q), we have $J_r^{V} = J_r^{W}$ ; these are nonempty cyclic intervals in the correct order by the induction hypothesis. Furthermore, it is clear from Figure 8 that $J_p^{W}(l+a) = \{l+a\}$ for $a\in \{1,2,3\}$ and $J_p^{W}(l) = [n] \backslash \{l+1, l+2, l+3\}$ . The result therefore holds in this case.

Now, we proceed to consider the first three cases of Figure 8. We first describe $J_q^{V}(*)$ , which can be handled identically for all three cases.

In V, there are no propagators inside q by construction, so we see from Figure 9 that

$$ \begin{align*}l, l+1, \ldots ,j \in J^{V}_q(j) \text{ (if}\ l\ \text{exists)}\ \text{and}\ j+1 \in J^{V}_q(j+1).\end{align*} $$

Note that $j+2 \not \in J^{V}_q(j+1)$ by Lemma 3.10, so $J^{V}_q(j+1) = \{j+1\}$ , and by the induction hypothesis, we must have $j+2 \in J^{V}_q(i)$ . Thus, there exist vertices $d,e \in [j+2,i+1]$ with $d <e$ , such that

(3.1) $$ \begin{align} J^{V}_q(i) = [j+2,d-1], \ J^{V}_q(i+1) = [d,e-1], \ J^{V}_q(j) = [e,j], \ J^{V}_q(j+1) = \{j+1\}, \end{align} $$

and all intervals are nonempty.

We now consider what happens as we move from V to each of the three remaining cases for W. We need to consider both $J^{W}_p$ and $J^{W}_r$ for $r \neq p$ , because the addition of p can have a knock-on effect on latter steps in the algorithm.

Cases 1 and 2: These cases behave very similarly except when j or $j+1$ are not in the support of p, which can occur in Case 2 only; see below. Consequently, we handle the majority of the proof for these two cases simultaneously. Write $p=(m,m+2)$ where $m\in \{i, i+1, l\}$ . Let $1\leq a\leq 3$ be the number of nonsupporting vertices inside q in V (note that there is at least 1); so these vertices are $l, \ldots , l+a-1$ . Note that these vertices are nonsupporting in V but are all in the support of p in W.

We first calculate $I^{W}_w$ for a starting vertex ${w \in [n]\backslash \{l, l+1, \ldots ,j,j+1\}}$ . Note that p has no effect on other propagators for starting vertices in this range (because p will be the final propagator encountered by the algorithm), so if $r \neq p$ , then $I_w^W(r) = I_w^V(r)$ . Meanwhile, the value of $I^{W}_w(p)$ depends on which step in the algorithm the propagator q contributes a vertex in the diagram V, i.e., on the value of $I^{V}_w(q)$ . Thus, if $w\in J_q^{V}(i)$ , then

$$ \begin{align*} I_w^{W}(r) = \begin{cases} \max\{i+1, m\} & \text{if } r=p \\ I_{w}^{V}(r) & \text{if } r\neq p\;, \end{cases} \end{align*} $$

whereas if $w\in J_q^{V}(i+1)$ or $w\in J_q^{V}(j)$ , then

$$ \begin{align*} I_w^{W}(r) = \begin{cases} l & \text{if } r=p \\ I_{w}^{V}(r) & \text{if } r\neq p \;. \end{cases} \end{align*} $$

We also need to understand $I^{W}_w$ for $w \in \{l,l+1,\ldots ,j,j+1\}$ . For the majority of these vertices, we use the following observation: if p is the first propagator to be assigned a value by $I_w^{W}$ , then the remainder of $I_w^{W}$ proceeds identically to the assignments of $I^{V}_{w+1}$ (recall Remark 3.9). Thus, we have, for any $0\leq b <a$ ,

$$ \begin{align*} I_{l+b}^{W}(r) = \begin{cases} l+b & \text{if } r=p\\ I_{l+b+1}^{V}(r) & \text{if } r\neq p\;. \end{cases} \end{align*} $$

Similarly, if j is in the support of p, then we have

$$ \begin{align*} I_j^{W}(r) = \begin{cases} j & \text{if}\ r=p\ \text{and}\ j\ \text{is in the support of}\ p\\ I_{j+1}^{V}(r) & \text{if}\ r\neq p\ \text{and}\ j\ \text{is in the support of}\ p \;. \end{cases} \end{align*} $$

If j is not in the support of p, then we must be in Case 2 of Figure 8 with two vertices in the right-hand region. In this case, if we start the algorithm at j, we need to know whether there will be any unassigned propagators other than p when we reach vertex i, so as to know what p contributes.

Consider the Wilson loop diagram X formed from V by replacing the propagator $q = (i,j)$ with $q = (i, j-1)$ . The diagram X is still admissible, because we have not decreased the support of any set of propagators. It follows from the position of q in X that $I_j^X(q) = j$ , and from Lemma 3.10 that $I_{j+1}^X(q) \neq j$ . By the induction hypothesis, we must therefore have $I_{j+1}^X(q) = i$ . In particular, this means that if we start at $j+1$ and assign propagators to vertices according to the algorithm, when we reach vertex i in X, all propagators other than q must have been assigned.

Therefore, if we start at j in W, we first assign q to j, then proceed to assign as in X starting at $j+1$ , and hence when we get to i, the only remaining unassigned propagator is p. We obtain

$$ \begin{align*} I_j^{W}(r) = \begin{cases} m & \text{if}\ r =p\ \text{and}\ j\ \text{is not in the support of}\ p \\ I_{j}^{V}(r) & \text{if}\ r\neq p\ \text{and}\ j\ \text{is not in the support of}\ p\; .\end{cases} \end{align*} $$

This completes the analysis of $I_j^W$ . Finally, we consider what happens when we start the algorithm at vertex $j+1$ . If $j+1$ is in the support of p, then we can argue as above to get

$$ \begin{align*} I_{j+1}^{W}(r) = \begin{cases} j+1 & \text{if}\ r=p\ \text{and}\ j+1\ \text{is in the support of}\ p\\ I_{j+2}^{V}(r) & \text{if}\ r\neq p\ \text{and}\ j+1\ \text{is in the support of}\ p\;. \end{cases} \end{align*} $$

Now, suppose $j+1$ is not in the support of p. If we start at $j+1$ , we need to know whether there are any unassigned propagators supported on edge i when we reach vertex i. We already know that $J_q^{V}(j+1) = \{j+1\}$ ; in particular, this means that q contributes i in $I_{j+2}^{V}$ , by the induction hypothesis applied to V. However, the construction of $I^{V}_{j+1}$ first assigns q to $j+1$ and proceeds identically to $I^{V}_{j+2}$ . In particular, if i was assigned in $I^{V}_{j+1}$ , then it would not be available to assign to q in $I^{V}_{j+2}$ , as all other propagators supported at i in V come before q.

Therefore, p is the only potentially unassigned propagator on edge i when we reach vertex i in the algorithm for $I_{j+1}^W$ , and

$$ \begin{align*} I_{j+1}^{W}(r) = \begin{cases} m & \text{if}\ r=p\ \text{and}\ j+1\ \text{is not in the support of}\ p\\ I_{j+1}^{V}(r) & \text{if}\ r\neq p\ \text{and}\ j+1\ \text{is not in the support of}\ p \;. \end{cases} \end{align*} $$

We can now describe the intervals $J^{W}_r(*)$ for Cases 1 and 2 of Figure 8. For $r \neq p$ , the intervals are clearly still cyclic and appear in the correct order, and we can assemble the intervals for the $J_p^{W}(*)$ as follows. Recall that $p = (m,m+2)$ , $1 \leq a \leq 3$ , is the number of nonsupporting vertices inside q in V, and these nonsupporting vertices are denoted $\{l,l+1, \dots \}$ .

• • If $m=l$ , then either $a=2$ (so $l+1=m+1$ , $j=m+2$ , and $j+1=m+3$ ) or $a=3$ (so $l+1=m+1$ , $l+2=m+2$ , $j=m+3$ , and $j+1$ is not in the support of p). In both cases,

  $$ \begin{gather*} J^{W}_p(m) = [m+4, m], \qquad J^{W}_p(m+1) = \{m+1\}, \\ J^{W}_p(m+2) = \{m+2\}, \qquad J^{W}_p(m+3) = \{m+3\}, \end{gather*} $$
  which are nonempty and otherwise as required.

• • If $m=i+1$ , then checking each of the three different possibilities for a, we likewise get

  $$ \begin{gather*} J^{W}_p(m) = [m+4, d-1], \qquad J^{W}_p(m+1) = [d, m+1], \\ J^{W}_p(m+2) = \{m+2\}, \qquad J^{W}_p(m+3) = \{m+3\}, \end{gather*} $$
  which are nonempty and otherwise as required. Recall that d was defined in equation (3.1).

• • If $m=i$ , then $a=1$ or $a=2$ ; in the former case, $l=m+2$ , $j=m+3$ , and $j+1$ are not in the support of p, so

  $$ \begin{gather*} J^{W}_p(m) = \{m+4\}, \qquad J^{W}_p(m+1) = [m+5, d-1], \\ J^{W}_p(m+2) = [d, m+2], \qquad J^{W}_p(m+3) = \{m+3\}, \end{gather*} $$
  while in the latter, $l=m+2$ , $l+1=m+3$ , j, and $j+1$ are not in the support of p, so
  $$ \begin{gather*} J^{W}_p(m) = [m+4, j+1], \qquad J^{W}_p(m+1) = [j+2, d-1], \\ J^{W}_p(m+2) = [d, m+2], \qquad J^{W}_p(m+3) = \{m+3\}, \end{gather*} $$
  which are again as required.

Case 3: In this case, there are no nonsupporting vertices $l, l+1, \ldots $ inside q. Again, write ${p=(m, m+2)}$ , where $m\in \{j, j+1, j+2\}$ . We proceed as in the previous cases, by computing $I^{W}_w$ for vertices w in roughly increasing order of difficulty.

For $w \in [n]\backslash \{j+1,m,m+1,m+2,m+3\}$ , if $w\in J_q^{V}(i)$ or $w\in J_q^{V}(i+1)$ , then

$$ \begin{align*} I_w^{W}(r) = \begin{cases} m & \text{if } r=p \\ I_{w}^{V}(r) & \text{if } r\neq p \;, \end{cases} \end{align*} $$

whereas if $w\in J_q^{V}(j)$ , then

$$ \begin{align*} I_w^{W}(r) = \begin{cases} \max\{m, j+1\} & \text{if } r=p \\ I_{w}^{V}(r) & \text{if } r\neq p \end{cases} \;. \end{align*} $$

Finally, for $j+1$ and the vertices in the support of p, we have

$$ \begin{align*} I_{j+1}^{W}(r) &= \begin{cases} j+1 & \text{if } r=q\\ j+2 & \text{if } r=p\\ I_{j+3}^{V}(r) & \text{if } r\neq p,q \;, \end{cases} \\ I_m^{W}(r) &= \begin{cases} m & \text{if}\ r=p\ \text{and}\ q\ \text{not supported on}\ m\\ m+1 & \text{if}\ r=p\ \text{and}\ q\ \text{supported on}\ m\\ I_{m}^{V}(r) & \text{if } r\neq p \;, \end{cases} \\ I_{m+1}^{W}(r) & = \begin{cases} m+1 & \text{if}\ r=p\ \text{and}\ q\ \text{not supported on}\ m+1 \\ m+2 & \text{if}\ r=p\ \text{and}\ q\ \text{supported on}\ m+1 \\ I_{m+1}^{V}(r) & \text{if } r\neq p,q \;, \end{cases}\\ I_{m+2}^{W}(r) & = \begin{cases} m+2 & \text{if } r=p \\ I_{m+3}^{V}(r) & \text{if } r\neq p \;, \end{cases}\\ I_{m+3}^{W}(r) & = \begin{cases} m+3 & \text{if } r=p \\ I_{m+4}^{V}(r) & \text{if } r\neq p \;. \end{cases} \end{align*} $$

Note that $I_{m+2}^{V}(r) = I_{m+3}^{V}(r)$ for all propagators r in V, and that if $j+1\not \in \{m, m+1, m+2, m+3\}$ , then $j+2$ and $j+3$ are nonsupporting vertices in V, so in that case, $I_{j+2}^{V}(r) = I_{j+3}^{V}(r) = I_{j+4}^{V}(r)$ for r in V.

Therefore, once again, we can see that the $J_r^{W}(*)$ are cyclic for all $r\neq p$ in W. Assembling the intervals for p, we have the following statements.

• • If $m=j$ , then

  $$ \begin{gather*}J_p^{W}(m) = [m+4,e-1], \qquad J_p^{W}(m+1) = [e,m], \\ J_p^{W}(m+2) = [m+1,m+2], \qquad J_p^{W}(m+3) = \{m+3\}\;.\end{gather*} $$
  Recall that e was defined in equation (3.1).

• • If $m=j+1$ , then

  $$ \begin{gather*}J_p^{W}(m) = [m+4,m-1], \qquad J_p^{W}(m+1) = [m,m+1], \\ J_p^{W}(m+2) = \{m+2\}, \qquad J_p^{W}(m+3) = \{m+3\}\;.\end{gather*} $$

• • If $m=j+2$ , then

  $$ \begin{gather*}J_p^{W}(m) = [m+4,m], \qquad J_p^{W}(m+1) = \{m+1\}, \\ J_p^{W}(m+2) = \{m+2\}, \qquad J_p^{W}(m+3) = \{m+3\}\;.\end{gather*} $$

The result now follows by induction.▪

Proof For each $i \in [n]$ , let $I_i$ be the set of vertices assigned to the propagators of W by Algorithm 3.5 with starting vertex i. By Lemma 3.11, we know that $|I_i| = k$ for each $i \in [n]$ . We prove that $I_{i+1} \supseteq I_i \backslash \{i\}$ for all $i \in [n]$ ; this is equivalent to the definition of Grassmann necklace given in Definition 2.6.

Fix n, and suppose, by way of contradiction, that there exists an admissible diagram for which there exists an i with $m\in I_i\setminus \{i\}$ and $m \not \in I_{i+1}$ . Let W be such a counterexample with the minimal number of propagators.

If $i \not \in I_i$ , then there are no propagators supported on i at all. In this case, it is clear that applying Algorithm 3.5 at vertex i and vertex $i+1$ produces exactly the same result, i.e., $I_{i+1} = I_i$ , contradicting that W is a counterexample.

Now, suppose that $i \in I_i$ . Let p be the propagator which contributes i to $I_i$ , that is, $I^W_i(p) = i$ ; thus, one end of p must lie on either edge $i-1$ or edge i. In both cases, let b denote the edge supporting the other end of p, i.e., $p = (i, b)$ or $p = (i-1, b)$ .

Case I: Suppose p has one end on edge $i-1$ . By Remark 3.9, the construction of $I_i^W$ and $I_{i+1}^W$ is locally the same (indeed, locally identical in this case) from vertex $i+1$ to $b-1$ , so we have $I_{i+1}^W \cap [i+1,b-1] = I_{i}^W \cap [i+1,b-1]$ . Note that if $b = i+1$ , then this interval is empty, and the equality remains true.

By Lemma 3.12, it must happen that we have $I_{i+1}^W(p) = b$ , as otherwise b would never be contributed by p. Consequently, when the construction of $I_{i+1}^W$ reaches vertex b, there cannot be any remaining unassigned propagators that are supported on b and clockwise of p (Remark 3.8). It follows that the same must be true when $I_i^W$ reaches vertex b, because $I_i^W$ and $I_{i+1}^W$ behave identically on the interval $[i+1,b-1]$ as noted in the previous paragraph.

The previous two paragraphs also imply that $m \geq _i b+1$ , because $I_{i+1}^W \cap [i+1,b-1] = I_{i}^W \cap [i+1,b-1]$ and $b \in I_{i+1}^W$ .

Now, let $W' = (\mathcal {P}_{out}(p,<_i), [n])$ , i.e., the diagram obtained from W by removing both p and all propagators inside p. The diagram $W'$ has strictly fewer propagators than W did.

Observe that $I_i^W$ and $I_b^{W'}$ are locally the same from vertex b onward, because by the above observations, the propagators removed from W to create $W'$ are exactly those that come first in the ordering defined by $I_i^W$ . Similarly, $I_{i+1}^W$ and $I_{b+1}^{W'}$ are locally the same from $b+1$ onward. By Remark 3.9, this yields the equalities

$$ \begin{align*} I_i^{W} \cap [b,i-1] & = I_b^{W'}, \\ I_{i+1}^{W} \cap [b+1,i-1] & = I_{b+1}^{W'}. \end{align*} $$

Because we have already noted that $m \geq _i b+1$ , this implies that $m\in I_b^{W'}\setminus \{b\}$ and $m\not \in I_{b+1}^{W'}$ . This contradicts the minimality of W.

Case II: Suppose p has one end on edge i. Note that by assumption we have $I_i(p) = i$ ; this means that p must be the clockwise-most propagator lying on edge i, and hence we must have $I_{i+1}(p) = i+1$ as well. Observe also that $m\geq _i i+2$ , because $i+1\in I_{i+1}$ .

Let $W'$ be the diagram obtained from W by removing the propagator p. We have

$$ \begin{align*} I_i^{W} \backslash \{i\} & = I_{i+1}^{W'} \;, \\ I_{i+1}^{W} \backslash \{i+1\} & = I_{i+2}^{W'}\;, \end{align*} $$

because in both cases, the algorithm in $W'$ proceeds identically to that in W after assigning p. Because $m \neq i+1$ , we have $m\in I_{i+1}^{W'}\setminus \{i+1\}$ , but $m\not \in I_{i+2}^{W'}$ , contradicting the minimality of W. This completes the proof.▪

Proof We have shown in the previous theorem that $(I_1,\dots ,I_n)$ is a Grassmann necklace; it remains to check that this Grassmann necklace corresponds to the positroid $M(W)$ . Recall from the discussion following Definition 2.6, and equation (2.3) in particular, that it suffices to show the following points.

• • For each $i \in [n]$ , $I_i$ is a basis for $M(W)$ .

• • If J is lexicographically smaller than $I_i$ with respect to $<_i$ (for any $i \in [n]$ ), then J is not a basis for $M(W)$ .

The first point follows immediately. The algorithm assigns each propagator to a vertex in the support of that propagator, so $I_i$ is a basis for $M(W)$ by Corollary 2.4.

Now, fix $i \in [n]$ , and write $I_i = \{a_1 <_i a_2 <_i \dots <_i a_k\}$ . Label the propagators of W according to the ordering imposed by $I_i$ , so that $I_i(p_{r}) = a_{r}$ for $1 \leq r \leq k$ . Define $\mathcal {P}_r: = \{p_1,p_2,\dots ,p_r\}$ for each $r\geq 0$ , with $\mathcal {P}_0 = \emptyset $ .

Let $J = \{j_1 <_i j_2<_i \dots <_i j_k\}$ be a k-set, and suppose that $J<_i I_i$ in the $<_i$ -lexicographic order. Let m be the minimal index such that $j_m <_i a_m$ , i.e., the first entry at which J and $I_i$ differ. We will show that J must be a dependent set.

If $\text {Prop}(j_m) = \emptyset $ , then J is automatically dependent, because the corresponding column of $C(W)$ contains only zeros, so suppose henceforth that $\text {Prop}(j_m) \neq \emptyset $ .

In order to exhibit a dependent subset of vertices in J, we first define a sequence of sets of propagators by

$$ \begin{align*}Q_0 = \text{Prop}(j_m), \qquad Q_{l+1} = \text{Prop}(I_i(Q_l))\quad \forall l \geq 0.\end{align*} $$

It is easily verified that this is an increasing chain of sets. Indeed, if $q \in Q_l$ , then $I_i(q) \in I_i(Q_l)$ , and because $I_i(q)$ is one of the vertices that supports q, we must have $q \in \text {Prop}(I_i(Q_l)) = Q_{l+1}$ . Because $\mathcal {P}$ is finite, the sequence stabilizes in finitely many steps. Let $Q := \bigcup _{l \geq 0} Q_l$ be this set of propagators.

We will show that $Q \subseteq \mathcal {P}_{m-1}$ , which will imply the theorem by the following argument. If $Q \subseteq \mathcal {P}_{m-1}$ , then we have $I_i(Q)\subseteq J$ , and hence $I_i(Q) \cup \{j_m\} \subseteq J$ as well. Because $I_i(Q) \cup \{j_m\}$ only supports the propagators in Q but has $|Q|+1$ vertices, it is a dependent set in $M(W)$ . Thus, J is also a dependent set, and the Grassmann necklace $(I_1,\dots ,I_n)$ constructed from W does indeed define the positroid $M(W)$ .

All that remains is to prove $Q\subseteq \mathcal {P}_{m-1}$ , which we do by inductively proving $Q_l \subseteq \mathcal {P}_{m-1}$ for all $l \geq 0$ . The base case $Q_0 \subseteq \mathcal {P}_{m-1}$ is immediate; because $j_m \not \in I_i$ by construction, there cannot be any unassigned propagators supported on $j_m$ when the algorithm reaches that vertex, i.e., ${\text {Prop}(j_m) \subseteq \mathcal {P}_{m-1}}$ .

Now, assume that $Q_0,\dots ,Q_{l-1} \subseteq \mathcal {P}_{m-1}$ , and consider $Q_{l}$ . If $Q_{l} \setminus Q_{l-1} = \emptyset $ , then we are done, with $Q = Q_l$ . Otherwise, let $q \in Q_{l} \setminus Q_{l-1}$ . By construction, there is some propagator $p_r \in Q_{l-1}$ such that $p_r$ and q are both supported on $I_i(p_r) = a_r$ . If q is clockwise of $p_r$ on vertex $a_r$ , then we immediately have $q \in \mathcal {P}_{m-1}$ by Remark 3.8. It remains to consider the case that q is counterclockwise of $p_r$ at $a_r$ .

Note that we cannot have $a_r+ 1 = j_m$ when q is counterclockwise of $p_r$ , because $q \not \in \text {Prop}(j_m)$ by assumption. If the other end of $p_r$ (i.e., the end not supported on $a_r$ ) lies on an edge between $a_r$ and $j_m$ , then because q is inside $p_r$ with respect to $<_{a_r-1}$ , we must have $V(q) \subseteq [a_r-1,j_m]$ , and hence $q \in \mathcal {P}_{m-1}$ by Lemma 3.10; this is illustrated in Figure 10. In particular, if $l=1$ , then $p_r \in Q_{0} = \text {Prop}(j_m)$ , and we must be in this case.

Figure 10:

If q is counterclockwise of $p_r$ and the other end of $p_r$ lies on an edge between $a_r$ and $j_m$ , then $V(q) \subseteq [a_{r-1},j_m]$ . The vertex $a_r$ lies somewhere within the (blue) highlighted region.

If not, then there must be some propagator $p_s \in Q_{l-2}$ such that $p_r$ and $p_s$ are both supported on $I_i(p_s) := a_s$ ; see Figure 11. Because $p_r$ is clockwise of q, and q cannot be supported on $I_i(p_s)$ because $q \not \in Q_{l-1}$ , it follows that $I_i(p_s) <_i I_i(p_r)$ . Therefore, q is inside $p_s$ with respect to $<_{a_s - 1}$ as well.

Figure 11:

If the other end of $p_r$ does not lie on an edge between $a_r$ and $j_m$ , then we must have a propagator $p_s \in Q_{l-2}$ in one of the depicted configurations. The (blue) highlighted regions indicate the approximate position of a vertex whose precise position is unknown. Cutoff propagators indicate that the location of the propagator’s other end is unknown; in particular, no meaning should be ascribed to the angle at which these propagators are drawn.

Now, repeat the argument above with $p_s$ in place of $p_r$ . If the other end of $p_s$ lands on an edge between q and $j_m$ , then we have $q \in \mathcal {P}_{m-1}$ as above; if not, then there exists some $p_t \in Q_{l-3}$ with $p_s$ supported on $I_i(p_t)$ and q on the inside of $p_t$ in the $a_t-1$ order. Therefore, $I_i(p_t) <_i I_i(p_r)$ . Because there are finitely many steps this process can take before reaching $Q_0$ , and any $p_* \in Q_0 = \text {Prop}(j_m)$ has $j_m$ in its support by definition, this argument eventually terminates with the construction of a propagator constraining the positioning of q as required. This completes the induction step, and hence the proof.▪

Proof For any $i \in [n]$ , $i-1$ is maximal with respect to the $<_{i}$ order, and so by Lemma 3.10, there can be no propagator p with $I_{i}(p) = i-1$ . Thus. $i-1 \not \in I_{i}$ , so $i-1$ is not a coloop. Because this holds for any $i \in [n]$ , the Grassmann necklace admits no coloops.

If $j \in [n]$ is a loop, then, in particular, we have $j \not \in I_j$ , which can only happen if there are no propagators supported on vertex j. Conversely, if j supports no propagators, then Algorithm 3.5 never assigns a propagator to j and hence $j \not \in I_i$ for all $i \in [n]$ .▪