13
$\begingroup$

There are Catalan number $C_n$ of standard Young tableaux of shape $(n,n)$, which we view as $2\times n$ matrices. Denote by $P_n$ the average of these matrices: $$ P_n \, := \, \frac{1}{C_n} \, \sum_{A \, \in \, \text{SYT}(n,n)} A $$ Note that $P_n=(p_{ij})$ is a rational matrix with entries monotone increasing in rows and columns. Also, by the 180$^\circ$ rotational symmetry, $p_{ij} + p_{3-i,n+1-j} = 2n+1$. For example, $p_{11}=1$, $p_{2n}=2n$.

The asymptotic density of $P_n$ as $n\to \infty$ is easy to obtain by a direct calculation or via the Brownian excursion (see e.g. here or there), but my question is different.

Question. Let $\beta(n):= \min_{(ij)\ne (kl)} |p_{ij}-p_{kl}|$. Is it true that $\beta(n) = o(1)$?

It would be cool if there was an easy way to see this. I really want a generalization of this result to all large partitions, but at the moment even this is confounding.

UPDATE (May 18, 2019):
Let me explain the motivation behind the question. Recall the 1/3-2/3 conjecture that every poset $\mathcal P=(X,\prec)$ that is not a linear order contains two elements $x,y\in X$ such that $$\frac13 \le P(x\prec y) \le \frac23 $$ For width 2 posets this was shown by Linial in this paper, but I thought that for shapes $(n,n)$ one can improve $1/3$ to perhaps $(1/2-\varepsilon)$, since we know so much about Catalan numbers (including the average of Catalan objects). Linial's proof cannot be easily improved, unfortunately. Now, a beautiful Kahn-Linial proof of the weaker $1/2e$ bound starts with the average LE of $\mathcal P$. If $\beta(n)=o(1)$, their argument plus the (earlier) Grünbaum Theorem implies the $(1/e-\varepsilon)$ bound, already a nice result.

Now, Richard's calculaitons give $p_{17} \to 9949/1024 \approx 9.7158$, $p_{23} \to 9.75$. This means that taking $x=(1,7)$ and $y=(2,3)$ in $(n,n)$ gives $$0.3553 < \frac1e \left(1-\frac{35}{1024}\right) < P(x\prec y) < \frac2e \left(1+\frac{35}{1024}\right) < 0.6447 $$ for $n$ large enough (unless I miscalculated). This improvement over $1/3$ bound is good to know, but surely one can do better.

UPDATE (May 27, 2020):
In our most recent paper we found an upper bound $O\bigl(n^{-5/4}\bigr)$ for the sorting probability for these Catalan posets. This problem was stated in the previous update. Note that we obtained only the upper, but not the lower bounds!

Swee Hong Chan, Igor Pak, Greta Panova,
Sorting probability of Catalan posets, preprint, 2020.

$\endgroup$
9
  • 1
    $\begingroup$ Another trivial observation that might be useful is that $p_{i,j} \geq p_{i-1,j} + 1$ and $p_{i,j} \geq p_{i,j-1} + 1$. $\endgroup$ May 15, 2019 at 15:48
  • $\begingroup$ Observation 1: for $n \leq 12$: the minimum is obtained at a unique pair $(i,j) \neq (k,l)$ and its 180°-rotation counterpart. $\endgroup$ May 15, 2019 at 16:07
  • $\begingroup$ Observation 2: $|p_{14} - p_{22}| \leq 1$ and $|p_{12}-p_{21}| \leq 2$ for all $4 \leq n \leq 13$, so either of these pairs might be a candidate for a witness for an affirmative answer to your question. $\endgroup$ May 15, 2019 at 16:08
  • $\begingroup$ @ChristianStump: I seriously doubt $(p_{12},p_{21})$ could work. $\endgroup$ May 15, 2019 at 16:20
  • 1
    $\begingroup$ @ChristianStump: $a_{12}$ will be greater than $a_{21}$ (by only 1) about $1/4$ of the time, because there are $C_{n-1}$ tableaux where the first column is $1,2$. But $a_{21}$ will be greater than $a_{12}$ by at least 1, and in fact sometimes much more, about $3/4$ of the time. So $p_{21}-p_{12}$ is gonna be at least $1/2$, not $o(1)$. $\endgroup$ May 15, 2019 at 16:39

1 Answer 1

7
$\begingroup$

This is not a solution, but rather a long comment. Let $f^{a,b}$ denote the number of standard Young tableaux (SYT) of shape $(a,b)$. The number of SYT $T$ of shape $(n,n)$ with $T_{1d}=k$ is $f^{d-1,k-d}f^{n-k+d,n-d}$. Hence $$ p_{1d} = \frac{1}{C_n}\sum_{k=d}^{2d-1} kf^{d-1,k-d}f^{n-k+d,n-d}. $$ There is a similar formula for $p_{2,d}$, though the number of terms in the sum increases as $n\to\infty$. In particular, \begin{eqnarray*} p_{12} & = & \frac{1}{C_n}\left( 2f^{n,n-2}+3f^{n-1,n-2}\right)\\ & = & \frac{1}{C_n}\left( \frac{2\cdot 3(2n-2)!}{(n+1)!(n-2)!} +\frac{3\cdot (2n-2)!}{n!(n-1)!}\right)\\ & = & \frac{3(3n-1)}{2(2n-1)}. \end{eqnarray*} Write $\bar{p}_{ij}=\lim_{n\to\infty}p_{ij}$ (assuming this limit exists, which I believe is always the case). Thus $\bar{p}_{12}=\frac 94$.

