A Probabilistic Characterization of the Dominance Order on Partitions

Abstract

A probabilistic characterization of the dominance partial order on the set of partitions is presented. This extends work in "Symmetric polynomials and symmetric mean inequalities". Electron. J. Combin., 20(3): Paper 34, 2013. Let $n$ be a positive integer and let $\nu$ be a partition of $n$. Let $F$ be the Ferrers diagram of $\nu$. Let $m$ be a positive integer and let $p\in (0,1)$. Fill each cell of $F$ with balls, the number of which is independently drawn from the random variable $X=Bin(m,p)$. Given non-negative integers $j$ and $t$, let $P(\nu ,j,t)$ be the probability that the total number of balls in $F$ is $j$ and that no row of $F$ contains more that $t$ balls. We show that if $\nu$ and $\mu$ are partitions of $n$, then $\nu$ dominates $\mu$, i.e. ${\sum }_{i=1}^k\nu (i)\ge {\sum }_{i=1}^k\mu (i)$ for all positive integers $k$, if and only if $P(\nu ,j,t)\le P(\mu ,j,t)$ for all non-negative integers $j$ and $t$. It is also shown that this same result holds when $X$ is replaced by any one member of a large class of random variables. Let $p=\{p_n{\}}_{n=0}^{\infty }$ be a sequence of real numbers. Let ${\mathcal{T}}_p$ be the $\mathbb{N}$ by $\mathbb{N}$ matrix with $({\mathcal{T}}_p{)}_{i,j}=p_{j-i}$ for all $i,j\in \mathbb{N}$ where we take $p_n=0$ for $n<0$. Let $(p^i{)}_j$ be the coefficient of $x^j$ in $(p(x){)}^i$ where $p(x)={\sum }_{n=0}^{\infty }{p}_n{x}^n$ and $p^0(x)=1$. Let ${\mathcal{S}}_p$ be the $\mathbb{N}$ by $\mathbb{N}$ matrix with $({\mathcal{S}}_p{)}_{i,j}=(p^i{)}_j$ for all $i,j\in \mathbb{N}$. We show that if ${\mathcal{T}}_p$ is totally non-negative of order $k$ then so is ${\mathcal{S}}_p$. The case $k=2$ of this result is a key step in the proof of the result on domination. We also show that the case $k=2$ would follow from a combinatorial conjecture that might be of independent interest.

13 pages