Provando il principio del Pigeonhole nei piani di taglio

Question

Esercizio 3 da https://massimolauria.net/courseses/2015.proofComplexity/ lecture6.pdf

.

Considerare il set di disuguaglianze $ x_i + x_j \ leq1 $ per $ 1 \ Leq I .

Trova una derivazione di $ \ sum_ {i= 1} ^ n x_i \ leq 1 $ in $ o ( n ^ 2) $ lunghezza.

Se fosse solo algebra, potrei solo mostrare la contraddizione che al massimo uno $ x_i $ potrebbe essere 1 e essere fatto, ma come si traduce in aerei da taglio PS? Immagino che un'idea simile sarebbe ottenuta ottenendo $ \ sum_ {i= 1} ^ n x_i \ leq n-1 - (n-2) x_i $ per tutti < Span Class="Math-Container"> $ i $ Attraverso l'aggiunta di $ x_i + x_j $ per tutte le $ 1 \ Leq J \ Leq N $ Ma sono bloccato lì.

Grazie per il tuo aiuto.

Answer 1

La prova è per induzione.Ecco il passo induttivo.

Supponiamo di conoscere entrambe le seguenti disuguaglianze: $$ x_1 + \ cdots + x_m \ leq 1 \\ x_2 + \ cdots + x_ {m + 1} \ leq 1 $$ Aggiungili per ottenere $$ X_1 + 2X_2 + \ CDOT + 2X_M + X_ {M + 1} \ Leq 2 $$ Aggiungere l'axiom $ x_1 + x_ {m + 1} \ leq 1 $ per ottenere $$ 2x_1 + \ cdots + 2x_ {m + 1} \ leq 3 $$ Dividi per 2 e rotondo per ottenere $$ x_1 + \ cdots + x_ {m + 1} \ leq 1 $$ Ti permetterò di compilare i dettagli rimanenti.