Séminaire Lotharingien de Combinatoire 84 (2021), Article B84a

SKEW SHAPE ASYMPTOTICS, A CASE-BASED INTRODUCTION

IGOR PAK^{⋆}

Abstract. We discuss various tools in the emerging area of Asymptotic Algebraic Combinatorics, as they apply to one running example of thick ribbons. Connections to other areas, exercises and open problems are also included.

1. Introduction

1.1. Foreword. This paper is a short introduction to some ideas in Asymptotic Algebraic Combinatorics. We do not intend to be broad or thorough, but rather give a cross section of the area concentrated around a single example, which turned out to have rich connections to many different results and open problems. We also include a number of exercises for the curious reader. Of course, this is not a substitute of a serious survey, but in the absence of such we envision this paper as a quick guide to the literature, and an easy entry point to the area.

1.2. Thick ribbons. Let δ_{k} = (k − 1, k − 2, …, 2, 1) ⊢ \binom{k}{2} be a staircase shape of size k. Let τ_{k} = (δ_{2k}/δ_{k}) ⊢ n be a thick ribbon shape of size k, see Figure 1. Here and below, we have n = \frac{k(3k−1)}{2}.

Denote by a_{k} := | SYT(τ_{k})| the number of standard Young tableaux of shape τ_{k}. The sequence {a_{k}} is rapidly growing:

1, 16, 101376, 1190156828672, 68978321274090930831360, …

For example, a_{2} = | SYT(321/1)| = 16. For larger values, see [OEIS, A278289]. The main goal of the paper is to give lower and upper bounds on a_{k}. Roughly, a_{k} ≈ \sqrt{n!}. More precisely, it is known and easy to see that

log a_{k} = \frac{3}{2} k^{2} log k + O(k^{2}) = \frac{1}{2} n log n + O(n) as k → ∞,

see [MPP4]. The following result frames the answer in an asymptotic language.

Theorem 1.1 ([MPT]). There exists a universal constant ϕ, such that

log a_{k} = \frac{1}{2} n log n + ϕ n + o(n)  as  n = \frac{1}{2} k(3k − 1) → ∞.

The rest of the paper is concerned with the following problem.

Main Problem 1.2. Find ϕ, i.e., give sharp rigorous estimates for ϕ.

June 1, 2021.

⋆Department of Mathematics, UCLA, Los Angeles, CA 90095. Email: pak@math.ucla.edu.

The best bounds we present are:

(1.1)  − 0.2368 ≤ ϕ ≤ − 0.1648,

given by Lower Bound 9.2 and Upper Bound 6.1. The result in [MPT] does not determine the exact value of ϕ, but rather presents it as a solution of a variational problem (cf. [Gor1] and Exercise 12.4). It is unlikely that it can be computed exactly other than numerically.

Figure 1. Staircases δ_{3} and δ_{6}, thick ribbon τ_{3} = δ_{6}/δ_{3}, and a standard Young tableau of shape τ_{3}.

The bounds (1.1) are remarkably close to each other, as opposed to the way these things usually go. In fact, the calculations by Pantone suggest that ϕ ≈ −0.18, see [OEIS, A278289], leaving very little room for improvement on either side. Let us emphasize that getting best bounds is not really the point of this paper as we present a number of relatively weak bounds. The idea is to review the tools which in this particular case can give weaker bounds, but stronger in other cases perhaps, and often best used in combination.

1.3. Style and structure of the paper. In Section 2, we begin with an informal general discussion of how to obtain bounds for combinatorial numbers, notably how to approach them when some easy ideas fail.o Then, one by one, we introduce tools of the area, starting with the classical and more established ideas and leading to the most recent work. We largely restrict ourselves to the running example of the skew shape τ_{k}, leaving only a trail of crumbs for the interested reader to recover the full story from the references. We also heavily use figures, examples and exercises in place of formal general statements.

We do not present most definitions, standard results and notation, but instead assume that the reader is familiar with them or is able to quickly catch up using [Sag] and [S2, Ch. 7]. In every section, we supplement the results with exercises, which we believe will be helpful. In fact, the upper and lower bounds are never carefully proved and can be viewed as exercises in their own right. Additional exercises are included in Section 11. We expect the reader to be committed to doing the exercises as this is probably the only way to get a grasp of the area.

In Section 12, we state several conjectures and open problems directly related to the subject. Although natural, they show both the power of tools in Algebraic Combinatorics, and their limitations in larger setting. We conclude with Section 13, where we give brief historical remarks, mostly aimed as a guide to the references.

Finally, let us relate the style of this paper to general goals of Asymptotic Algebraic Combinatorics. In the context of “two cultures in mathematics” [Gow], one often assumes that Combinatorics belong to the second, “problem solving” culture. This is far from the truth. Like other broad fields, Combinatorics spans both cultures, even if some areas in it are more at home in one than the other. Traditionally, the culture of ever improving estimates aiming towards the true value for a key benchmark problem (as in [Ber]) was foreign to the whole area of Algebraic Combinatorics. While the specific benchmark problem we chose is not of utmost importance, it serves as a convenient battleground for several competing tools and techniques which can later be applied to other problems. With this style of exposition, we are aiming to lend further support to this important culture in the area.

2. Finding bounds

2.1. The basics. Suppose one is given an integer sequence {c_{k}} to investigate. The first thing to do is to check whether c_{k} has a nice product formula. This often works, e.g. for binomial coefficients, Catalan numbers, number of boxed plane partitions, alternating sign matrices, etc. When a product formula exists and can be proved, it is relatively straightforward to compute the exact asymptotics to everyone’s satisfaction. On the other hand, when there are some relatively large prime divisors appearing in {c_{k}}, one should look elsewhere. For example, in our sequence {a_{k}}, we have primes 251|a_{4} and 327317328039199|a_{8}, making the prospects of a product formula rather unpromising.

The second approach is to look for a nice recurrence relation, convert it into a closed form generating function (GF), and then use various analytic tools. This works well for numerous sequences, e.g. Fibonacci, Bell, Bernoulli, Apéry, and partition numbers, see e.g. [FS, Odl, PW]. Theorem 1.1 rules out

(2.1)  A(t) := ∑_{k=1}^{∞} \frac{a_{k} t^{k}}{(k(3k − 1)/2)!}

being rational or algebraic, making it unlikely that progress can be made in this direction. However, the asymptotics do not rule out A(t) from being D-finite and ADE (cf. §11.1); it would be interesting to prove that. We refer to [P2] for more on this approach.

The next thing to try is to look for a determinant formula, and this is where one finds an early success. Indeed, the following Aitken–Feit determinant formula [Ait, Feit] is a standard result in the area, and applies to all skew shapes:

(2.2)  f^{λ/μ} = n! det (\frac{1}{(λ_{i} − μ_{j} − i + j)!})_{i,j=1}^{ℓ(λ)} ,

where f^{λ/μ} := |SYT(λ/μ)| denotes the number of standard Young tableaux of shape λ/μ, see e.g. [S2, Cor. 7.16.3]. The alternating sign nature of the formula allows only mediocre upper bounds in our case. To understand this, consider the leading (diagonal) term in the Laplace expansion of (2.2):

(2.3)  n! ∏_{i=1}^{ℓ(λ)} \frac{1}{(λ_{i} − μ_{i})!} .

We show in §4.2, that this product gives the right order of magnitude. Since we have only ℓ(λ)! = exp Θ(k log k) terms in the Laplace expansion, the product (2.3) rigorously implies an asymptotic upper bound (see Exercise 11.1). This also shows the limitations of the determinant approach in this case. Indeed, it is very hard to see how any nontrivial lower bound can be obtained from (2.2) in view of the signs in the Laplace expansion. Nor do other determinant tricks seem directly applicable, see [K1, K2].

2.2. Asymptotic thinking. While it is hard to give a broad description of what kind of arguments lead to good bounds, one natural approach is clear: clever use of identities and other summation formulas to bound one term in the summation (cf. [TV]). Let us give one important example to illustrate this approach.

Let D_{n} = max{f^{λ}, λ ⊢ n} denote the maximal dimension of the irreducible S_{n}-module, where f^{λ} := χ^{λ}(1) = | SYT(λ)|. For more on {D_{n}}, see [OEIS, A003040]. To get a bound on D_{n}, recall the Burnside formula:

∑_{λ⊢n} (f^{λ})^{2} = n!

This gives an upper bound D_{n} ≤ \sqrt{n!}, and a lower bound D_{n} ≥ \sqrt{n!/p(n)}, where p(n) = e^{O(\sqrt{n})} is the number of partitions. Putting these together and using Stirling’s formula, we obtain

