Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
Thanks, this makes sense. I realize that I didn't really phrase the question exactly has I wanted, because I do have some assumptions about the set $X$. In particular I want to assume it is unbounded. I have rephrased the question here: mathoverflow.net/questions/132148/… –  Gabe May 28 '13 at 19:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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