2.1 Background on posets

For further reference, see [Reference Stanley11].

Let $P$ be a poset. A subposet of $P$ is a subset $P' \subset P$ equipped with a partial order $\leq '$ , such that for any $x, y \in P'$ , we have that $x \leq ' y$ in $P'$ if and only if $x \leq y$ in $P$ . For any $x, y \in P$ , we say that $x$ covers $y$ (which we denote using $x \gtrdot y$ ) if $x \gt y$ and there does not exist a $z \in P$ such that $x \gt z \gt y$ . The Hasse diagram of a poset $P$ is a drawing where the vertices are the elements of $P$ , and for any two $x, y \in P$ , if $x \gtrdot y$ , then the corresponding vertex of $x$ is connected to the corresponding vertex of $y$ via an edge where $x$ is drawn higher (vertically) than $y$ . Now, a chain of $P$ is a subset $\mathcal{C} \subset P$ such that all its elements are comparable; such a chain is maximal if there does not exist another chain $\mathcal{C}'$ for which $\mathcal{C} \subsetneq \mathcal{C}'$ . The length of such a chain $\mathcal{C}$ is $|\mathcal{C}| - 1$ . Finally, a finite lattice is graded if all of its maximal chains are of the same length.

2.2 Probabilistic background

In this section we will prove two useful probability lemmas that will be used in the proofs of Theorems 1.3 and 1.6. These two lemmas will both follow from standard applications of well-known results in statistics (e.g., the Markov bound, Chernoff bounds, random walk theory).

2.2.1 Sum of geometric variables

Throughout the proof of Theorem 1.6, we will often use the following tail bounds on a sum of independent geometric random variables. Here we use the convention that a geometric random variable with parameter $p$ is a random variable $X$ which satisfies that for all positive integers $k$ , $\mathbb{P}(X = k) = (1-p)^{k-1}p$ .

Lemma 2.1. Fix a $p \in (0, 1]$ . Let $G_1, G_2, \ldots , G_k$ be independent geometric random variables with parameter $p$ . Then for all $t \gt 0$ , we have that

$$ \begin{align*} \mathbb{P}\Bigg (\!\sum _{i=1}^k G_i \gt \frac {k}{p} + t\sqrt {\frac {k}{p^3}} \Bigg ) \leq e^{-\frac {t^2}{2p + 2t\sqrt {p/k}}} \quad \text {and} \quad \mathbb{P}\Bigg (\!\sum _{i=1}^k G_i \lt \frac {k}{p} - t\sqrt {\frac {k}{p^3}} \Bigg ) \leq e^{-\frac {t^2}{2p - t\sqrt {p/k}}}. \end{align*}$$

Proof. We only prove the first bound, as the proof for the other bound is analogous. Extend $G_1, G_2, \thinspace \ldots$ to an infinite sequence. Let

$$ \begin{align*} B_i &= \begin{cases} 1 & i = \sum _{j = 1}^m G_j \text{ for some }m \\[2pt] 0 & \text{else.} \end{cases} \end{align*}$$

Then evidently each $B_i$ is given by an independent Bernoulli variable with parameter $p$ (i.e. $\mathbb{P}(B_i = 1) = p$ ). Let $\mu = k + t\sqrt {k/p}$ and $\delta = \frac {t/\sqrt {kp}}{1 + t/\sqrt {kp}}$ ; note that $(1 - \delta )\mu = k$ . We thus have that by a multiplicative Chernoff bound,

$$ \begin{align*} \mathbb{P}\Bigg (\!\sum _{i=1}^k G_i \gt \frac {k}{p} + t\sqrt {\frac {k}{p^3}} \Bigg ) = \mathbb{P}\Bigg (\!\sum _{i=1}^{ \lfloor k/p + t\sqrt {k/p^3} \rfloor } B_i \lt k \Bigg ) \leq e^{-\delta ^2 \mu /2} = e^{-\frac {t^2}{2p + 2t\sqrt {p/k}}}, \end{align*}$$

as desired.

2.2.2 Simple random walks

Consider an infinite sequence $X_1, X_2, \ldots$ of independent and identically distributed (i.i.d.) random variables in $\mathbb{Z}$ , where

$$ \begin{align*} X_i &= \begin{cases} 1 & \text{with probability }\frac {1}{2} \\[3pt] -1 & \text{with probability }\frac {1}{2}. \end{cases} \\[-15pt] \end{align*}$$

The simple random walk on $\mathbb{Z}$ is the random process given by the infinite sequence of random variables $S_1, S_2, \thinspace \ldots$ where $S_n = X_1 + \cdots + X_n$ . The hitting time of any nonzero integer $m$ is the random variable $\tau _m$ , denoting the smallest positive integer $t$ for which $S_t = m$ . Note that $\tau _m$ is a sum of $m$ i.i.d. copies of $\tau _1$ for all positive integers $m$ (and by symmetry, $\tau _m = \tau _{-m}$ ). Now, it is well-known that the generating function $\mathbb{E}[z^{\tau _1}]$ of $\tau _1$ satisfies

$$ \begin{align*} \mathbb{E}[z^{\tau _1}] = \sum _{i=0}^{\infty } \mathbb{P}(\tau _1 = n)z^n &= \frac {1 - \sqrt {1-z^2}}{z} \\[3pt] &= \sum _{n=0}^{\infty } (\!-1)^n\binom {1/2}{n+1}z^{2n+1}. \end{align*}$$

In particular, by elementary calculus we may find that $(\!-1)^n\binom {1/2}{n+1} = \Theta (n^{-3/2})$ . Using the information above, we may derive the following bound.

Lemma 2.2. There exists an absolute constant $c_2\leq \frac {1}{2}$ such that for all positive integers $n$ ,

$$ \begin{align*} \mathbb{P}\big(\tau _m \geq n^2\big) &\geq 1 - e^{-c_2m/n}. \end{align*}$$

Proof. By the above, we have that there exists an absolute constant $c_3$ such that for all positive integers $n$ ,

$$ \begin{align*} \mathbb{P}(\tau _1 = 2n - 1) &\geq c_3n^{-3/2}. \end{align*}$$