(2.4)  log D_{n} = \frac{1}{2} n log n − \frac{1}{2} n − O(\sqrt{n}) .

Since \sqrt{n!} is the scale on which D_{n} is lying, it is the next term of the asymptotics which is most interesting. In other words, the ratio D_{n}/\sqrt{n!} is the right quantity to consider. Given (2.4), it is natural to conjecture that in fact we have

(2.5)  log D_{n} = \frac{1}{2} n log n − \frac{1}{2} n − c\sqrt{n} + o(\sqrt{n}) .

This is the celebrated Vershik–Kerov–Pass (VKP) conjecture which remains open [KP, VK2].

To bring this discussion back to {a_{k}}, one can make several conclusions. First, a_{k} lies on the same scale of \sqrt{n!}, where n = |τ_{k}|, so the asymptotics of a_{k}/\sqrt{n!} is exactly the right quantity to consider. Second, the success of using the Burnside identity suggests one should consider numerous summation formulas involving f^{λ/μ}. In fact, this is the approach that works best for both the upper and the lower bounds. Third, the fact that ϕ > −0.5 implies that a_{k} is exponentially larger than D_{n}, making the summations very large and involving exponentially large terms. Finally, the existence of the limit ϕ given by Theorem 1.1, suggests that this is an easier problem than the VKP conjecture. This turns out to be true as the problem is amenable to a variety of techniques and ideas.

2.3. Probabilistic thinking. In place of identities as above, one can ask a more delicate question: what is the shape of λ which attains the maximum f^{λ} = D_{n}. This may seem vague, but it turns out that the limit shape of maximal λ is well defined after scaling the maximal shapes by \frac{1}{\sqrt{n}}. The answer was computed by Vershik and Kerov [VK1] and by Logan and Shepp [LS], see also [Rom]. Note that when the row/column lengths of λ are constrained to t\sqrt{n}, the maximal dimension f^{λ} is given by a function D_{n}(t), which is exponentially smaller than D_{n}, for all 1 ≤ t < 2, see [LS]. The proof is based on the variational principle and uses the hook-length formula (see §6.1) in an essential way.

For our setting, one can ask for the limit shape of random A ∈ SYT(λ/μ), where one considers scaled partitions \frac{1}{\sqrt{n}} \{(i, j) ∈ λ/μ, A(i, j) ≤ αn\} → L_{α}. See Figure 2 for an example of limit curves in a k ×2k rectangle. The existence of such limit curves is proved by [Sun], see also [Gor1, MPT]. If one knows the exact shape of {L_{α}, 0 < α < 1}, one can estimate

log f^{λ/μ} ≈ ∫_{0}^{1} log |L_{α}|! dα ,

and an even better estimate can be obtained by taking adjacent ribbon hooks, see below.

Figure 2. The limit curves in a k × 2k rectangle (created by Dan Romik, April 2020), and two partitions of the rectangle.

Of course, getting closed formulas for the limit curves is a difficult problem, which often involves asymptotics of determinants of multivariate functions, see [BP2, Gor2]. In the absence of closed formulas for {L_{α}}, one can still use this approach in selecting which bounds fit the problem best. For example, for λ = (2k)^{k}, we have | SYT(λ)| > | SYT(k^{k})|^{2}, but this is a rather poor lower bound as the square boundary cuts sharply across the limit shape curves. Indeed, one can check that the right-hand side is smaller than the product (k!)^{k+1}| SYT(δ_{k})|^{2}, which comes from a partition that is better aligned with the limit shape curves, see Figure 2.

3. Notation and basic asymptotics

As we mentioned earlier, we employ the standard notations in Algebraic Combinatorics and Representation Theory of S_{n}, see e.g. [Sag] and [S2, Ch. 7]. We refer to [S2, Ch. 3] and [Tro] for poset notation and standard results.

We write ℕ = {0, 1, 2, …}, [n] = {1, …, n} and ℝ_{+} = {x ≥ 0}. We use the standard asymptotics notations f ∼ g, f = o(g), f = O(g) and f = Ω(g), see e.g. [FS, §A.2]. We use c ≈ c′ to approximate their numerical value with the usual rounding rules, e.g. π ≈ 3.14 and π ≈ 3.1416.

Throughout the paper, we make heavy use of Stirling’s formula log n! = n log n − n + O(log n). Here and everywhere below log denotes the natural logarithm. We need four more products:

\begin{matrix}(2n − 1)!! := 1 · 3 · 5 ⋯ (2n − 1),  Φ(n) := 1! · 2! ⋯ n! , \\ Ψ(n) := 1! · 3! · 5! ⋯ (2n − 1)! ,  Λ(n) := 1!! · 3!! · 5!! ⋯ (2n − 1)!! \end{matrix}

These products have similar asymptotic formulas:

log(2n − 1)!! = n log n + (log 2 − 1)n + O(1) [OEIS, A001147],

log Φ(n) = \frac{1}{2} n^{2} log n − \frac{3}{4} n^{2} + O(n log n) [OEIS, A000178],

log Ψ(n) = n^{2} log n + (log 2 − \frac{3}{2}) n^{2} + O(n log n) [OEIS, A168467],

log Λ(n) = \frac{1}{2} n^{2} log n + (\frac{log 2}{2} − \frac{3}{4}) n^{2} + O(n log n) [OEIS, A057863].

4. Linear extensions of posets

4.1. Antichain partition. Observe that

(4.1)  a_{k} ≥ k! · (k + 1)! ⋯ (2k − 1)! = \frac{Φ(2k − 1)}{Φ(k − 1)} .

This follows from counting standard Young tableaux with numbers in the first antidiagonal smaller than the numbers in the second antidiagonal, etc., see Figure 3. These are in bijection with permutations in each antidiagonal, of sizes k, k + 1, …, 2k − 1, respectively. This gives the following.

Lower Bound 4.1 ([MPP4, §8.2]).

ϕ ≥ \frac{11 log 2}{6} − \frac{log 3}{2} − \frac{3}{2} ≈ −0.7785.

It is easy to see that this approach works for all posets, see e.g. [MPP4, §2]. It was shown in [BP1] that one can consider any antichain partition, or even slightly more involved Greene–Kleitman–Fomin (GKF) parameters.

Exercise 4.2. Prove that lower bound (4.1) is optimal over all antichain partitions.

Figure 3. Skew shape τ_{5} = δ_{10}/δ_{5}, antichain partition, chain partition, and a lower order ideal of (3, 5) ∈ τ_{5} with br(3, 5) = 6.

4.2. Chain partition. Observe that

(4.2)  a_{k} ≤ \binom{n}{1, 2, …, k − 1, k, k, …, k} = \frac{n!}{(k!)^{k−1}Φ(k)} .

To prove this, simply observe that SYT(τ_{k}) is a subset of column-strict tableaux, and that the columns have lengths 1, 2, …, k − 1, k, k, …, k (k columns of length k).

Upper Bound 4.3 ([MPP4, §8.2]).

ϕ ≤ \frac{1}{6} − \frac{log 2}{2} + \frac{log 3}{2} ≈ 0.3694.

It is easy to see that this approach works for all chain partitions of posets, see e.g. [MPP4, §2]. It was shown in [BP1] that one can also consider somewhat more involved GKF parameters.

Exercise 4.4. Prove that lower bound (4.2) is optimal over all chain partitions.

4.3. Lower order ideals. Observe that

(4.3)  a_{k} ≥ \frac{n!}{1^{2k−1} · 3^{2k−3} · 6^{2k−5} ⋯ \binom{k}{2}^{1}} .

For general posets, this was first observed by Stanley [S2, Exc. 3.57] and proved by Hammett and Pittel [HP, Eq. (1.1)]. Heuristically, to see this, observe that br(i, j) := \binom{2k−i−j+2}{2} is the number of squares (p, q) ∈ τ_{k} such that i ≤ p, j ≤ q. Thus, br(i, j)^{−1} is the probability that (i, j) is the smallest of these squares in a random permutation. While these events are not independent, it is known that they do have positive correlations, giving (4.3).

Exercise 4.5. Give a formal proof of (4.3). Check that it does not give a nontrivial lower bound on ϕ.

Exercise 4.6. Reverse the role of upper and lower ideals by rotating τ_{k} by 180 degrees. Does this give a better or worse lower bound?

5. Thin ribbons and slim diagrams

5.1. Alternating permutations. Denote by E_{m} the m-th Euler number, defined as the number of alternating permutations in S_{m} :

