46

While the actual algorithm used in Tetris makes it impossible to achieve the combination of tetrominos necessary for the inescapable loss, in a perfect "abstract" Tetris, yes, Heidi Burgiel's first paper "How to Lose at Tetris" (which she wrote towards the end of our time in grad school in Seattle) answers Question 1 in the negative. It was published in ...

16

Not sure, please check carefully. (Well, now more sure and the argument is more direct.)
I claim that the array $(h)$ majorates the array $(q)$, that is,
$\sum \varphi (h_{ij})\geqslant \sum \varphi(q_{ij})$ for any convex function $\varphi$,
in particular for $-\log$, that is your inequality.
Denote the hook lengths of the first (largest) column
by $0&...

answered Jul 7 '16 at 20:56

Fedor Petrov

64.5k66 gold badges143143 silver badges266266 bronze badges

15

There is a connection! (Though see the edit below.) Keating and Snaith make their conjecture by modeling the distribution of $\zeta(s)$ by the distribution of the characteristic polynomial of a random unitary matrix, distributed according to Haar measure. This is connected to symmetric function theory by Schur-Weyl duality.
To my knowledge the first time ...

13

First, just for clarity about the question, the Reifegerste preprint dates from September 2003, her paper was published in 2004, and Jacob Post's thesis is from 2009.
But the theorem is easy to show from things known well before that (basically what can be found in Knuth's treatment in The Art of Computer Programming), though I'm not sure I can point ...

13

[Responding particularly to Bruce...] You may want to take a look at my thesis, which was the first place that the Knuth versions of RSK were "Fominized". There are lots of examples, which others have told me they've found helpful in understanding this material. (I'm sure Fomin already understood that this could be done, but it doesn't appear in his ...

12

When a tableau has two rows (of any length, skew is ok), there is a nice bijection between linear extensions on the poset defined by the shape of the tableau and order ideals on another related poset. This is what Theorem 4.12 in Promotion and Rowmotion says. Once we move to three rowed tableaux, though, it's not so clear how to biject from linear extensions ...

12

I think the following is a simple combinatorial argument which constructs the most dominant semistandard $\lambda$-tableau of content $\mu$ whenever $\lambda\trianglerighteq\mu$. (n.b. I haven't followed the reference given in Richard Stanley's comment, so I don't know whether I'm duplicating what's done there.)
In a nutshell, the idea is "put the largest ...

11

This is a technical question for those very familiar with the proof. Basically, GNW show by induction that the quantity on the l.h.s. has a product formula, with some hook numbers inside. Since the probabilities add up to 1, this gives a recurrence relation for the number of standard Young tableaux (SYT), mimicking the branching rule. This in turn allows ...

10

It's hard to prove that there isn't a way to do something, but I think the answer is no.
The saturation conjecture, now a theorem of Knutson and Tao, says that $c_{(N \alpha) (N \beta)}^{N \gamma} >0$ implies $c_{\alpha \beta}^{\gamma} >0$ for any positive integer $N$ and any partitions $\alpha$, $\beta$ and $\gamma$. Note that the corresponding ...

answered Sep 11 '13 at 12:25

David E Speyer

121k1010 gold badges301301 silver badges578578 bronze badges

10

A sensible "yes" to your question would imply that the computational complexity of the calculation of Littlewood-Richardson coefficients is the same that of a calculation of eigenvalues of Hermitian matrices, so that they can be calculated in polynomial time. This seems to be impossible, see H. Narayanan, On the complexity of computing Kostka numbers and ...

answered Sep 11 '13 at 12:10

Carlo Beenakker

95.9k99 gold badges235235 silver badges346346 bronze badges

9

The question is natural but looks difficult to approach strictly within the combinatorial definitions. Maybe it's helpful here to suggest a broader geometric framework, which applies more generally to reductive algebraic groups but involves here a general linear group having the symmetric group $S_n$ as Weyl group. Recall that the "Bruhat order" was ...

8

I think that these conjectures are essentially equivalent to results in the literature, but the translation is not straightforward. I know corresponding results for the Hecke algebras of the symmetric groups. When you work in this generality you have to change some of the statements a little in order to get them to work. Primarily this is because your column ...

8

For a very nice bijective proof of the Murnaghan-Nakayama rule I recommend Section 3.3 of Nick Loehr's article Abacus proofs of Schur function identities, SIAM J. Disc. Math. 24 (2010) 1356-1370. Chapter 11 of Loehr's recent textbook Bijective combinatorics gives an expanded version of his article with minimal prerequisites.
To explain the connection: the ...

8

For more details on this answer, together with two proofs of the following theorem, see arXiv:1705.07604 preprint
``External powers of tensor products as representations of general linear groups'' by Greta Panova and myself.
The following result converts the original question into a problem about the representation theory of the symmetric groups for which ...

8

This is a classical application of Frobenius formula and Vandermonde determinant. We have $$\dim V_{\lambda}=\frac{n!}{l_1! \cdots l_k!} \prod_{i<j}(l_i-l_j),$$
where $l_i=\lambda_i+k-i$. See Section 4.1 of
W. Fulton, J. Harris: Representation Theory (a first course), GTM 129 (1991).

answered Dec 6 '17 at 12:02

Francesco Polizzi

52.5k33 gold badges138138 silver badges224224 bronze badges

7

I would look at chapter 7 in Enumerative Combinatorics, Volume 2, by Richard Stanley. A second place that can also be helpful for getting a good understanding of RS is Bruce Sagan's book called The Symmetric Group.

7

For $j\geqslant0$ let $c_j$ denote the $2$-core partition $(j,j-1,\dots,1)$.
Your conditions on partitions of $2n$ can be re-phrased as asking for $2$-restricted partitions of $2$-weight $n$ and $2$-core $c_0$. Now for any $j$, there is a standard way to biject between $2$-restricted partitions of weight $n$ with $2$-core $c_j$ and $2$-restricted partitions ...

7

You might find useful the $q$-Plancherel measure, which is a result of RSK applied to a probability distribution on $S_n$, where each permutation $\sigma$ is weighted with $q^{maj(\sigma)}/(n!)_q$, where $maj(\sigma)$ is the sum of all $~i$, such that $\sigma(i)>\sigma(i+1)$, $1\le i < n$. See V. Feray and P.-L. Méliot, Asymptotics of q-Plancherel ...

7

Another large family of distributions that contains both $U[0,1]$ inputs (leading to the usual Plancherel measure) and $U\{1,2,\ldots,d\}$ (as in Ryan O'Donnell's answer) as special cases is the following. Let $(\alpha, \beta, \gamma)$ be an element of the Thoma simplex, i.e., a triple where
$\gamma\in [0,1]$ and $\alpha$ and $\beta$ are vectors
$$ \alpha = (...

7

I gave an answer for inducing the trivial representation in a comment at Decomposing the conjugacy representation of Sym$(n)$ for small $n$. It is in terms of a plethysm that seems to be just as intractable as the notorious $s_m[s_n]$.

answered Jan 20 '14 at 3:22

Richard Stanley

34.4k99 gold badges121121 silver badges197197 bronze badges

7

If a diagonal basis existed, tensoring with a fixed representation would kill all but finitely many basis elements. This is not the case because e.g. tensoring with the $1$-dimensional trivial representation doesn't kill anything.

7

The formula follows from a result in EC2 (Stanley's "enumerative Combinatorics" Vol. 2) -- Chapter 7, equation (7.96), which is a result from the expansion of Schur functions in terms of fundamental quasisymmetric functions. The equation reads:
$$\sum_{m\geq 0} s_{\lambda/\mu} (1^m) z^m = \frac{\sum_T z^{des(T)+1}}{(1-z)^{n+1}},$$
where $T$ ranges over all ...

6

The equivalent result is well known (and made explicit) in the literature on dual Knuth transformations. From there, you can use the fact that $P(\sigma) = Q( \sigma^{-1})$ to complete the proof. Haima's paper is the standard reference.
Haiman says two skew tableaux are dual equivalent if they are always of the same shape when acted on by a sequence of jeu ...

6

As far as I know, the Viennot's construction only works for RS algorithm taking permutations as input. For matrices there's a generalised version called matrix-ball construction, which can be found in 4.2 of "Young Tableaux" by William Fulton. I am not sure whether there is a matrix-ball construction for dual RSK algorithm.
However, if only consider ...

6

This is given in Exercise 7.74 of Enumerative Combinatorics II by Richard Stanley which is a formula for the restrictions in terms of plethysm and inner product.

6

Kuperberg in Random words, quantum statistics, central limits, random matrices attributes Theorem 1 to Johansson and he gives two additional interesting proofs of this result.
A proof of a more general result is presented in my joint work with Benoit Collins Representations of Lie groups and random matrices.
Asymptotics when both $n$ and $m$ tend to ...

6

My answer is regarding the first part of your Question 1. There is a paper linked in comments (below your question) which shows that, in general, there is no winning strategy. The paper is based upon essentially assuming that any given sequence of tetrominoes can occur.
The rules for what sequences of tetrominoes are or aren't allowed in a game is usually ...

6

Let $P^* = evac(P)$. As noted above, if $RSK(u)=(P,Q)$, then $RSK(w_0uw_0) = (P^*,Q^*)$. Conjugation by $w_0$ induces an automorphism of the Hecke algebra sending $T_x \mapsto T_{w_0 x w_0}$ and $c_x \mapsto c_{w_0 x w_0}$, from which the result you want follows. However you might be interested that something stronger is true: if $u=RSK^{-1}(P,Q)$ and $\...

6

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 ...

answered May 15 '19 at 23:15

Richard Stanley

34.4k99 gold badges121121 silver badges197197 bronze badges

5

I recently discovered "The Robinson-Schensted-Knuth" correspondence and the bijections of commutativity and associativity" by Danilov and Koshevoy (2008). It explains all the points described in the rest of this answer in far more detail and care. In summary, everything is known for $q=0$. I would still be interested to hear answers for general $q$.
A lot, ...

Only top voted, non community-wiki answers of a minimum length are eligible

#### Related Tags

young-tableaux × 114co.combinatorics × 64

rt.representation-theory × 57

symmetric-groups × 29

algebraic-combinatorics × 19

reference-request × 14

pr.probability × 10

symmetric-functions × 10

partitions × 9

robinson-schensted-knuth × 8

schur-functions × 7

ag.algebraic-geometry × 6

lie-algebras × 6

permutations × 6

schur-functors × 5

gr.group-theory × 4

posets × 4

determinants × 3

invariant-theory × 3

bijective-combinatorics × 3

nt.number-theory × 2

lie-groups × 2

finite-groups × 2

computational-complexity × 2

asymptotics × 2