In connection with string theory I encountered the following problem:

Given the set M_N of all semi-standard Young tableaux of size N (i.e. all fillings of Ferrers diagrams with natural numbers with weakly increasing rows and strictly increasing columns, the content of which sum to N).

The conjecture, which I cannot prove and for which I know no counterexample states:

M_N is the union of disjoint families, where each family consists of a father diagram and all his daughters, which are obtained from the father diagram by deletion of one box.

The conjecture holds for N<=8

http://www.itp.uni-hannover.de/~dragon/young.ps or


There numbers a,b are attached to the Ferrers diagrams, where a is the number of semi-standard Young Tableaux of size N and b the number of fathers, who remain after the daughters have filled up their families.

Light cone string theory proves that the conjecture holds for all M_N with less than 25 rows, i.e. for N < 325. But string theory provides no counterexample for N >= 325.

Any suggestions, e.g. how to compute the number a(N,lambda) of Young diagrams with size N and shape lambda, would be helpful.

Norbert Dragon

-- http://www.itp.uni-hannover.de/~dragon/

Superstition brings bad luck.

  • $\begingroup$ I do not understand the statement of the conjecture. How do you obtain the daughters precisely? $\endgroup$ – Martin Rubey May 6 '13 at 16:10
  • $\begingroup$ The daughters are obtained from their father diagram by removing one box, e.g. the diagram 3,2,1 has daughters 2,2,1 and 3,1,1 and 3,2. The looked for families of father and daughter diagrams characterize the SO(D-2)representations in string theory which are needed for the construction of SO(D-1) representations. $\endgroup$ – Norbert Dragon May 6 '13 at 16:50

I use standard facts about symmetric functions that can be found, e.g, in Chapter 7 of Enumerative Combinatorics, vol. 2. Let $s_\lambda$ denote a Schur function and $p_1=s_1=x_1+x_2+\cdots$. Then $\frac{\partial s_\lambda}{\partial p_1}=\sum_\mu s_\mu$, where the $\mu$'s are obtained by removing a single box from $\lambda$. Moreover, the coefficient of $q^n$ in $s_\lambda(q,q^2,q^3,\dots)$ is equal to the number of SSYT with entries summing to $n$. Thus if we let $c_n$ be the coefficient of $q^n$ in the symmetric function $f$ defined by $$ f+\frac{\partial}{\partial p_1}f = \sum_\lambda s_\lambda\cdot s_\lambda(q,q^2,q^3,\dots), $$ and if $c_n=\sum a_{\mu,n}s_\mu$, then we need $a_{\mu,n}$ copies of the shape $\mu$ in a set of fathers generating all SSYT with entries summing to $n$. Hence we need to show that $a_{\mu,n}\geq 0$. Now $$ \sum_\lambda s_\lambda\cdot s_\lambda(q,q^2,q^3,\dots) = \exp \sum_{n\geq 1} \frac{q^n}{1-q^n}p_n. $$ This leads to a simple linear first-order differential equation with solution $$ f = (1-q) \sum_\lambda s_\lambda\cdot s_\lambda(q,q^2,q^3,\dots). $$ If $h_u$ denotes the hook length of the square $u$ of $\lambda$, then $$ s_\lambda(q,q^2,q^3,\dots) = \frac{q^{b(\lambda)}}{\prod_{u\in \lambda} (1-q^{h_u})}, $$ where $b_\lambda=\sum i\lambda_i$. Since there is always a hook length equal to one, the power series $(1-q)s_\lambda(q,q^2,q^3,\dots)$ will be a product of factors of the form $1/(1-q^h)$, $h\geq 1$, so will have nonnegative coefficients as desired. Thus we have not just an existence proof, but a precise generating function for the number of fathers of each shape.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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