Thus, there exists an absolute constant $c_2 \leq \frac {1}{2}$ such that for all positive integers $n$ ,

$$ \begin{align*} \mathbb{P}\big(\tau _1 \geq n^2\big) &\geq \frac {c_2}{n}. \end{align*}$$

Using the inequality $1 - x \leq e^{-x}$ (which holds for all $x \in [0, 1]$ ), we find that for all positive integers $n$ ,

$$ \begin{align*} \mathbb{P}\big(\tau _1 \lt n^2\big) \leq 1 - \frac {c_2}{n} \leq e^{-c_2/n}. \end{align*}$$

Now, recall that $\tau _m$ may be viewed as a sum of $m$ i.i.d. copies of $\tau _1$ . Thus we have that

$$ \begin{align*} \mathbb{P}\big(\tau _m \lt n^2\big) \leq \mathbb{P}\big(\tau _1 \lt n^2\big)^m \leq e^{-c_2m/n}, \end{align*}$$

and thus

$$ \begin{align*} \mathbb{P}\big(\tau _m \geq n^2\big) &\geq 1 - e^{-c_2m/n} \end{align*}$$

as desired.

Now, fix some parameter $q \in (0, 1/2)$ . Consider an infinite sequence $Y_1, Y_2, \ldots$ of i.i.d. random variables in $\mathbb{Z}$ , where

$$ \begin{align*} Y_i &= \begin{cases} 1 & \text{with probability }q \\[3pt] 0 & \text{with probability }1 - 2q \\[3pt] -1 & \text{with probability }q. \end{cases} \end{align*}$$

The lazy simple random walk on $\mathbb{Z}$ with parameter $q$ is the random process given by the infinite sequence of random variables $T_1, T_2, \thinspace \ldots$ where $T_n = Y_1 + \cdots + Y_n$ . We may again define the hitting time of any nonzero integer $m$ as the random variable $\tau '_m$ denoting the smallest positive integer $t$ for which $T_t = m$ . The following corollary will be useful in the proof of Theorem 1.6.

Corollary 2.3. Let $c_2$ be the absolute constant used in the statement of Lemma 2.2. Then for all positive integers $m$ and integers $n \gt 1$ ,

