Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $X_1,X_2,\ldots,X_n $ be indeterminates. Denote by $S$ the set of all linear inequalities of the form $X_{i_1}+X_{i_2}+\ldots+X_{i_k} \geq k,$ with $k \in \{ 1,2,\ldots,n \}$ and $1 \leq i_1< i_2 < \ldots < i_k \leq n $.

Consider the following illustrative example. We are given constraints $$ D=\{X_1+X_2+X_3\geq 3, X_1+X_3+X_4 \geq 3, X_1+X_2 + X_4 \geq 3, X_2+X_3+X_4 \geq 3\} \subset S. $$ We can infer that the inequality $$ X_1+X_2+X_3+X_4 \geq 4, $$ another member of $S$, also holds via a "complicated" nonintegral linear combination: $$ \frac{1}{3}(X_1+X_2+X_3)+\frac{1}{3}(X_1+X_3+X_4)+\frac{1}{3}(X_2+X_3+X_4)+\frac{1}{3}(X_1+X_3+X_4) \geq 4 $$

In general, it is conceivable that we can be given some set of constraints $D$ and can only infer an inequality in $S$ via a very complicated and nonobvious $\mathbb{R}_+$-linear combination. Indeed, deducing an inequality is much like solving an LP. I am interested in a simpler algorithm for deducing all inequalities in $S$ from those given in $D$.

One idea I had for such an algorithm is as follows. Notice that $$ X_i+X_j+X_k \geq 3 \implies (X_i \geq 1) \vee (X_j \geq 1) \vee (X_k \geq 1). $$ For instance, in our case, we know that $$ X_1+X_2+X_3 \geq 3 \implies (X_1 \geq 1) \vee (X_2 \geq 1) \vee (X_3 \geq 1) $$ Therefore we know that the following logical expression is true $$ ((X_1 \geq 1) \vee (X_2 \geq 1) \vee (X_3 \geq 1)) \wedge (X_2+X_3+X_4 \geq 3) \wedge (X_1+X_3+X_4 \geq 3) \wedge (X_1+X_3+X_4 \geq 3). $$ Expanding, and using $$ (X_a \geq 1) \wedge (X_b+X_c+X_d \geq 3) \implies (X_a+X_b+X_c+X_d \geq 4), $$ which amounts to taking an ordinary (having coefficients $+1$) sum, this implies that $$ X_1+X_2+X_3+X_4 \geq 4. $$ More generally, we can infer from $$ X_{i_1}+X_{i_2}+\ldots+X_{i_k} \geq k $$ that $$ (X_{i_2}+\ldots+X_{i_k} \geq k-1) \vee (X_{i_1}+X_{i_3}+\ldots+X_{i_k} \geq k-1) \vee \ldots $$ and we can continue on inductively. One would like to show that no matter which selection of these inequalities we make, assuming everything is consistent, we can sum them to obtain any inequality that can be deduced via a general linear combination. So the question is

${\bf Question}$: Can every inequality that holds be deduced by adding such "simple" inequalities obtained via the procedure above?

${\bf Remark}$: there are many ways to interpret this question, which leads me to think that something of the sort ought to be known. E.g, in terms of average, in terms of the $n$-hypercube, and in terms of (0,1) matrices.

${\bf Clarification}$: any of the inequalities from $D$ can be used in the disjoint union.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

Consider the inequalities:

$X_1+X_2+X_3 \geq 0$

$X_3 + X_4 + X_5 \geq 0$

$X_2+X_4+X_6 \geq 0$

$X_1 + X_5+X_6 \geq 0$

By adding all and dividing by $2$, we can deduce $X_1+X_2+X_3+X_4+X_5+X_6\geq 0$.

But I don't think you can get it by this sort of logic:

These inequalities are very symmetric - if the $X_i$ correspond to the edges of the tetrahedron, then the four inequalities correspond to the four faces. Suppose you try to break up one of the inequalities into smaller inequalities in this manner. Without loss of generality,it's $X_1+X_2+X_3 \geq 0$. Suppose it breaks into the smaller inequality $X_1+X_2\geq 0$. You will no longer be able to deduce that $X_1+X_2+X_3+X_4+X_5+X_6\geq 0$, because there is now the counterexample $X_1=0$, $X_2=0$, $X_3=-2$, $X_4=1$, $X_5=1$, $X_6=-1$.

We can produce counterexamples of this type using block designs, where the variables correspond to blocks and the inequalities correspond to points. Because each inequality will share variables with each other inequality, combining inequalities through disjoint union will be very difficult. But since each variable shows up in the same number of inequalities, combining them through weighted sum will be very easy.

share|improve this answer
    
Thank you for your answer. It is my fault for not being precise enough, but you're allowed to use the original inequalities. So in this case, $X_1+X_2+X_3 \geq 0$ can also be used. As long as we can add inequalities with coefficient $+1$. –  user21277 May 29 '13 at 21:07
    
I don't think that helps. By breaking inequalities into smaller inequalities, you could get $X_1 \geq 0$, $X_1+X_2\geq 0$, $X_4\geq 0$, $X_4+X_5\geq 0$, $X_4 \geq 0$, $X_2+X_4\geq 0$, $X_5 \geq 0$, $X_1+X_5 \geq 0$. Then further applications of your process don't get you anything, but there's no way to combine these to get what you want without using rational coefficients. –  Will Sawin May 29 '13 at 22:28
    
I adjusted all the constant terms to $0$ for simplicity. –  Will Sawin May 29 '13 at 22:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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