16
2 Layout on a Single Row
There are h 1 (|S 1 | − h 1 ) such combinations in the first case, and thus,
t β tqr = h 1 (|S 1 | − h 1 ). Similarly
t β tqr = h 2 (|S 2 | − h 2 ).
Hence,
t t,q∈S 1
β tqr +
t t,q∈S 2
β tqr = h 1 (|S 1 | − h 1 ) + h 2 (|S 2 | − h 2 ).
On the other hand,
t ∈S 1
q∈S 2
β min{t,q},max{t,q},r = h 1 (|S 2 | − h 2 ) + h 2 (|S 1 | − h 1 ).
We want to prove that
h 1 (|S 1 | − h 1 ) + h 2 (|S 2 | − h 2 ) − {h 1 (|S 2 | − h 2 ) + h 2 (|S 1 | − h 1 )} ≤ 0.
Since |S 2 | = |S 1 | − 1, we obtain
h 1 (|S 1 | − h 1 ) + h 2 (|S 1 | − 1 − h 2 ) − {h 1 (|S 1 | − 1 − h 2 ) + h 2 (|S 1 | − h 1 )} ≤ 0.
This can be simplified to
−h
2
1 − h 2 − h
2
2 + h 1 + 2h 1 h 2 ≤ 0,
which is equivalent to
h 1 − h 2 ≤ (h 1 − h 2 )
2 .
Because this is always true for integers h 1 and h 2 , the result is proved.
It is straightforward to check that for f = 4, (2.33) is of the form (2.28)–(2.30).
To see this, consider (2.33) with S 1 = {i, j } and S 2 = {k}, with i < j < k < r.
Note that the second sum of (2.33) has no terms because |S 2 | = 1, and hence (2.33)
becomes
β ij r −
t ∈S 1
q∈S 2
β tqr ≤ 0.
Therefore, we obtain
β ij r − β ikr − β jkr ≤ 0,
which is constraint (2.30).