E_{m} := |{σ ∈ S_{m}, σ(1) < σ(2) > σ(3) < σ(4) > …}| ,

see [S3] and [OEIS, A000111]). Now observe that for k ≡ 0 mod 2, we have

(5.1)  a_{k} ≥ E_{4k−3} · E_{4k−7} · E_{4k−11} ⋯ E_{2k+1}.

To see this, break the ribbon shape τ_{k} into thin ribbons as in Figure 4 and consider standard Young tableaux with numbers in smaller ribbons smaller than numbers in larger ribbons. Recall that

E_{m} ∼ \frac{4}{π} (\frac{2}{π} )^{m} m!

(see e.g. [FS, S3]). This and (5.1) gives the following.

Lower Bound 5.1.

ϕ ≥ α_{2} := − \frac{3}{2} − \frac{23 log 2}{6} − \frac{log 3}{2} − log π ≈ −0.5370.

Exercise 5.2. Compute the lower bound corresponding to the ribbon partition in Figure 4. Prove that of all patterns σ(1)∗σ(2)∗σ(3)∗…, where ∗ ∈ {<, >}, the alternating permutations form the largest class. Use Exercise 4.2 to show that Lower Bound 5.1 cannot be improved by a better partition of τ_{k} into ribbons.

Figure 4. Partitions of τ_{6} = δ_{12}/δ_{6} into zigzag ribbons, 3-ribbons and 2-row diagrams.

5.2. r-ribbons. Denote by F_{m}^{(r)} = SYT(δ_{m}/δ_{m−r}) the number of standard Young tableaux of the r-ribbon shape. For example, δ_{m}/δ_{m−2} are the usual zigzag ribbons, so F_{m}^{(2)} = E_{2m−1}. It follows from [BR] that

(5.2)  F_{m}^{(3)} = \frac{(3m)! E_{2m} m^{Θ(1)}}{(2m)! 2^{2m}}  and F_{m}^{(5)} = \frac{(5m)! (E_{2m})^{2} m^{Θ(1)}}{((2m)!)^{2} 2^{6m}} .

Now observe that for k ≡ 0 mod 3, we have

(5.3)  a_{k} ≥ F_{2k−1}^{(3)} · F_{2k−4}^{(3)} · F_{2k−7}^{(3)} ⋯ F_{k+2}^{(3)}.

To see this, consider a partition of τ_{k}, k ≡ 0 mod 3, into 3-ribbons as Figure 4. Now formulas (5.2) and (5.3) give the following.

Lower Bound 5.3.

ϕ ≥ α_{3} := − \frac{3}{2} − \frac{log 3}{2} + \frac{11 log 2}{6} − \frac{2 log π}{3} ≈ −0.4431.

Exercise 5.4. Find the analogue of (5.3) for F^{(5)}. Use it to derive the following.

Lower Bound 5.5.

ϕ ≥ α_{5} := − \frac{3}{2} + \frac{43 log 2}{30} − \frac{log 3}{2} + log 5 − \frac{4 log π}{5} ≈ −0.3621.

Exercise 5.6. Denote by α_{r} the lower bound on ϕ obtained from taking r-ribbons. Prove that {α_{r}} is strictly increasing and thus has a limit α := lim_{r→∞} α_{r}, such that α ≤ ϕ. Prove or disprove that α = ϕ.

Exercise 5.7. Find the closed form exponential generating function (EGF) for E_{m} to conclude that it is D-algebraic (ADE). Use the formulas in [BR] for conclude the same result for r-ribbons, r = 3, 4, 5.

5.3. Slim diagrams. Observe that a partition of τ_{k} into 2-row diagrams in Figure 4 gives

(5.4)  a_{k} ≤ \binom{n}{1, 5, 9, …, 2k, 2k, …, 2k} · [C_{1} · C_{3} · C_{5} ⋯] · (C_{k+1})^{⌈ \frac{k}{2} ⌉} ,

where C_{m} = \frac{1}{m+1} \binom{2m}{m} is the m-th Catalan number. To see this, follow the argument in §4.2.

Exercise 5.8. Check that (5.4) improves the upper bound in (4.2), but does not improve the bound on ϕ over that in the Upper Bound 4.3. Prove that the same holds for partitions of τ_{k} into r-row slim diagrams, for every fixed r. Explain formally why these slim diagrams are less effective for upper bounds compared to ribbons for lower bounds.

6. Hook-length formula

6.1. The setup. Let λ ⊢ n. Denote by f^{λ} = | SYT(λ)| the number of standard Young tableaux of shape λ. The hook-length formula (HLF) states that

(HLF)  f^{λ} = n! ∏_{(i,j)∈λ} \frac{1}{h_{λ}(i, j)} ,

where h_{λ}(i, j) = λ_{i} − i + λ′_{j} − j + 1 is the hook-length of the square (i, j). See [NPS, P1] for some of our favorite proofs.

6.2. Staircase shape. Denote by b_{m} := f^{δ_{m}} = | SYT(δ_{m})| the number of standard Young tableaux of staircase shape, see [OEIS, A005118]. It follows from the HLF that

(6.1)  b_{m} = \frac{\binom{m}{2}!}{1^{m−1} · 3^{m−2} · 5^{m−3} ⋯ (2m − 1)} = \frac{\binom{m}{2}!}{Λ(m)} .

Observe that

(6.2)  a_{k} · b_{k} ≤ b_{2k} ,

since together two tableaux of shape δ_{k} and δ_{2k}/δ_{k} can form a single tableau of shape δ_{2k}. This gives the following.

Upper Bound 6.1.

ϕ ≤ \frac{1}{2} − \frac{log 2}{6} − \frac{log 3}{2} ≈ −0.1648.

Exercise 6.2. Prove or disprove: the exponential generating function (EGF) for b_{m} is D-finite.

6.3. Three staircases. Observe that

(6.3)  a_{k} ≥ b_{k}^{2} b_{k+1} \binom{2\binom{k}{2}}{\binom{k}{2}}.

This follows immediately from the partition of τ_{k} into shapes δ_{k}, δ_{k} and δ_{k+1} as in Figure 5. Combined with (6.1), this gives the following.

Lower Bound 6.3.

ϕ ≥ \frac{1}{2} − \frac{5 log 2}{6} − \frac{log 3}{2} ≈ −0.6269.

Figure 5. Partition of τ_{6} = δ_{12}/δ_{6} into three staircases δ_{6}, δ_{6} and δ_{7}.
Partition of τ_{6} into δ_{6} and ζ_{6}. DeWitt shape ς_{3} = δ_{12}/ρ_{3} and its partition
into δ_{3}, δ_{3} and τ_{6}.

Exercise 6.4. Let ξ_{k} = (2k − 1, …, k). Partition δ_{2k} into two staircases δ_{k} and one skew shape ζ_{k} := ξ_{k}/δ_{k}, see Figure 5. Define z_{k} := | SYT(ζ_{k})|. Use the HLF applied to shape (2k − 1, …, k) to get an upper bound on z_{k}. Note that

a_{k} ≤ b_{k} z_{k} \binom{k^{2} + \binom{k}{2}}{\binom{k}{2}} .

Use this and (6.1) to obtain an upper bound on a_{k}.

6.4. DeWitt shape. Denote by ρ_{k} = (k^{k}) the k × k square diagram, and define the DeWitt shape ς_{k} := δ_{4k}/ρ_{k}, see Figure 5. It was shown in [DeW] (see also [H+, KS, MPP3]), that

d_{k} := |SYT(ς_{k})| = n! \frac{Φ(k)^{3} Φ(3k) Ψ(k) Ψ(3k)}{Φ(2k)^{3} Ψ(2k)^{2} Ψ(4k)} ,

where n = 7k^{2} = |ς_{k}|. Now observe that

(6.4)  a_{2k} · b_{k}^{2} ≤ d_{k} .

Using this and (6.1), we get the following.

Upper Bound 6.5.

ϕ ≤ −\frac{17 log 2}{3} + log 3 + \frac{7 log 7}{6} + \frac{1}{2} ≈ −0.0590.

7. Littlewood–Richardson coefficients

7.1. Basic formulas. Let λ ⊢ n, μ ⊢ m, ν ⊢ n − m. Recall two properties of the Littlewood–Richardson coefficients (LR-coefficients for short):

(7.1)  f^{μ}f^{ν} \binom{n}{m} = ∑_{λ⊢n} c_{μν}^{λ} f^{λ} and f^{λ/μ} = ∑_{ν⊢n−m} c_{μν}^{λ} f^{ν} .

It was observed in [MPP4, Prop. 2.4], that

(7.2)  f^{λ/μ} ≤ \frac{n!f^{μ}}{m!f^{λ}} .

Indeed, putting together equations in (7.1), we obtain

f^{λ/μ} = ∑_{ν⊢n−m} c_{μν}^{λ} f^{ν} ≤ ∑_{ν⊢n−m} \binom{n}{m} \frac{f^{μ} f^{ν}}{f^{λ}} f^{ν} = \frac{f^{μ}}{f^{λ}} \binom{n}{m} ∑_{ν⊢n−m} (f^{ν})^{2} = \frac{n!f^{μ}}{m!f^{λ}} .

Now, applying (7.2) to τ_{k} = δ_{2k}/δ_{k}, we get the following.

Upper Bound 7.1.

ϕ ≤ \frac{3}{2} − \frac{log 2}{2} ≈ 1.1534.

Exercise 7.2. Explain why this upper bound is so poor.

7.2. Evaluations. Let λ = δ_{2k}, μ = δ_{k}, ν = ξ_{k} := (2k − 1, …, k) and x_{k} := | SYT(ξ_{k})|. Note that λ/ν = μ, which implies c_{μν}^{λ} = 1. Observe that (7.1) gives a_{k} ≥ x_{k}. Applying (HLF), we have the following.

Upper Bound 7.3.

ϕ ≥ \frac{1}{2} − \frac{log 2}{6} − log 3 ≈ −0.7141.

Exercise 7.4. Recall from [Sag, S2, vL] the combinatorial interpretation of LR-coeffi-cients c_{μν}^{λ} as the number x_{k} := |LR(λ/μ, ν)| of lattice tableaux of shape λ/μ and weight ν. Observe that there is a unique lattice tableau in LR(τ_{k}, ν), see Figure 6. Deduce that c_{μν}^{λ} = 1, for λ/μ = τ_{k} as above.

Figure 6. The unique lattice tableau in LR(τ_{5}, ξ_{5}).

7.3. Upper bound on LR-coefficients. Recall from [PPY, Thm. 1.5] that

(7.3)  c_{μν}^{λ} ≤ \sqrt{\binom{n}{m}} , for all λ ⊢ n , μ ⊢ m , ν ⊢ n − m.

To see this, use (7.1) to obtain

∑_{λ⊢n} (c_{μ,ν}^{λ})^{2} ≤ ∑_{λ⊢n} c_{μ,ν}^{λ} \frac{f^{λ}}{f^{μ}f^{ν}} = \frac{1}{f^{μ}f^{ν}} · f^{μ}f^{ν} \binom{n}{k} = \binom{n}{k}.

This implies

f^{λ/μ} = ∑_{ν⊢n−m} c_{μν}^{λ} f^{ν} ≤ p(n − m) \sqrt{\binom{n}{m}} · \sqrt{(n − m)!} < p(n) \sqrt{\frac{n!}{m!}} ,

where p(n) denotes the number of partitions of n. Applying this to λ/μ = τ_{k} and using p(n) = e^{O(\sqrt{n})}, we get the following.

Upper Bound 7.5.

ϕ ≤ \frac{4 log 2}{3} − \frac{log 3}{2} − \frac{1}{2} ≈ −0.1251.

Exercise 7.6 ([PPY, §4.1]). In the opposite direction, prove that for every 0 ≤ k ≤ n, we have

∑_{λ⊢n} ∑_{μ⊢k,ν⊢n−k} (c_{μ,ν}^{λ})^{2} ≥ \binom{n}{k}.

What does this formula say about how sharp (7.3) is?

8. Naruse hook-length formula

8.1. The setup. Let λ/μ be a skew shape and D be a subset of the Young diagram of λ. A square (i, j) ∈ D is called active if (i + 1, j), (i, j + 1) and (i + 1, j + 1) are all in λ \ D. An excited move is a replacement of an active (i, j) ∈ D with (i + 1, j + 1). An excited diagram of λ/μ is a subset of squares in λ obtained from the Young diagram μ after a sequence of excited moves on active cells. Let E(λ/μ) be the set of excited diagrams of λ/μ, see Figure 7. The Naruse hook-length formula (NHLF) states that for every skew shape λ/μ we have

(NHLF)  |SYT(λ/μ)| = n! ∑_{D∈E(λ/μ)} ∏_{(i,j)∈λ\D} \frac{1}{h_{λ}(i, j)} ,

where n = |λ/μ|.

Exercise 8.1 ([MPP4, §12.1], see also [PPS]). Denote by λ^{∗} the skew shape obtained by rotating the diagram λ by 180 degrees. Apply the NHLF to λ^{∗}. Conclude the inequality

∏_{(i,j)∈λ} h_{λ}(i, j) ≤ ∏_{(i,j)∈λ} h_{λ}^{∗}(i, j),

Figure 7. Example of an excited move. Set E(λ/μ), for λ = (5, 4, 4, 1)

and μ = (2, 1). The arrows indicate excited moves.

where h_{λ}^{∗}(i, j) = (i + j − 1). Compare this with

∑_{(i,j)∈λ} h_{λ}(i, j) = ∑_{(i,j)∈λ} h_{λ}^{∗}(i, j),

and explain the discrepancy.

8.2. Basic bounds. Observe that since μ ∈ E(λ/μ), we have

(8.1)  |SYT(λ/μ)| ≥ F (λ/μ) := n! ∏_{(i,j)∈λ/μ} \frac{1}{h(i, j)} .

Taking λ = δ_{2k} and μ = δ_{k}, we obtain the following.

Lower Bound 8.2.

ϕ ≥ \frac{1}{6} − \frac{3 log 2}{2} + \frac{log 3}{2} ≈ −0.3237.

Now, for the upper bound observe that the hooks decrease under excited moves. This gives

(8.2)  |SYT(λ/μ)| ≤ F (λ/μ) · |E(λ/μ)|.

For λ = δ_{2k}, μ = δ_{k}, and k even, observe that the excited diagrams are in bijection with non-intersecting paths as shown in Figure 8. Thus,

|E(τ_{k})| ≤ \binom{2k − 2}{k − 1}^{k/2} .

Combined with (8.2), this gives the following.

Upper Bound 8.3.

ϕ ≤ \frac{1}{6} − \frac{5 log 2}{6} + \frac{log 3}{2} ≈ 0.1384.

Exercise 8.4. Before moving on, show that both the lower and the upper bounds are not exact, i.e., they can be improved by some ε > 0, using better counting over excited diagrams.

Figure 8. Non-intersecting paths in bijection with excited diagrams, in the beginning and after three moves.

8.3. Non-intersecting paths. Recall that non-intersecting paths with fixed start and end points are given by a determinant. For thick ribbons, this determinant was computed by Proctor:

(8.3) |E(τ_{k})| = ∏_{1≤i<j≤k} \frac{k + i + j − 1}{i + j − 1} = [\frac{Φ(3k − 1) Φ(k − 1)^{3} (2k − 1)!! (k − 1)!!}{Φ(2k − 1)^{3}(3k − 1)!!}]^{1/2} ,

see [MPP4, Lemma 8.1] and [OEIS, A181119]. Combined with (8.2), this gives the following.

Upper Bound 8.5.

ϕ ≤ \frac{1}{6} − \frac{7 log 2}{2} + 2 log 3 ≈ −0.0621.

Exercise 8.6 (see [MPP3, §7]). Prove that the excited diagrams in this case are in bijection with lozenge tilings of half of a (k − 1) × (k − 1) × k hexagon. Recall the MacMahon box formula for the number M(a, b, c) of lozenge tilings of an a × b × c hexagon. Use this to get an upper bound |E(τ_{k})|^{2} ≤ M(k − 1, k − 1, k). Show that this inequality gives the same bound on ϕ as in Upper Bound 8.5. Explain why.

9. Flipped HLF

9.1. The setup. A skew shape λ/μ is called slim if λ_{ℓ} ≥ μ_{1} + ℓ − 1, where ℓ = λ′_{1} is the number of parts in λ. For a subset D of Young diagram λ. Define D^{⋄} ⊂ λ to be a subset of elements (ℓ + 1 − i, j), for all (i, j) ∈ D. We refer to D^{⋄} as vertical flipping and consider it only when it is well defined.

A subset D of λ is called a flipped excited diagram if after vertical flipping it is a usual excited diagram, see Figure 9. Let E^{⋄}(λ/μ) be the set of flipped excited diagrams of λ/μ. Note that if λ/μ is slim and D ∈ E(λ/μ), then D^{⋄} ∈ E^{⋄}(λ/μ) is well defined. Thus, |E^{⋄}(λ/μ)| = |E(λ/μ)|. In [MPP3, §3.4], we show that

