11
$\begingroup$

Could anyone provide me with a nice proof that the dominance order $\leq$ on partitions of an integer $n$ satisfies the following: if $\lambda, \tau$ are 2 partitions of $n$, then $\lambda \leq \tau \Longleftrightarrow \tau ' \leq \lambda '$, where $\lambda'$ is the conjugate partition of $\lambda$ (i.e. the transpose of the set of 'dots' which $\lambda$ represents).

I feel like there must be a nice clever and concise/intuitive proof of this, but all I can come up with is an ugly brute force approach based on the definition of sums of the components $\lambda_i$. Could anyone suggest a particularly nice way to obtain this result? Many thanks.

$\endgroup$
2
  • $\begingroup$ In fact I seem to have now found a proof of quite the opposite result - that conjugation preserves the order - in MacDonald's Symmetric Functions and Hall Polynomials, (1.11). The proof seems valid to me, but I've been asked to prove that conjugation reverses the order, is this incorrect? $\endgroup$
    – Tom
    Commented Feb 13, 2012 at 1:05
  • 1
    $\begingroup$ Conjugation definitely reverses the ordering; preserving the ordering would be absurd given that the maximal partition $(n)$ and the minimal paritition $(1,1,\ldots,1)$ are conjugates of each other. You must have misread Macdonald (who has only one capital in his name; no relation to hamburgers). $\endgroup$ Commented Feb 13, 2012 at 10:20

6 Answers 6

5
$\begingroup$

Since I am currently writing lecture notes on this topic, let me show how I present the result there, precisely along the lines suggested by Andrew Wilson. This is a slight variation of one the proofs in Macdonald, Symmetric functions and Hall polynomials. I think it is both conceptually and computationally simple.

Lemma: The inequality $\lambda\geq\mu$ holds if and only if the Young diagram from $\lambda$ can be obtained from that of $\mu$ by successively moving boxes from a lower to a higher row (one box at a time), in such a way that each intermediate step is the Young diagram of a partition.

Note that this Lemma immediately implies the duality: simply apply the corresponding moves in the opposite order to the conjugate partitions.

Proof: Moving a box from row $j$ to row $i$ in $\mu$ (where $i<j$) gives $$(\nu_1,\dots,\nu_m)=(\mu_1,\dots,\mu_{i-1},\mu_i+1,\dotsm,\mu_j-1,\dots,\mu_m).$$ If the result is a partition, it is clear that $\nu>\mu$. This proves the if statement. For the only if statement, it suffices to prove that, if $\lambda>\mu$, then there exists such a partition $\nu$ with $\nu\leq\lambda$. Iterating this procedure, we must eventually reach a step when $\nu=\lambda$.

The inequality $\nu\leq\lambda$ is equivalent to $$\lambda_1+\dots+\lambda_k>\mu_1+\dots+\mu_k,\qquad i\leq k\leq j-1.\qquad(*)$$ Thus, it is natural to define $i$ as the smallest integer $k$ such that ($*$) holds and $j$ as the smallest integer $k$ such that $k>i$ and ($*$) fails. Note that $i$ exists by our assumption $\lambda>\mu$, and $j$ exists since $\lambda$ and $\mu$ are partitions of the same number.

It remains to prove that, with these values of $i$ and $j$, $\nu$ is a partition. That is, we must prove that $\mu_{i-1}>\mu_i$ (or $i=1$) and $\mu_j>\mu_{j+1}$. Note that $i$ is the smallest integer such that $\lambda_i>\mu_i$. It follows that $\mu_{i-1}=\lambda_{i-1}\geq\lambda_i>\mu_i$ (or $i=1$). Moreover, since $\lambda_1+\dots+\lambda_{j-1}>\mu_1+\dots+\mu_{j-1}$ and $\lambda_1+\dots+\lambda_{j}=\mu_1+\dots+\mu_{j}$ and $\lambda_1+\dots+\lambda_{j+1}\geq\mu_1+\dots+\mu_{j+1}$ we must have $\lambda_j<\mu_j$ and $\lambda_{j+1}\geq\mu_{j+1}$. Combining these facts gives $\mu_{j+1}\leq\lambda_{j+1}\leq\lambda_j<\mu_j$.

