Fix $n>0$ and $X\subseteq\mathbb{R}^n$. A function $f:X\longrightarrow\mathbb{R}$ is linear if it is of the form $$ f(\bar{x})=a_1x_1+\ldots+a_nx_n+b $$ for some $a_i,b\in\mathbb{R}$.

Suppose we have linear functions $f_1,\ldots,f_t$ and $g_1,\ldots,g_t$ with the following property:

For any $\bar{x}\in X$ there are permutations $\sigma$ and $\tau$ of $\{1,\ldots,t\}$ such that $$ f_{\sigma(1)}(\bar{x})\leq g_{\tau(1)}(\bar{x})< f_{\sigma(2)}(\bar{x})\leq g_{\tau(2)}(\bar{x})<\ldots< f_{\sigma(t)}(\bar{x})\leq g_{\tau(t)}(\bar{x}). $$

Is it true that there are $i,j\in\{1,\ldots,t\}$ such that $f_i(\bar{x})\leq g_j(\bar{x})$ for all $\bar{x}\in X$?

When $n=1$ it's not too hard to show that the answer is yes, but the argument relies on the ordering of $\mathbb{R}$. Although in this case we only need the weaker assumption that for all $\bar{x}\in X$ and $i\in\{1,\ldots,t\}$ there are $j,k\in\{1,\ldots,t\}$ such that $f_i(\bar{x})\leq g_j(\bar{x})$ and $f_k(\bar{x})\leq g_i(\bar{x})$.

I am having trouble proving the general case, or imagining a counterexample.

It would even be helpful to show that there are $i,j\in\{1,\ldots,t\}$ and some bounded set $A$ such that $f_i(\bar{x})\leq g_j(\bar{x})$ for all $\bar{x}\in X\backslash A$.


For a counterexample, take $n=4$, take $t=2$, and take $X$ to be the standard set of four unit basis vectors in $\mathbb R^4$. At each of the four points $x\in X$, assign values to the two $f$'s and two $g$'s so as to defeat, at that point, one of the four possible inequalities $f_i(x)\leq g_j(x)$, while still satisfying the requirement about existence, for that $x$, of some $\sigma$ and $\tau$ with the required ordering. The arbitrary choices of values for the $f$'s and $g$'s can be extended to linear functions because the points in $X$ are linearly independent.

EDIT: In more detail, for the first $x\in X$, defeat the inequality $f_1\leq g_1$ by arranging the values in the order $f_2(x) < g_1(x)<f_1(x)<g_2(x)$. At the second point, defeat $f_1\leq g_2$ by arranging $f_2<g_2<f_1<g_1$ there. Proceed similarly to defeat $f_2\leq g_1$ at the third point of $X$ and to defeat $f_2\leq g_2$ at the fourth point.

Note also that, since you allow a constant term in your linear functions, we could build a similar example in $\mathbb R^3$ using four affinely independent points.


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.