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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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