On distribution of the depth index on perfect matchings

This paper investigates the depth index statistic on perfect matchings by providing a new combinatorial description and calculating its generating polynomial, ultimately proving that this statistic is equidistributed with the rank function of the Bruhat order.

The Gist

Imagine you have a group of $2n$people standing in a single line, numbered from 1 to$2n$. Your job is to pair them all up so that everyone has exactly one partner. In math, this is called a perfect matching.

You can visualize this by drawing an arch (or a bridge) over the heads of every pair. If person 1 is paired with person 4, you draw an arch from 1 to 4. If person 2 is paired with 3, you draw a smaller arch between them.

Now, imagine these arches are made of rubber bands. Sometimes, the rubber bands might cross over each other. Sometimes, one rubber band might sit completely "inside" another (like a nesting doll). Sometimes, they just sit side-by-side without touching.

The Two Ways to Count "Messiness"

The paper explores two different ways to measure how "tangled" or "messy" a specific arrangement of these pairs is.

1. The "Intertwining Number" (The Tangle Count)
This is the main character of the story. Imagine you extend the rubber bands infinitely to the left and right (like infinite strings going off the edge of the page). The "intertwining number" counts how many times these lines cross each other.

• Analogy: Think of a bowl of spaghetti. The intertwining number is how many times the strands of pasta cross over one another. The more crossings, the more "intertwined" the mess is.

2. The "Depth Index" (The Stack Height)
This is a different way to measure the mess. Instead of counting crossings, you look at how many arches are "sitting on top" of a specific person or a specific arch.

• Analogy: Imagine the arches are layers of a cake or shelves in a library. The "depth" of a person is how many shelves are stacked above their head. The "depth index" is the total sum of all these layers across the whole line.

The Big Discovery: A Hidden Connection

The authors, Yonah and Yuval, discovered a beautiful secret relationship between these two ways of counting.

In the world of set partitions (where groups can have more than 2 people), these two numbers are related by a simple rule: If you add the "Tangle Count" and the "Stack Height" together, you always get the same total number. It's like a seesaw: if the tangle goes up, the stack height goes down, but the total weight stays the same.

However, the paper focuses specifically on perfect matchings (pairs only). Here, the relationship is even more fascinating.

The authors proved that the distribution of the "Tangle Count" (Intertwining Number) is essentially the same as the distribution of the "Stack Height" (Depth Index), just shifted by a constant amount.

The "Magic Mirror" Analogy:
Imagine you have a room full of people arranging their pairs in every possible way.

• If you look at the room through a "Tangle Mirror," you see a specific pattern of how messy the arrangements are.
• If you look at the same room through a "Stack Height Mirror," you see a different pattern.
• The Surprise: The authors found that these two patterns are actually the same shape, just rotated or flipped. If you take the "Tangle" pattern and flip it upside down (mathematically, this involves a specific transformation), it matches the "Stack Height" pattern perfectly.

Why Does This Matter?

In the world of advanced mathematics (specifically something called "Bruhat order" on symmetric groups), there is a concept called "Rank" or "Length." This is a measure of how far a specific arrangement is from being the "perfectly ordered" state.

The paper shows that the Intertwining Number (our Tangle Count) is mathematically equivalent to this Rank.

The "Elevator" Metaphor:
Think of the "Rank" as the floor number in a skyscraper.

• The "perfectly ordered" pairs are on the ground floor (Rank 0).
• The most chaotic, crossed-up pairs are on the top floor.
• The authors proved that the "Intertwining Number" is just a different way of counting which floor you are on. If you know the tangle count, you know exactly which "floor" of mathematical complexity you are standing on.

The Final Result: A Formula for the Chaos

The paper concludes with a specific formula (a generating function) that tells you exactly how many ways you can arrange $2n$ people to get a specific level of "tangle."

It turns out this formula is a famous mathematical object known as the q-double factorial.

• Simple takeaway: The paper provides a precise recipe to calculate the probability of finding a certain amount of "tangle" in a random pairing of people. It connects a visual, geometric problem (crossing lines) with a deep algebraic structure (symmetric groups and ranks).

Summary in One Sentence

The paper proves that counting how many times your rubber band arches cross each other is mathematically the same as measuring the "rank" or "complexity" of that arrangement in a grand mathematical hierarchy, revealing a hidden symmetry between geometry and algebra.

Technical Summary

Here is a detailed technical summary of the paper "The Distribution of the Intertwining Number on Perfect Matchings" by Yonah Cherniavsky and Yuval Khachatryan-Raziel.

1. Problem Statement

The paper investigates the combinatorial distribution of the intertwining number ($i(\pi)$) on the set of perfect matchings ($PM_{2n}$) of the set $[2n] = \{1, 2, \dots, 2n\}$.

