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



Arrangements of hyperplanes
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.


