Exercise: Denote $[n] = \{1,2,\ldots,n\}$. Let $P\subseteq \mathbb{R}^{m\times n}$ be the feasible region of the system
$$\begin{split}x\geq\, & 0\\x_{ij} \leq\,& 1 \text{ for all $i\in[m]$ and $j\in [n]$}\\x_{ij} + x_{i'j} + x_{ij'} + x_{i'j'} \leq\, & 3\text{ for all $i,i'\in[m]$ and $j,j'\in [n]$ with $i\neq i'$ and $j\neq j'$}\end{split} $$
Consider the case $m = n = 4$. Give the cutting-plane proof of $\sum\limits_{i,j = 1}^4 x_{ij} \leq 9$ from the system.
What I've tried: I know that $\sum\limits_{i,j = 1}^4x_{ij} = x_{11} + x_{12} + \ldots + x_{43} + x_{44}$. From the system I know that $$\begin{split}x_{11} + x_{12} + x_{21} + x_{22} \leq &\,3\\x_{14} + x_{13} + x_{34} + x_{33} \leq &\,3\\x_{31} + x_{32} + x_{23} + x_{24} \leq & \,3\end{split}$$ Adding up these inequalities I get $$x_{11} + x_{12} + \ldots + x_{23} + x_{24} \leq \, 9$$
and I have my cutting-plane proof.
Question: Is this correct? If not; what am I doing wrong?
Thanks in advance!
No, that's incorrect since $\sum\limits_{i,j=1}^4 x_{ij}$ has $16$ summands and your sum only has $12$.
Cutting planes proof system also has the following derivation rule (this is actually the most important one, since it's the only rule that uses the fact that we have integer coefficients): $${ a\sum\limits_{i=1}^k \lambda_i x_i \le b\over \sum\limits_{i=1}^k\lambda_i x_i \le \left\lfloor {b \over a}\right\rfloor}$$
Note that for rational numbers the fact you are trying to prove is incorrect, for example $x_{ij} = {3 \over 4}$ for all $i,j \in [4]$ satisfy the conditions but $\sum\limits_{i,j\in[4]} x_{ij} = {3 \over 4} \cdot 16 = 12$. So we need somehow use that $x_{ij} \in \{0,1\}$.
Let's start by proving this fact in a convenient way (a.k.a. ZFC). Let $S_i = x_{i1} + x_{i2} + x_{i3} + x_{i4}$. If $S_i \le 2$ for all $i \in [4]$ then $S_1 + S_2 + S_3 + S_4 \le 8$ and we are done. Then for some $i_0 \in [4]$, $S_{i_0} \ge 3$. Let $A_i = \{j \colon x_{i,j} = 1\}$. If $|A_{i} \cap A_{j}| \ge 2$ for $i \neq j$, then we have a contradiction with $x_{i,a} + x_{i,b} + x_{j,a} + x_{j,b} \le 3$ where $a \neq b \in A_i \cap A_j$. Hence for each $i \neq i_0$, $|A_i| \le |[4] \setminus A_{i_0}| + 1$. If $S_{i_0} = 3$ then $A_i \le 2$ for each $i \in [4] \setminus \{i_0\}$ and if $A_{i_0} = 4$ then $A_i \le 1$ for $i \in [4] \setminus \{i_0\}$.
Unfortunately, proving in cutting planes goes in the opposite direction, we gradually derive facts until we derived what we were after. I'll denote $\sum\limits_{i\in A;j\in B}x_{ij} = S(A,B)$. $2 S(\{1,2\}, \{1,2,3\}) = S(\{1,2\}, \{1,2\}) + S(\{1,2\}, \{1,3\}) + S(\{1,2\}, \{2,3\})$. Thus we can add three $S(\{i,j\}, \{i',j'\}) \le 3$ and gain $$ 2 S(\{1,2\}, \{1,2,3\}) \le 9 $$ Now we are able to use division rule: $$ S(\{1,2\}, \{1,2,3\}) \le \left\lfloor {9 \over 2} \right\rfloor = 4 $$ Similarly we can derive $S(A, B) \le 4$ for all $|A|=2;\; |B| = 3$; $A,B \subseteq [4]$ . Let's do the same thing once again: $$3 S([2], [4]) = \sum\limits_{i \in [4]} S([2], [4] \setminus \{i\}) \le 16$$ and by division rule $$S([2],[4]) \le \left\lfloor {16 \over 3} \right\rfloor = 5$$ Similarly: $$2 S([3],[4]) \le \sum\limits_{i \in [3]} S([3] \setminus \{i\}, [4]) \implies S([3],[4]) \le 7$$ And finally: $$3 S([4],[4]) \le \sum\limits_{i \in [4]} S([4] \setminus \{i\}, [4]) \implies S([4],[4]) \le \left\lfloor {7 \cdot 4 \over 3} \right\rfloor = 9.$$