Extending Muirhead’s Inequality

Abstract

We present a method to prove an inequality concerning a linear combination of symmetric monomial functions. This is based on Muirhead’s inequality combining with a graph theoretical setting. As an application we prove some interesting inequalities motivated from extremal combinatorics.

1 Introduction

We start with the following conjecture due to the last author.

Conjecture 1

Let $r\ge 3$ be an integer, let $a_1,\ldots ,a_r\in (0,1)$ be real numbers, and let $a=a_1\cdots a_r$. Then we have

$$\begin{aligned} \prod _{i=1}^r \left( a_i+a_i^2+\cdots +a_i^{r-1}+a_i^{r}\right) - \prod _{i=1}^r \left( a_i+a_i^2+\cdots +a_i^{r-1}+a\right) \ge 0 \end{aligned}$$

(1)

with equality holding if and only if $a_1=\cdots =a_r$.

This conjecture is motivated by study of multiply intersecting hypergraphs, where one of the main tools is the so-called random walk method, see Chapter 15 of [1]. Here we briefly explain how Conjecture 1 is related to a problem of random walk. Let $p\in (0,1-\frac{1}{r})$ be a real number, and let us define an infinite random walk $W_p$ in the two-dimensional grid ${\mathbb {Z}}^2$. The walk $W_p$ starts at the origin, and at each step it moves from (x, y) to $(x,y+1)$ (one step up) with probability p and from (x, y) to $(x+1,y)$ (one step right) with probability $1-p$. Then $W_p$ hits the line $y=(r-1)x+1$ with probability $\alpha _p$, where $\alpha _p\in (0,1)$ is a unique root of the equation

$$\begin{aligned} X=p+(1-p)X^r. \end{aligned}$$

Let $p_1,\ldots ,p_r\in (0,1-\frac{1}{r})$ be real numbers. Let $W'$ be another infinite random walk defined similarly to $W_p$, but this time, at step j ($j=1,2,\dots$) the walk takes up with probability $p_i$ and right with probability $1-p_i$, where $i:=j \bmod r$. This walk $W'$ hits the line $y=(r-1)x+r$ with probability $\beta$, where $\beta \in (0,1)$ is a unique root of the equation

$$\begin{aligned} X=\prod _{i=1}^r(p_i+(1-p_i)X). \end{aligned}$$

We are interested in $\beta$ because we can use it to bound the measure of multiply intersecting hypergraphs. We also mention that computing (or approximating) $\beta$ is more difficult than that of $\alpha _p$. Thus it is desirable that $\beta$ is bounded in terms of $\alpha _{p_i}$. Indeed we conjecture that $\beta \le \alpha _{p_1} \alpha _{p_2}\cdots \alpha _{p_r}$, which follows from (1) (if true). See Appendix for the proof.

In this paper we prove Conjecture 1 for the cases $3\le r\le 11$ with aid of computer search. For the proof we extend Muirhead’s inequality, and propose an approach to prove a more general inequality concerning a linear combination of symmetric monomial functions.

Let r and d be fixed positive integers, and let

$$\begin{aligned} \Lambda :=\{\lambda =(\lambda _1,\ldots ,\lambda _r)\in {\mathbb {Z}}^r: \lambda _1\ge \cdots \ge \lambda _r\ge 0,\,|\lambda |=d\}, \end{aligned}$$

(2)

where $|\lambda |:=\lambda _1+\cdots +\lambda _r$, that is, $\Lambda$ is a set of non-increasing sequences (vectors) representing a partition of d into r parts. For $\lambda \in \Lambda$ we define the symmetric monomial functions $m_\lambda (x)$ of degree d in variables $x=(x_1,\ldots ,x_r)$ by

$$\begin{aligned} m_\lambda (x):=\sum _{\sigma }x^\sigma = \sum _{\sigma }\prod _{i=1}^rx_i^{\sigma _i}, \end{aligned}$$

where the sums run over all distinct orderings (permutations) $\sigma =(\sigma _1,\ldots ,\sigma _r)$ of the vector $\lambda =(\lambda _1,\ldots ,\lambda _r)$. We also define the normalized symmetric monomial functions ${\bar{m}}_\lambda (x)$ by

$$\begin{aligned} {\bar{m}}_\lambda (x):=\frac{m_\lambda (x)}{m_\lambda (\mathbf{1})}. \end{aligned}$$

For example, if $r=d=4$ and $\lambda =(2,2,0,0)$ then

$$\begin{aligned} m_\lambda (x)=x_1^2x_2^2+x_1^2x_3^2+x_1^2x_4^2+x_2^2x_3^2+x_2^2x_4^2+x_3^2x_4^2, \end{aligned}$$

and ${\bar{m}}_\lambda (x)=m_\lambda (x)/6$. (For more about monomial symmetric functions, see e.g., Chapter 7 of [5].) For $\lambda ,\mu \in \Lambda$ we write ${\bar{m}}_\lambda \ge {\bar{m}}_\mu$ if ${\bar{m}}_\lambda (x)\ge {\bar{m}}_\mu (x)$ holds for all $x\ge 0$, where $x\ge 0$ means that $x=(x_1,\ldots ,x_r)$ satisfies $x_i\ge 0$ for all $1\le i\le r$. In [4] (see also [2, 3]) Muirhead proved that

$$\begin{aligned} {\bar{m}}_\lambda \ge {\bar{m}}_\mu \text { if and only if } \lambda\, \succ\, \mu , \end{aligned}$$

where $\lambda\, \succ\, \mu$ means

$$\begin{aligned} \lambda _1+\cdots +\lambda _i\ge \mu _1+\cdots +\mu _i \text { for all } 1\le i\le r. \end{aligned}$$

(3)

Moreover ${\bar{m}}_\lambda (x)= {\bar{m}}_\mu (x)$ if and only if $\lambda =\mu$ or $x_1=\cdots =x_r$.

Now we define a bipartite graph ${\mathcal{G}}=(V({\mathcal{G}}),E({\mathcal{G}}))$ corresponding to $\Lambda$ as follows. For the vertex set let $V({\mathcal{G}})=U\sqcup U'$, where U and $U'$ are distinct copies of $\Lambda$. Then two vertices $\lambda \in U$ and $\lambda '\in U'$ are adjacent in ${\mathcal{G}}$ if and only if $\lambda\, \succ\, \lambda '$. Let $c:V({\mathcal{G}})\rightarrow {\mathbb {R}}_{\ge 0}$ be a given capacity function. We say that a flow $\phi :E({\mathcal{G}})\rightarrow {\mathbb {R}}_{\ge 0}$ is optimal if

$$\begin{aligned} \sum _{\lambda \in e}\phi (e)\le c(\lambda ) \text { for all } \lambda \in U, \text { and} \sum _{\lambda '\in e}\phi (e)=c(\lambda ') \text { for all } \lambda '\in U'. \end{aligned}$$

