1
$\begingroup$

Say we have $n$ variables $x_1,x_2...,x_n$.

Question 1.

We want to put conditions of the following form:

$$x_i+...+x_j>x_k+...+x_l$$ Where

  1. The left side contains as many variables as the right side (but variables may be used multiple times, e.g.: $2\cdot x_3>x_2+x_1$), and

  2. No single inequality is enough by itself to imply an inequality of the form $x_i>x_j$, i.e. with less than $3$ variables (this rules out, for instance, $x_1+x_2+x_3>x_1+x_2+x_4$).

We can have as many such inequalities as we want.

Is it possible for some $i,k$ to write down a set of such conditions such that all valuations that satisfy them also satisfy $x_i>x_k$?


Question 2.

What if we restrict to inequalities with certain coefficients? I.e. is it possible if we allow conditions of the form:

$$\alpha^1\cdot x_i+...+\alpha^{n}\cdot x_j>\alpha^1\cdot x_k+...+\alpha^n\cdot x_l$$

Where $\alpha\in (0,1)$, and $n$ is the number of variables in the inequality.

Is it possible in this case to induce $x_i>x_k$?

$\endgroup$
7
  • $\begingroup$ You need another restriction: that no variable appears on both sides of an equation. Otherwise you could have $x_1+x_2>x_1+x_3$, forcing $x_2>x_3$. $\endgroup$
    – TonyK
    Commented Nov 4, 2018 at 12:54
  • $\begingroup$ @TonyK, thanks, edited. $\endgroup$
    – user600670
    Commented Nov 4, 2018 at 12:59
  • $\begingroup$ The way you put it is guaranteed to have readers scratching their heads... $\endgroup$
    – TonyK
    Commented Nov 4, 2018 at 13:04
  • $\begingroup$ ...but I suppose it does also rule out other undesirable equations, like $2x_1>2x_2$. $\endgroup$
    – TonyK
    Commented Nov 4, 2018 at 13:13
  • $\begingroup$ @TonyK, is this better? $\endgroup$
    – user600670
    Commented Nov 4, 2018 at 16:01

1 Answer 1

1
$\begingroup$

Doesn't something like $x_1+x_2>x_3+x_4$ and $x_3+x_4>x_2+x_5$ achieve what you're looking for?

$\endgroup$
1

You must log in to answer this question.

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