• Context: The intertwining number was originally defined by Ehrenborg and Readdy for general set partitions. It counts the number of crossings in an "extended arc diagram" of a partition.
• Specific Object: A perfect matching is a set partition where every block has exactly two elements. These can be viewed as fixed-point-free involutions in the symmetric group $S_{2n}$.
• Goal: The authors aim to derive an explicit generating function for the intertwining number on $PM_{2n}$ and establish its relationship with the rank function (length function) of the strong Bruhat order on fixed-point-free involutions.

2. Methodology

The authors employ a combination of combinatorial definitions, geometric interpretations via arc diagrams, and algebraic manipulation of generating functions.

A. Definitions and Representations

• Arc Diagrams: The authors utilize standard and extended arc diagrams. In the extended version, half-arcs connect $-\infty$ to "openers" (minimal elements of blocks) and "closers" (maximal elements) to $+\infty$.
• Statistics Defined:
  • Intertwining Number ($i(\pi)$): The number of crossings in the extended arc diagram.
  • Depth-Index ($t(\pi)$): A statistic related to the "depth" of vertices and arcs (number of arcs above them).
  • Bruhat Length ($\ell(\pi)$): The length function of the strong Bruhat order on fixed-point-free involutions, previously studied by Deodhar and Srinivasan.
  • Local Configurations: Pairs of arcs are classified as crossings ($cr$), nestings ($ne$), or alignments ($al$).

B. Key Theoretical Tools

1. Fundamental Identity: The paper relies on a known identity from previous work [3] stating that for any set partition $\pi \in \Pi_n$:
   $$t(\pi) + i(\pi) = \binom{n}{2}$$
   This links the intertwining number directly to the depth-index.
2. Decomposition of Statistics: The authors express the depth-index and the Bruhat length in terms of local arc configurations ($cr, ne, al$) and the total vertex depth ($tvd$).
   • They prove that $\ell(\pi) = cr(\pi) + 2ne(\pi)$.
   • They derive an expression for $t(\pi)$ involving $cr, ne, al$, and $tvd$.
3. Involution Argument: The authors utilize a known involution $\phi: PM_{2n} \to PM_{2n}$ (from [6]) that preserves the number of alignments ($al$) but swaps the number of crossings and nestings ($cr \leftrightarrow ne$).
4. Palindromic Polynomials: They use the property that the generating polynomial for the Bruhat length, $[2n-1]_q!!$, is palindromic. This allows them to relate the distribution of a statistic to its "complement" via the transformation $q \to 1/q$.

3. Key Contributions and Results

A. Distribution of the Depth-Index

The authors first establish the generating function for the depth-index ($t(\pi)$) on perfect matchings.

• Theorem 3.1: The generating polynomial for the depth-index is:
  $$TPM_{2n}(q) = \sum_{\pi \in PM_{2n}} q^{t(\pi)} = q^{\binom{n+1}{2}} [2n-1]_q!!$$
  where $[2n-1]_q!!$ is the $q$-analogue of the double factorial.
• Implication: This proves that the depth-index $t(\pi)$ is equidistributed with the statistic $\binom{n+1}{2} + \ell(\pi)$, where $\ell(\pi)$ is the Bruhat length.

B. Main Result: Distribution of the Intertwining Number

Using the identity $i(\pi) = \binom{2n}{2} - t(\pi)$ and the result for the depth-index, the authors derive the main theorem.

• Theorem 3.15: The generating polynomial for the intertwining number on perfect matchings is:
  $$IPM_{2n}(q) = \sum_{\pi \in PM_{2n}} q^{i(\pi)} = q^{\binom{n}{2}} [2n-1]_q!!$$
  where $[2n-1]_q!! = \prod_{i=1}^n \frac{1-q^{2i-1}}{1-q}$.

C. Equidistribution with Bruhat Rank

The paper demonstrates that the intertwining number on perfect matchings is essentially equidistributed with the rank function of the strong Bruhat order on fixed-point-free involutions. Specifically, the distribution of $i(\pi)$ is a shifted version of the distribution of $\ell(\pi)$.

4. Significance

• Combinatorial Unification: The paper bridges the gap between the combinatorial statistics of set partitions (intertwining number) and the algebraic structure of the symmetric group (Bruhat order on involutions).
• Explicit Generating Function: It provides a closed-form $q$-analogue for the distribution of the intertwining number, a parameter that had previously been less understood in the specific context of perfect matchings.
• Geometric Interpretation: By linking the depth-index to the dimension of matrix varieties and the Bruhat order, the results offer a geometric perspective on the combinatorics of perfect matchings.
• Methodological Insight: The proof elegantly combines local arc configurations (crossings/nestings) with global symmetries (involutions and palindromic polynomials) to solve the distribution problem.

In summary, the paper resolves the distribution of the intertwining number on perfect matchings, showing it follows a specific $q$-double factorial pattern shifted by a quadratic term, thereby connecting it deeply to the structure of the strong Bruhat order.