4
$\begingroup$

Assume $A = \prod_{i=1}^n\{0,1\}$, i.e. element $(a_1,\cdots,a_n)=a\in A$ is n-tuples like $(1,0,1,\cdots)$.

There is an obvious partial order on the $A$: say $a < b$ for $a,b\in A$ if and only if $\forall i\in \{1,\cdots,n\}$ $a_i\leq b_i$. Note this is only a partial order.

We define the order-preserved partition $(A_1,A_2)$ of $A$: $A_1 \cup A_2 = A$, $A_1\cap A_2 = \emptyset$, and for any $a\in A_1,b\in A_2$, we have $a\ngeq b$, i.e. there is no element in $A_1$ bigger than any element in $A_2$. We also denote the pair as $A_1 < A_2$.

We define an increasing function on the partial ordered set $A$: $f((a_1,\cdots,a_n))=\prod_{i=1}^np_i^{1-a_i}$, where $0 < p_1,p_2\cdots,p_n <1$.

The question is that for any fixed order-preserve partition $(A_1,A_2)$ of $A$ whether we can find a positive number $\theta >0$ and $f$ of above form such that $A_1 \subset\{ f<\theta\}$ and and $A_2 \subset \{f>\theta\}$ or not.

In some sense, I want to know whether order-preserve partition can be obtained geometrically by above certain type function $f$.

I tried $n\leq 3$ case, above question has easy positive answer.

Thanks a lot

$\endgroup$
1
  • $\begingroup$ Doesn't the Steiner triple system (Fano plane) provide a counterexample when $n=7$? $\endgroup$
    – bof
    May 7, 2016 at 4:11

1 Answer 1

1
$\begingroup$

No. There is a counterexample for each $n\geq4$.

I will only show a counterexample for $n=4$; you can get one for any higher $n$ by appending $0$'s.

Let $A_{1}=\left\{ \left( x,y,z,w\right) \in\left\{ 0,1\right\} ^{4}\ \mid\ x+y\leq1\text{ and }z+w\leq1\right\} $. Let $A_{2}=\left\{ 0,1\right\} ^{4}\setminus A_{1}$. Then, $\left( A_{1},A_{2}\right) $ is what you call an order-preserved partition (I have seen this being called an "admissible partition"). Your conjecture claims that there exist $p_{1} ,p_{2},p_{3},p_{4}\in\left( 0,1\right) $ and $\theta\in\mathbb{R}_{+}$ such that the function $f:\left\{ 0,1\right\} ^{4}\rightarrow\mathbb{R},\ \left( x,y,z,w\right) \mapsto p_{1}^{1-x}p_{2}^{1-y}p_{3}^{1-z}p_{4}^{1-w}$ satisfies $A_{1}\subseteq f^{-1}\left( \left( -\infty,\theta\right) \right) $ and $A_{2}\subseteq f^{-1}\left( \left( \theta,+\infty\right) \right) $.

Assume that this were true. Then, there would exist $q_{1},q_{2},q_{3} ,q_{4}\in\left( 0,1\right) $ and $\eta\in\mathbb{R}$ such that the function $g:\left\{ 0,1\right\} ^{4}\rightarrow\mathbb{R},\ \left( x,y,z,w\right) \mapsto q_{1}x_{1}+q_{2}x_{2}+q_{3}x_{3}+q_{4}x_{4}$ satisfies $A_{1}\subseteq g^{-1}\left( \left( \eta,\infty\right) \right) $ and $A_{2}\subseteq g^{-1}\left( \left( -\infty,\eta\right) \right) $. (Indeed, take $q_{i}=\ln p_{i}$ and $\eta=\ln p_{1}+\ln p_{2}+\ln p_{3}+\ln p_{4}-\ln\theta $. Then, the inequalities $f\left( x,y,z,w\right) \lesseqgtr\theta$ become $g\left( x,y,z,w\right) \gtreqless\eta$ after taking natural logarithms and slightly rewriting.)

Now, the two points $\left( 1,0,1,0\right) $ and $\left( 0,1,0,1\right) $ both belong to $A_{1}$ and therefore to $g^{-1}\left( \left( \eta ,\infty\right) \right) $ (since $A_{1}\subseteq g^{-1}\left( \left( \eta,\infty\right) \right) $). Since $g^{-1}\left( \left( \eta ,\infty\right) \right) $ is a convex set, the midpoint between these two points (that is, the point $\left( \dfrac{1}{2},\dfrac{1}{2},\dfrac{1} {2},\dfrac{1}{2}\right) $) must therefore also belong to $g^{-1}\left( \left( \eta,\infty\right) \right) $.

But the two points $\left( 1,1,0,0\right) $ and $\left( 0,0,1,1\right) $ belong to $A_{2}$ and therefore to $g^{-1}\left( \left( -\infty,\eta\right) \right) $ (since $A_{2}\subseteq g^{-1}\left( \left( -\infty,\eta\right) \right) $). Since $g^{-1}\left( \left( -\infty,\eta\right) \right) $ is a convex set, the midpoint between these two points (that is, the point $\left( \dfrac{1}{2},\dfrac{1}{2},\dfrac{1}{2},\dfrac{1}{2}\right) $) must therefore also belong to $g^{-1}\left( \left( -\infty,\eta\right) \right) $.

So the point $\left( \dfrac{1}{2},\dfrac{1}{2},\dfrac{1}{2},\dfrac{1} {2}\right) $ must belong to $g^{-1}\left( \left( \eta,\infty\right) \right) $ and to $g^{-1}\left( \left( -\infty,\eta\right) \right) $ at the same time. But this is absurd, since $g^{-1}\left( \left( \eta ,\infty\right) \right) \cap g^{-1}\left( \left( -\infty,\eta\right) \right) =\varnothing$. So we have a contradiction.

I am wondering whether it is possible to fix your conjecture by (essentially) assuming that the kind of counterexamples above (viz., two points in $A_{1}$ having the same midpoint as two points in $A_{2}$) does not exist.

A stronger requirement that definitely makes your conjecture true is the following:

(1) no convex combination of the points in $A_1$ can be a convex combination of the points in $A_2$ at the same time.

Indeed, if (1) is true, then the convex hull of $A_1$ is disjoint from the convex hull of $A_2$; but (from basic linear optimization theory) we know that this entails that there exists a hyperplane separating $A_1$ from $A_2$; this immediately translates into the existence of $g$ and $\eta$ as above.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .