# Arrangements of hyperplanes

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