172
Appendix B. NCut consistency with multiple versions of each node
By adding the above two equations together, we get
vol(A)vol(A)((2k − 1)d Ax + (2k − 1)d Ax )
≤ cut(A, A)
vol(A) − vol(A)
(c − 1)(d Ax − d Ax )
+
kd Ax + (c + k − 1)d Ax
2
+
kd Ax + (c + k − 1)d Ax
2
.
Combining with (B.7), we get
(2c − 1)
2 (d Ax + d Ax )
(2k − 1)d Ax + (2k − 1)d Ax
≤
vol(A) − vol(A)
(c − 1)(d Ax − d Ax )
+
kd Ax + (c + k − 1)d Ax
2
+
kd Ax + (c + k − 1)d Ax
2
.
(B.8)
In the inequality (B.5), the left numerator is greater than or equal to the right numerator. Thus, the left denominator has to be greater than or equal to the right
denominator:
vol(A)vol(A) ≥
vol(A) + kd Ax + (c + k − 1)d Ax
vol(A) − kd Ax − (c + k − 1)d Ax
.
If vol(A) ≤ vol(A), then the above inequality implies
vol(A) ≤ vol(A) + kd Ax + (c + k − 1)d Ax .
When d Ax ≥ d Ax , by applying it to (B.8), we get
(2c − 1)
2 (d Ax + d Ax )
(2k − 1)d Ax + (2k − 1)d Ax
≤
kd Ax + (c + k − 1)d Ax
(c − 1)(d Ax − d Ax )
+
kd Ax + (c + k − 1)d Ax
2
+
kd Ax + (c + k − 1)d Ax
2
≤
kd Ax + (c + k − 1)d Ax
(c + k − 1)d Ax + kd Ax
+
kd Ax + (c + k − 1)d Ax
2
≤
(c + 2k − 1)d Ax + (c + 2k − 1)d Ax
(c + k − 1)d Ax + kd Ax
.
(B.9)
Since c ≥ 3, c = k + k, k ≥ 1 and k ≥ 1, so (2c − 1) 2 ≥ 3c 2 , c + 2k − 1 < 3c
and c + 2k − 1 < 3c. Then (B.9) implies
c
(2k − 1)d Ax + (2k − 1)d Ax
<
(c + k − 1)d Ax + kd Ax
=⇒
c(2k − 1)d Ax < (c + k − 1)d Ax