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$?

  • $\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 Nov 4 '18 at 12:54
  • $\begingroup$ @TonyK, thanks, edited. $\endgroup$ – user600670 Nov 4 '18 at 12:59
  • $\begingroup$ The way you put it is guaranteed to have readers scratching their heads... $\endgroup$ – TonyK Nov 4 '18 at 13:04
  • $\begingroup$ ...but I suppose it does also rule out other undesirable equations, like $2x_1>2x_2$. $\endgroup$ – TonyK Nov 4 '18 at 13:13
  • $\begingroup$ @TonyK, is this better? $\endgroup$ – user600670 Nov 4 '18 at 16:01

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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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