Proving the pigeonhole principle in Cutting Planes

Question

Exercise 3 from https://massimolauria.net/courses/2015.ProofComplexity/lecture6.pdf

Consider the set of inequalities $x_i+x_j\leq1$ for $1\leq i<j\leq n$.

Find a derivation of $\sum_{i=1}^n x_i\leq 1$ in $O(n^2)$ length.

If it were just algebra I could just show by contradiction that at most one $x_i$ could be 1 and be done but how does it translate it into cutting planes PS? I guess a similar idea would be by obtaining $\sum_{i=1}^n x_i \leq n-1 -(n-2)x_i$ for all $i$ through addition of $x_i+x_j$ for all $1\leq j\leq n$ but I'm stuck there.

Thanks for your help.

Answer 1

The proof is by induction. Here is the inductive step.

Suppose that we know both of the following inequalities: $$ x_1 + \cdots + x_m \leq 1 \\ x_2 + \cdots + x_{m+1} \leq 1 $$ Add them to get $$ x_1 + 2x_2 + \cdots + 2x_m + x_{m+1} \leq 2 $$ Add the axiom $x_1 + x_{m+1} \leq 1$ to get $$ 2x_1 + \cdots + 2x_{m+1} \leq 3 $$ Divide by 2 and round down to get $$ x_1 + \cdots + x_{m+1} \leq 1 $$ I'll let you fill in the remaining details.