Similarly, $$ p_{21} = \frac{1}{C_n}\left( \sum_{k=2}^{n+1} kf^{n-1,n-k+1}\right). $$ Now \begin{eqnarray*} \frac{f^{n-1,n-k+1}}{C_n} & = & \frac{(2n-k)!(k-1)n!(n+1)!}{n!(n-k+1)!(2n)!}\\ & \to & \frac{k-1}{2^k}. \end{eqnarray*} Thus (assuming we can interchange a limit and an infinite sum) $$ \bar{p}_{21} = \sum_{k\geq 2}\frac{k(k-1)}{2^{k-1}} = 4 $$ (modulo computational error). In general, $\bar{p}_{1d}$ will be given by a finite sum, and $\bar{p}_{2d}$ by an infinite series.

Addendum. I worked out $\bar{p}_{1d}$ in general, namely, \begin{eqnarray*} \bar{p}_{1d} & = & \sum_{k=d}^{2d-1} k(2d-k+1)f^{d-1,k-d}2^{-k}\\ & = & 2^{-2d+1}(d+1)\left(4^d-{2d+1\choose d}\right). \end{eqnarray*} Beginning with $d=2$, the numbers are $$ \frac 94,\ \frac{29}{8},\ \frac{325}{64},\ \frac{843}{128},\ \frac{4165}{512},\ \frac{9949}{1024},\ \frac{185517}{16384},\dots. $$ We can also write $$ \bar{p}_{1,d-1} =2d-\frac{d{2d\choose d}}{4^{d-1}}. $$

Addendum #2. I worked out $\bar{p}_{2d}$. If my computation is correct, then $$ \bar{p}_{2d} = 2d+\frac{d{2d\choose d}}{4^{d-1}}. $$ Compare with the formula for $\bar{p}_{1,d-1}$ above.

Is there a less computational reason for such simple formulas? Do they extend to shapes other than $n(1,1)$, e.g., $n(1,1,1)$ or $n(2,1)$?

$\endgroup$
7
  • 1
    $\begingroup$ Richard, nope - I had a completely different thought. It is quite likely that for some number theoretic reason you don't have a coincidence of the kind you are describing. Rather, when looking at $(p_{1j} - 2j)$ and scaling everything to $[0,1]$ interval you get density given by the semicircle projection. Same for $(p_{2j} - 2j)$ but the semicircle is concave, not convex. Instead of looking at the beginning $j=O(1)$ as you suggest, look at the middle range. There is no obvious relation between two sets of values, so one would guess that $\beta(n) = O(1/\log n)$. $\endgroup$
    – Igor Pak
    May 16, 2019 at 6:02
  • $\begingroup$ One more thing - if you make denominators $4^n$, the numerator sequence is known and computed rather far: oeis.org/A018218 If the other sequence is also known, more values can be checked. $\endgroup$
    – Igor Pak
    May 16, 2019 at 6:39
  • 2
    $\begingroup$ Echoing what Igor is saying, it seems conceivable that $\beta(n) = o(1)$ without having $\overline{p}_{ij}=\overline{p}_{kl}$ for any $ij, kl$ because there could be e.g. a sequence $(a_n,b_n)$ of indices depending on $n$ with $|p_{1a_{n}} - p_{2b_n}| = o(1)$. $\endgroup$ May 16, 2019 at 15:48
  • $\begingroup$ Asymptotically, Richard's formulas give $2d\pm c\sqrt{d}$ formula which look exactly right from the semicircle POV. $\endgroup$
    – Igor Pak
    May 18, 2019 at 19:57
  • 2
    $\begingroup$ @SamHopkins: Indeed, let $n\to \infty$. Let $a(d) := \overline p_{1d}$, $b(d):=\overline p_{2,d}$. Then $a(d) = 2d-c\sqrt{d} - c' + O(1/\sqrt{d})$, $b(d) = 2d+c/\sqrt{d} + c' + O(1/\sqrt{d})$, for some explicit $c,c'$. Then one should be looking at the fractional part of $a(d+\sqrt{d})-b(d) = 2c\sqrt{d} +c'' + O(1/\sqrt{d})$. It seems, $\sqrt{n}$ mod 1 is ergodic and rates of convergence are relatively well understood arxiv.org/abs/1311.6387 Thus, if one is careful one can possibly derive $\beta(n) = o(1)$ from here. $\endgroup$
    – Igor Pak
    May 18, 2019 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.