Let $\alpha :\Lambda \rightarrow {\mathbb {R}}_{\ge 0}$, which can be viewed as a coefficient vector $\alpha =(\alpha _\lambda :\lambda \in \Lambda )\in {\mathbb {R}}_{\ge 0}^{\Lambda }$. Then we define a linear combination of normalized symmetric monomial functions

$$\begin{aligned} {\bar{m}}(\alpha ):=\sum _{\lambda \in \Lambda }\alpha _\lambda {\bar{m}}_\lambda . \end{aligned}$$

(4)

Let $\alpha ,\alpha '\in {\mathbb {R}}_{\ge 0}^{\Lambda }$ and let c be a capacity function on $V({\mathcal{G}})=U\sqcup U'$ defined by $c=\alpha$ on U and $c=\alpha '$ on $U'$. We say that $\alpha$ suppresses $\alpha '$, denoted by $\alpha\, \succ\, \alpha '$, if ${\mathcal{G}}$ admits an optimal flow. While the Muirhead’s inequality says that if $\lambda\, \succ\, \mu$ then ${\bar{m}}_\lambda\, \succ\, {\bar{m}}_\mu$, our result stated below claims that if $\alpha\, \succ\, \alpha '$ then ${\bar{m}}(\alpha )\ge {\bar{m}}(\alpha ')$. This can be seen as an extension from the inequality about normalized symmetric monomial functions to the inequality about linear combinations of them.

Theorem 1

