Links and the Diaconis-Graham Inequality
Christopher Cornwell Nathan McNew




    
In 1977 Diaconis and Graham proved two inequalities relating different measures of disarray in permutations, and asked for a characterization of those permutations for which equality holds in one of these inequalities. Such a characterization was first given in 2013. Recently, another characterization was given by Woo, using a topological link in ℝ^3 that can be associated to the cycle diagram of a permutation.
We show that Woo’s characterization extends much further: for any permutation, the discrepancy in Diaconis and Graham's inequality is directly related to the Euler characteristic 
of the associated link.  This connection provides a new proof of the original result of Diaconis and Graham.  We also characterize permutations with a fixed discrepancy in terms of their associated links and find that the stabilized-interval-free permutations are precisely those whose associated links are nonsplit.



Dichalcogenides and difulfides nanostructures for hydrogen storage
    Andréia Luisa da Rosa
    April 29, 2024
==================================================================





§ INTRODUCTION



Many different metrics can be used to measure the disarray of a shuffled list.  Treating the list as a permutation π∈ S_n, and denoting by π_i the number in position i of π, some popular metrics are:

    
  * I(π) = ∑_i=1^n #{j>i |π_j<π_i}, the number of inversions in π.
    
  * D(π) = ∑_i=1^n |π_i-i|, the sum of the absolute  differences between the indices and values of π (called Spearman's footrule).
    
  * T(π), the minimum number of transpositions required to produce π.
 

Notice that all three metrics are zero when π is the identity permutation. In 1849 Cayley showed that T(π) is equal to n minus the number of cycles in π, i.e.  T(π) = |π|-(π) where (π) is the number of cycles in π. 


The so-called Diaconis-Graham inequalities <cit.> relate these three metrics for any permutation π:

    I(π) + T(π) ≤ D(π) ≤ 2 I(π).

Diaconis and Graham give a simple proof of the second inequality, and permutations where equality holds have a nice characterization: D(π) = 2 I(π) if and only if π contains no 3‐inversions (a triplet i < j < k where π_i > π_j > π_k, equivalently an occurrence of the pattern 321). Their proof of the first inequality is not so intuitive, however, and they don't characterize when equality holds.  Such a characterization was first given in 2013 by Hadjicostas and Monico <cit.>.  Building on their work, and results of the present authors, Woo <cit.> gives a simpler, remarkable characterization of these permutations in terms of their cycle diagrams and an associated link.



The “cycle diagram” (or cobweb plot) of a permutation π is obtained by plotting the permutation as follows: For each index i, draw a vertical line from (i,i) to (i,π_i), followed by a horizontal line to (π_i,π_i). If i is a fixed point of π then there is an isolated point plotted at (i,i).  Such a diagram allows a nice visualization of the cycle structure of the permutation. 




r0.37


  4,5,2,6,1,3
[scale=0.38]

		(0) at (1, 0.75) ;
		(1) at (0.5, 2.75) ;
		(2) at (1.75, 4.25) ;
		(3) at (2.5, 1.5) ;
		(4) at (3.5, 5.5) ;
		(5) at (3.5, 1) ;
		(6) at (5.5, 2.5) ;
		(7) at (1.75, 1.75) ;
		(8) at (2.5, 2.5) ;
		(9) at (3.5, 3.5) ;
		(10) at (4.5, 4.25) ;
		(11) at (5, 5) ;
		(12) at (1.25, 3.5) ;
		(13) at (1.75, 3.25) ;
		(14) at (3.25, 4.5) ;
		(15) at (3.75, 4.5) ;
		(16) at (4.25, 2.5) ;
		(17) at (4.75, 2.25) ;
		[thick, in=-90, out=135, looseness=1.25] (0.center) to (1.center);
		[thick,in=150, out=90, looseness=1.50] (1.center) to (12.center);
		[thick,in=-135, out=-30] (13.center) to (9.center);
		[thick,in=-135, out=60] (9.center) to (4.center);
		[thick,in=135, out=30, looseness=1.25] (4.center) to (11.center);
		[thick,in=60, out=-45] (11.center) to (6.center);
		[thick,in=-30, out=-120] (6.center) to (17.center);
		[thick,in=45, out=150] (16.center) to (8.center);
		[thick,in=45, out=-120] (8.center) to (3.center);
		[thick,in=-60, out=-135] (3.center) to (7.center);
		[thick,in=-120, out=120] (7.center) to (2.center);
		[thick,in=-180, out=60] (2.center) to (14.center);
		[thick,in=120, out=0] (15.center) to (10.center);
		[thick,in=45, out=-45, looseness=0.75] (10.center) to (5.center);
		[thick,in=-30, out=-135] (5.center) to (0.center);


    

    The cycle diagram of the cycle 452613 along with the associated knot, a trefoil.
    



After adding “decorations” at crossings, the cycle diagram may be viewed as a knot (or link) diagram. That is, considering lines in the diagram as strands of a knot, at each crossing between a vertical line and horizontal line we add the information that the vertical line is crossing over the horizontal.  Now, if each isolated point (any fixed point of π) is made to represent a small disjoint and unlinked component, then we may consider this a planar diagram of a link, which we denote L_π.[The term knot typically requires a single connected component, but a link may have multiple components. This happens whenever the permutation doesn't consist of a single cycle.]


The method described here of associating a link to a permutation was first introduced in <cit.>, where it is shown that the count of the cycles of length n associated to an unknotted planar diagram is enumerated by the large Schroeder numbers, and a generating function is given for the sequence enumerating permutations associated to an unlink.[An unlink is a link that is topologically the same as one in which each of the link components is a round circle, and these circles bound disks that are pairwise disjoint.]  Subsequently, Woo <cit.> showed that a permutation π is associated to an unlink if and only if equality holds in the first part of (<ref>), i.e. I(π)+T(π) = I(π) + n -(π) = D(π).  In this paper we show that this analogy extends much further.  

Denote by χ(L) the Euler characteristic of a link L, a well-known link invariant which is described in Section <ref> below.  We also introduce the function 
    x(π) D(π) - I(π) - |π|,
 which will be the primary permutation statistic of interest in this paper.  This quantity x(π) is essentially the difference between the two quantities in the first inequality of (<ref>), up to the number of cycles occurring in π, i.e. x(π) =  D(π) - (I(π) + T(π)) -(π).
Our main theorem describes the relationship between these two quantities.


    For any permutation π the difference x(π)=D(π) -I(π) - |π| is equal to the negative Euler characteristic of the associated link, i.e. 
    x(π) = -χ(L_π).

 
  This result leads to a completely new proof of the first inequality of (<ref>), described in Section <ref>.

 
The inequality

    I(π) + T(π) ≤ D(π)
    
holds for all permutations π,
with equality holding precisely for those permutations whose diagram corresponds to an unlink (for which the Euler characteristic equals (π)).

We are able to similarly characterize those permutations π with a given number of cycles where D(π) exceeds I(π)+T(π) by a fixed amount. The corollary below follows immediately from Theorem <ref>.


    For any integer k≥ 0, the set of permutations π where D(π) exceeds I(π)+T(π) by exactly k is precisely the set of permutations corresponding to links with Euler characteristic χ(L_π)=-k+(π).


Before giving the proof of Theorem <ref> in Section <ref>, we prove several lemmata in Section <ref> that will be needed in the proof.  From these results we obtain the following theorem, which may be of independent interest.  

A link L in ℝ^3 is called a split link if there exists a surface in ℝ^3, homeomorphic to a 2-sphere, which is disjoint from L and has components of L in both its interior and exterior.  If no such surface exists, L is called non-split.  We are able to characterize those permutations corresponding to non-split links as follows.

 
    A permutation π corresponds to a non-split link L_π if and only if π is a stabilized-interval-free permutation.


The stabilized-interval-free permutations were defined and enumeratated by Callan <cit.>. See Section <ref> for details.  The following corollary then follows from his enumeration.

 
    The probability a randomly chosen derangement of n corresponds to a non-split link tends to 1 as n→∞.




§ CYCLE DIAGRAMS AND SEIFERT SURFACES OF LINKS





As discussed in the introduction, the cycle diagram of a permutation π may be decorated with crossing information and viewed as a link diagram. We write G_π for this decorated cycle diagram and L_π for the associated link in ℝ^3. If there are no fixed points of π, the diagram G_π is referred to in the literature as a grid diagram of the link (see <cit.> for a survey). 

r0.33


3,6,7,4,9,8,2,5,1
The diagram G_π, where π=367498251.
    


Standard definitions of grid diagrams do not allow for isolated points, such as G_π might contain on the diagonal. However, a grid diagram for L_π is easily obtained by replacing each isolated point by a small square contained in adjacent rows and columns, thereby producing a grid diagram with size |π|+#{fixed points}. 

We orient the strands of L_π so that vertical lines are oriented away from the diagonal; tracing the diagram in the order that π permutes its elements agrees with this orientation of the link.

Each crossing in an oriented link diagram has a sign, positive or negative. Our orientation convention causes every crossing in G_π to be negative, so every link L_π is the mirror of a positive link. In addition, if L_1 and L_2 are two link components of L_π then the linking number (cf. <cit.>) of L_1 and L_2 must be non-positive, and is only 0 if the planar projections of L_1 and L_2 into G_π are disjoint. 


    For a permutation π, the link L_π is a split link if and only if G_π is disconnected (as a subset of the plane).


The linking numbers of pairs of link components are a link invariant. Thus, given a split link, for any of its components L_1 that is on one side of the splitting sphere, L_1 has linking number 0 with every component found on the other side of the sphere. Hence, using the previous observation, there is a proper subset of the set of link components of L_π whose planar projection in G_π is disjoint from the projection of link components that are not in this subset (i.e., G_π is disconnected as a union of lines and points in the plane).



Write (G_π) for the number of crossings in G_π. Another statistic of G_π of interest is the number of upper-right corners in the diagram: indices i, 1≤ i≤ n, which satisfy both π(i)<i and π^-1(i) < i. Define s(G_π) to be the number of upper-right corners plus the number of fixed points of π. (Note: each small square replacing an isolated diagonal point would have exactly one upper-right corner.) 

Any link in ℝ^3 may be regarded as the boundary of an oriented surface  embedded in ℝ^3, a Seifert surface of the link. Given a diagram of the link (with orientation), Seifert described an algorithm to determine such a surface (<cit.>, cf. <cit.>). Our manner of proving the main result is informed by this algorithm, so we describe it here.

Given an oriented link diagram Z, remove each crossing in Z by changing how the strands are connected in a neighborhood of the crossing, as in Figure <ref> below. Note that the change is made to be coherent with the orientation on strands outside of the neighborhood. The result Ẑ is a union of oriented simple closed curves, no two of which intersect, called Seifert circles. As we will use them again in the algorithm, we remember the arcs on Seifert circles that were paired inside one of the neighborhoods.



Each Seifert circle bounds a disk, oriented so that the orientation on the Seifert circle agrees with the induced boundary orientation. Place the disks in ℝ^3 at heights so that, if Seifert circles S and S' are such that S is in the interior of S' (in the plane of the diagram), then the disk for S is above the disk for S'. 

Finally, for each crossing from Z we consider the associated arcs in Ẑ that were paired. Viewing these arcs as part of the boundary of disks for Seifert circles, attach at those arcs two opposite sides of a half-twisted band, as in Figure <ref> (with the remaining, unattached, part of the band's boundary now agreeing with the original crossing strands from Z). This completes the construction of the surface.



In Seifert's original algorithm, if the surface is disconnected after attachment of half-twisted bands then handles are added to connect the surface. This is needed when the link diagram is disconnected as a subset of the plane. In this paper, we leave the surface disconnected in this case.[For the sake of clarity, we highlight the difference between components of a diagram G_π and the link components of L_π⊂ℝ^3. For example, the diagrams depicted in Figure <ref> each have a single connected component; however, the associated link has 3 link components.]


Note that for a permutation π, the orientation convention and the fact that vertical segments cross over horizontal in G_π make the result of removing a crossing always appear the same (see Figure <ref>). A consequence is that, for any Seifert circle of G_π, above the diagonal it is (weakly) increasing in the vertical and horizontal directions; below the diagonal it is decreasing in the vertical and horizontal directions. Thus, there is exactly one upper-right corner and one lower-left corner on each Seifert circle. That is, s(G_π) equals the number of Seifert circles from the algorithm.



Given a permutation π, we let F_π denote the surface constructed from the grid diagram G_π through the algorithm above. The main result presented in this paper relates the value of the permutation statistic x(π) = D(π)-I(π)-|π| to a numerical invariant of the surface F_π, namely the Euler characteristic of F_π. 

The Euler characteristic of a surface F may be defined via a triangulation of the surface (see <cit.> for a brief, but informative, introduction to triangulations of surfaces). If a triangulation of F has v vertices, e edges, and f faces, the Euler characteristic is χ(F) = v - e + f. While the Euler characteristic of F may be computed this way, it is an invariant of F and is independent of choice of triangulation.

To define the Euler characteristic of a link, we consider orientable surfaces having the link as boundary. Were we to allow for any such surface, then the Euler characteristic could be arbitrarily increased by adding a separate surface component that is a sphere (and has no boundary). To avoid this pitfall, but still allow for disconnected surfaces, we require that every surface component have a non-empty boundary.

    We say that an orientable surface F is a (potentially disconnected) Seifert surface of an oriented link L if every component of F has non-empty boundary and the boundary of  F (with induced orientation) agrees with L. The Euler characteristic of L, written χ(L) is the maximal Euler characteristic of a Seifert surface of L.


A triangulation of F_π may be chosen so that there is an edge corresponding to each paired arc where the half-twisted bands were attached to a disk of a Seifert circle. 
Note that a disk has Euler characteristic equal to 1. By choosing the triangulation to be such that each of the half-twisted bands consists of exactly two triangles in the triangulation (sharing one “diagonal” edge in the interior of the band), one may check that  

    χ(F_π) = s(G_π) - (G_π).


There is a relationship between grid diagrams and Legendrian links that is often exploited in the knot theory (and Legendrian knot theory) literature. We use this relationship to see that F_π has maximum Euler characteristic among Seifert surfaces of L_π. 


If F is a Seifert surface of L_π, then χ(F) ≤χ(F_π), and so χ(L_π) = χ(F_π).

   
Let G_π^↻ be the grid diagram obtained by rotating G_π clockwise 90^∘, changing all crossings to retain that vertical strands cross over horizontal. There is a Legendrian link Λ_π associated to G_π^↻ which has the topological type of the mirror of L_π (see <cit.>). One of the classical invariants of a Legendrian link Λ is the Thurston-Bennequin number tb(Λ). For the Legendrian Λ_π, its value comes out as tb(Λ_π) = (G_π) - s(G_π). Now, by the Eliashberg-Bennequin inequality <cit.>, we have tb(Λ_π) ≤ -χ(F) for any surface F with Λ_π as its boundary link (not allowing connected components of F to have empty boundary). Since mirroring leaves the Euler characteristic of a surface unchanged, and noting that -χ(F_π) = (G_π) - s(G_π), we obtain the desired result.






§ PROOF OF COROLLARY <REF>



From the classification of surfaces, a connected surface with one boundary component has Euler characteristic at most 1 (and a connected surface with more than one boundary component has Euler characteristic less than 1). Let F be an oriented surface with b boundary components, such that every surface component has non-empty boundary. Since χ(F) equals the sum of the Euler characteristics of the connected components of F, we have that χ(F) ≤ b. 
Given a permutation π, if b is the number of cycles of π then b is also the number of link components in L_π. This provides a new proof of the Diaconis-Graham inequality.
Given any permutation π, 
    I(π)+T(π)  =  I(π) + |π|-cyc(π)  ≤ D(π).


By Theorem <ref>, 
    D(π) - I(π)-|π|+cyc(π) = -χ(F_π)+b ≥ 0

since b = (π) counts both the number of boundary components of the surface F_π and the number of cycles appearing in π. 


We also obtain a different proof of Alex Woo's <cit.> characterization of the permutations associated to an unlink.

    A permutation is associated to an unlink if and only if it is shallow as defined in <cit.>, namely D(π) - I(π) -|π| +(π) = 0.
  This follows directly from Theorem <ref>. In particular, our Theorem implies that a permutation is shallow if and only if -χ(L_π) = -b; this occurs exactly when each component of F_π is a disk, implying L_π is an unlink.  Unlike the proof in <cit.> this approach doesn't rely on the original recursive characterization of shallow permutations given by Hadjicostas and Monico. 



§ LEMMATA
 
We define the direct sum of two permutations, σ⊕τ in the usual way, if σ is a permutation of length m_1 and τ is a permutation of length m_2 then σ⊕τ is a permutation of m_1+m_2 given by

    (σ⊕τ)(i) = σ(i)     1≤ i ≤ m_1 
    τ(i-m_1) + m_1     m_1 < i ≤ m_1+m_2.

  The direct sum of two permutations satisfies both 
    x(σ⊕τ) = x(σ)+x(τ)

    and   
    χ(L_σ⊕τ) = χ(L_σ)+χ(L_τ).




    It follows immediately from the definitions that both D(σ⊕τ) = D(σ)+D(τ) and I(σ⊕τ) = I(σ)+I(τ), and so the same holds for the function x.  Since the component of the diagram corresponding to σ is disconnected from the component corresponding to τ, and our convention is to construct disconnected surfaces for each component of the diagram of G_σ⊕τ, we find that 
    
    χ(L_σ⊕τ) = χ(F_σ⊕τ) = χ(F_σ) + χ(F_τ)= χ(L_σ)+χ(L_τ).



The following lemma shows that a “translation” of a grid diagram and corresponding permutation leaves both the link type and the statistic x(π) unchanged.  

 
    For a permutation π∈ S_n, and the permutation (in one line notation) σ = 234⋯ n1 ∈ S_n (note σ = (123 ⋯ n) in cycle notation) define π' = σπσ^-1. Then the link type of L_π is the same as that of L_π' and also 
    x(π)=x(π').



In the terminology of grid diagrams, the grid diagrams G_π and G_π' are related by two translations (one being horizontal and the other being vertical).  By viewing the grid diagram as being on a torus, identifying opposite edges of the square, the conjugation action has the result of translating each column to the right by one, and each row up by one. The original rightmost column (respectively topmost row) appears on the far left side (bottom side) of the grid afterwards (see <cit.> for details and Figure <ref> for an example).  




It is well known (<cit.>) that the translation operation on a grid diagram leaves the associated link type unchanged. It then follows that L_π and L_π' have the same link type, and 

    -χ(L_π)  =  -χ(L_π').

Thus, we need only to show that x(π)=x(π').  Write out π = π_1π_2…π_n in one-line notation and define a, b to be the integers such that π_a = n and π_n = b. We can express the permutation π' as π' = π'_1π'_2…π'_n, where

    π'_k+1 = π_k + 1,    for  1≤ k≤ n-1, k a 
    π'_a+1 = 1 
    π'_1 = b+1.

In the edge case that a=n=b, the first line, indicating the value of π_k+1', 1≤ k≤ n-1, is unchanged; however, instead of the second and third line we have that π_1' = 1.

Now we may compute that 

    D(π') = ∑_i=1^n|π'_i - i|       = a + b + ∑_1≤ i<n
     i a |π_i+1 - (i+1)| 
       = D(π) + 2a + 2b - 2n

in the case when a n. If it is the case that a=n (and so b=n also) then 
    D(π') = ∑_i=2^n|π'_i - i| = ∑_i=1^n-1|π_i - i| = D(π),
 since |π'_1 - 1| and |π_n-n| are both zero.

In order to understand how the inversions change between π and π', note that if i,j ∉{a,n}, then (π_i, π_j) are in the same relative position to each other in π (i.e. whether π_i is left of or right of π_j in one-line notation), as the relative position of (π'_i+1, π'_j+1) in π'.

Since every π_i  b appears to the left of π_n = b in π, we get that the two elements π_i, π_n make an inversion if and only if π_i > b, a total of (n-b) inversions in π that involve π_n. After translation, π'_1=b+1 is to the left of every other element in π', so it makes an inversion with π'_i+1 if and only if b + 1 > π'_i+1, a total of b inversions in π' involving π'_1 (or 0 inversions in the case that b=n, since π_1'=1 in that case). Thus, if b n, then in going from π to π' there is a net change of b - (n-b)=2b-n inversions involving the element π_n (in π) or π'_1 (in π'). In the edge case b=n, we get that there is a net change of 0 inversions involving n (in π) and 0 involving 1 in π'.


We can make similar considerations for inversions that involve π_a in π and π'_a+1=1 in π' (assuming a n). One of these, already considered above, is the inversion involving π_a, π_n that associate with the inversion in π' involving π'_1, π'_a+1. The net change in inversions going from π to π' involving the elements π_a or π'_a+1 respectively is a - (n-a) = 2a - n. 

When a n and b n, we have shown that

    D(π') - I(π')       = D(π) + 2a + 2b - 2n - (I(π) + 2b-n + 2a - n) 
       = D(π) - I(π).

In the case that a = n (forcing b=n also), we have both D(π) = D(π') and I(π) = I(π').  Hence, we obtain the desired equality x(π') = x(π).


 
    The Seifert circles obtained from a connected component of a cycle diagram admit a partial order under containment, and there is a unique maximal Seifert circle S_max containing all of the others.  Furthermore, each Seifert circle has a unique upper-right and lower-left corner, and both are on the main-diagonal.



    These results are all demonstrated in the proofs of Lemma 20 and Lemma 22 (and remark 21) of <cit.>.  While the statements of these lemmas refer only to diagrams corresponding to cycles, it is straightforward to see that all of the arguments go through identically for any connected component of a diagram.


We say that a permutation π stabilizes an interval I if π(i) ∈ I for every i∈ I. 
 
    The diagram G_π of a permutation π is disconnected (i.e. the union of any fixed points, vertical and horizontal segments of the diagram is disconnected as a subset of the plane) if and only if the permutation π stabilizes a nontrivial subinterval I⊂ [1,n].


It follows immediately that if π stabilizes an interval I, then a square drawn to encompass the points on the diagonal corresponding to the integers in I will disconnect the components of the diagram of π. So we focus on the reverse direction.  

Suppose that the diagram of π is disconnected. This occurs if and only if there is a simple closed curve in the plane, not intersecting any point on G_π, which separates the diagram into two (non-empty) sub-diagrams – one in the interior, the other in the exterior of the closed curve. Call these sub-diagrams G^(1)_π and G^(2)_π.  Note that the diagonal nodes {1,…,|π|} are split into two subsets s^(1)(π) and s^(2)(π) (where i∈ s^(k)(π) if and only if diagonal node i is part of G^(k)_π). 

Assume that 1 ∈ s^(1)_π.  If s^(1)_π corresponds to an interval we are done, so suppose it does not, and let n_1,n_2 ∈ s^(1)_π be the smallest pair of integers such that n_2 > n_1+1 and the entire interval I=[n_1+1,n_2-1]⊆ s_π^(2).  If π stabilizes I, then again we are done.  So we now suppose it does not and derive a contradiction, which will complete the proof.  

If π does not stabilize I, then for some i∈ I, π(i) ∉ I, and hence, π(i)>n_2 (by the minimality of n_1,n_2).  Note that since the vertical line segment in G^(2)_π that extends upward from i, extends above height n_2, we have π^-1(n_2)>i (otherwise, i and n_2 could not be in disconnected sub-diagrams, as the horizontal segment of G^(1)_π that is at height n_2 would intersect the vertical one extending upward from i). Thus π^-1(n_2)>n_2.  Similarly, there must be j>n_2 with π(j)∈ I, and so, in order to avoid a crossing it must be that π(n_2)>n_2.  Thus, we find that the line segments adjacent to the point (n_2,n_2) form a lower-left corner of some Seifert circle S_1.  

Appealing to Lemma <ref>, each Seifert circle has a unique lower-left and upper-right corner (both of which lie on the main diagonal). We find that S_1 must lie completely inside the Seifert circle S_2 that contains the line segments connected to the point (i,π_i) (whose lower left corner must have x-coordinate at most i<n_2, and whose upper right corner has y-coordinate at least π_i>n_2).  Since the line segments connected to (i,π_i) are part of G_π^(2), all of the line segments that were used to create S_2 must also be part of G_π^(2). However, they completely surround the point (n_2,n_2), disconnecting it from the diagonal points at or below n_1, which is not possible with G_π^(1) and G_π^(2) being separated by a simple closed curve.




 §.§ Non-split links and stabilized-interval-free permutations
  

Callan <cit.> defined a permutation π to be  stabilized-interval-free if there is no nontrivial interval I ⊂{1,2,… |π|} stabilized by π.  He then showed that such permutations are enumerated by sequence https://oeis.org/A075834A075834 in the OEIS <cit.>, the integer sequence whose generating function A(x) has the property that the coefficient of x^n-1 in A(x)^n is n!.  

Theorem <ref>, that the permutations whose diagrams correspond to non-split links are precisely the stabilized-interval-free permutations, follows from Lemma <ref> and Proposition <ref>.

Since the n-th term in the sequence https://oeis.org/A075834A075834 is asymptotically n!/e(1 - 1/n +O(n^-2)), which is almost the same as that of the derangements (whose count is n!/e +O(1)), and of which the stabilized-interval-free permutations are a subset, we find that the probability a randomly chosen derangement of n corresponds to a non-split link tends to 1 as n→∞, as noted in Corollary <ref>.



§ PROOF OF THEOREM <REF>
 
We will prove that x(π) = -χ(L_π) by induction on the length of the permutation, |π|.  An interesting problem would be to find a non-inductive proof of this theorem.
 
 For permutations of length at most 2, the result is immediate: in every case the corresponding link L_π is an unlink. (When π=1 or π=21, the permutation has a single cycle, the link has a single component, and x(π)=-χ(L_π)=-1. When π=12 the permutation and link have 2 cycles/components, and x(π)=-χ(L_π)=-2.

We now suppose that the result holds for permutations of all lengths less than n and that |π| = n>2.  For any permutation of length n one of the following cases hold:


    
  * Case 1: The cycle diagram G_π is disconnected.
    
  * Case 2: The diagram G_π is connected but there exists an index 1<i<n such that either π_j≤ i for all j<i or π_j≥ i for all j>i. (In this situation the outermost Seifert circle touches the main diagonal at the index i.)
    
  * Case 3: The diagram G_π is connected and no index with the property described in case 2 exists. (The outermost Seifert circle doesn't touch the main diagonal, except at the bottom left and upper right corners.)

In each case we will see that the result can be reduced to the case of permutations of smaller length, which will complete the induction.




 §.§ Case 1.
 G_π is disconnected. 


In this case, by Lemma <ref>, there exists a nontrivial subinterval I⊂ [1,n] so that π stabilizes I.  By repeated application of Lemma <ref> (if necessary) we can translate the grid diagram of π to the grid diagram of another permutation π' (with x(π)=x(π') and -χ(L_π) = -χ(L_π')) such that the interval I has been translated to an interval, stabilized by π', of the form [a,n] for some integer a.  Now, it is clear that π' also stabilizes the complementary interval [1,a-1] and so π' decomposes as a direct sum π'=ρ⊕τ.  Since both ρ and τ are permutations of length shorter than |π|, we are done by Lemma <ref> and induction.



 §.§ Case 2.
 The diagram G_π is connected and there is an index 1<i<n such that either π_j≤ i for all j<i or π_j≥ i for all j>i.  


We consider the case π_j≤ i for all j<i, the other case being similar. Let L be a horizontal line drawn across G_π at y=i+1/2. Since G_π is connected, with components both above and below this horizontal line, it must contain vertical line segments crossing L.  These vertical line segments must correspond to indices j where j and π_j lie on opposite sides of the value i+1/2.   Furthermore, as π is a permutation, there must be an equal number of indices j<i+1/2 with π_j>i+1/2 as there are j>i+1/2 with π_j<i+1/2.  


Given our hypothesis that π_j≤ i for all j<i, there exists precisely one index j that can satisfy the former property, namely j=i. Hence there exists also exactly one index k>i with π_k<i+1/2.  Thus the diagram G_π crosses L twice, once at i and again at k.  (Note that both of these line segments must be part of the outermost Seifert circle, S_max, and that S_max therefore “touches” the diagonal at the point (i,i).) We now produce a permutation π', of length n+1, whose associated link corresponds to cutting the strands along the line L and reattaching the two loose ends on either side. 

This new permutation π'=π'_1π'_2⋯π'_nπ'_n+1 is defined as follows. For 1≤ j < i define π'_j = π_j; also, define π'_i = π_k and π'_k+1 = i+1. Finally, for i≤ j≤ n, j k, set π'_j+1 = π_j+1. Using that G_π intersects L only at the vertical lines in positions i and k, it is not hard to check that D(π') = D(π) and I(π') = I(π). For example, the construction makes clear that if an inversion in π is at elements that are both in positions less than i, or that both have positions greater than i, then there is a corresponding inversion in π' (involving the same positions in the first case, and positions that are shifted by 1 in the latter case). An inversion in π that involves positions i and j, for j>i, corresponds to an inversion in π' involving i+1 and j+1; in addition, inversions involving j, for some j< i, and position k correspond to inversions in π' at positions j and i.

Since |π'| =|π|+1, we have that x(π') = x(π) - 1.



Recall that part of the surface F_π is a disk in a horizontal plane of ℝ^3, having S_max as its boundary. Viewing L as being contained in that plane, the surface F_π' is homeomorphic to the result of cutting F_π along the line L. Consequently, the Euler characteristic changes as χ(F_π') = χ(F_π) + 1 (there is a triangulation so that the cut is along one edge between two vertices on the boundary of the surface, cf. Figure <ref>; cutting can be seen to duplicate the edge and the two vertices). Thus, the desired equality holds for π if and only if it holds for π'. 



Since G_π' is not connected, the argument from Case 1 allows us to decompose π' as ρ⊕τ. Additionally, π' cannot have a fixed point. This implies that the length of ρ and the length of τ are at most two less than |π'|; that is, max{|ρ|, |τ|}≤ n-1. 



 §.§ Case 3.
 The diagram G_π is connected and no index with the property described in Case 2 exists.


In this case, we construct a new permutation π' with |π'| = |π|-2.  As we will see, the key observation is that all of the line segments occurring in the cycle diagram of this new permutation π' are also present in the cycle diagram of π, but all of those line segments in G_π corresponding to the outermost Seifert circle have been removed.  Furthermore, we will see that π' has the property that x(π')=-χ(F_π') if and only if x(π)=-χ(F_π).  

Some preliminaries are needed in order to define π' and prove that it has the desired property. First, as in Case 2, the connected diagram G_π has a unique maximal Seifert circle S_max. To define π' we need first to identify the columns in the diagram where S_max has vertical line segments. These columns will necessarily be indexed by 1, n, and every column in which G_π has a crossing that creates a part of the Seifert circle S_max. 
Say that there are a such crossings that are above the diagonal and b such crossings that are below the diagonal.

Write i_1 < i_2 < ⋯ < i_a for those columns where S_max has a crossing above the diagonal. On the other side, write j_1 > j_2 > ⋯ > j_b be the columns where S_max has a crossing below the diagonal, written in decreasing order. Finally, define i_0 = 1 = j_b+1 and i_a+1=n=j_0.  

Notice, by the hypothesis of Case 3 that no index with the property described in Case 2 exists, it is necessary that the outermost Seifert circle S_max touches the main diagonal only at (1,1) and (n,n), and so every vertical line segment of S_max is in one of the columns indexed above.    Thus, it must be that π_i_a = n and π_j_b = 1. 




Now, we define an intermediate permutation π̅= π∘ (i_a  i_a-1⋯  i_1 1 j_b  j_b-1⋯ j_1 n), using cycle notation.  Alternatively, the construction of π̅ can be made as follows. Beginning from the one-line notation π=π_1π_2…π_n: move π_1 into position i_1, then move π_i_1 into position i_2. Continue this way until moving π_i_a=n into position i_a+1=n. Next, move π_n = π_j_0 into position j_1, move π_j_1 into position j_2, and so on. Finally, move π_j_b=1 into position j_b+1=1. No change is made to other elements in the one-line notation; the resulting permutation is π̅.

The one-line notation π̅= π̅_1π̅_2…π̅_n is the following. 

    π̅_ℓ = π_i_k-1   if ℓ = i_k for some 1≤ k≤ a+1
    π_j_k-1   if ℓ = j_k for some 1≤ k≤ b+1
    π_ℓ   otherwise.

Note that |π̅| = |π| and that π̅ fixes both 1 and n. The permutation π', used in the induction, is the permutation such that π̅= id_1 ⊕π' ⊕id_1 (where id_1 is the identity permutation on one element), and can be obtained from π̅ by setting π'_k = π̅_k+1-1 for 1≤ k≤ n-2.  
Note, the link type of L_π' is generally different than the link type of L_π. 

As mentioned above,  
we have the following relationship between the Seifert circles of G_π and those of G_π', the verification of which is left to the reader.

The diagram G_π' is the result of removing S_max from G_π (after only smoothing the crossings on S_max).


Setting c = a+b, so that c is the number of crossings of G_π on S_max, we see that G_π' has exactly c fewer crossings than G_π. It also has exactly one less upper right corner, the one from S_max. Since -χ(F_π) may be determined (<ref>) as the number of crossings of G_π minus the number of upper right corners of G_π (and likewise for π'), we get that 
    -χ(F_π) + χ(F_π') = c - 1.


We may finish Case 3, and so complete the proof of Theorem <ref>, by showing that x(π) - x(π') = c-1. The remainder of the paper is devoted to doing just this, with the bulk of that effort focused on understanding how inversions in π compare to those in π'.

To begin, we consider certain sets of pairs of elements from π. Given 0≤ k ≤ a, define A_k = {(π_ℓ, π_i_k) : i_k<ℓ<i_k+1}. Given 0≤ k ≤ b, define B_k = {(π_j_k, π̅_ℓ) : j_k+1<ℓ<j_k}, with the one exception that the pair (π_n, n) is also in B_0 (i.e., noting that j_0 = n = π̅_n, make the upper bound on ℓ be a weak upper bound for k=0). Finally, define 
    A = ⋃_k=0^aA_k;     B =⋃_k=0^bB_k.


Regarding the definition of B_k note that if j_k+1 < ℓ < j_k, with ℓ i_k' for any k', then π̅_ℓ = π_ℓ. If it is the case that ℓ = i_k' for some 1≤ k'≤ a then π̅_ℓ = π_i_k'-1. 



Every ordered pair (p,q) ∈  A∪ B is an inversion in π.

 Let k and ℓ be such that 0≤ k≤ a and i_k < ℓ < i_k+1. In the case that k=a, π_i_k = n, and so it is clear that (π_ℓ, π_i_k) is an inversion in π.

Now, for k with 0≤ k< a, there is a crossing of G_π in the crossings corresponding to S_max at grid coordinates (i_k+1, π_i_k). If it were the case that 
π_i_k < π_ℓ for some ℓ with i_k < ℓ < i_k+1 then the vertical line segment extending from index ℓ would create a crossing at coordinates (ℓ,π_i_k). But then a Seifert circle corresponding to this crossing would contain a part of S_max in its interior, which contradicts S_max being maximal. Therefore, every pair in A is an inversion in π.

The pair (π_n, n) ∈ B_0 is an inversion in π, as G_π being connected requires that π_n < n, and (π_n, n) = (π_n, π_i_a).  Now, suppose that ℓ is such that, for some 0≤ k≤ b we have j_k+1 < ℓ < j_k and that ℓ i_k' for all 1≤ k'≤ a.  Since π̅_ℓ = π_ℓ in this case, a pair (π_j_k,π̅_ℓ)∈ B is equal to (π_j_k, π_ℓ). That this is an inversion in π follows from an analogous argument to the previous one for pairs in A. 

Finally, suppose for some 0≤ k≤ b there exists such a k', so that j_k+1 < i_k' < j_k. Recall that π_i_k'-1=π̅_i_k'. We must have that π̅_i_k' > i_k' since there is a crossing above the diagonal at coordinates (i_k', π_i_k'-1). Additionally, considering the crossing corresponding to column j_k+1, which is below the diagonal (or, that π_j_b=1=j_b+1), we have π_j_k≤ j_k+1. Hence, π_j_k≤ j_k+1 < i_k' < π_i_k'-1.  Since i_k'-1< i_k' < j_k, we see that (π_j_k, π̅_i_k') = (π_j_k, π_i_k'-1) is an inversion in π.



The definition of the sets B_k, particularly the use of pairs having the form (π_j_k, π̅_ℓ) for j_k+1<ℓ<j_k, rather than the form (π_j_k, π_ℓ), is convenient. On the one hand, it ensures that we find certain inversions of π in A∪ B – namely, pairs (π_j_k, π_i_k'-1) with j_k+1 < i_k' < j_k that may exist. In addition, the definition helps by making A and B disjoint.


    Let 0≤ k≤ a and 0≤ k'≤ b. Then A_k ∩ B_k' = ∅.


    Fix 0≤ k≤ a and 0≤ k'≤ b and suppose (p,q) ∈ A_k ∩ B_k'. We have p = π_j_k' and q = π_i_k. By the definition of A_k, we have i_k < j_k' < i_k+1 (preventing k' from being 0). In addition, q = π̅_ℓ for some j_k'+1 < ℓ < j_k'. However, q = π_i_k= π̅_i_k+1, and so ℓ =  i_k+1, a contradiction. And so A_k ∩ B_k' = ∅.

We note that, from their definition, it is clear that the sets A_k, 0≤ k≤ a are themselves pairwise disjoint; as are the sets B_k, k=0,1,…,b.


  Fix p,q with 1≤ p < q ≤ |π|. Then the relative position of p and q in π is different than the relative position of p and q in π̅ if and only if
	
    (p,q) ∈ A∪ B.


Note that just as p < q in the statement, the definitions of A_k and B_k are such that ordered pairs in these sets have a first coordinate that is less than the second coordinate.


We have already observed that each (p,q)∈ A∪ B is an inversion in π, meaning that q appears to the left of p in π. If (p,q) ∈ B_k for some k, with q=π̅_ℓ for some j_k+1<ℓ<j_k, then q appears to the right of p=π_j_k in π̅ since π̅_j_k+1=π_j_k. Now, if (p,q)∈ A_k for some 0≤ k≤ a, then π_i_k appears in position i_k+1 in π̅. Letting ℓ be such that i_k < ℓ < i_k+1, then π_ℓ will either appear in position ℓ in π̅ or it will appear in a position that is farther left (when ℓ = j_k', since j_k'+1 < j_k'). 

In both cases, q = π_i_k appears to the right of p=π_ℓ in π̅.  Thus, we may conclude that the relative position of p and q does change if (p,q) ∈ A∪ B.

Suppose that p < q are elements such that the relative position of p and q in π is different than their relative position in π̅. It must be that one of p and q, at least, has position in π that is in {i_0,i_1,…,i_a}∪{j_0,j_1,…,j_b}  (since elements in other positions in π_1π_2…π_n do not change their position). 

In the first case, let x = π_i_k for some 0≤ k≤ a, and that x equals one of p, q. Let y be the other element of {p,q}. Considering the construction of π̅, x appears in π̅ farther to the right than its position in π. For the relative position of x and y to change, y cannot be in position i_k' for some 0≤ k'≤ a, since π_i_k and π_i_k' have the same relative position in π and π̅. Hence, y must appear in π̅ farther to the left than it appears in π, or in the same position as in π.
As a consequence, in π we have y appearing to the right of x; moreover, its position is either left of i_k+1 or equal to j_k' where j_k'+1 < i_k+1≤ j_k' (the weak inequality needed when k'=0). In the first case, Lemma <ref> and the fact that p < q together imply that q = x = π_i_k and p = π_ℓ for some i_k<ℓ<i_k+1; we find that (p,q) ∈ A. In the second case we have that j_k'+1 < i_k+1≤ j_k' and x = π_i_k = π̅_i_k+1. By Lemma <ref> (which implies that π_j_k' < π̅_i_k+1), it must be that x = q and we conclude that (p,q) ∈ B.

The remaining case is that one of p,q is equal to π_j_k for some 0≤ k≤ b, and that the other is π_ℓ for some ℓ, and is such that π_ℓ=π̅_ℓ.  Since the relative position of p, q is different in π̅ compared to in π, and π_j_k=π̅_j_k+1, it must be that j_k+1 < ℓ < j_k. As shown in Lemma <ref>, we must have π_j_k < π_ℓ, so p = π_j_k and q = π_ℓ = π̅_ℓ. And so (p, q) ∈ B, concluding the proof of the lemma.



Let (p,q) be an ordered pair with p<q. By combining Lemma <ref> and Lemma <ref>, if (p,q) is not an inversion in π then it cannot be an inversion in π̅. We see that the cardinality of A∪ B equals I(π) - I(π̅).

Let c = a+b be the number of crossings in S_max. Using Lemma <ref> we have

    I(π) - I(π̅)      = ∑_k=0^a|A_k| + ∑_k=0^b|B_k| 
       = ∑_k=0^a(i_k+1 - i_k - 1) + (j_0 - j_1) + ∑_k=1^b(j_k - j_k+1 - 1) 
       = (i_a+1 - i_0) + (j_0 - j_b+1) - (c+1)  
       = 2n-3 - c,

the last equation since i_a+1 = n = j_0, j_b+1 = 1 = i_0.


The total displacement of the permutation changes as follows. For each i_k, 1≤ k≤ a, recall π̅_i_k = π_i_k-1. Since π_i_k-1 < π_i_k and also i_k is less than both π_i_k and π_i_k-1, we have |π_i_k - i_k| - |π̅_i_k - i_k| = π_i_k - π_i_k-1. In addition, |π_i_0 - i_0| - |π̅_i_0 - i_0| = π_i_0 - 1, since π̅_i_0 = i_0=1. 

Similarly, we have |j_k - π_j_k| - |j_k - π̅_j_k| = π_j_k-1 - π_j_k for each 1≤ k≤ b, and we have |π_j_0 - j_0| - |π̅_j_0 - j_0| = n - π_n. Putting this together,

    D(π) - D(π̅) = π_i_a - 1 + n - π_j_b = 2(n - 1).

Recall the permutation π', defined so that π̅= id_1 ⊕π' ⊕id_1. It is clear that D(π̅) = D(π'), I(π̅) = I(π'), and |π̅| - |π'| = 2. Therefore,

    x(π) - x(π') = 2(n-1) - (2n-3 - c) - 2 = c - 1,

proving what was needed for the induction step in Case 3.

amsplain


