Global Methods for Combinatorial Isoperimetric Problems
With a focus on global methods, this innovative text employs morphisms to transform new problems into more restricted and easily solvable settings while preserving essential structure.
TABLE OF CONTENTS Global Methods for Combinatorial Isoperimetric Problems
Chapter 6: Higher Compression
In this chapter we develop the theory of compression as we did that of stabilization in the previous chapter. We begin with an observation of Bezrukov, that the number of induced edges in products of graphs which have nested solutions for the (induced) EIP is an additive function on ideals in the compressibility order. This observation reduces the EIP on such graphs to a maximum weight ideal problem, a fundamental insight. It facilitates, among other things, the proof of a theorem of Ahlswede and Cai giving a simple sufficient condition for products of graphs to have lexicographic nested solutions for EIP. We present a variety of applications of the Ahlswede Cai theorem, demonstrating its power and flexibility. Then we present a striking theorem of Bezrukov, Das and Els sser, that all products of Petersen graphs have nested solutions for EIP but the optimal numberings are not lexicographic.
6.1 Additivity
Definition 6.1
A set function, ?:2 V ? 
, is additive if ? A, B ? 2 V such that A ? B = 
, ? ( A ? B) = ? ( A) + ? ( B) .
Lemma 6.1
If ? : 2 V ? is additive then
-
? (
) = 0 -
? A, B ? 2 V , ? ( A ? B) = ? ( A) + ? ( B) ? ? ( A ? B) .
Exercise 6.1
Copyright Cambridge University Press 2004 under license agreement with Books24x7