(Flipped-HLF)  |SYT(λ/μ)| = n! ∑_{D∈E^{⋄}(λ/μ)} ∏_{(i,j)∈λ\D} \frac{1}{h_{λ}(i, j)} ,

where n = |λ/μ|.

Figure 9. Slim skew shape λ/μ, where λ = (9, 8, 6), μ = (2, 1), and the set E^{⋄}(λ/μ) of flipped excited diagrams.

Exercise 9.1. In the context of the lower bound (8.1), prove that

n! ∏_{(i,j)∈λ/μ} \frac{1}{h_{λ}(i, j)} ≥ n! ∏_{(i,j)∈λ/μ^{⋄}} \frac{1}{h_{λ}(i, j)} ,

where μ^{⋄} ⊂ λ denotes the subset of squares of λ obtained by the vertical flip of μ. Conclude that (Flipped-HLF) gives a better upper bound than (8.2).

9.2. The staircase phenomenon. In this section, we follow [MPP5]. Clearly, diagram τ_{k} is not slim. However, we can create two smaller slim diagrams by partitioning δ_{k} into a square ρ_{k/2} and two smaller staircases δ_{k/2}, where k is even. In the right-hand side of (NHLF), consider only excited diagrams which do not move ρ_{k/2}, which are thus restricted to slim shapes. Since the sum over excited diagrams in each slim shape is equal to the sum over flipped excited diagrams, this gives a lower bound on a_{k}.

There are two additional properties of thick ribbons τ_{k} = δ_{2k}/δ_{k} which play a role here. First, because the hooks in δ_{2k} are invariant under flipped excited moves, we conclude that the terms we are summing in the right-hand side of (Flipped-HLF) are all equal. Second, by Exercise 9.3 below, the number of such terms is equal to 2^{\binom{k/2}{2}}, for each of the two slim diagrams. Putting these together, we obtain

a_{2k} ≥ \frac{n! 2^{k(k−1)}}{Ψ(2k + 1) [(2k + 1)!! (2k + 5)!! ⋯ (6k − 3)!!]^{2}} ,

where n = |ν_{2k}| = k(6k + 1). This gives the following.

Lower Bound 9.2 ([MPP5]).

ϕ ≥ \frac{1}{2} − \frac{2 log 2}{3} − \frac{log 3}{4} ≈ −0.2368.

Figure 10. Making two smaller slim diagrams out of thick ribbon τ_{k}, where k is even. Same with three slim diagrams.

Exercise 9.3. Prove that for every slim shape λ/μ, such that μ = δ_{ℓ}, we have |E(λ/μ)| = 2^{\binom{ℓ}{2}}, as in Figure 9. Hint: Use non-intersecting paths as above to give a bijection with domino tilings of the Aztec diamond, see [OEIS, A006125].

Exercise 9.4. Make three slim smaller diagrams as in Figure 10 to obtain another lower bound for ϕ. Is this a better bound?

10. Slanted HLF

10.1. The setup. For a skew shape λ/μ, define a slanted shape λ^{▽}/μ^{▽} as in Figure 11. The slanted excited moves are now vertical moves as in Figure 11, while the squares of λ/μ move diagonally as before. Slanted excited diagrams are defined similarly, see an example in Figure 12, where slanted diagrams are in dark blue. We use E^{▽}(λ/μ) to denote the set of slanted excited diagrams of λ^{▽}/μ^{▽}.

Figure 11. Transforming skew shape λ/μ into a slanted shape λ^{▽}/μ^{▽}, where λ = (7, 7, 6, 4) and μ = (4, 3, 1). Two types of slanted excited moves.

In [MZ] and earlier in a different language in [KT, OO], the authors show that

(Slanted-HLF)  |SYT(λ/μ)| = \frac{n! f^{λ}}{m!} ∑_{D∈E^{▽}(λ/μ)} ∏_{(i,j)∈D} a_{λ}(i, j) ,

where m = |λ|, n = |λ/μ|, f^{λ} = | SYT(λ)| as above, and a_{λ}(i, j) := λ_{i} − j + 1 is the arm length of the square (i, j) ∈ λ.

Exercise 10.1. Suppose the smallest part λ_{ℓ} is at least μ_{1}. Show that in this case E^{▽}(λ/μ) is in bijection with E^{⋄}(λ/μ). Then compare (Slanted-HLF) vs. (Flipped-HLF).

Figure 12. Slanted excited diagrams in E^{▽}(λ/μ), where λ = (6, 5, 3) and μ = (2, 1).

Exercise 10.2. Let λ = δ_{2k} and μ = δ_{k}. For a slanted excited diagram D = μ^{▽}, suppose square (i, j) ∈ D is an image of (p, q) ∈ μ. From (Slanted-HLF), we have

(10.1)  |SYT(λ/μ)| ≥ G(λ/μ) := \frac{n! f^{λ}}{m!} ∏_{(i,j)∈μ^{▽}} a_{λ}(i, j) .

Use this to obtain an explicit lower bound for ϕ.

Exercise 10.3. Check that the arm lengths a_{λ}(i, j) are non-increasing under slanted excited moves. This gives

(10.2)  |SYT(λ/μ)| ≤ G(λ/μ) · |E^{▽}(λ/μ)|.

Exercise 10.4. Using the above notation, observe that a_{λ}(i, j) ≤ h_{λ}(p, q). Conclude that G(λ/μ) ≤ F (λ/μ) for every λ/μ, i.e., the lower bound in (10.1) is never better than the lower bound in (8.1).

10.2. Lower and upper bounds. We follow [MZ, §9.6] in this section. Let λ = δ_{2k+1} and μ = δ_{k+1}, where k is even. As before, let n = |τ_{k+1}|. Define u_{k} := |E^{▽}(λ/μ)|. It follows from (Slanted-HLF) that

(10.3)  a_{k+1} = |SYT(λ/μ)| = n! 2^{n} u_{k} \frac{Φ(3k) Ψ(2k) Ψ(k/2)}{Φ(4k) Ψ(3k/2)} .

By employing ad hoc estimates on u_{k}, see Exercise 10.7 below, one can get the following.

Lower Bound 10.5 ([MZ, Thm. 1.4]).

ϕ ≥ \frac{1}{2} − \frac{9 log 2}{2} + 2 log 3 ≈ −0.4219.

Upper Bound 10.6 ([MZ, Thm. 1.4]).

ϕ ≤ \frac{1}{2} − \frac{13 log 2}{2} + \frac{7 log 3}{2} ≈ −0.1603.

Exercise 10.7 ([MZ, §7.2]). Let

w(μ, ℓ) := |SSYT(μ, ≤ ℓ)| = s_{μ}(1, …, 1) , ℓ ones,

where SSYT(μ, ≤ ℓ) denotes the set of semistandard Young tableaux of shape μ with entries ≤ ℓ. Give an explicit injection to show that

w(δ_{k+1}, k) ≤ u_{k} ≤ w(δ_{k+1}, 2k).

Use Stanley’s hook–content formula [S2, Thm. 7.21.2] to obtain product formulas for w(δ_{k+1}, ℓ). Conclude that

lim inf_{k→∞} \frac{1}{n} log u_{k} ≥ \frac{log 2}{3} ≈ 0.2310 , and
lim sup_{k→∞} \frac{1}{n} log u_{k} ≤ \frac{3 log 3}{2} − \frac{5 log 2}{3} ≈ 0.4927 .

Use these to derive the Upper Bound 10.6 and the Lower Bound 10.5. Note that lim_{k→∞} \frac{1}{n} log u_{k} exists by Exercise 12.4, but this result is not needed to prove the bounds.

Exercise 10.8. Let λ = ρ_{2k} and μ = ρ_{k} be two square shapes. Compare the bounds given by (Slanted-HLF) vs. (NHLF) for the thick hook ϱ_{k} = λ/μ.

11. Additional exercises

11.1. General bounds.

Exercise 11.1. Follow up on the discussion in §2.1 and prove an upper bound for general f^{λ/μ} from the Aitken–Feit determinant formula (2.2).

Exercise 11.2 ([McK]). Recall the identity

∑_{λ⊢n} f^{λ} = v_{n} ,

where v_{n} = |{σ ∈ S_{n}, σ^{2} = 1}| is the number of involutions in S_{n}, see e.g. [OEIS, A000085]. Use this identity to conclude (2.4). Which approach gives a better upper bound for the constant c in (2.5)? Explain why.

