If Alice and Bob each take a walk, a random one, what is the chance they will meet? If n
people walk randomly in Manhattan from the Upper East Side going south or west, how often
will two of them meet until they reach the Hudson? If they do not want to see each other more
than once, in what relative order will they most likely arrive at the Hudson shore? If we make
a rhombus like an Aztec diamond from 2 × 1 dominoes, what would it most likely look like? If
water molecules arrange themselves on a square grid, what angles between the hydrogen atoms
will be formed near the boundaries? And if ribosomes are transcribing the mRNA, how do they
hop between the sites (codons)?

The answers to the above questions are all intertwined, bridging algebra with probability,
integrability with stochasticity, random tilings with random permutations, as revealed in the
recent work1[MPPY24].

Figure 1. (a) a pipe dream of the permutation w = 241653, (b) a permuton in the shape of
an ice cream, (c) an example of a layered permutation, (d) illustration of the corresponding
configuration in the 6-vertex model lying inside the frozen region.

The story started with a problem of Richard Stanley from 2017 – what is the (asymptotically)
maximal value of a principal specialization of a Schubert polynomial. Schubert polynomials \(Sw\) in
n variables, indexed by permutations \(w\in S_n\), present cohomology classes of the flag variety and
are central objects of study at the intersection of Algebraic Combinatorics and Algebraic Geometry.
However, the problem can be stated as a simple tiling model: let us tile the triangle in the
square grid given by i+j ≤ n+1, i, j = 1, . . . , n, with crosses or elbows (see Figure 1 (a)), which
form a network of lines aka “pipe dreams”. Moreover, impose a special noncrossing condition that
no two pipes can cross more than once. The configuration in Figure 1 (a) satisfies the noncrossing
condition, and counting those is a statistical mechanics problem involving long-range interactions.
It is notoriously difficult to study, we do not even know that the number of such configurations
asymptotically grows as \(2^{c n^2}\) for some c. Curiously, the bounds on the upper and lower limits
we have so far give c ∈ [0.29, 0.37]. The lower bound comes from a specific construction with
so-called layered permutations, where explicit product formulas give the count. The upper bound
follows by embedding noncrossing pipe configurations into the so-called “reduced bumpless pipe
dreams”, a particular subset of the Alternating Sign Matrices (known in statistical mechanics as
square ice with domain-wall boundary conditions and uniform weights; it is a particular case of
the Six-Vertex model).

In our quest to resolve Stanley’s problem, we explored the generalization of Schubert polynomials,
the Grothendieck polynomials \(\mathfrak{G}_w^\beta\), which capture the K-theory of the flag variety. They
can also be studied as partition functions (generating functions) of the pipe dreams described
above, except that each double and further intersection is “penalized” by the factors \(\beta\). When
\(\beta\) = 0, we recover the Schubert polynomials; when \(\beta\) = 1, the model corresponds to pipe dreams
that bounce off each other after the first intersection. For which permutations is \(\mathfrak{G}_w^\beta(1,\ldots,1)\)
maximal? What is the asymptotic behavior of the number of \(\beta\)-weighted pipe dreams?

When \(\beta\) = 1, finding the asymptotically maximal value is easy by counting the number of
tilings (pipe dreams) without constraints. There are \(2^{\binom{n}{2}}\) such tilings (two choices of each of
the \(\binom{n}{2}\) tiles) distributed among \(n!\sim e^{n \log(n) }\) permutations. Thus, the maximal value is still
around \(2^{n^2/2  -o(n^2) }\). But what is the maximal permutation? What does a typical permutation
look like? To answer the second question, we realized that the trajectories (pipes) are in bijection
with histories of hopping particles in the Totally Asymmetric Simple Exclusion Process (TASEP),
initially developed in 1968 to understand RNA translation:

Analyzing the behavior of hopping particles utilizes Integrable Probability. That is, we express
certain observables of the particle system via Schur functions (a central object in Algebraic
Combinatorics), then turn to analysis and probability to extract asymptotics of the observables
via contour integrals. This produces a very interesting permuton (a continuous version of a
permutation matrix) in the shape of an... ice cream cone with one scoop. See Figure 1 (b).

So what about layered permutations, which give large Schubert polynomials? In the Grothendieck
model, they are also close to maximal (see Figure 1 (c)). In this case, there are no product
formulas, so how do we compute the values and maximize them? The Grothendieck model can
also be related to the Six-Vertex model. For \(\beta\) = 1, it corresponds to the 2-enumeration of
Alternating Sign Matrices, which are in 2-1 correspondence with domino tilings of the Aztec
diamond. A layered permutation has its last part reversed, making it a frozen region of the
2-ASM/Aztec diamond. The existence of the frozen boundary of the Aztec diamond was one of
the early feats at the intersection of combinatorics with statistical mechanics from 1996. So when
our layered permutation has the last layer close to the tangent to the arctic circle, the number of
configurations is still asymptotically maximal, that is, \(2^{n^2/2}\). See Figure 1 (d).

References:
[MPPY24] Alejandro H. Morales, Greta Panova, Leonid Petrov, and Damir Yeliussizov, Grothendieck Shenanigans:
Permutons from Pipe Dreams via Integrable Probability, arXiv preprint (2024). arXiv:2407.21653
[math.PR].