I have a function $f: M_k \to R$, where $M_k \subset \{0,1\}^n$ is the set of all n-tuples with exactly $k$ entries that are $1$ while the rest is $0$.

I wish to show that $f$ is strong monotonically increasing in $M_k$, that is:

$\forall (x_1, \dots, x_n),(y_1, \dots, y_n) \in M_k:\\ (x_1, \dots, x_n) <(y_1, \dots, y_n) \Rightarrow f((x_1, \dots, x_n)) < f((y_1, \dots, y_n))$

Here, $(x_1, \dots, x_n) < (y_1, \dots, y_n)$ holds iff $x_i \leq y_i \; \forall 1 \leq i \leq n$ and $\exists j: x_j < y_j$.

My problem is that this seems to be undefined since no two distinct tuples can fulfill this.

Any tuple with $x_i < y_i$ must have another element with $x_j > y_j$, because each tuple has exactly $k$ entries that are 1?

Is strong monotonicity even defined in this case or is each function on $M_k$ strongly monotone per default?

Thanks in advance!

  • $\begingroup$ In your criterion for tuple inequalities, is $1<i$ a typo, or do you mean to exclude the first element from consideration? $\endgroup$ Jun 25 '18 at 14:03
  • $\begingroup$ Yeah, I would agree with your assessment: you have to rob Peter to pay Paul, so to speak, since you must have exactly $k\;1$'s in your tuple. Given your definition of monotonicity, it is vacuously satisfied for every possible $f$; every possible $f$ is therefore strongly monotonic. Not sure this says anything useful, though. $\endgroup$ Jun 25 '18 at 14:16
  • $\begingroup$ Thanks a lot! This is part of some longer proof and I was kinda stuck at this point. $\endgroup$
    – user568813
    Jun 25 '18 at 14:30

Claim: Given two distinct $n$-tuples, $\mathbf{x}=(x_1,\dots,x_n)$ and $\mathbf{y}=(y_1,\dots,y_n),$ with exactly $k$ entries equal to $1$ and the rest $0,$ where $1\le k< n,$ and given the definition $$(u_1,\dots,u_n)<(v_1,\dots,v_n) \iff [(\forall\,i)(1\le i\le n)(u_i\le v_i)\;\land\;(\exists\,j)(u_j<v_j)], $$ it follows that $(x_1,\dots,x_n)\not<(y_1,\dots,y_n).$

Proof: If there does not exist a $j$ such that $x_j<y_j,$ we are done. Suppose, therefore, that there does exist a $j$ such that $x_j<y_j$. It follows from the definition of the $n$-tuples under consideration that $x_j=0$ and $y_j=1$. If we consider the non-$j$ entries, there must be exactly $k$ of them in $\mathbf{x}$ that are $1$, and $k-1$ of them in $\mathbf{y}$ that are $1$. By the Pigeonhole Principle, there must be at least one number, $\ell,$ such that $1\le\ell\le n,$ with $j\not=\ell,$ such that $x_{\ell}=1$ and $y_{\ell}=0.$ But then $x_{\ell}>y_{\ell},$ making the condition $(\forall\,i)(1\le i\le n)(x_i\le y_i)$ false. Hence, $\mathbf{x}\not<\mathbf{y}.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.