Exercise 11.3. Find a closed form EGF for {v_{n}}. Prove that it is D-finite.

Exercise 11.4 ([VK2]). Prove that

D_{n} ≤ \sqrt{n!} e^{−c\sqrt{n}} for some c > 0,

cf. (2.5). Conclude that “most” dimensions f^{λ} are much smaller than D_{n}.

Exercise 11.5. In the context of §2.3, check that

|SYT(k^{2k})| > (k!)^{k+1} |SYT(δ_{k})|^{2} > |SYT(k^{k})|^{2}.

Exercise 11.6. Prove that for every series parallel poset P = (P, ≺), we have

e(P) = ∏_{x∈X} \frac{1}{br(x)} ,

where e(P) is the number of linear extensions of P. Conclude the HLF for trees.

Exercise 11.7 ([SK]). Let B_{n} denote the Boolean lattice, the poset of all subsets of [n] ordered by inclusion. Use induction to prove that B_{n} has a partition into \binom{n}{⌊n/2⌋} saturated chains. Use this partition to obtain an upper bound for e(B_{n}). Compare this bound with the lower bound obtained via the natural partition of B_{n} into (n + 1) antichains.

Exercise 11.8. In §7.3, we used a simple f^{ν} ≤ \sqrt{(n − m)!} inequality to obtain an upper bound. Using the fact that we must have ν_{1}, ℓ(ν) ≤ 2k and the result in [LS], give a better upper bound for f^{ν}, and then for ϕ.

Exercise 11.9. Let ν be a collection of squares in ℕ^{2}, such that ν ⊂ [k] × [k] and n := |ν| > ϵk^{2} for some fixed ϵ > 0. Use chains and antichains bounds to prove that log | SYT(ν)| = \frac{1}{2}n log n + O(n).

Exercise 11.10. Fix d ≥ 3, and let ν be a collection of squares in [k]^{d}, and n := |ν| > ϵk^{d} for some fixed ϵ > 0. Generalize standard Young tableaux to d-dimensional space, and prove that log | SYT(ν)| = \frac{d−1}{d} n log n + O(n) bound.

Exercise 11.11. Let H_{k} ⊂ ℕ^{3} be the k × k × k cube. Use partition of H_{k} into k layers of k × k squares ρ_{k} to give an upper bound for the constant implied by the O(n) notation in the previous exercise. Compare it with the chain upper bound.

Exercise 11.12. What is the cost of computing a_{k} using the Aitken–Feit determinant formula? Do this carefully.

11.2. More skew shapes. Exercise 11.13. Note that c_{k} := | SYT(ρ_{2k−1}/δ_{k})| can be computed by the HLF. Show that a_{k} b_{2k−1} ≤ c_{k}. Hint: See Figure 13. Use this inequality to derive an explicit upper bound on ϕ.

