Sorry the title may be unclear. I do not know how to give it a good title.....
Let $\Delta$ be a probability simplex of $R^N$; i.e. set of all points $x$ such that $x\geq0$ and $\sum_{k=1}^Nx^k\leq1$.
Let $\mathcal{F}$ be the set of all continuous functions $f:\Delta\rightarrow R$ satisfying the following properties:
(a) $f(x)=f(y)$ implies that $f(x)=f(\lambda x+(1-\lambda)y)$ for all $\lambda\in(0,1)$.
(b) $f(x)>f(y)$ implies that $f(x)>f(\lambda x+(1-\lambda)y)$ for all $\lambda\in(0,1)$.
(c)There exists distinct $x,y\in\Delta$ such that $f(x)\neq f(y)$.
(i.e. I want $f$ to have thin and linear level curves. No two level curves intersect in $\Delta$. Moreover, $f$ is monotone along every line segment in $\Delta$)
We are given a collection $S$ of $M$ distinct pairs $(x,A)$, where for each pair $A$ is a convex polytope in $\Delta$ and $x$ is an extreme point of $A$. Fix an integer $K\leq M$.
My question is, what are the necessary and sufficient conditions such that (where $I$ is an indicator function)
$\max_{f\in\mathcal{F}}\sum_{(x,A)\in S}I(x\in\arg\max_{x'\in A}f(x'))=K$ ?
That is, when is it the case that among those $M$ pairs $(x,A)$, we can have at most $K$ pairs $(x,A)$ such that $x$ is the maximal point in $A$ according a common $f\in\mathcal{F}$?
I think my question can also be stated as a geometric problem. Roughly speaking, I need that for each convex polytope and a given extreme point, assign a supporting hyperplane. No two hyperplanes intersect in the simplex. Those hyperplanes can be ordered from low to high in the simplex. Moreover, all convex polytope are below their supporting hyperplane.
Suppose $A$ is a convex polytope in $\Delta$ and $x$ is an extreme point of $A$. Then we know that there exists a hyperplane containing $x$ such that $A$ lies in one side of the hyperplane. (Supporting hyperplane theorem)
Now suppose, we are given $M$ distinct pairs $(x,A)$. What are the necessary and sufficient conditions (geometric properties) for that $K\leq M$ is the largest number such that we can pick $K$ pairs $(x,A)$ out of the given $M$ pairs and then do the following
(1) For each $(x,A)$ in those $K$ pairs, construct hyperplane $H\supset\{x\}$ supporting $A$.
(2) Now we have $K$ tuples $(x,A,H)$. We can index them as $(x_i,A_i,H_i),i=1,\cdots,K$ such that
(3) $H_i\cap H_j\cap\Delta=\emptyset$ for all $i\neq j$ (no two hyperplanes intersect within the simplex)
(4) $H_i$'s are ordered within the simplex in the following sense:
$H_2\cap\Delta,\cdots,H_K\cap\Delta$ are on the same side of $H_1$;
$H_i$ separates $H_{i-1}\cap\Delta$ and $\{H_{i+1}\cap\Delta,\cdots,H_K\cap\Delta\}$ for all $1<i<K$;
$H_1\cap\Delta,\cdots,H_{K-1}\cap\Delta$ are on the same side of $H_K$
(5) All $A_i$ are "below" $H_i$ in the following sense:
$H_i$ separates $A_i$ and $\{H_{i+1},\cdots,H_k\}$ for every $1\leq i<K$;
$A_1,\cdots,A_K$ are all on the same side of $H_K$.
For example, in the following graph, we have three hyperplanes $H_i$ passing through $x_i$ such that all $A_i$ are "below" $H_i$.
In the following graph, we can have two hyperplanes $H_1$ and $H_2$ such that $A_1$ and $A_2$ are "below" them respectively. But no matter how we draw $H_1$ and $H_2$, there is no way to have $H_3$ containing $x_3$ such that $A_3$ is also "below" $H_3$. So the largest number $K=2$.
This is a convex geometry problem, right? Also a combinatorial problem? Any reference is welcome. Thank you.
