IMC 2024 · Day 2 · P9

Define a standard Young tableaux of shape $m \times n$ as an $m \times n$ matrix with the set of entries $\{1, 2, \dots, mn\}$, increasing in every row and in every column as in (ii).

Call two standard Young tableaux $Y_1, Y_2$ friends, if they differ by a switch of two consecutive numbers $x, x+1$ (the places of $x$ and $x+1$ must be not neighbouring, for such a switch preserving the monotonicity in rows and columns).

For a nice $m \times n$ matrix $A$ we construct a standard Young tableaux $Y_A$ of shape $m \times n$ as follows: if $A$ has $n_i$ entries equal to $i$ ($i = 1, 2, \dots, 2t$), we replace them by the numbers from $n_1 + \dots + n_{i-1} + 1$ to $n_1 + \dots + n_i$ preserving monotonicity.

Note that our $Y_A$ has exactly $2t - 1$ friends, where $2t$ is the number of distinct entries in $A$, and moreover, every standard Young tableaux with odd number of friends corresponds to a unique nice matrix. It remains to apply the handshaking lemma (i.e., the sum of the degrees equals twice the number of edges in this graph).