Let $\alpha ,\alpha '\in {\mathbb {R}}_{\ge 0}^{\Lambda }$. If $\alpha\, \succ\, \alpha '$ then ${\bar{m}}(\alpha )\ge {\bar{m}}(\alpha ')$ with equality holding if and only if the following two conditions are satisfied:

• (i) $\sum _{\lambda \in e}\phi (e)=c(\lambda )$ for all $\lambda \in U$, and

• (ii) ${\bar{m}}_\lambda \ge {\bar{m}}_{\lambda '}$ for all adjacent $\lambda \in U$ and $\lambda '\in U'$.

Proof

Let ${\mathcal{G}}$ be the bipartite graph on $V({\mathcal{G}})=U\sqcup U'$ defined above, and let $\phi$ be an optimal flow. If $\lambda \in U$ and $\lambda '\in U'$ are adjacent by an edge e in ${\mathcal{G}}$, then ${\bar{m}}_\lambda \ge {\bar{m}}_{\lambda '}$ and $\phi (e){\bar{m}}_\lambda \ge \phi (e){\bar{m}}_{\lambda '}$. Using this trivial fact we have

$$\begin{aligned} {\bar{m}}(\alpha )&= {\sum\limits _{\lambda\in U}c(\lambda ){\bar{m}}_\lambda }\\&\ge \sum\limits _{\lambda \in U}\left( \sum\limits _{\lambda \in e}\phi (e)\right){\bar{m}}_\lambda \\&= \sum \limits _{e\in E({\mathcal{ G}})}\sum\limits _{\lambda \in e}\phi (e){\bar{m}}_\lambda\\&\ge \sum\limits _{e\in E({\mathcal{ G}})}\sum\limits_{\lambda '\in e}\phi (e){\bar{m}}_{\lambda '} \\&=\sum \limits_{\lambda '\in U'}\left( \sum \limits _{\lambda '\in e}\phi(e)\right) {\bar{m}}_{\lambda '}\\&=\sum\limits _{\lambda '\in U'}c(\lambda '){\bar{m}}_{\lambda '}\\&={\bar{m}}(\alpha ').\end{aligned}$$

One can readily verify the equality conditions. $\square$

We note that ${\bar{m}}(\alpha )\ge {\bar{m}}(\alpha ')$ does not necessarily imply $\alpha \succ \alpha '$, see Example 1 in the last section. Using Theorem 1 we were able to verify Conjecture 1 for $3\le r\le 11$.

Theorem 2

Conjecture 1 is true for $3\le r\le 11$.

Though our proof of Theorem 2 is based on Theorem 1, we need two more ideas. First, we actually prove a stronger inequality (see Conjecture 2) holding for all non-negative variables, from which we derive the inequality (1). This is needed because (1) holds only for variables in the unit interval, while Theorem 1 only applies to inequalities valid for all non-negative variables. Second, as a bipartite graph applied to Theorem 1 we do not use the graph whose vertex set is $\Lambda$ because it is too large. Instead we construct a graph on a much smaller vertex set which has a nicer poset structure induced by (3) (see Theorem 3). This reduces the computation markedly.

2 Proof of Theorem 2

Throughout this section let $r\ge 3$ be a fixed integer. As mentioned in the end of the previous section the inequality (1) is not suitable for applying Theorem 1. So we should find an inequality which holds for all non-negative variables and implies (1). This inequality will be obtained by factorizing (1).

For $s=(s_1,\ldots ,s_r)$ and $1\le k\le r$ we define the elementary symmetric functions $e_k(s)$ by

$$\begin{aligned} e_k(s):=\sum _{i_1<\cdots <i_k}s_{i_1}\cdots s_{i_k}, \end{aligned}$$

see, e.g., [5]. Let $e_0(s):=1$. Then we have

$$\begin{aligned} \prod _{i=1}^r(s_i+z)=\sum _{k=0}^r e_k(s)z^{r-k}. \end{aligned}$$

To factorize the LHS of (1), we apply the above identity to $s=(s_1,\ldots ,s_r)$, where

$$\begin{aligned} s_i=a_i+a_i^2+\cdots +a_i^{r-1}, \end{aligned}$$

(5)

and $z=1$ or $z=a$. Then we have

$$\begin{aligned} \prod _{i=1}^r \left( a_i+a_i^2+\cdots +a_i^{r-1}+a_i^{r}\right)&=\prod _{i=1}^r a_i(1+s_i) =a\prod _{i=1}^r (s_i+1)=\sum _{k=0}^r e_k(s)a,\\ \prod _{i=1}^r \left( a_i+a_i^2+\cdots +a_i^{r-1}+a\right)&=\prod _{i=1}^r (s_i+a) =\sum _{k=0}^r e_k(s)a^{r-k}. \end{aligned}$$

Thus, writing $e_k$ instead of $e_k(s)$ for simplicity, the LHS of (1) is rewritten as

$$\begin{aligned}&\sum _{k=0}^r (a-a^{r-k})e_k\\&=\sum _{k=0}^{r-2} (a-a^{r-k})e_k-(1-a)e_r\\&=(a-a^r)e_0+(a-a^{r-1})e_1+\cdots +(a-a^2)e_{r-2}-(1-a)e_r\\&=(1-a)\big ({\tilde{F}}-{\tilde{G}}), \end{aligned}$$

where

$$\begin{aligned} {\tilde{F}}&=(a+a^2+\cdots +a^{r-1})e_0+(a+\cdots +a^{r-2})e_1+\cdots +(a+a^2)e_{r-3}+ae_{r-2},\\ {\tilde{G}}&=e_r. \end{aligned}$$

Letting

$$\begin{aligned} f_i=e_0+e_1+\cdots +e_i, \end{aligned}$$

(6)

we have

$$\begin{aligned} {\tilde{F}}&=a(e_0+e_1+\cdots +e_{r-2})+a^2(e_0+\cdots +e_{r-3})+\cdots + a^{r-2}(e_0+e_1)+a^{r-1}e_0,\\&= a(f_{r-2}+f_{r-3}a+\cdots +f_1 a^{r-3}+f_0 a^{r-2}), \end{aligned}$$

and also

$$\begin{aligned} {\tilde{G}}=e_r=\prod _{i=1}^r s_i=\prod _{i=1}^r a_i(s_i/a_i) =a\prod _{i=1}^r(1+a_i+\cdots +a_i^{r-2}). \end{aligned}$$

Consequently we obtain the following expression:

$$\begin{aligned} {{`{\rm the\, LHS\, of}\, (1)\text{'}}}=a(1-a)(F-G), \end{aligned}$$

where

$$\begin{aligned} F&= f_{r-2}+f_{r-3}a+\cdots +f_1 a^{r-3}+f_0 a^{r-2}, \end{aligned}$$

(7)

$$\begin{aligned} G&=\prod _{i=1}^r(1+a_i+\cdots +a_i^{r-2}). \end{aligned}$$

(8)

Finally to prove Conjecture 1 it suffices to show the following conjecture.

Conjecture 2

Let $r\ge 3$ be an integer, and let $a_1,\ldots ,a_r$ be non-negative real numbers. Then

$$\begin{aligned} F-G \ge 0, \end{aligned}$$

where F and G are defined by (7) and (8) with (5) and (6). Moreover, equality holds if and only if $a_1=\cdots =a_r$.

Note that Conjecture 2 is slightly stronger than Conjecture 1 because the condition for $a_i$ is weaker. Moreover this condition is precisely what we need to apply Theorem 1. Note also that $F-G\ge 0$ if

$$\begin{aligned} F^{(d)}-G^{(d)}\ge 0 \end{aligned}$$

for every d, where $F^{(d)}$ (resp. $G^{(d)}$) denote the degree d part of F (resp. G).

Now we translate the problem of showing $F^{(d)}-G^{(d)}\ge 0$ (for fixed r and d) to a problem of finding an optimal flow. Recall the definitions of $\Lambda$ and ${\bar{m}}(\alpha )$ from (2) and (4). Let $\alpha ,\alpha '\in {\mathbb {R}}_{\ge 0}^\Lambda$ be such that

$$\begin{aligned} {\bar{m}}(\alpha )=F^{(d)} \text { and } {\bar{m}}(\alpha ')=G^{(d)}. \end{aligned}$$

Then, by Theorem 1, $F^{(d)}-G^{(d)}\ge 0$ follows from $\alpha\, \succ\, \alpha '$. Thus our problem is translated to show $\alpha\, \succ\, \alpha '$. However the number of non-zero entries in $\alpha$ and $\alpha '$ grows rapidly as r grows, and it is not so easy to verify $\alpha\, \succ\, \alpha '$ in this naive setting in practice. To overcome the difficulty we look at the posets derived from the polynomials $F^{(d)}$ and $G^{(d)}$ in detail, and we reduce the complexity using the structure of the posets.

Let $\Lambda (\alpha ')=\{\mu \in \Lambda :\alpha '_\mu >0\}$ be the set of partitions corresponding to $G^{(d)}$. For $\mu \in \Lambda (\alpha ')$ it follows from (8) that $\mu _1\le r-2$. We partition $\Lambda (\alpha ')$ by the value of $\mu _r$. Let

$$\begin{aligned} \Lambda _h=\{\lambda \in \Lambda :\lambda _r=h\}. \end{aligned}$$

Then we have $\Lambda (\alpha ')=\bigsqcup _{h=0}^{r-2}{\tilde{Q}}_h$, where

$$\begin{aligned} {\tilde{Q}}_h=\{\mu \in \Lambda _h:\mu _1\le r-2\}. \end{aligned}$$

(9)

Lemma 1

Let $\Lambda (\alpha )=\{\lambda \in \Lambda :\alpha _\lambda >0\}$. Then we have $\Lambda (\alpha )=\bigsqcup _{h=0}^{r-2}{\tilde{P}}_h$, where

$$\begin{aligned} {\tilde{P}}_h=\{\lambda \in \Lambda _h:\lambda _1\le r-1+h,\,\lambda _{r-1-h}= \lambda _r\}. \end{aligned}$$

(10)

Proof

In view of (7), $\lambda \in {\tilde{P}}_h$ comes from $f_{r-2-h}a^h$. Then, $\lambda$ is decomposed into two parts $\mu =(\mu _1,\ldots ,\mu _r)$ from $f_{r-2-h}$ and $\nu =(\nu _1,\ldots ,\nu _r)$ from $a^{h}$. By (5) and (6) we have

$$\begin{aligned} r-1\ge \mu _1\ge \cdots \ge \mu _{r-h-2}\ge 0=\mu _{r-1-h}=\cdots =\mu _r. \end{aligned}$$

We also have $\nu _1=\cdots =\nu _r=h$. Then the set of sequences $\lambda =\mu +\nu$ defines ${\tilde{P}}_h$. $\square$

We note that $I:=\Lambda (\alpha )\cap \Lambda (\alpha ')$ is nonempty. For example we have

$$\begin{aligned} {\tilde{P}}_{r-2}={\tilde{Q}}_{r-2}=\{(r-2,\ldots ,r-2)\}. \end{aligned}$$

We want to look at $\Lambda (\alpha )\setminus I$ and $\Lambda (\alpha ')\setminus I$ rather than $\Lambda (\alpha )$ and $\Lambda (\alpha ')$. To this end we need some preparation. Recall that $\Lambda$ itself is a poset, and the bipartite graph ${\mathcal{G}}$ is defined on $V({\mathcal{G}})=U\sqcup U'$, where both U and $U'$ are distinct copies of $\Lambda$. For $x\in {\mathbb {R}}^{\Lambda }$ let $p(x):=(y_{\lambda }:\lambda \in \Lambda )$, where

$$\begin{aligned} y_{\lambda }:= {\left\{ \begin{array}{ll} x_\lambda &{} \text {if }x_\lambda >0,\\ 0 &{} \text {if }x_\lambda \le 0, \end{array}\right. } \end{aligned}$$

that is, p(x) extracts positive entries from x. Let $\beta :=p(\alpha -\alpha ')$ and $\beta ':=p(\alpha '-\alpha )$. Then $\alpha -\alpha '=\beta -\beta '$ and

$$\begin{aligned} {\bar{m}}(\alpha )-{\bar{m}}(\alpha ')={\bar{m}}(\alpha -\alpha ')={\bar{m}}(\beta -\beta '). \end{aligned}$$

So our aim is to show that ${\bar{m}}(\beta -\beta ')\ge 0$. These coefficient vectors $\beta$ and $\beta '$ define two subposets of $\Lambda$:

$$\begin{aligned} \Lambda (\beta ):=\{\lambda \in U:\beta _\lambda>0\} \text { and } \Lambda (\beta '):=\{\mu \in U':\beta '_{\mu }>0\}. \end{aligned}$$

These posets are equipped with a nice property as stated in the next theorem, and this is the reason why we can efficiently verify the existence of an optimal flow in ${\mathcal{G}}$ with the capacity function coming from $\beta$ and $\beta '$.

Theorem 3

There exist unique positive integer k and partitions

$$\begin{aligned} \Lambda (\beta )&=A_1\sqcup \cdots \sqcup A_k,\\ \Lambda (\beta ')&=B_1\sqcup \cdots \sqcup B_k, \end{aligned}$$

with representatives $\tilde{\lambda }_1,\ldots ,\tilde{\lambda }_k$ and $\tilde{\mu }_1,\ldots ,\tilde{\mu }_k$ satisfying $\tilde{\lambda }_i=\min A_i$, $\tilde{\mu }_i=\max B_i$, and $\tilde{\lambda }_i\,\succ\, \tilde{\mu }_i$ for all $1\le i\le k$.

For a concrete example of such partitions, see Example 2 in the next section. We remark that $A_i$ (resp. $B_i$) does not necessarily have the maximum (resp. minimum) element, see Example 3.

We partition $\Lambda (\beta )$ and $\Lambda (\beta ')$ by the value of the last element. It follows from (9) and (10) that $\Lambda (\beta )=\bigsqcup _{h=0}^{r-3}P_h$ and $\Lambda (\beta ')=\bigsqcup _{h=0}^{r-3}Q_h$, where

$$\begin{aligned} P_h&=\{\lambda \in \Lambda _h: r-1\le \lambda _1\le r-1+h,\,\lambda _{r-1-h}=\lambda _r\},\\ Q_h&=\{\mu \in \Lambda _h: \mu _1\le r-2,\,\mu _{r-1-h}>\mu _r\}. \end{aligned}$$

Then the disjoint union $P_h\sqcup Q_h$ is a proper subset of $\Lambda _h$.

We have already fixed r and d, and now we fix h. We will define two maps $D^\infty :P_h\rightarrow Q_h$ and $U^\infty :Q_h\rightarrow P_h$, which will play a key role for the proof of Theorem 3. To this end we need two auxiliary maps D and U (down and up, respectively). Before going into the details of the proof we explain our plan. Let $\lambda \in P_h$ and $\mu \in Q_h$ with $\lambda\,\succ\,\mu$. We can draw the Young diagrams corresponding to $\lambda$ and $\mu$, and starting from $\lambda$ we can get $\mu$ by moving a box at a right upper corner to a left lower corner one by one. (We will give a formal definition of such operations shortly.) In this process we can find $D^\infty (\lambda )$ and $U^\infty (\mu )$ such that $\lambda\,\succ\,U^\infty (\mu )\,\succ\, D^\infty (\lambda )\,\succ\, \mu$ with some additional nice properties. Actually we will get $D^\infty (\lambda )$ from $\lambda$ by repeating the down map D finitely many times, and we will get $U^\infty (\mu )$ from $\mu$ by repeating the up map U finitely many times.

Definition 1

For $\lambda \in \Lambda _h\setminus Q_h$ define p and q as follows.

(Case I) If $\lambda _1\ge r-1$ then

$$\begin{aligned} p&=\max \{i:\lambda _i=\lambda _1\},\\ q&=\min \{i:\lambda _i\le \lambda _1-2\}. \end{aligned}$$

(Case II) If $\lambda _1<r-1$ and $\lambda _{r-1-h}=\lambda _r$ then

$$\begin{aligned} p&=\max \{i:\lambda _i\ge \lambda _r+2\},\\ q&=\min \{i:\lambda _i=\lambda _r\}. \end{aligned}$$

Define a map $D:\Lambda _h\rightarrow \Lambda _h$ by $D(\lambda ):=\lambda '$ if $\lambda \not \in Q_h$, where

$$\begin{aligned} \lambda '_i={\left\{ \begin{array}{ll} \lambda _p-1 &{} \text {if }i=p,\\ \lambda _q+1 &{} \text {if }i=q,\\ \lambda _i &{} \text {otherwise}, \end{array}\right. } \end{aligned}$$

and by $D(\lambda ):=\lambda$ if $\lambda \in Q_h$. (See Example 2.)

Definition 2

For $\mu \in \Lambda _h\setminus P_h$ define p and q as follows.

(Case III) If $\mu _{r-1-h}>\mu _r$ then

$$\begin{aligned} p&=\min \{i:\mu _i=\mu _{r-2-h}\},\\ q&=\max \{i:\mu _i>\mu _r\}. \end{aligned}$$

(Case IV) If $\mu _{r-1-h}=\mu _r$ and $\mu _1\le r-2$ then

$$\begin{aligned} p&=1,\\ q&=\max \{i:\mu _i=\mu _2\}. \end{aligned}$$

Define a map $U:\Lambda _h\rightarrow \Lambda _h$ by $U(\mu ):=\mu '$ if $\mu \not \in P_h$, where

$$\begin{aligned} \mu '_i={\left\{ \begin{array}{ll} \mu _p+1 &{} \text {if }i=p,\\ \mu _q-1 &{} \text {if }i=q,\\ \mu _i &{} \text {otherwise}, \end{array}\right. } \end{aligned}$$

and by $U(\mu ):=\mu$ if $\mu \in P_h$.

Lemma 2

Let $\lambda \in \Lambda _h\setminus Q_h$ and $\mu \in Q_h$. If $\lambda\,\succ\,\mu$ then $D(\lambda )\,\succ\, \mu$.

Proof

Let $\lambda '=D(\lambda )$. By definition of $\lambda '$ we only need to check that

$$\begin{aligned} \lambda '_1+\cdots +\lambda '_i\ge \mu _1+\cdots +\mu _i \end{aligned}$$

(11)

for all $p\le i<q$ because if $i<p$ or $i\ge q$ then the sum for $\lambda '$ and the sum for $\lambda$ are the same.

For Case I we have $\lambda '_i\ge \lambda _i-1\ge r-2\ge \mu _i$ for each $p\le i<q$, which yields (11).

For Case II we note that if $p<j<q$ then $h+1=\lambda _j\le \mu _j$ and $h=\lambda _q<\mu _q$ (and if $j>q$ then $\lambda _j=\mu _j$). Hence, for $p\,\le\, i\,<\,q$, we have

$$\begin{aligned} \lambda _{i+1}+\cdots +\lambda _r<\mu _{i+1}+\cdots +\mu _r. \end{aligned}$$

Since $|\lambda |=|\mu |=d$ it follows that

$$\begin{aligned} \lambda _{1}+\cdots +\lambda _i>\mu _{1}+\cdots +\mu _i. \end{aligned}$$

Thus we have

$$\begin{aligned} \lambda '_{1}+\cdots +\lambda '_p+\cdots +\lambda '_i= \lambda _{1}+\cdots +(\lambda _p-1)+\cdots +\lambda _i \ge \mu _1+\cdots +\mu _i, \end{aligned}$$

as needed. $\square$

Lemma 3

Let $\mu \in \Lambda _h\setminus P_h$ and $\lambda \in P_h$. If $\lambda\,\succ\,\mu$ then $\lambda\,\succ\,U(\mu )$.

Proof

Let $\mu '=U(\mu )$. We only need to show that

$$\begin{aligned} \lambda _1+\cdots +\lambda _i\ge \mu '_1+\cdots +\mu '_i \end{aligned}$$

for all $p\le i<q$.

For Case III suppose, to the contrary, that

$$\begin{aligned} \lambda _1+\cdots +\lambda _i+1\le \mu '_1+\cdots +\mu '_i \end{aligned}$$

(12)

for some $p\le i<q$. The RHS is equal to $\mu _1+\cdots +\mu _i+1$, and at most $\lambda _1+\cdots +\lambda _i+1$ because $\lambda\,\succ\,\mu$. Thus we have

$$\begin{aligned} \lambda _1+\cdots +\lambda _i=\mu _1+\cdots +\mu _i. \end{aligned}$$

(13)

Since $|\lambda |=|\mu |$ we also have $\lambda _{i+1}+\cdots +\lambda _r=\mu _{i+1}+\cdots +\mu _r$. Moreover, noting $\lambda _j<\mu _j$ for $r-1-h\le j\le q$, and $\lambda _j=\mu _j$ for $q<j\le r$, we have that $p\le i<r-1-h$ and

$$\begin{aligned} \lambda _{i+1}+\cdots +\lambda _{r-2-h}>\mu _{i+1}+\cdots +\mu _{r-2-h}. \end{aligned}$$

This together with $\mu _{i+1}=\mu _{r-2-h}$ gives us $\lambda _{i+1}>\mu _{i+1}$ and

$$\begin{aligned} \lambda _i\ge \lambda _{i+1}>\mu _{i+1}=\mu _i. \end{aligned}$$

On the other hand it follows from (13) and $\lambda _1+\cdots +\lambda _{i-1}\ge \mu _1+\cdots +\mu _{i-1}$ that $\lambda _i\le \mu _i$. This is a contradiction.

For Case IV suppose (12). Since $\lambda _1\ge r-1\ge \mu _1+1=\mu '_1$ we may assume that $2\le i<q$. Using $\lambda _1>\mu _1$ and $\mu _2=\mu _i$ with (13) we have $\lambda _i<\mu _i$. Then $\lambda _{i+1}\le \lambda _i<\mu _i=\mu _{i+1}$ and

$$\begin{aligned} \lambda _1+\cdots +\lambda _{i+1}= \mu _1+\cdots +\mu _{i}+\lambda _{i+1}< \mu _1+\cdots +\mu _{i}+\mu _{i+1}, \end{aligned}$$

which contradicts the assumption $\lambda\,\succ\,\mu$. $\square$

Let $D^n=(D\circ \cdots \circ D)$ (n times), and define $D^\infty =\lim _{n\rightarrow \infty }D^n$. If $\lambda \in P_h$ then $D^\infty (\lambda )=D^n(\lambda )$ for some $n\le r$. Indeed we first repeat Case I until $\lambda _1<r-1$, and next repeat Case II until $\lambda _{r-1-h}>\lambda _r$, and then eventually the resulting $\lambda$ comes into $Q_h$. Thus $D^\infty$ is a map from $P_h$ to $Q_h$. Similarly we define a map $U^\infty :Q_h\rightarrow P_h$ by $U^\infty =\lim _{n\rightarrow \infty }U^n$, which is actually obtained by applying U at most r times. By Lemma 2 and Lemma 3 we get the following results. (See Example 3.)

Lemma 4

Let $\lambda \in P_h$ and $\mu \in Q_h$ with $\lambda\,\succ\,\mu$.

• (1) $D^\infty (\lambda )\,\succ\, \mu$ and $D^\infty (\lambda )=\max \{\mu '\in Q_h:\lambda\,\succ\,\mu '\}$.

• (2) $\lambda\,\succ\,U^\infty (\mu )$ and $U^\infty (\mu )=\min \{\lambda '\in P_h:\lambda '\,\succ\, \mu \}$.

Lemma 5

It follows that

• (i) $(U^\infty \circ D^\infty )(\lambda )=\lambda$ for all $\lambda \in U^\infty (Q_h)$, and

• (ii) $(D^\infty \circ U^\infty )(\mu )=\mu$ for all $\mu \in D^\infty (P_h)$.

Proof

Let $\mu \in Q_h$, and define $\lambda :=U^\infty (\mu )$, $\mu ':=D^\infty (\lambda )$, and $\lambda ':=U^\infty (\mu ')$.

Since $\lambda =U^\infty (\mu )$ we have $\lambda\,\succ\,\mu$. Then by (1) of Lemma 4 we have

$$\begin{aligned} \mu '=D^\infty (\lambda )=\max \{\mu ''\in Q_h:\lambda\,\succ\,\mu ''\}\,\succ\, \mu . \end{aligned}$$

Thus $\{\lambda ''\in P_h:\lambda ''\,\succ\, \mu '\}\subset \{\lambda ''\in P_h:\lambda ''\,\succ\, \mu \}$ and taking the minimum element of each set we get $\lambda '\,\succ\, \lambda$. On the other hand $\lambda\,\succ\,\mu '$ follows from $\mu '=D^\infty (\lambda )$. Applying (2) of Lemma 4 we obtain $\lambda\,\succ\,U^\infty (\mu ')=\lambda '$. Consequently $\lambda =\lambda '$ and $(U^\infty \circ D^\infty )(\lambda )=U^\infty (\mu ')=\lambda '=\lambda$. This proves (i) of this lemma. One can show (ii) similarly. $\square$

Proof of Theorem 3

By Lemma 5 there exists $k=k(h)$ such that $U^\infty (Q_h)=\{\tilde{\lambda }_1,\ldots ,\tilde{\lambda }_k\}$ and $D^\infty (P_h)=\{\tilde{\mu }_1,\ldots ,\tilde{\mu }_k\}$. For $1\le i\le k$ let

$$\begin{aligned} A_i&=\{\lambda \in P_h:(U^\infty \circ D^\infty )(\lambda )=\tilde{\lambda }_i\},\\ B_i&=\{\mu \in Q_h:(D^\infty \circ U^\infty )(\mu )=\tilde{\mu }_i\}. \end{aligned}$$

Then $P_h=A_1\sqcup \cdots \sqcup A_k$ and $Q_h=B_1\sqcup \cdots \sqcup B_k$. Moreover, by Lemma 4, we have $\tilde{\lambda }_i=\min A_i$ and $\tilde{\mu }_i=\max B_i$. Finally we get the desired partitions $\Lambda (\beta )=\bigsqcup _{h=0}^{r-3}\bigsqcup _{i=1}^{k(h)}A_i$ and $\Lambda (\beta ')=\bigsqcup _{h=0}^{r-3}\bigsqcup _{i=1}^{k(h)}B_i$. $\square$

Using Theorem 3 we can further reduce the problem and decrease the computation sharply. This reduction is based on the following simple observation. By Theorem 3 we have $\tilde{\lambda }_i=\min A_i$ implying

$$\begin{aligned} \sum _{\lambda \in A_i}\beta _\lambda {\bar{m}}_\lambda \ge {\tilde{c}}_i\,{\bar{m}}_{\tilde{\lambda }_i}, \end{aligned}$$

where ${\tilde{c}}_i:=\sum _{\lambda \in A_i}\beta _\lambda$, and similarly

$$\begin{aligned} \sum _{\mu \in B_i}\beta '_\mu {\bar{m}}_\mu \ge {\tilde{c_i}}{'}_i\,{\bar{m}}_{\tilde{\mu }_i}, \end{aligned}$$

where ${\tilde{c_i}}{'}_i:=\sum _{\mu \in B_i}\beta '_\mu$. So we define two coefficient vectors $s,s'\in {\mathbb {R}}_{\ge 0}^{\Lambda }$ as follows: for each $\lambda ,\mu \in \Lambda$ let

$$\begin{aligned} s_\lambda := {\left\{ \begin{array}{ll} {\tilde{c}}_i&{}\hbox { if }\lambda =\tilde{\lambda }_i\text { for some}\ i,\\ 0&{}\text {otherwise,} \end{array}\right. } \quad \text {and}\quad s'_\mu := {\left\{ \begin{array}{ll} {\tilde{c_i}}{'}&{}\hbox { if }\mu =\tilde{\mu }_i\text { for some}\ i,\\ 0&{}\text {otherwise.} \end{array}\right. } \end{aligned}$$

Then it follows from the definition that ${\bar{m}}(\beta )\ge {\bar{m}}(s)$, ${\bar{m}}(s')\ge {\bar{m}}(\beta ')$, and

$$\begin{aligned} {\bar{m}}(\beta -\beta ')\ge {\bar{m}}(s-s'). \end{aligned}$$

Thus our aim is now reduced to showing $s\,\succ\, s'$, which yields ${\bar{m}}(s-s')\ge 0$ and so ${\bar{m}}(\beta -\beta ')\ge 0$, as required. Finally, similarly as we changed from $\alpha ,\alpha '$ to $\beta ,\beta '$ we modify $s,s'$ one last time to get $t,t'\in {\mathbb {R}}_{\ge 0}^\Lambda$ by $t:=p(s-s')$ and $t':=p(s'-s)$. Since $t-t'=s-s'$ it suffices to show $t\,\succ\, t'$ to verify $s\,\succ\, s'$, see Example 4 in the next section. In summary we have shown that

$$\begin{aligned} {\bar{m}}(\alpha ) - {\bar{m}}(\alpha ')= {\bar{m}}(\beta ) - {\bar{m}}(\beta ')\ge {\bar{m}}(s) - {\bar{m}}(s')= {\bar{m}}(t) - {\bar{m}}(t'). \end{aligned}$$

The point is that the number of non-zero entries in t and $t'$ is much smaller than those in $\alpha$ and $\alpha '$, for example, if $r=11$ and $d=52$ then the former is only 367 while the latter is 6594. This is the reason why such reductions make the computation much faster. Consequently we can complete the proof of Conjecture 2 by showing $t\,\succ\, t'$, and we have indeed verified this for $3\le r\le 11$ (and all d) with aid of a computer.

Thus the inequality in Conjecture 2 holds for $3\le r\le 11$. Moreover if $a_1=\cdots =a_r$, then clearly $F-G=0$. On the other hand if $F-G=0$ then we need ${\bar{m}}(\alpha )-{\bar{m}}(\alpha ')=0$. This together with (ii) of Theorem 1 implies that ${\bar{m}}_\lambda ={\bar{m}}_{\lambda '}$ for all adjacent $\lambda$ and $\lambda '$ in the graph ${\mathcal{G}}$. Therefore all $a_i$ are the same, which verifies the equality condition in Conjecture 2. This completes the proof of Theorem 2.

3 Some Examples

Example 1

We present an example showing that the converse of Theorem 1 does not hold, that is, an example satisfying ${\bar{m}}(\alpha )\ge {\bar{m}}(\alpha ')$ but $\alpha \,\not\succ\,\alpha '$.

Let $r=2$ and $d=4$. Then $\Lambda =\{(4,0),(3,1),(2,2)\}$, and

$$\begin{aligned} {\bar{m}}_{(4,0)}(x)=\tfrac{1}{2}(x_1^4+x_2^4), \quad {\bar{m}}_{(3,1)}(x)=\tfrac{1}{2}(x_1^3x_2+x_1x_3^3), \quad {\bar{m}}_{(2,2)}(x)=x_1^2x_2^2. \end{aligned}$$

Let $\alpha =(2,0,2)$ and $\alpha '=(0,4,0)$. Then we have

$$\begin{aligned} {\bar{m}}(\alpha )&= 2{\bar{m}}_{(4,0)}(x) + 2{\bar{m}}_{(2,2)}(x) = (x_1^4+x_2^4)+2x_1^2x_2^2,\\ {\bar{m}}(\alpha ')&= 4{\bar{m}}_{(3,1)}(x) = 2(x_1^3x_2+x_1x_2^3). \end{aligned}$$

A routine calculus shows that ${\bar{m}}(\alpha )\ge {\bar{m}}(\alpha ')$ for all $x_1,x_2\ge 0$.

Let ${\mathcal{G}}$ be the corresponding bipartite graph. Then, by writing only vertices with positive capacities, we have $V({\mathcal{G}})=\{(4,0),(2,2)\}\sqcup \{(3,1)\}$. There is only one edge joining (4, 0) and (3, 1), where the capacity of (4, 0) is 2 while the capacity of (3, 1) is 4. Thus there is no optimal flow, and $\alpha \,\not\succ\, \alpha '$.

Example 2

Let $r=8$, $d=29$, and $h=0$. Let $\tilde{\lambda }= (7,7,5,4,4,2,0,0)\in P_0$ and $\tilde{\mu }=(6,6,6,5,4,1,1,0)\in Q_0$. We get the following sequence by applying D:

$$\begin{aligned} \tilde{\lambda }\longrightarrow (7,6,6,4,4,2,0,0) \longrightarrow (6,6,6,5,4,2,0,0) \longrightarrow \tilde{\mu }. \end{aligned}$$

This shows that $D^\infty (\tilde{\lambda })=D^3(\tilde{\lambda })=\tilde{\mu }$. See Figure 1, where the map D sends a box with ‘$\bullet$’ to the position marked by ‘$\times$.’

Example 3

(Continued from Example 2) Let

$$\begin{aligned} A&:=\{\lambda \in P_0:(U^\infty \circ D^\infty )(\lambda )=\tilde{\lambda }\},\\ B&:=\{\mu \in Q_0:(D^\infty \circ U^\infty )(\mu )=\tilde{\mu }\}. \end{aligned}$$

Then it follows that $A=\{76554200,76555100,76644200,\tilde{\lambda }\}$, and $B=\{\tilde{\mu }\}$, and moreover $\min A=\tilde{\lambda }$ (but A does not have the maximum element) and $\max B=\tilde{\mu }$, see Figure 2, where black arrows correspond to D and red arrows correspond to U.

Example 4

We describe the partitions in Theorem 3 for the case $r=7$ and $d=15$. Then $\Lambda (\beta )=\{\lambda _1,\ldots ,\lambda _{19}\}$ and $\Lambda (\beta ')=\{\mu _1,\ldots ,\mu _{19}\}$ listed below with their capacities, e.g., $\lambda _1=(6,2,2,2,1,1,1)$ and $c(\lambda _1)=140$.

$$\begin{array}{lllllll} \lambda _1&6222111&140&&\mu _1&3322221&105 \\ \lambda _2&6321111&210&&\mu _2&3332211&210 \\ \lambda _3&6411111&42&&\mu _3&3332220&140 \\ \lambda _4&7221111&105&&\mu _4&3333210&210 \\ \lambda _5&7311111&42&&\mu _5&4222221&42 \\ \lambda _6&6322200&420&&\mu _6&4322211&420 \\ \lambda _7&6332100&1260&&\mu _7&4322220&210 \\ \lambda _8&6333000&140&&\mu _8&4332210&1260 \\ \lambda _9&6422100&1260&&\mu _9&4333110&420 \\ \lambda _{10}&6431100&1260&&\mu _{10}&4422210&420 \\ \lambda _{11}&6432000&840&&\mu _{11}&4432110&1260 \\ \lambda _{12}&6441000&420&&\mu _{12}&4441110&140 \\ \lambda _{13}&6521100&1260&&\mu _{13}&5222211&105 \\ \lambda _{14}&6522000&420&&\mu _{14}&5222220&42 \\ \lambda _{15}&6531000&840&&\mu _{15}&5322210&840 \\ \lambda _{16}&6540000&210&&\mu _{16}&5332110&1260 \\ \lambda _{17}&6611100&210&&\mu _{17}&5422110&1260 \\ \lambda _{18}&6621000&420&&\mu _{18}&5431110&840 \\ \lambda _{19}&6630000&105&&\mu _{19}&5521110&420 \end{array}$$

Then we can view $\Lambda (\beta )$ and $\Lambda (\beta ')$ as posets, where the partial order is introduced by the majorization. Figure 3 shows the corresponding Hasse diagrams, where $\lambda _i$ is denoted by and $\mu _j$ is denoted by $\boxed {j}$.

The partitions in Theorem 3 in this case are

$$\begin{aligned} \Lambda (\beta )&=A_1\sqcup A_2\sqcup A_3\sqcup A_4,\\ \Lambda (\beta ')&=B_1\sqcup B_2\sqcup B_3\sqcup B_4, \end{aligned}$$

where

$$\begin{array}{ll} A_{1}=\{\lambda _i:1\le i\le 5\}, & B_{1}=\{\mu_1,\mu _2,\mu _5,\mu _6,\mu _{13}\},\\A_{2}=\{\lambda _6\}, & B_{2}=\{\mu _3,\mu _4,\mu _7,\mu _8,\mu _{10},\mu _{14},\mu _{15},\mu_{16},\mu _{17}\},\\ A_{3}=\{\lambda _7,\lambda _8\}, & B_{3}=\{\mu_9,\mu _{11},\mu _{12},\mu _{18}\},\\ A_{4}=\{\lambda _i:9\le i\le19\}, & B_{4}=\{\mu _{19}\}. \end{array} $$

The representatives $\tilde{\lambda }_i=\min A_i$ and $\tilde{\mu }_i=\max B_i$ are given by

$$\begin{array}{llll} \tilde{\lambda }_1=\lambda _1,&\tilde{\lambda }_2=\lambda _6,& \tilde{\lambda }_3=\lambda _7,&\tilde{\lambda }_4=\lambda _9,\\ \tilde{\mu }_1=\mu _{13},&\tilde{\mu }_2=\mu _{17},& \tilde{\mu }_3=\mu _{18},& \tilde{\mu}_4=\mu _{19}. \end{array} $$

Example 5

Here we present an example of the reduction after applying Theorem 3. Let $r=8$, $d=29$. In this case the number of partitions in Theorem 3 is $k=12$, and the corresponding representatives are listed below.

$$\begin{array}{llll} \tilde{\lambda}_1=74333333, &\tilde{\lambda }_2=75542222, &\tilde{\lambda}_3=75544400, &\tilde{\lambda }_4=75554111,\\ \tilde{\lambda }_5=75554300, &\tilde{\lambda}_6=75555200, &\tilde{\lambda}_7=76544111, &\tilde{\lambda }_8=76544300,\\\tilde{\lambda }_9=76553111,&\tilde{\lambda}_{10}=76553300,&\tilde{\lambda}_{11}=76554200, &\tilde{\lambda }_{12}=76653200,\end{array}$$

$$\begin{array}{llll} \tilde{\mu}_1=54443333,&\tilde{\mu }_2=66533222,&\tilde{\mu}_3=66544310,&\tilde{\mu }_4=66553211,\\ \tilde{\mu}_5=66554210,&\tilde{\mu }_6=66555110,&\tilde{\mu}_7=66643211,&\tilde{\mu }_8=66644210,\\ \tilde{\mu}_9=66652211,&\tilde{\mu }_{10}=66653210,&\tilde{\mu}_{11}=66654110,&\tilde{\mu }_{12}=66663110.\end{array}$$

The corresponding capacities are the following.

$$\begin{array}{llll}{\tilde{c}}_1=64,&{\tilde{c}}_2=13272,&{\tilde{c}}_3=2520,&{\tilde{c}}_4=1120,\\{\tilde{c}}_5=3360,&{\tilde{c}}_6=840,&{\tilde{c}}_7=6720,&{\tilde{c}}_8=11760,\\{\tilde{c}}_9=75936,&{\tilde{c}}_{10}=16800,&{\tilde{c}}_{11}=23520,&{\tilde{c}}_{12}=93800,\end{array}$$

$$\begin{array}{llll}{\tilde{c}}'_1=336,&{\tilde{c}}'_2=27272,&{\tilde{c}}'_3=74536,&{\tilde{c}}'_4=91568,\\{\tilde{c}}'_5=21840,&{\tilde{c}}'_6=1680,&{\tilde{c}}'_7=6720,&{\tilde{c}}'_8=11200,\\{\tilde{c}}'_9=1680,&{\tilde{c}}'_{10}=7840,&{\tilde{c}}'_{11}=3360,&{\tilde{c}}'_{12}=1680.\end{array}$$

Then to construct t and $t'$ we compute

$$\begin{array}{llll}\tilde c_1-{\tilde{c}}'_1=-272,& \tilde c_2-{\tilde{c}}'_2=-14000,&\tilde c_3-{\tilde{c}}'_3=-72016,&\tilde c_4-{\tilde{c}}'_4=-90448,\\\tilde c_5-{\tilde{c}}'_5=-18480,& \tilde c_6-{\tilde{c}}'_6=-840,&\tilde c_7-{\tilde{c}}'_7=0,&\tilde c_8-{\tilde{c}}'_8=560,\\\tilde c_9-{\tilde{c}}'_9=74256,& \tilde c_{10}-{\tilde{c}}'_{10}=8960,&\tilde c_{11}-{\tilde{c}}'_{11}=20160,& \tilde c_{12}-{\tilde{c}}'_{12}=92120.\end{array}$$

Figure 4 shows the reduced graph for t and $t'$, that is, the top five vertices are corresponding to ${\bar{m}}(t)$ and the bottom six vertices are corresponding to ${\bar{m}}(t')$, and $\tilde{\lambda }$ and $\tilde{\mu }$ are adjacent if $\tilde{\lambda }\,\succ\, \tilde{\mu }$. In this picture we label the vertices by ${\tilde{c}}_i-{\tilde{c}}'_i$ instead of the capacity $|{\tilde{c}}_i-{\tilde{c}}'_i|$. Then one of the optimal flows is shown in Fig. 5.

Appendix

Write $a_i$ for $\alpha _{p_i}$, and let $q_i=1-p_i$.

Fact 1

Let $t\ge 1$ be an integer, and let $l_j$ be the line $y=(r-1)x+j$. Then the walk $W_{p_i}$ hits the line $l_t$ with probability $a_i^t$, and the walk $W'$ hits the line $l_{rt}$ with probability $\beta ^t$.

Proof

Suppose that the probability that the walk $W_{p_i}$ hits the line $l_t$ is given by $X^t$ for some $X\in (0,1)$. After the first step, the walk is at (0, 1) with probability $p_i$, and at (1, 0) with probability $q_i$. From (0, 1) the probability for the walk hitting $l_t$ is $X^{t-1}$, and from (1, 0) the probability is $X^{t-1+r}$. Then it follows

$$\begin{aligned} X^t=p_iX^{t-1}+q_iX^{t-1+r}, \end{aligned}$$

that is,

$$\begin{aligned} X=p_i+q_iX^r. \end{aligned}$$

Thus $X=a_i$, and the walk hits the line $l_t$ with probability $a_i^t$.

Next suppose that the probability that the walk $W'$ hits the line $l_{rt}$ is given by $Y^t$ for some $Y\in (0,1)$. After the first r steps, it is at $(x,r-x)$ with probability

$$\begin{aligned} \sum _{I\in \left( {\begin{array}{c}[r]\\ x\end{array}}\right) }\prod _{i\in I}p_i\prod _{j\in [r]\setminus I}q_j, \end{aligned}$$

where $[r]=\{1,2,\ldots ,r\}$. From $(x,r-x)$ the probability for the walk hitting $l_{rt}$ is $Y^{x+t-1}$. This yields

$$\begin{aligned} Y^t=\sum _{x=0}^rY^{x+t-1} \sum _{I\in \left( {\begin{array}{c}[r]\\ x\end{array}}\right) }\prod _{i\in I}p_i\prod _{j\in [r]\setminus I}q_j, \end{aligned}$$

that is,

$$\begin{aligned} Y=\sum _{x=0}^rY^{x} \sum _{I\in \left( {\begin{array}{c}[r]\\ x\end{array}}\right) }\prod _{i\in I}p_i\prod _{j\in [r]\setminus I}q_j =\prod _{i=1}^r(p_i+q_iY). \end{aligned}$$

Thus $Y=\beta$, and the walk hits the line $l_{rt}$ with probability $\beta ^t$. $\square$

Define a polynomial f(x) by

$$\begin{aligned} f(X):=-X+\prod _{i=1}^r(p_i+q_iX). \end{aligned}$$

By definition $f(\beta )=0$.

Fact 2

If $0<y<1$ and $f(y)\le 0$, then $\beta \le y$.

Proof

This follows because $f(0)>0$, $f(1)=0$, $f'(1)=-1+\sum _{i=1}^r q_i> -1+r\cdot \frac{1}{r}=0$ (here we used $p_i<1-\frac{1}{r}$), and $f''(x)>0$ for $x>0$. $\square$

Fact 3

The inequality $a:=a_1\cdots a_r\le \beta$ follows from (1).

Proof

By Fact 7 it suffices to show $f(a)\le 0$. Since $a_i=p_i+q_ia_i^r$ we have

$$\begin{aligned} a=a_1\cdots a_r=\prod _{i=1}^r(p_i+q_ia_i^r), \end{aligned}$$

and

$$\begin{aligned} f(a)=-a+\prod _{i=1}^r(p_i+q_ia) =-\prod _{i=1}^r(p_i+q_ia_i^r)+\prod _{i=1}^r(p_i+q_ia). \end{aligned}$$

So we need to show

$$\begin{aligned} \prod _{i=1}^r(p_i+q_ia)\le \prod _{i=1}^r(p_i+q_ia_i^r). \end{aligned}$$

(14)

Solving $a_i=p_i+(1-p_i)a_i^r$ for $p_i$ gives

$$\begin{aligned} p_i=\frac{a_i-a_i^r}{1-a_i^r}. \end{aligned}$$

Then

$$\begin{aligned} p_i+q_ia&= \frac{a_i-a_i^r}{1-a_i^r} +\left( 1-\frac{a_i-a_i^r}{1-a_i^r}\right) a=\frac{1}{1-a_i^r}\left( a_i-a_i^r+(1-a_i)a\right) ,\\ p_i+q_ia_i^r&=a_i =\frac{1}{1-a_i^r}\left( a_i(1-a_i^r)\right) . \end{aligned}$$

Noting that $0<a_i<1$ we see that (14) is equivalent to

$$\begin{aligned}&\prod _{i=1}^r(a_i-a_i^r+(1-a_i)a) \le \prod _{i=1}^ra_i({1-a_i^r})\\ \Longleftrightarrow \quad&\prod _{i=1}^r\left( 1-a_i^{r-1}+(1-a_i)\frac{a}{a_i}\right) \le \prod _{i=1}^r(1-a_i^r)\\ \Longleftrightarrow \quad&\prod _{i=1}^r\left( 1+a_i+\cdots +a_i^{r-2} +\frac{a}{a_i}\right) \le \prod _{i=1}^r\left( 1+a_i+\cdots +a_i^{r-1} \right) , \end{aligned}$$

and multiplying both sides by $a=a_1\cdots a_r$ we get (1). $\square$

Fig. 1

The down map sending $\tilde{\lambda }=77544200$ to $\tilde{\mu }=66654110$

Fig. 2

Example for Lemma 4 and Lemma 5

Fig. 3

Hasse diagram of $\Lambda (\beta )$ and $\Lambda (\beta ')$ as posets for $r=7$ and $d=15$

Fig. 4

The reduced graph for t and $t'$ ($r=8$ and $d=29$)

Fig. 5

An optimal flow in the reduced graph ($r=8$ and $d=29$)