Exercise 11.14. Recall (or compute directly) the asymptotics for | SYT(ρ_{k}|, see e.g. [OEIS, A039622]. Consider two more partitions of a square as in Figure 13 and find the upper bounds on ϕ. Compare them with the bound in the previous exercise. Is it clear a priori which bound is better?

Exercise 11.15. Use the approach in (6.2) to get an upper bound for | SYT(ϱ_{k})| for the thick hook ϱ_{k} := ρ_{2k}/ρ_{k}. Compare with the true value given by the HLF.

Exercise 11.16. Use the approach in (6.2) to get an upper bound for | SYT(ς_{k})| for the DeWitt shape ς_{k} = δ_{4k}/ρ_{k}. Compare with the actual asymptotics.

Figure 13. Three partitions of a square and a thick hook ϱ_{k} := ρ_{2k}/ρ_{k}.

Exercise 11.17 (see [MPP4, §9.2]). Use (8.1) for the thick hook ϱ_{k} := ρ_{2k}/ρ_{k}. How good is the resulting lower bound? Compare with upper bound first using non-intersecting paths, and then with the exact asymptotics given by the MacMahon box formula for M(k, k, k), see e.g. [OEIS, A008793].

Exercise 11.18. Explain the similarity of asymptotics in Exercises 8.6 and 11.17 on the level of lozenge tilings of the hexagon, and then on the level of standard Young tableaux. Can you make the connection formal, at least in one direction?

Exercise 11.19. A remarkable result by Lam, Postnikov and Pylyavskyy [LPP, Thm. 5] gives an inequality for LR-coefficients. Translate this result into asymptotic language for unions and intersections of skew shapes.

11.3. Other shapes in the plane.

Exercise 11.20. Recall the shifted analogue of the HLF for shifted shapes, see e.g. [S2, §7.21] and [Sag, p. 139]. Use it to compute the asymptotics of the shifted staircase as in Figure 14. Check your calculations here: [OEIS, A003121]

Exercise 11.21. Define a θ-truncated square η_{k,θ} as in Figure 14, obtained by removing a shifted triangle of size θk from a k-square. Use the chain and the antichain partitions to prove that

log |SYT(η_{k,θ})| = \frac{1}{2} n log n + O(n),

where n = k^{2} − \frac{θk}{2} is the size of η_{k,θ}, and the constants implied by the O(·) notation can depend on θ. Now use formulas in [Pan] (see also [AR, §8.2]), to prove that O(n) can be replaced with c(θ)n + o(n), and compute the exact formula for c(θ). Explain why c(θ) is monotone on [0, 1].

Exercise 11.22. Define a θ-truncated triangle and a double θ-truncated square η_{k,θ} as in Figure 14. Give upper and lower bounds for the corresponding asymptotic constant.

Exercise 11.23. Partition the square into a shifted staircase and a θ-truncated square, see Figure 14. Use this to get an upper bound for c(θ). Explain why this upper bound is sharper than the corresponding chain partition bound.

Exercise 11.24. Consider a skew shifted staircase as in Figure 14. Use the shifted analogue of the NHLF, see [MPP3, §9.5] and [NO], to get the lower and upper bounds on the corresponding asymptotic constant. Partition the shifted staircase into a smaller shifted staircase and a skew shifted staircase. Use the shifted HLF for the shifted staircase, see Exercise 11.20, to derive an upper bound from this outpartition. Which bound is better?

Figure 14. \underline{First row}: shifted staircase, truncated square, truncated triangle, double truncated square, two partitions of a square, and a skew shifted staircase. \underline{Second row}: partition of a shifted staircase, partition of a square 4-octagon, two partitions and one outpartition of an octagon.

Exercise 11.25. Consider a k-octagon ω_{k}, defined as the difference of a square ρ_{3k} and four rotated staircases δ_{k}. Use two partitions in Figure 14 to obtain lower bounds on the number of standard Young tableaux of the k-octagon via exact formulas for shifted staircases and truncated squares, see above. Try to guess which bound is sharper before the calculation, and check if your guess is confirmed by the calculation.

Exercise 11.26. Use a 5-ribbon partition to get yet another lower bound for k-octagons ω_{k}. Compare with the bound in the previous exercise.

Exercise 11.27. Use an outpartition as in Figure 14 to get an upper bound for k-octagons ω_{k}. Compare with the chain upper bound.

Exercise 11.28. Consider the plane region B_{k} of squares which fit the circle of radius k. Read about the Gauss circle problem. Prove that

log |SYT(B_{k})| = \frac{1}{2} n log n + O(n),

where n = |B_{k}| ∼ πk^{2}. Do you think that O(n) can be replaced with cn + o(n)?

Exercise 11.29. Find two subsets of squares D, D′ ⊂ ℕ^{2} which are equal up to a permutation of rows and columns, and | SYT(D)| ≠ | SYT(D′)|. Generalize the Young symmetrizer to obtain the corresponding S_{n}-characters χ^{D} = χ^{D′}. Conclude that we do not always have χ^{D}(1) = | SYT(D)|, and the Algebraic Combinatorics technology no longer applies.

Exercise 11.30. Use the #P-completeness of | SYT(D)| proved in [DP], to argue why the determinant formula is unlikely to extend for general D.

12. Conjectures and open problems

12.1. Enumeration. Recall the definitions of classes of GFs from [P2, S2].

Open Problem 12.1 (see §5.2). Prove that the exponential generating function (EGF) for F_{m}^{(r)} is D-algebraic (ADE), for every fixed r > 1.

Open Problem 12.2 (see §2.1). Prove that the EGF A(t) given by (2.1) is not D-finite.

12.2. Slanted exciting diagrams and lozenge tilings. We start with some unfinished business.

Open Problem 12.3 (see §10.2). Improve the upper bound on u_{k} = |E^{▽}(τ_{k+1})|.

Note that even a relatively small improvement of the Upper Bound 10.6 can perhaps give a bound better than Upper Bound 6.1.

Exercise 12.4. Prove that u_{k} is equal to the number of lozenge tilings of a region Γ_{k} as in the Figure 15. Note that asymptotically, after the region Γ_{k} is scaled by \frac{1}{k} in both directions, this gives a piecewise linear region. Use the technology in [Gor2] to prove the existence of lim_{k→∞} \frac{1}{k^{2}} log u_{k}. Use (10.3) to conclude Theorem 1.1.

Thus, Main Theorem 1.2 is equivalent to the following.

Open Problem 12.5. Compute lim_{k→∞} \frac{1}{k^{2}} log u_{k} .

Figure 15. Region Γ_{k} with u_{k} lozenge tilings for k = 3.

12.3. Limits for general shapes. The main result in [MPT] of which Theorem 1.1 is a corollary, proves existence of the limit

(12.1)  lim_{n→∞} \frac{1}{n} [log |SYT(λ/μ)| − \frac{1}{2} n log n] ,

where the skew shape λ/μ is obtained from a piecewise smooth region in the plane, scaled by \sqrt{n}. For (usual) Young diagram shapes this follows easily from the (HLF), see [MPP4].

Conjecture 12.6. The limit (12.1) holds for general piecewise smooth regions, not just for skew shapes.

This conjecture extends Exercise 11.9. It is open even in the special case of k-octagons.

Conjecture 12.7. Prove that for k-octagons ω_{k} with n = 9k^{2} − 4\binom{k}{2} we have

log |SYT(ω_{k})| = \frac{1}{2} n log n + cn + o(n) as k → ∞,

for some c ∈ ℝ.

In ℝ^{d}, the analogous conjecture is likely to hold as well but is open even for 3dimensional Young diagram shapes (also called solid partitions).

Conjecture 12.8. Let S ⊂ ℝ_{+}^{3} be a 3-dimensional piecewise linear shape, such that (a, b, c) ∈ S implies (x, y, z) ∈ S for all x ≤ a, y ≤ b, z ≤ c. Then there is a limit:

(12.2)  lim_{n→∞} \frac{1}{n} [log |SYT(Λ_{n})| − \frac{2}{3} n log n] ,

where the shape Λ_{n} is obtained by a scaling of S by \sqrt[3]{n}.

Even in the special case of a 3-dimensional cube this conjecture is open, and is especially attractive.

Conjecture 12.9. Let H_{k} ⊂ ℕ^{3} be a k × k × k cube. Then there is a limit:

(12.3)  lim_{n→∞} \frac{1}{k^{3}} [log |SYT(H_{k})| − 2k^{3} log k].

In view of §2.3, we also conjecture the existence of the limit surfaces for the shapes of integers ≤ αn in random A ∈ SYT(Λ_{n}). It would be exciting to prove this even for the cube, but this goes beyond the scope of this paper.

13. Brief historical remarks

The study of Young tableaux goes back to the works of Alfred Young (c. 1900), and is so extensive that a quick overview would not give it justice. We refer to the extensive Ch. 7 in [S2] which gives a thorough overview of the subject, textbook [Sag] for the friendly introduction, and to [AR] for an extensive survey of enumerative results. See also [DP] for complexity aspects and the recent #P-completeness of | SYT(D)| for general D ⊂ ℕ^{2} (cf. Exercise 11.30).

The hook-length formula goes back to Thrall (1952) and Frame–Robinson–Thrall (1954). It has been reproved and generalized in numerous ways. We refer to [CKP, §6.2] for a survey. Similarly, the Littlewood–Richardson coefficients are classical and go back to the 1930s. They are the subject of intensive investigation in its own right with many generalizations and variations. We refer to [vL] for a somewhat dated but helpful entry point, and to [PPY] for a recent asymptotic analysis based in part on some earlier observations by Stanley.

The study of limit shapes and the Vershik–Kerov–Logan–Shepp theory is in itself a subject of intensive investigation. We refer to [Rom] for a thorough treatment and connections to longest increasing subsequences in random permutations. A related followup story of random lozenge tilings, the Arctic circle phenomenon, etc., is well presented in [Gor2]. It relates to the subject of this paper in connection with excited diagrams, and provides the motivation for many of the limit questions and conjectures above.

The equation (NHLF) is in an unpublished work by Naruse, and is discussed at length in [MPP1, MPP2]. We refer to [Kon, MPP2] for elementary proofs, to [MPP1, §9] for a survey of other formulas for f^{λ/μ} = | SYT(λ/μ)|, to [MPP3, §9] for a variety of other exact formulas (some conjectured and proved in later work by other authors), and to [NO] for further generalizations. The asymptotic applications of (NHLF) were first introduced in [MPP4], and advanced in [MPP3, MZ].

Despite superficial similarities, our two variations on (NHLF) have very different nature. Equation (Flipped-HLF) is given in [MPP3, §3] and further explored in [MPP5]. A simple proof via reduction to (NHLF) is given in [PP]. Equation (Slanted-HLF) is due to Morales and Zhu [MZ], and is equivalent to the Okounkov–Olshanski formula [OO] (see also [S1]). In [MZ], the authors also give a simple proof, and establish a previously conjectured equivalence to the rule in [KT].

In conclusion, let us mention that the unusual style of this paper borrows ideas from several sources. First, we are heavily influenced by the brief exercise-based presentation by Lovász [Lov], which is itself a continuation of a long tradition, see e.g. the celebrated problem books by Pólya–Szegő (1925) and Yaglom–Yaglom (1954). Second, we learned the value of worked out publishable examples clarifying the theory from the Pemantle– Wilson papers, see [PW]. Third, while the idea of a “running example” is standard, we personally were influenced by Krattenthaler’s presentation [K4].

Acknowledgements. We are grateful to Alejandro Morales, Greta Panova and Martin Tassy for numerous interesting conversations. Much of this paper grew from our previous work in the area. We are also thankful to Sam Dittmer, Anna Gordenko, Vadim Gorin, Victor Kleptsyn, Fëdor Petrov, Leo Petrov, Dan Romik, Richard Stanley, Anatoly Vershik and Damir Yeliussizov for helpful comments on the subject. Special thanks to Christian Krattenthaler for careful reading of the paper and for the kindness he extended to us over the years. The author was partially supported by the NSF.

References

[AR] R. Adin and Y. Roichman, Standard Young tableaux, in Handbook of Enumerative Combinatorics (M. Bóna, editor), CRC Press, Boca Raton, 2015, 895–974.

[Ait] A. C. Aitken, The monomial expansion of determinantal symmetric functions, Proc. Roy. Soc. Edinburgh, Sect. A 61 (1943), 300–310.

[BR] Y. Baryshnikov and D. Romik, Enumeration formulas for Young tableaux in a diagonal strip, Israel J. Math. 178 (2010), 157–186.

[Ber] I. Berlin, Anything you can do, in Annie Get Your Gun, Broadway, New York, 1946.

[BP1] I. A. Bochkov and F. V. Petrov, The bounds for the number of linear extensions via chain and antichain coverings, Order, published online 22 Oct. 2020, 6 pp.

[BP2] A. Borodin and L. Petrov, Lectures on Integrable probability: Stochastic vertex models and symmetric functions, in Stochastic processes and random matrices, Oxford Univ. Press, Oxford, 2017, 26–131.

[CS] L. Carlitz and R. Scoville, Enumeration of rises and falls by position, Discrete Math. 5 (1973), 45–59.

[CKP] I. Ciocan-Fontanine, M. Konvalinka and I. Pak, The weighted hook length formula, J. Combin. Theory, Ser. A 118 (2011), 1703–1717.

[DeW] E. A. DeWitt, Identities relating Schur s-functions and Q-functions, Ph.D. thesis, University of Michigan, 2012, 73 pp.; available at https://tinyurl.com/y9ktq5v7.

[DP] S. Dittmer and I. Pak, Counting linear extensions of restricted posets, Electron. J. Combin. 27 (2020), issue 4, #P4.48, 13 pp.

[Feit] W. Feit, The degree formula for the skew-representations of the symmetric group, Proc. Amer. Math. Soc. 4 (1953), 740–744.

[FS] P. Flajolet and R. Sedgewick, Analytic combinatorics, Cambridge Univ. Press, Cambridge, 2009, 810 pp.

[FRT] J. S. Frame, G. de B. Robinson and R. M. Thrall, The hook graphs of the symmetric group, Canad. J. Math. 6 (1954), 316–324.

[Gor1] A. Gordenko, Limit shapes of large skew Young tableaux and a modification of the TASEP process, preprint (2020), 43 pp., arXiv:2009.10480.

[Gor2] V. Gorin, Lectures on Random Lozenge Tilings, Cambridge Univ. Press, Cambridge, UK, 2021, 249 pp.; monograph draft is available at https://tinyurl.com/w22x6qq.

[Gow] W. T. Gowers, The two cultures of mathematics, in Mathematics: frontiers and perspectives, Amer. Math. Soc., Providence, RI, 2000, 65–78.

[H+] Z. Hamaker, A. H. Morales, I. Pak, L. Serrano and N. Williams, Bijecting hidden symmetries for skew staircase shapes, preprint (2021), 19 pp.; arXiv:2103.09551.

[HP] A. Hammett and B. Pittel, How often are two permutations comparable? Trans. Amer. Math. Soc 360 (2008), 4541–4568.

[KP] S. Kerov and A. M. Pass, Representations of symmetric groups with maximal dimension, J. Soviet Math. 59 (1992), 1131–1135.

[KT] A. Knutson and T. Tao, Puzzles and (equivariant) cohomology of Grassmannians, Duke Math. J. 119 (2003), 221–260.

[Kon] M. Konvalinka, A bijective proof of the hook-length formula for skew shapes, Europ. J. Combin. 88 (2020), 103104, 14 pp.

[K1] C. Krattenthaler, Advanced determinant calculus, Sém. Lothar. Combin. 42 (1999), Art. B42q, 67 pp.

[K2] C. Krattenthaler, Advanced determinant calculus: a complement, Linear Algebra Appl. 411 (2005), 68–166.

[K3] C. Krattenthaler, Plane partitions in the work of Richard Stanley and his school, in The mathematical legacy of Richard P. Stanley, Amer. Math. Soc., Providence, RI, 2016, 231–261.

[K4] C. Krattenthaler, Advanced determinant calculus, talk at Asymptotic Algebraic Combin., BIRS, Banff, Canada, 14 March 2019; talk slides: https://tinyurl.com/y5nxe3bo.

[KS] C. Krattenthaler and M. Schlosser, The major index generating function of standard Young tableaux of shapes of the form “staircase minus rectangle”, Contemp. Math. 627 (2014), 111– 122.

[LPP] T. Lam, A. Postnikov and P. Pylyavskyy, Schur positivity and Schur log-concavity, Amer. J. Math. 129 (2007), 1611–1622.

[LS] B. F. Logan and L. A. Shepp, A variational problem for random Young tableaux, Adv. Math. 26 (1977), 206–222.

[Lov] L. Lovász, Combinatorial problems and exercises, Amer. Math. Soc., Providence, RI, 2007, 642 pp.

[McK] J. McKay, The largest degrees of irreducible characters of the symmetric group, Math. Comp. 30 (1976), 624–631.

[MPP1] A. H. Morales, I. Pak and G. Panova, Hook formulas for skew shapes I. q-analogues and bijections, J. Combin. Theory, Ser. A 154 (2018), 350–405.

[MPP2] A. H. Morales, I. Pak and G. Panova, Hook formulas for skew shapes II. Combinatorial proofs and enumerative applications, SIAM Jour. Discrete Math. 31 (2017), 1953–1989.

[MPP3] A. H. Morales, I. Pak and G. Panova, Hook formulas for skew shapes III. Multivariate and product formulas, Algebraic Combin. 2 (2019), 815–861.

[MPP4] A. H. Morales, I. Pak and G. Panova, Asymptotics of the number of standard Young tableaux of skew shape, Europ. J. Combin. 70 (2018), 26–49.

[MPP5] A. H. Morales, I. Pak and G. Panova, unpublished.

[MPT] A. H. Morales, I. Pak and M. Tassy, Asymptotics for the number of standard tableaux of skew shape and for weighted lozenge tilings, preprint (2018), 22 pp.; arXiv:1805.00992.

[MZ] A. H. Morales and D. G. Zhu, On the Okounkov–Olshanski formula for standard tableaux of skew shapes, preprint (2020), 37 pp.; arXiv:2007.05006.

[NO] H. Naruse and S. Okada, Skew hook formula for d-complete posets via equivariant K-theory, Algebraic Combin. 2 (2019), 541–571.

[NPS] J.-C. Novelli, I. Pak and A. V. Stoyanovskii, A direct bijective proof of the hook-length formula, Discrete Math. Theor. Comput. Sci. 1 (1997), 53–67.

[Odl] A. M. Odlyzko, Asymptotic enumeration methods, in Handbook of combinatorics, vol. 2, Elsevier, Amsterdam, 1995, 1063–1229.

[OO] A. Okounkov and G. Olshanski, Shifted Schur functions, St. Petersburg Math. J. 9 (1998), 239–300.

[P1] I. Pak, Hook length formula and geometric combinatorics, Sém. Lothar. Combin. 46 (2001), Art. B46f, 13 pp.

[P2] I. Pak, Complexity problems in enumerative combinatorics, in Proc. ICM (Rio de Janeiro), vol. 3, 2018, 3139–3166; expanded version at arXiv:1803.06636.

[PPY] I. Pak, G. Panova and D. Yeliussizov, On the largest Kronecker and Littlewood–Richardson coefficients, J. Combin. Theory, Ser. A 165 (2019), 44–77.

[PP] I. Pak and F. Petrov, Hidden symmetries of weighted lozenge tilings, Electron. J. Combin. 27 (2020), issue 3, #P3.44, 18 pp.

[PPS] I. Pak, F. Petrov and V. Sokolov, Hook inequalities, Math. Intelligencer 42 (2020), no. 2, 1–8.

[Pan] G. Panova, Tableaux and plane partitions of truncated shapes, Adv. Appl. Math. 49 (2012), 196–217.

[PW] R. Pemantle and M. C. Wilson, Twenty combinatorial examples of asymptotics derived from multivariate generating functions, SIAM Rev. 50 (2008), 199–272.

[PR] B. Pittel and D. Romik, Limit shapes for random square Young tableaux, Adv. Appl. Math. 38 (2007), 164–209.

[Pro] R. A. Proctor, New symmetric plane partition identities from invariant theory work of De Concini and Procesi, Europ. J. Combin. 11 (1990), 289–300.

[RV] A. Regev and A. Vershik, Asymptotics of Young diagrams and hook numbers, Electron. J. Combin. 4 (1997), no. 1, #RP 22, 12 pp.

[Rom] D. Romik, The surprising mathematics of longest increasing subsequences, Cambridge Univ. Press, New York, 2015, 353 pp.

[Sag] B. E. Sagan, The symmetric group, Springer, New York, 2001, 238 pp.

[SK] J. Sha and D. J. Kleitman, The number of linear extensions of subset ordering, Discrete Math. 63 (1987), 271–278.

[OEIS] N. J. A. Sloane, The online encyclopedia of integer sequences, oeis.org.

[S1] R. P. Stanley, On the enumeration of skew Young tableaux, Adv. Appl. Math. 30 (2003), 283– 294.

[S2] R. P. Stanley, Enumerative combinatorics, Cambridge Univ. Press, vol. 1 (second ed.), 2012, 626 pp., and vol. 2, 1999, 581 pp.

[S3] R. P. Stanley, A survey of alternating permutations, in Combinatorics and graphs, Amer. Math. Soc., Providence, RI, 2010, 165–196.

[Sun] W. Sun, Dimer model, bead and standard Young tableaux: finite cases and limit shapes, preprint

        (2018), 67 pp.; arXiv:1804.03414.

[TV] T. Tao and V. H. Vu, Additive combinatorics, Cambridge Univ. Press, Cambridge, 2006, 512 pp.

[Tro] W. T. Trotter, Partially ordered sets, in Handbook of combinatorics, Vol. 1, Elsevier, Amsterdam, 1995, 433–480.

[vL] M. A. A. van Leeuwen, The Littlewood–Richardson rule, and related combinatorics, in Math. Soc. Japan Memoirs 11, Tokyo, 2001, 95–145.

[VK1] A. M. Vershik and S. V. Kerov, The asymptotic character theory of the symmetric group, Funct. Anal. Appl. 15 (1981), 246–255.

[VK2] A. M. Vershik and S. V. Kerov, Asymptotic of the largest and the typical dimensions of irreducible representations of a symmetric group, Funct. Anal. Appl. 19 (1985), 21–31.