$$ \begin{align*} \mathbb{P}\big(\tau '_m \geq n^2\big) &\geq 1 - e^{-c_2m/n}. \end{align*}$$

Proof. Let $\tau ^\ast _m$ be the number of indices $i$ between $1$ and $\tau '_m$ inclusive for which $Y_i \neq 0$ . Then evidently $\tau ^\ast _m \leq \tau '_m$ , and moreover $\tau ^\ast _m$ shares the same distribution as $\tau _m$ (as $\tau ^\ast _m$ considers only the nonzero $Y_i$ when calculating the hitting time). Hence, we have that

$$ \begin{align*} \mathbb{P}\big(\tau '_m \geq n^2\big) \geq \mathbb{P}\big(\tau ^\ast _m &\geq n^2\big) \geq 1 - e^{-c_2m/n}, \end{align*}$$

as desired.

2.3 Ungarian Markov chains on posets of order ideals

Given any lattice $L$ and element $x \in L$ , let the random variable $T_L(x)$ denote the number of steps elapsed in the Ungarian Markov chain $\textbf {U}_L$ of $L$ until $x$ has transitioned into $\hat {0}$ . Define $T_L \,:\!=\, T_L(\hat {1})$ and $\mathcal{E}_L(x) \,:\!=\, \mathbb{E}(T_L(x))$ . By definition, $\mathcal{E}_L(\hat {1}) = \mathcal{E}_p(L)$ .

Consider any poset $P$ . An order ideal of $P$ is a subset $I \subset P$ such that for any $x, y \in P$ satisfying $x \geq y$ , we have that $x \in I$ implies $y \in I$ . Establish a partial order on the order ideals of $P$ by stating that $I \leq J$ if $I \subset J$ ; under this partial order, the order ideals of a poset $P$ form a (distributive) lattice, which we will denote as $J(P)$ .

Consider any order ideal $I$ of a poset $P$ . Evidently ${\text {cov}}_{J(P)}(I)$ is precisely the set of order ideals $J$ that are obtained by removing a maximal element of $I$ . Hence the Ungarian Markov chain $\textbf {U}_{J(P)}$ is stochastically equivalent to the Markov chain with state space $J(P)$ which on each step, given any $I \in J(P)$ , deletes a randomly selected subset of the maximal elements of $I$ .

Now, fix a parameter $p$ and a poset $P$ . Simulate $\textbf {U}_{J(P)}$ with parameter $p$ , starting with the order ideal $I = P$ . For any nonnegative integer $k$ , let $I_k$ denote the order ideal which we obtain after $k$ steps. For any $x \in P$ , let the random variable $G_x$ denote the number of nonnegative integers $k$ such that $x$ is a maximal element of $I_k$ ; observe that the random variables $G_x$ are independent and all stochastically equivalent to a geometric random variable with parameter $p$ . Now, define ${\text {MC}}(P)$ to be the set of maximal chains of $P$ . By considering the last element $x_1 \in P$ to be removed from the order ideal, then the last element $x_2$ among those covering $x_1$ to be removed from the order ideal, and so on, we may iteratively construct a (maximal) chain $C \in {\text {MC}}(P)$ satisfying $T(J(P)) = \sum _{x \in C} G_x$ . Thus we always have

$$ \begin{align*} T(J(P)) &= \max _{C \in {\text {MC}}(P)}\sum _{x \in C} G_x. \end{align*}$$

This interpretation reformulates the Ungarian Markov chain $\textbf {U}_{J(P)}$ as a variant of the well-studied last-passage percolation with geometric weights random process. In particular, under this formulation we readily retrieve the following corollary.

Corollary 2.4. For any order ideal $J' \in J(P)$ and any $t \geq 0$ , we have that

$$ \begin{align*} \mathbb{P}(T_{J(P)}(J') \geq t) \leq \mathbb{P}(T(J(P)) \geq t). \end{align*}$$

Proof. Interpret $J' \in J(P)$ as an order ideal $P'$ of $P$ . Then evidently the subposet $\{x \in J(P) \colon x \leq J'\}$ of $J(P)$ is isomorphic to $J(P')$ as a poset. Now, note that every maximal chain of $P'$ is contained within a maximal chain of $P$ . Thus, by simulating the Ungarian Markov chain $\textbf {U}_{J(P)}$ using the geometric random variables $G_x$ , we find that

$$ \begin{align*} T_{J(P)}(J') &= T(J(P')) \\[3pt] &= \max _{C \in MC(P')} \sum _{x \in C} G_x \end{align*}$$

$$ \begin{align*} &\leq \max _{C \in MC(P)} \sum _{x \in C} G_x \\[3pt] &= T(J(P)). \end{align*}$$

From this, we readily obtain that for all $t \gt 0$ ,

$$ \begin{align*} \mathbb{P}(T_{J(P)}(J') \geq t) &\leq \mathbb{P}(T(J(P)) \geq t), \end{align*}$$

as desired.

Now, for any $n, m \in \mathbb{Z}^+$ , define the poset $R_{n, m}$ to be the product of a chain of length $n-1$ and a chain of length $m-1$ . Fix a parameter $p \in (0, 1)$ . Then the last-passage percolation with geometric weights random process with parameter $p$ on $R_{n, m}$ can be interpreted using the multicorner growth Totally Asymmetric Simple Exclusion Process (TASEP) with parameter $p$ as follows. The multicorner growth TASEP is a sequence of random Young diagrams $\{\lambda _k\}_{k \in \mathbb{Z}_{\geq 0}}$ , where $\lambda _0 = \varnothing$ is the empty set and $\lambda _{k+1}$ is constructed by adding in each external corner of $\lambda _k$ with independent probability $p$ . For each $k$ , let $\lambda _k' \subset \lambda _k$ be the Young sub-diagram consisting only of the first $n$ rows and $m$ columns of $\lambda _k$ . Again, simulate the Ungarian Markov chain $\textbf {U}_{J(R_{n,m})}$ starting at $R_{n, m} \in J(R_{n, m})$ , and let the random subset $I_k \subset R_{n, m}$ denote the order ideal we obtain after $k$ steps. Then by considering the Hasse diagram of $R_{n, m}$ , we may find that the complement of $I_k$ in $R_{n, m}$ may be viewed as a Young diagram, which is identically distributed (as a random Young diagram) as $\lambda _k'$ . This correspondence is illustrated more clearly in Figure 1. In particular, note that the growth of the Young diagrams $\{\lambda _k\}$ outside of the first $n$ rows and $m$ columns do not influence the growth of the Young diagrams $\{\lambda _k'\}$ , in the sense that the probability distribution of $\lambda _{k+1}'$ conditioned on $\lambda _k$ is the same as the distribution of $\lambda _{k+1}'$ conditioned on $\lambda _k'$ . Hence $T_{J(R_{m,n})}$ is precisely the smallest index $k$ such that $\lambda _k'$ is an $n \times m$ grid of squares. For more information on the multicorner growth TASEP, see [Reference Romik9, Chapters 4, 5].

Now, an important ingredient towards the proof of Theorem 1.3 will be the following convergence of the rescaled distributions of $T_{J(R_{m,n})}$ , taken from [Reference Romik9, Theorem 5.31] but originally appearing as [Reference Johansson6, Theorem 1.2].

Theorem 2.5. Consider any $0 \lt p \lt 1$ . For any $x, y \gt 0$ , define

$$ \begin{align*} \Phi _p(x, y) &= \frac {1}{p}(x + y + 2\sqrt {(1-p)xy}), \\[3pt] \eta _p(x, y) &= \frac {(1-p)^{1/6}}{p}(xy)^{-1/6}(\sqrt {x} + \sqrt {(1-p)y})^{2/3}(\sqrt {y}+\sqrt {(1-p)x})^{2/3}. \end{align*}$$

Now, let $\{m_k\}_{k=1}^{\infty }$ and $\{n_k\}_{k=1}^{\infty }$ be sequences of positive integers, satisfying that

$$ \begin{align*} \lim _{k \rightarrow \infty } m_k = &\lim _{k \rightarrow \infty } n_k = \infty , \\[3pt] 0 \lt \liminf _{k \rightarrow \infty } \frac {m_k}{n_k} &\lt \limsup _{k \rightarrow \infty } \frac {m_k}{n_k} \lt \infty . \end{align*}$$

Then we have that for all positive reals $t$ ,

$$ \begin{align*} \lim _{k \rightarrow \infty } \mathbb{P}\bigg (\frac {T(J(R_{m_k, n_k})) - \Phi _p(m_k, n_k)}{\eta _p(m_k, n_k)} \leq t \bigg ) &= F_2(t), \end{align*}$$

where $F_2(t)$ is the Tracy-Widom distribution.

The following asymptotic of $F_2(t)$ will also be useful to us.

Theorem 2.6. [Reference Baik, Buckingham and DiFranco2, Equation 25] In the $t \rightarrow +\infty$ limit, we have

$$ \begin{align*} F_2(t) = 1 - \frac {1}{32 \pi t^{3/2}}e^{-4t^{3/2}/3} \big(1 + O\big(t^{-3/2}\big)\big). \end{align*}$$

Figure 1.

An example of an order ideal of $R_{3, 4}$ and a corresponding Young diagram. The blue dots form the order ideal, while the red boxes display the Young diagram. Note that the Young diagram may extend beyond the $3 \times 4$ box of dots forming $R_{3, 4}$ , but the growth of the Young diagram in this region does not influence the evolution of the corresponding order ideal.

4.1 The sublattice of 312-avoiding permutations

The right weak order on $S_n$ is the partial order where for any permutation $\sigma$ and descent $i \in \text {Des}(\sigma)$ , the permutation $\sigma ' = \sigma \circ (i \quad i + 1 )$ is covered by $\sigma$ . It is well-known that the right weak order on $S_n$ is a lattice [Reference Björner and Brenti1]; thus from now on we will use $S_n$ to implicitly denote this lattice. Given a permutation $\sigma \in S_n$ , say a triple of indices $(i_1, i_2, i_3) \subset [n]^3$ with $i_1 \lt i_2 \lt i_3$ forms a $312$ -pattern with respect to $\sigma$ if $\sigma (i_1) \gt \sigma (i_3) \gt \sigma (i_2)$ . Call a permutation $\sigma \in S_n$ $312$ -avoiding if no triple of indices forms a $312$ -pattern with respect to $\sigma$ . Let $\text {Av}_n(312)$ denote the subset of $S_n$ consisting of the $312$ -avoiding permutations, and let $\text {Av}_n(312)$ inherit a poset structure from $S_n$ . Then as discussed in Subsection 1.1, $\text {Av}_n(312)$ is a sublattice of $S_n$ , and $\text {Av}_n(312) \cong \text {Tam}_n$ .

Now, to further describe the poset structure on $\text {Av}_n(312)$ , we will consider the following projection operator $\pi _\downarrow \,:\, S_n \rightarrow \text {Av}_n(312)$ , first defined by Defant in [Reference Defant4]. Given any permutation $\sigma \in S_n$ , if there exist indices $i, j$ such that $i + 1 \lt j$ and $\sigma (i + 1) \lt \sigma (j) \lt \sigma (i)$ we can perform an allowable swap by swapping the entries of $\sigma (i)$ and $\sigma (i+1)$ . Then $\pi _\downarrow$ sends $\sigma$ to the permutation obtained by starting at $\sigma$ and repeatedly applying allowable swaps until no more can be performed. Clearly the resulting permutation $\pi _\downarrow (\sigma)$ is in $\text {Av}_n(312)$ , and as shown in [Reference Defant4, Section 3], the resulting permutation $\pi _\downarrow (\sigma)$ is well-defined and independent of the order in which we perform allowable swaps. In fact, Defant proved the following commutation relation between $\pi _\downarrow$ and the meet operation $\wedge$ :

Lemma 4.1. (Lemma 3.1, [Reference Defant4]) Consider any positive integer $n$ . Given any subset $T \subset S_n$ , we have that

$$ \begin{align*} \pi _\downarrow \Big (\bigwedge T \Big ) = \bigwedge \{\pi _\downarrow (\sigma) \,:\, \sigma \in T\}. \end{align*}$$

Here both meet operations are taken in $S_n$ , but since $\text {Av}_n(312)$ is a sublattice of $S_n$ , the meet operation on the right hand side can be taken in $\text {Av}_n(312)$ as well.

Now, the following proposition characterises how $\pi _\downarrow$ interacts with the covering relation on  $S_n$ .

Proposition 4.2. Consider any permutation $\sigma \in \text {Av}_n(312)$ , and consider a descent $i \in \text {Des}(\sigma)$ . Let $j \in [n]$ be the minimal index such that $\sigma (k) \geq \sigma (i)$ for all $k \in [j, i]$ . Let $\tau = \sigma \circ (i, i+1)$ be the permutation obtained from $\sigma$ by swapping $\sigma (i)$ and $\sigma (i+1)$ . Then

$$ \begin{align*} \pi _\downarrow (\tau ) &= \sigma \circ \begin{array}{lllll} \big(i+1 & i &\,\, \ldots \,\,& j+1 & j\big) \end{array}. \end{align*}$$

Proof. Note that if $j \lt i$ , then we have that $\sigma (i-1) \gt \sigma (i)$ . So the triplet $(i-1, i, i+1)$ forms a $312$ -pattern in $\tau = \sigma \circ (i, i + 1)$ , so we may admissibly swap $i-1$ and $i$ to obtain $\sigma \circ (i+1 \ i \ i-1)$ . Continuing inductively, we find that for any $k \gt j$ , the permutation $\sigma \circ (i+1 \ i \ \ldots \ k+1 \ k)$ contains the $312$ -pattern $(k-1, k, i+1)$ , so we may admissibly swap $k - 1$ and $k$ . Hence we may retrieve $\sigma \circ \big(i+1 \ i \ \ldots \ j+1 \ j \big)$ by performing admissible swaps on $\sigma$ .

Now let $\tau _0 = \sigma \circ \big( i+1 \ i \ \ldots \ j+1 \ j \big)$ , and suppose $\tau _0$ contains a $312$ -pattern $(i_1, i_2, i_3)$ . In the above paragraph we were repeatedly swapping the index mapping to $\sigma (i+1)$ with an adjacent index, so any $312$ -pattern in $\tau _0$ must contain the index mapping to $\sigma (i+1)$ , which is $j$ . We also only swapped the indices within the interval $[j, i+1]$ , so such a $312$ -pattern must also contain another index within this interval. Thus the $312$ -pattern must satisfy $i_2 = j$ and $j \lt i_3 \leq i+1$ . By the minimality of $j$ we have that $\tau _0(j-1) = \sigma (j-1) \lt \sigma (i) \leq \tau (i_3)$ , so we must have $i_1 \lt j-1$ . But then we have

$$ \begin{align*} \tau _0(i_1) \gt \tau _0(i_3) \gt \tau _0(j-1), \\[3pt] \sigma (i_1) \gt \tau _0(i_3) \gt \sigma (j-1). \end{align*}$$

Since $\sigma ^{-1}(\tau _0(i_3)) \in [j, i]$ , we have that $(i_1, j-1, \sigma ^{-1}(\tau _0(i_3)))$ is a $312$ -pattern in $\sigma$ , a contradiction. Hence $\tau _0$ is $312$ -avoiding, so $\pi _\downarrow (\tau ) = \tau _0$ as desired.

Using Proposition 4.2, we may now derive the following relationship between ${\text {cov}}_{S_n}$ and ${\text {cov}}_{\text {Av}_n(312)}$ .

Lemma 4.3. Given any permutation $\sigma \in \text {Av}_n(312)$ , we have that the map

$$ \begin{align*} \pi _\downarrow \,:\, {\text {cov}}_{S_n}(\sigma) &\rightarrow {\text {cov}}_{\text {Av}_n(312)}(\sigma) \\[3pt] \tau &\rightarrow \pi _\downarrow (\tau ) \end{align*}$$

is a bijection.

By combining Lemmas 4.1 and 4.3, we may now reinterpret Ungar moves on $\text {Av}_n(312)$ as follows. Given any permutation $\sigma \in \text {Av}_n(312)$ and subset $T \subset {\text {cov}}_{S_n}(\sigma)$ , we have that

$$ \begin{align*} \pi _\downarrow \Bigg (\bigwedge _{S_n(312)}(T \cup \{\sigma \})\Bigg ) = \bigwedge _{\text {Av}_n(312)}\{\pi _\downarrow (\tau ) \,:\, \tau \in T\} \cup \{\sigma \}. \end{align*}$$

Hence for any $\sigma \in \text {Av}_n(312)$ , applying a random Ungar move to $\sigma$ in $\text {Av}_n(312)$ is equivalent to applying a random Ungar move to $\sigma$ in $S_n$ , then applying the $\pi _\downarrow$ operator.

4.2 A graph-theoretic formulation of the Tamari lattice

In the proof of Theorem 1.6, it will be useful to work with a graph-theoretic interpretation of $\text {Tam}_n$ . Before we present this interpretation, we will first review some relevant prerequisite information.

A rooted tree is a (graph-theoretic) tree where we specify one vertex to be the ‘root.’ Within a rooted tree, we may naturally assign an orientation to each of the edges by having them point ‘away’ from the root. If two vertices $v, w$ are connected by an edge pointing towards $w$ , then we will call $v$ the parent of $w$ , and $w$ the child of $v$ . If a vertex has no children, then we call it a leaf. An ordered tree is a rooted tree where we also specify an ordering of the children of each node. We may view ordered trees as trees that we may draw on a plane, such that each parent is ‘higher’ than their child, and the ordering of the children of each vertex from left to right is precisely the ordering we have defined. Hence ordered trees are also called plane trees.

A forest is a disjoint union of trees. For any forest $F$ , let $V(F)$ denote its set of vertices. An ordered forest is a forest equipped with an ordering on each tree, along with an ordering of the trees of the forest from left to right. A map $\varphi \,:\, V(F) \rightarrow V(F')$ is an isomorphism of ordered forests if it is a graph isomorphism which preserves the ordering of the roots and the natural orientations of the edges. We will denote the set of ordered forests on $n$ vertices up to isomorphism as $\mathcal{F}_{\operatorname {ord}}(n)$ .

The (left-to-right) preorder traversal of an ordered forest on $n$ vertices is a labelling of the vertices from $1$ to $n$ , iteratively assigned as follows.

1. 1. We assign the label $1$ to the root of the leftmost tree.

2. 2. If the label $i$ was just assigned to a non-leaf vertex, we next assign $i + 1$ to its leftmost child.

3. 3. If the label $j$ was just assigned to a leaf vertex, and $i$ is the largest index less than $j$ which has at least one still-unlabelled child, then we label the leftmost unlabelled child of $i$ with the label $j+1$ .

4. 4. If after assigning the label $i$ , all vertices in the tree containing vertex $i$ are labelled, then we next assign $i + 1$ to the root of the tree immediately right of the tree containing vertex $i$ .

The right-to-left preorder traversal is defined analogously as above, except the instances of ‘right’ and ‘left’ are swapped. We will use ‘preorder traversal’ to denote the left-to-right preorder traversal, unless indicated otherwise. See Figure 3 for an example of an ordered forest with the preorder traversal labelling. Clearly an isomorphism $\varphi \,:\, V(F) \rightarrow V(F')$ of ordered forests preserves the preorder traversal labelling. Note that throughout the rest of the paper, we will label the vertices of a forest using the preorder traversal labelling, and we will identify each vertex with its label.

Figure 3.

An example of an ordered forest in $\mathcal{F}_{\text{ord}}(12)$ . The labels in the diagram are given by the preorder traversal.

Figure 4.

The tree on the left is labelled via the preorder traversal. The middle tree is obtained by operating on vertex $2$ of the left tree, and the right tree is obtained by operating on vertex $1$ of the left tree. Note that the preorder traversal labelling is preserved in both operations.

We now define a partial order $\leq$ on $\mathcal{F}_{\operatorname {ord}}(n)$ . We will later show that the poset $(\mathcal{F}_{\operatorname {ord}}(n), \leq )$ is isomorphic to $\text {Tam}_n$ . To do so we first define an operation on vertices of an ordered forest as follows.

Given any forest $F$ and vertex $v$ of $F$ , we will denote the forest obtained by operating on $v \in F$ by $F[v]$ . See Figure 4 for some examples of the effects of various operations on a given ordered forest. Observe that the preorder traversal labelling is preserved under any operation. We now define the poset structure on $\mathcal{F}_{\operatorname {ord}}(n)$ as follows.

We now prove that the poset $(\mathcal{F}_{\operatorname {ord}}(n), \leq )$ is isomorphic to $\text {Tam}_n$ .

Proof of Theorem 4.7. Recall that the sublattice $\text {Av}_n(312) \subset S_n$ of $312$ -avoiding permutations is isomorphic to $\text {Tam}_n$ as a lattice. It thus suffices to construct a poset isomorphism

$$ \begin{align*} \Phi \,:\, \text {Av}_n(312) \rightarrow (\mathcal{F}_{\operatorname {ord}}(n), \leq ). \end{align*}$$

We will construct $\Phi$ as follows. Given a $312$ -avoiding permutation $\sigma$ , consider its plot; that is, the set of points $p_i = (i, \sigma (i))$ in $\mathbb{R}^2$ . Now draw a graph with vertices $\{p_i\}$ , such that given any two integers $i, j \in [n]$ with $i \lt j$ , the points $p_i$ and $p_j$ are connected by a directed edge $p_j \rightarrow p_i$ if

• • $\sigma (i) \gt \sigma (j)$ , and

• • no points in the plot (other than $p_i, p_j$ themselves) are contained within the rectangle $[i, j] \times [\sigma (i), \sigma (j)]$ .

Observe that since $\sigma$ is $312$ -avoiding, the in-degree of any vertex in this graph is at most $1$ . Since this graph clearly cannot have a directed cycle, it cannot have an undirected cycle either. So this graph is a forest. Now, let $\Phi (\sigma)$ be a plane forest with vertices denoted $q_1, \ldots , q_n$ , satisfying the following properties:

• • vertices $q_i, q_j$ are connected by an edge if and only if $p_i, p_j$ are connected by a (directed) edge;

• • for any two integers $i, j \in [n]$ satisfying $i \lt j$ , if the vertices $q_i, q_j$ are connected by an edge, then $q_i$ lies vertically underneath $q_j$ in the plane;

• • for any three integers $i, j, k \in [n]$ satisfying $i \lt j \lt k$ , if the pairs of vertices $(q_i, q_k)$ and $(q_j, q_k)$ are connected by edges, then the vertex $q_i$ lies to the left of the vertex $q_j$ .

• • for any two integers $i, j \in [n]$ satisfying $i \lt j$ , if $q_i$ and $q_j$ are the roots of the trees they are in (i.e. the rectangles $[i, n] \times [1, \sigma (i)]$ and $[j, n] \times [1, \sigma (j)]$ contain only the points $p_i$ and $p_j$ respectively), then the tree rooted at $q_i$ is left of the tree rooted at $q_j$ .

Since the graph formed by the vertices $p_i$ was a forest, the graph $\Phi (\sigma)$ must be an ordered forest. Evidently such an ordered forest is unique (up to an isomorphism on ordered forests), so $\Phi$ is a well-defined map. As an example, Figure 5 demonstrates how $\Phi$ acts on the permutation $\sigma = 342651 \in S_6$ .

Now, we can establish an inverse correspondence $\varphi \,:\, (\mathcal{F}_{\operatorname {ord}}(n), \leq ) \rightarrow \text {Av}_n(312)$ as follows. Consider an ordered forest $F \in (\mathcal{F}_{\operatorname {ord}}(n), \leq )$ . For any vertex $v \in F$ , let $l(v)$ be its left-to-right preorder traversal label, and let $r(v)$ be its right-to-left preorder traversal label. Then let $\varphi (F)$ be the permutation $\sigma$ satisfying that $\sigma (n+1-r(v)) = l(v)$ for all $v \in V$ . Since the ordered sets $\{l(v)\}, \{r(v)\}$ are both permutations of $[n]$ , we have that $\varphi (F)$ is indeed a permutation. Also note that for any two vertices $v, w \in V(F)$ , if $l(v) \gt l(w)$ and $r(v) \gt r(w)$ , then $w$ must be an ancestor of $v$ . Thus there do not exist vertices $v_1, v_2, v_3 \in V(F)$ such that $r(v_1) \gt r(v_2) \gt r(v_3)$ but $l(v_1) \gt l(v_3) \gt l(v_2)$ . This is equivalent to $\varphi (F)$ being $312$ -avoiding, so $\varphi$ indeed forms a well-defined map from $(\mathcal{F}_{\operatorname {ord}}(n), \leq )$ to $\text {Av}_n(312)$ . Now, one can readily check that $\varphi$ and $\Phi$ are inverses to each other. Thus $\Phi$ is a bijection, as desired. As an example, for the permutation $\sigma = 342651 \in S_6$ , Figure 6 shows how $\varphi (\Phi (\sigma)) = \sigma$ .

Now, consider any $312$ -avoiding permutation $\sigma$ , and any $i \in [n]$ . Let $\Phi (\sigma) = F$ , and let $i$ correspond to the vertex $q_i \in V(F)$ . Observe that $i-1 \in \text {Des}(\sigma)$ if and only if $q_i$ is a non-leaf vertex. Moreover, for any $i \in [n]$ with $i-1 \in \text {Des}(\sigma)$ , let $\tau _i \,:\!=\, \sigma \circ ( i-1 \ i )$ , and let $\sigma [i] \,:\!=\, \pi _\downarrow (\tau _i)$ . Then by Proposition 4.2, we have that any $i$ with $i-1 \in \text {Des}(\sigma)$ satisfies $\Phi (\sigma [i]) = \Phi (\sigma)[q_i]$ . Hence for any $\sigma \in \text {Av}_n(312)$ , we have that $\Phi$ bijects ${\text {cov}}_{\text {Av}_n(312)}(\sigma)$ and ${\text {cov}}_{(\mathcal{F}_{\operatorname {ord}}(n), \leq )}(\Phi (\sigma))$ . So $\Phi$ is indeed a poset isomorphism, as desired.

Figure 5.

On the left is the plot of the permutation $\sigma = 342651 \in S_6$ , with directed edges drawn between the vertices of the plot as described above. On the right is the forest $\Phi (\sigma)$ .

Figure 6.

On the left is the forest $F = \Phi (342651) \in \mathcal{F}_{\text{ord}}$ from Figure 5. For each $v \in V(F)$ , the left blue label is $l(v)$ , while the right red label is $r(v)$ . On the right is the permutation $\varphi (\Phi (342651)) = 342651$ . To emphasise that $\Phi$ and $\varphi$ are inverse bijections, dashed lines are drawn on the right which indicate how the pairs of vertices in $V(F)$ are mapped.

From now on we will identify $\text {Tam}_n$ with $(\mathcal{F}_{\operatorname {ord}}(n), \leq )$ . By combining the identity $\Phi (\sigma [i]) = \Phi (\sigma)[q_i]$ from the proof of Theorem 4.7, the characterisation of Ungar moves on $\text {Av}_n(312)$ in Subsection 4.1, and the characterisation of Ungar moves on $S_n$ in Section 1, we may characterise the Ungar moves on $(\mathcal{F}_{\operatorname {ord}}(n), \leq )$ as follows.

Corollary 4.8. Consider an ordered forest $F \in (\mathcal{F}_{\operatorname {ord}}(n), \leq )$ , and identify the vertices of $F$ with their preorder traversal labels. For any vertices $i_1, i_2, \ldots i_m \in V(F)$ whose labels satisfy $i_1 \lt i_2 \lt \ldots \lt i_m$ , we have that

$$ \begin{align*} F \wedge \bigwedge _{k=1}^m F[i_k] = (\ldots ((F[i_1])[i_2]) \ldots [i_m]) \end{align*}$$

where the right hand side denotes the forest obtained by operating on $i_1$ in $F$ , then $i_2$ in $F[i_1]$ , and so on.

Notably, fix a parameter $p \in (0, 1]$ , and consider an ordered forest $F \in (\mathcal{F}_{\operatorname {ord}}(n), \leq )$ . Pick each vertex of $V(F)$ with independent probability $p$ , and let $\{i_1, \ldots i_m\}$ be the list of picked vertices ordered from smallest to largest label. Then a random Ungar move on $F$ sends

$$ \begin{align*} F \mapsto (\ldots ((F[i_1])[i_2]) \ldots [i_m]). \end{align*}$$

Throughout the rest of the paper, we will write that during a given Ungar move, a vertex $v$ receives an operation (or is operated on) if an Ungar move is applied to the given forest and $v$ is one of the vertices selected in said move. Also note that for any ordered forest $F$ and leaf vertex $v \in F$ , we have $F[v] = F$ . Hence even though every vertex of $F$ may be picked in the formulation of the random Ungar moves on $(\mathcal{F}_{\operatorname {ord}}(n), \leq )$ in Corollary 4.8, only the operations on the non-leaf vertices affect the resulting forest.

By Theorem 4.7, it is clear that the ordered forest corresponding to the maximal element $\hat {1} \in \text {Tam}_n$ is the tree which consists of a path on $n$ vertices, while the ordered forest corresponding to the minimal element $\hat {0} \in \text {Tam}_n$ is the forest which consists of $n$ vertices and no edges. Now, throughout the rest of the paper, we will use the following properties of the aforementioned operations and preorder traversal labelings:

5.1 Proof outline for Theorem 1.6

The strategy for the proof of Theorem 1.6 is as follows. Consider an ordered tree $T \in \text {Tam}_n$ , and run the Ungarian Markov chain $\textbf {U}_{\text {Tam}_n}$ starting at $T$ . Let the random variable $T_{n, T}$ denote the number of steps until the vertex $1$ has no more children. Now, our main claim (Lemma 5.11) in the proof of Theorem 1.6 may roughly be stated as follows: if $T$ is a tree with many children, each with many children of their own, then $T_{n, T}$ is at least $n^{1-o(1)}$ with high probability.

Given a tree $T \in \text {Tam}_n$ rooted at the vertex $1$ , we may produce a lower bound for $T_{n, T}$ by piecing together the following two heuristics.

Figure 7.

A diagram showing the estimation of $\tau - \tau _0$ employed in Heuristic 5.1. Not all edges and vertices of $T$ are shown, only the ones relevant to the Heuristic. As shown, Heuristic 5.1 mainly bounds $\tau - \tau _0$ by counting the number of operations $i$ receives in the first $\tau _0$ moves. Here the vertices which are initially children of $i$ are coloured red.

Figure 8.

A diagram showing the estimation of $\tau - \tau _0$ employed in Heuristic 5.2. The main difference between Heuristics 5.1 and 5.2 is that Heuristic 5.2 incorporates the effect of vertex $i$ operating even after move $\tau _0$ . This is shown by the diagonal red arrow in the diagram.

As a demonstration, suppose $T$ is a tree rooted at vertex $1$ with $\geq \log \log n$ children, each of which has $\sim n/\log \log n$ children. See Figure 9 for a depiction of $T$ . Suppose the $j$ th child of $1$ from the right is labelled $i_j$ . Simulate $\textbf {U}_{\text {Tam}_n}$ starting at $T$ , and let the random variable $t_j$ denote the number of steps until $i_j$ is disconnected from $1$ . Then for any positive integer $k \lt \log \log n$ ,

1. 1. Heuristic 5.1 above implies that w.h.p. either $t_{k+1} - t_k \gtrsim n/\log \log n$ or $t_{k+1} - t_k = \Omega _p(t_k)$ , so the $t_k$ grow exponentially;

2. 2. Heuristic 5.2 above implies that w.h.p. either $t_{k+1} - t_k \gtrsim n/\log \log n$ or $t_{k+1} - t_k = \Omega _p(t_k^2)$ , so $\log t_k$ grows exponentially.

Thus Heuristic 5.2 implies that $t_{\lfloor \log \log n \rfloor } \gtrsim n/\log \log n$ , so $\mathcal{E}(\text {Tam}_n;\, F) \gtrsim n/\log \log n$ , while Heuristic 5.1 suggests a slower (but nevertheless exponential) growth from the $t_k$ . In any case, either heuristic here is enough to guarantee that $T_{n, T}$ is at least $n^{1-o(1)}$ w.h.p.

Figure 9.

A diagram of the ‘optimal’ tree $T$ for the application of Heuristics 5.1 and 5.2.

The tree $T$ chosen for this demonstration is ideal for the application of Heuristics 5.1 and 5.2, as $T$ has height $2$ . In practice the height of $T$ will increase with $|T|$ , so the children of the root of $T$ will have less children of their own. Thus for a more ‘generic’ $T$ , to estimate $T_n$ we will need to group the children of the vertices together, and apply Heuristics 5.1 and 5.2 to these ‘groups’ of vertices. In this setting Heuristic 5.1 will be more useful to us, as Heuristic 5.2 is more difficult to generalise to a group of vertices, some of which may have fewer children. We will also need to apply an inductive argument in order to estimate how the subtrees formed by the descendants of the children of $1$ evolve over time. For this we will need a complex algorithm (Algorithm 5.13) for simulating $\textbf {U}_{\text {Tam}_n}$ that will document the sizes of the child sub-trees, while allowing each sub-tree to retain enough ‘randomness’ to apply the inductive -othesis.

Using these ideas, we will bound $\mathcal{E}(\text {Tam}_n)$ as follows. Simulate the Ungarian Markov Chain on $\text {Tam}_n$ starting at $\hat {1}$ . First, we will bound the probability with which $\hat {1}$ transitions (after some number of steps) to a forest $F$ containing a tree $T$ with many ( $\sim n$ ) vertices. We will do this by modelling the first move in which a vertex $i$ receives an operation with a geometric random variable $g_i$ , and then investigating the probability that the maximum value of $g_i$ is uniquely attained for some $i \lt n/2$ . Using the n-skyline (to be defined later) we will also scan the ‘peaks’ of $\{g_i\}$ to identify which vertices will become children of the root of $T$ . We will consider the sequence $\{a_i\}$ formed by the labels of these peaks, and we will let $t_i$ denote the number of steps (after the $g_1-1^{\text{th}}$ step) until the vertices $a_i$ and $1$ are disconnected. We will also use the n-summary to ensure that the children of $T$ are sufficiently ‘spread out’. We will find that with probability $1/2 - o(1)$ , our tree $T$ will satisfy our desired conditions, so it will suffice to bound $\mathbb{P}(T_{n, T} = \Omega (n^{1-o(1)}))$ .

Now, given a tree $T$ we with our desired properties, we will bound $\mathbb{P}(T_{n, T} = \Omega (n^{1-o(1)}))$ via an induction argument (on $n$ ). Using the n-summary , we may identify a subsequence $\{a_{i_j}\} \subset \{a_i\}$ of ‘landmark children’ which are spread out and have many children between them. In Lemma 5.14, we will combine Heuristics 5.1 and 5.2 with the inductive -othesis to show that for $l \lesssim \log \log n$ , the $t_{i_j}$ grow superexponentially. Combined with another application of Heuristic 5.1 in Lemma 5.19, this will establish our bound on $\mathbb{P}(T_{n, T} = \Omega (n^{1-o(1)}))$ (approximately given by Lemma 5.11. We will then apply Lemma 5.11 in Subsection 5.3 to establish Theorem 1.6.

Note that we will use slightly different notation in the proof for Theroem 1.6 from the notation provided above. Notably we will formulate 5.11 differently, without reference to $T_{n, T}$ . Nevertheless the main ideas in the proof of Theorem 1.6 are as described above.

5.2 Introduction to the proof of Theorem 1.6

The proof of Theorem 1.6 is organised as follows. We will first present several definitions that will be used repeatedly throughout the proof. The bulk of the proof of Theorem 1.6 will be dedicated to proving Lemma 5.11. Since the proof of Lemma 5.11 is rather involved, we will first prove Theorem 1.6 (and Theorem 5.10) assuming Lemma 5.11 in Subsection 5.3. We will then return to prove Lemma 5.11 in Subsection 5.4.

Now, as discussed in Section 4, identify the vertices of any ordered forest in $\text {Tam}_n$ with its labels under the preorder traversal labelling. In the proof of Theorem 1.6, we will simulate the Ungarian Markov chain $\textbf {U}_{\text {Tam}_n}$ using Algorithm 5.13. Throughout this section, while running $\textbf {U}_{\text {Tam}_n}$ , we will use the convention that ‘on the $t^{\text{th}}$ step’ refers to before the $t^{\text{th}}$ random Ungar move has been applied, while ‘after the $t^{\text{th}}$ step’ refers to after the $t^{\text{th}}$ random Ungar move has been applied. Now, we will fully define Algorithm 5.13 in Subsection 5.4, but for now we will note that Algorithm 5.13 will simulate the first few moves as follows. For any $i \in [n]$ and $t \in \mathbb{Z}^+$ , let $S_{i, t}$ and $B_{i, t}$ be i.i.d. Bernoulli variables with parameter $p$ (i.e. $\mathbb{P}(S_{i, t} = 1) = p)$ . Given any $t \in \mathbb{Z}^+$ , suppose that some $j \in [n]$ satisfies $S_{j, t'} = 0$ for all $t' \lt t$ . Then given any $i \in [n]$ , operate on the $t^{\text{th}}$ step as follows:

• • if $S_{i, t'} =0$ for all $t' \lt t$ , operate on vertex $i$ if and only if $S_{i, t} = 1$ ;

• • else, operate on vertex $i$ if and only if $B_{i, t} = 1$ .

Now, for any $i \in [n]$ , let $g_i$ be the smallest integer $t$ such that vertex $i$ receives an operation on move $t$ . If $\textbf {U}_{\text {Tam}_n}$ is simulated using Algorithm 5.13, then $g_i$ is precisely the smallest $t$ such that $S_{i, t} = 1$ . Observe that no matter how $\textbf {U}_{\text {Tam}_n}$ is simulated, the variables $\{g_i\}_{i \in [n]}$ are distributed as i.i.d. geometric random variables with parameter $p$ .

Similarly to the proof of Proposition 4.9 (c), we have that $E_{I, m}$ implies that for the first $m - 1$ steps, all of the vertices with label in $[i + 1, j]$ will be descendants of the vertex $i$ . Now, we will record data about the variables $\{g_i\}$ using a collection of two-rowed arrays. We will want our arrays to satisfy the following property.

We will use the following operation on two-rowed arrays to identify the ‘peaks’ of the bottom row.

Now, define the random array $J$ to be the $n$ -skyline of the array $ \Bigg[ \begin{matrix} 1 & \ 2 & \ \ldots & \ n \\ g_1 & \ g_2 & \ \ldots & \ g_n \end{matrix} \Bigg] $ . We will use $J$ to keep track of (a large subset of) the children of vertex $1$ . Observe that $J$ is completely determined by the values of the variables $g_i$ . Moreover, note that if $g_1 \gt g_{a_2}$ , then $J$ is $n$ -childlike.

Consider an $n$ -childlike array $A = \Bigg[ \begin{matrix} a_1 & \ a_2 & \ \cdots & \ a_l \\ b_1 & \ b_2 & \ \cdots & \ b_l \end{matrix} \Bigg] $ . Then by Proposition 4.9 (c), $E_A$ implies that after $g_1 - 1$ steps, the tree $\hat {1}$ transitions to a tree with vertex $1$ as its root and with vertices $a_2, \ldots , a_l$ all as children of vertex $1$ . Now, we will use the following notions to ensure the arrays we consider are sufficiently long and ‘equidistributed’.