$\endgroup$
2
  • $\begingroup$ Very nice! I knew this idea, but I wasn't aware it could be proved so slickly without handwaving. Please let me know once you've written your notes! (I've made a few little edits for clarity, hopefully without disturbing the flow.) $\endgroup$ Commented Jan 15, 2020 at 2:05
  • $\begingroup$ I like this approach very much, and the way you prove the lemma too. I give a variant in my own answer, with two rules that make it slightly clearer IMHO, and a more graphical presentation, with the hope that you enjoy it too. $\endgroup$ Commented Jan 22, 2021 at 22:08
2
$\begingroup$

This is one of the most fundamental properties of the dominance ordering; one should not be surprised or ashamed at actually using the definition of that ordering in proving it. However, here is an approach that you may find less technical, as it shows the equivalence of the definition of the dominance ordering with a characterisation that makes the anti-symmetry obvious.

I will denote the Young diagram of a partition $\lambda$ by $[\lambda]$, considered as a subset of the quarter-lattice $\mathbf N_{>0}^2$, of which I will also consider the following subsets: the "upper half planes" $H_k=\{(i,j)\in\mathbf N_{>0}^2\mid i\leq k\}$ for $k\in\mathbf N$, and the "upper right diagonal half planes" $D_l=\{(i,j)\in\mathbf N_{>0}^2\mid i-j\leq l\}$ for $l\in\mathbf Z$. (One should take the "half plane" with a grain of salt: that is what the subsets of $\mathbf R^2$ defined by the same inequalities look like; in particular note that $H_0=\emptyset$.) One can now give the definition of the dominance order as follows.

Definition. For two partitions $\lambda,\mu$ of the same number $n\in\mathbf N$, one has $\lambda\leq\mu$ if and only if for all $k\in\mathbf N$ one has $|[\lambda]\cap H_k|\leq|[\mu]\cap H_k|$.

Lemma. For two partitions $\lambda,\mu$ of the same number $n\in\mathbf N$, the condition $\lambda\leq\mu$ holds if and only if for all $l\in\mathbf Z$ one has $|[\lambda]\cap D_l|\leq|[\mu]\cap D_l|$.

Admitting this lemma for now, one easily deduces the anti-symmetry of conjugation: $$ \begin{align} \lambda\leq\mu &\iff \forall l\in\mathbb Z:|[\lambda]\cap D_l|\leq|[\mu]\cap D_l| \\& \iff \forall l\in\mathbb Z:|[\lambda']\cap D_{-1-l}|\geq|[\mu']\cap D_{-1-l}| \\& \iff \lambda' \geq \mu', \\\end{align} $$ where the middle equivalence comes from the fact that $D_{-1-l}$ is the "transpose" of the complement in $\mathbf N_{>0}^2$ of the set $D_l$, so that the partial diagrams have been replaced by their transpose complements, and since $|[\lambda]|=n=|[\mu]|$ this changes their size from $s$ to $n-s$. Note that only here do we use $|[\lambda]|=|[\mu]|$, the lemma would be valid for partitions of different sizes (but the partial orders in that setting are nevertheless of no significance).

Proof of the lemma. We prove by contraposition: there exists some $k\in\mathbf N$ with $|[\lambda]\cap H_k|>|[\mu]\cap H_k|$ if and only if there exists some $l\in\mathbf Z$ such that $|[\lambda]\cap D_l|>|[\mu]\cap D_l|$. While the details below may seem a bit technical, the idea is simple: in the first part we pass from $k$ to $l$ using $\mu$ only, pushing $D_l$ as far to the right as possible while keeping the "octant" $H_k\setminus D_l$ inside the diagram $[\mu]$, and in the second part we pass from $l$ to $k$ using $\lambda$ only, by similarly pushing $H_k$ down as far as possible while keeping the same octant inside the diagram $[\lambda]$.

Suppose first the existence of such $k\in\mathbf N$ with $|[\lambda]\cap H_k|>|[\mu]\cap H_k|$. Let $(k,y)$ be the first square of row $k$ that is absent from $[\mu]$ (so in fact $y=\mu_k+1$), and put $l=k-y$. Then $[\mu]\cap D_l\subseteq [\mu]\cap H_k$ (since any squares $(i,j)$ of $D_l\setminus H_k$ have $i>k$ and $j\geq i-l>y$ and therefore $(i,j)\notin[\mu]$) while $H_k\setminus D_l\subseteq[\mu]$ (the "maximal" square $(k,y-1)$ of $H_k\setminus D_l$, if it exists, lies in $[\mu]$ by construction). One thus has $|[\mu]\cap D_l|=|[\mu]\cap H_k|-|H_k\setminus D_l|$, and this suffices to obtain the required inequality: $$ |[\lambda]\cap D_l|\geq|[\lambda]\cap H_k|-|H_k\setminus D_l| >|[\mu]\cap H_k|-|H_k\setminus D_l|=|[\mu]\cap D_l|. $$ Conversely suppose the existence of $l\in\mathbf Z$ such that $|[\lambda]\cap D_l|>|[\mu]\cap D_l|$. Let $k\geq\max(0,l+1)$ be minimal such that $(k+1,k-l)\notin[\lambda]$. By the choice of $k$ we have $[\lambda]\cap D_l\subseteq [\lambda]\cap H_k$ (the minimal square $(k+1,k-l+1$ of $D_l\setminus H_k$ does not lie in $[\lambda]$), and $H_k\setminus D_l\subseteq[\lambda]$ (the maximal square $(k,k-l-1)$ of $H_k\setminus D_l$, if it exists, lies in $[\lambda])$. Then by a similar argument as above, $$ |[\lambda]\cap H_k| = |[\lambda]\cap D_l|+|H_k\setminus D_l| >|[\mu]\cap D_l|+|H_k\setminus D_l| \geq |[\mu]\cap H_l|. $$

It should be noted that the values chosen for $l$ respectively $k$ are not always the unique ones that will make the argument work, just the minimal respectively maximal ones.

$\endgroup$
1
  • $\begingroup$ A wonderful proof, thank you! Very thoroughly explained, I'm very grateful. Incidentally, regarding my above comment everyone was quite right, my apologies but I somehow managed to foolishly misread Macdonald, despite double-checking to make sure I had read it right initially - such are the perils of doing maths on no sleep... $\endgroup$
    – Tom
    Commented Feb 13, 2012 at 19:54
2
$\begingroup$

It seems to me that what you're being asked to prove is correct. (Maybe MacDonald is discussing a different order? I'm not sure, I don't have the text here.)

The only proof sketch (emphasis on sketch) I can give that seems more intuitive is to think of how dominance order affects the Ferrers diagram. Given a partition $\tau$, we can make a partition $\lambda$ such that $\lambda \leq \tau$ by "moving dots" up and to the left in the diagram (assuming French notation). After conjugation, this movement would now be down and to the right, implying $\tau^{\prime} \leq \lambda^{\prime}$. Obviously, this is far from rigorous, but you might be able to write it out a bit more formally without things getting too ugly.

$\endgroup$
1
  • $\begingroup$ This does works and gives a simple and elegant proof. By (1.16) in Macdonald's book Symmetric functions and Hall polynomials, you can indeed always go from $\lambda$ to $\tau$ by moving boxes as you indicate. $\endgroup$ Commented Nov 10, 2019 at 7:13
1
$\begingroup$

This question is pretty old, but I would like to propose "a nice clever and concise/intuitive proof" as asked, although it may be considered not formal enough. It is a variant of the answer by Hjalmar Rosengren.

In his 1973 paper, Brylawski shows that all partitions of integer $n$ and the dominance order are obtained from the initial partition $(n)$ by iterating the following two rules on any partition (assuming that the last part is followed by a null part):

  • if the $i$-th is larger than the $i+1$-th part by at least $2$, then decrease the $i$-th part by $1$ and increase the $i+1$-th one by $1$;
  • if its $i$-th part is equal to its $i+1$-th part plus $1$, and its $i+1$-th part is equal to its $j$-th part plus $1$ where $j$ is minimal with this property, then decrease the $i$-th part by $1$ and increase the $j$-th one by $1$.

This may be represented graphically on Ferrers diagrams as follows:

                                Brylawski rules

In the case $n=7$, for instance, we obtain:

                            the lattice of partitions of 7

Then, just notice that applying the first Brylawski rule to a partition is equivalent to applying the second rule to its conjugate; and conversely, applying the second Brylawski rule to a partition is equivalent to applying the first rule to its conjugate.

From this, the equivalence in the asked question is obvious: a partition $\lambda$ is reachable from a partition $\tau$ by iterating the Brylawski rules if and only if the conjugate $\tau'$ is reachable from the conjugate $\lambda'$ by iterating these rules.

Several studies envision the lattice of integer partitions from this iterated rules point-of-view, see for instance this one.

$\endgroup$
3
  • $\begingroup$ "applying the first Brylawski rule to a partition is equivalent to applying the second rule to its conjugate; and conversely" this is a tempting property, but I fear it's not true. Going from the partition 31 to 22 is the first Brylawski rule. The conjugate step is going from 22 to 211, which again is the first Brylawski rule. $\endgroup$
    – azimut
    Commented May 6 at 15:01
  • $\begingroup$ I think to make such a correspondence on the type of Brylawski rule work, you need to further classify those of the first type into type (1a) if $\lambda_i \geq \lambda_{i+1} + 3$ and type (1b) if $\lambda_i = \lambda_{i+1} + 2$. Now under conjugation, type (1a) corresponds to type (2) (and vice versa), and type (1b) corresponds to itself. The above counterexample is resolved as being a type (1b) one. $\endgroup$
    – azimut
    Commented May 6 at 15:10
  • $\begingroup$ It's again easier to think graphically about those 3 types. Type (1a) moves a box one square to the right and more than one square down. The conjugate counterpart obviously is type (2) which moves a box one square down and more than one square to the right. Type (1b) moves a box one square to the right and one square down, which is invariant under conjugation. $\endgroup$
    – azimut
    Commented May 6 at 15:17
0
$\begingroup$

I just stumbled across this question. This is, I think, a somewhat more elementary proof.

Proof by induction on number of elements:

Step 1: Clearly is true for 1.

Step 2: Assume true for partitions of size $k < l$.

Let $A= \lbrace a_1,a_2,...\rbrace $ and $B=\lbrace b_1, b_2, ... \rbrace $ be partitions of l so that $B \unrhd A$. Then:

$$\sum_{h=1}^k a_h \leq \sum_{h=1}^k b_h \space \forall k $$

Let the largest part of $A$ be size $n$ and assume there are $i$ copies, and let the largest part of $B$ be size $m$ and assume there are $j$ copies. Then it must be that $m \geq n$. Also, if $i > j$ then $m j + b_{j+1} \geq n (j + 1) $, and since $b_{j+1} < m$, it must be that $m (j+1) > n (j + 1)$, hence $m > n$.

Construct new partitions $A'$ and $B'$ of $l-1$ by replacing one of the $n$ parts in A with $n-1$ and one of the m parts in B with m-1.

Then $B' \unrhd A'$.

Proof:

We want to show: $$\begin{eqnarray}\sum_{h=1}^k a_h - \small\begin{cases} 0 \text{ if } k < i \\ 1 \text{ if } k \geq i \end{cases} \space \large\leq \space \normalsize\sum_{h=1}^k b_h - \small\begin{cases} 0 \text{ if } k < j \\ 1 \text{ if } k \geq j \end{cases} \end{eqnarray} \space \forall k $$ Look at the sum of the first $k$ terms for any $k$. There are a number of cases:

Case 1: $j \geq i$:

  • If $k < i$ the sums are unchanged from $B$ and $A$, so the RHS is $\geq$.
  • If $k \geq i$ and $k < j$, the LHS sum has been decreased by $1$, so the RHS sum is $>$.
  • If $k \geq j$, both the $A$ and $B$ sums have been decreased by $1$, so the RHS sum is $\geq$.

Case 2: $i > j$:

Note that we must have $m > n$.

  • If $k \geq j$, both the $A$ and $B$ sums have been decreased by $1$, so the RHS sum is $\geq$.
  • If $k < j$, the equation reduces to $k n \leq k m $, so the RHS is $\geq$.
  • If $k \geq j$ and $k < i$, things depend on how $b_k$ compares to $n$:
    • If $b_k \geq n$, then each of the RHS terms is $\geq$ the LHS terms, so the RHS is $\geq$.
    • If $b_k < n$, it still must be true that: $$n (k+1) \leq \sum_{h=1}^{k+1} b_h \space \implies n k < \sum_{h=1}^{k} b_h \implies n k \leq \sum_{h=1}^{k} b_h - 1$$ So, again, the RHS is $\geq$.

Now, Let $\hat{B}'$ be the conjugate of $B'$ and $\hat{A}'$ be the conjugate of $A'$. By induction, $\hat{A}'$ dominates $\hat{B}'$.

Let $\hat{B}$ be the conjugate of $B$ and $\hat{A}$ the conjugate of $A$. Then:

  • $\hat{B}$ is obtained from $\hat{B}'$ by adding 1 to the m'th part (or, by adding a $1$ part if there isn't an m'th part).
  • $\hat{A}$ is obtained from $\hat{A}'$ by adding 1 to the n'th part (or, by adding a $1$ part if there isn't an n'th parht).

Since $m \geq n$, adding $1$ to each partition in this way preserves the dominance order and $\hat{A} \unrhd\hat{B}$

$\endgroup$
0
$\begingroup$

I would be curious to know, if this would be an acceptable proof. I find no flaw, but then I am not an expert in this area:

Let $\lambda,\tau$ be two partitions of $n$. To avoid notational clutter extend them to infinite sequences by adding zeros, so that I may now add up to infinity but the sums will always be finite. Then $\lambda \leq \tau$ is defined by

$$ (1) \quad \quad \forall i\in \mathbb{N} : \quad \sum_{j=1}^i \lambda_j \leq \sum_{j=1}^i \tau_j. $$

We will show first that $\lambda \leq \tau$ implies $\tau'\leq \lambda'$. The desired order relation $\tau'\leq \lambda'$ is equivalent to

$$ (2) \quad \forall k\in \mathbb{N} : \quad \sum_{j=k}^\infty \lambda^\prime_j \leq \sum_{j=k}^\infty \tau^\prime_j, $$

because for both sequences $\sum_{j=k}^\infty \lambda^\prime_j = n - \sum_{j=1}^{k-1} \lambda^\prime_j$ for $k=1,2,\ldots$.

To deduce (2) from (1), note that (2) for the value $k=1$ holds, because by assumption

$$ \sum_{j=1}^\infty \lambda^\prime_j = \sum_{j\in \mathbb{N}} \lambda_j \leq \sum_{j\in \mathbb{N}} \tau_j = \sum_{j=1}^\infty \tau^\prime_j. $$

For the case $k=2$ note that the sequence $(\lambda_2', \lambda_3', ...)$ is the conjugate of the sequence $(\hat{\lambda}_j):=(\max [ \lambda_j-1,0])$. Now for the new sequences $\hat{\lambda},\hat{\tau}$ thus defined, we have

$$ (1^\prime) \quad \quad \forall i\in \mathbb{N} : \quad \sum_{j=1}^i \hat{\lambda_j} \leq \sum_{j=1}^i \hat{\tau_j}, $$ because if for some $i$ we have $\hat{\lambda}_i=0$, there is no problem, if the statement was true for $i-1$ and if $\hat{\lambda}_i>0$, then

$$ \quad \sum_{j=1}^i \hat{\lambda_j} = -i + \sum_{j=1}^i \lambda_j \leq -i + \sum_{j=1}^i \tau_j \leq \sum_{j=1}^i \hat{\tau_j}. $$

The claim for $k=2$ now follows by applying the previous argument for the case $k=1$ to the new sequences with the hats and the overall claim for all $k$ follows by iterating this argument. The other direction follows by symmetry as the conjugate of the conjugate is the original sequence. Q.E.D.

Note that the sequences $(\hat{\lambda}_j), (\hat{\tau}_j)$ need not be partitions of the same integer any more. But the argument for $k=1$ already avoids that the total sum is actually the same. So this proof shows that (1) implies (2) even if the two partitions belong to two different integers. To get the equivalence of $\lambda \leq \tau$ and $\tau^\prime \leq \lambda^\prime$ using this argument, we have to use that they partition the same integer as this is used in the equivalence of (2) and the order of the conjugates.

$\endgroup$
2
  • 2
    $\begingroup$ Nice idea, but too much handwaving ("iterating this argument", "the previous argument", "there is no problem"). I'd rewrite your $k=2$ case as a $k\geq 2$ case, and reframe the whole proof as an induction on the size of the partitions. $\endgroup$ Commented Jan 15, 2020 at 2:11
  • $\begingroup$ @darijgrinberg: Thank you for your comment. You are right, of course. $\endgroup$ Commented Jan 15, 2020 at 9:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .