GLOBAL METHODS FOR COMBINATORIAL ISOPERIMETRIC PROBLEMS
CONTENTS THE EDGE-ISOPERIMETRIC PROBLEM BASIC DE?NITIONS EXAMPLES APPLICATION TO LAYOUT PROBLEMS COMMENTS THE MINIMUM PATH PROBLEM INTRODUCTION ALGORITHMS REDUCTION OF WIRELENGTH TO MINPATH PATHMORPHISMS STABILIZATION AND COMPRESSION STABILIZATION COMPRESSION THE VERTEX-ISOPERIMETRIC PROBLEM DE?NITIONS AND EXAMPLES STABILIZATION AND VIP COMPRESSION FOR VIP OPTIMALITY OF HALES NUMBERING APPLICATIONS TO LAYOUT PROBLEMS STRONGER STABILIZATION GRAPHS OF REGULAR SOLIDS A SUMMARY OF COXETER THEORY THE STRUCTURE OF STABILITY ORDERS CALCULATING STABILITY ORDERS INTO THE FOURTH DIMENSION EXTENDED STABILIZATION HIGHER COMPRESSION ADDITIVITY THE MWI PROBLEM THE AHLSWEDE–CAI THEOREM THE BEZRUKOV–DAS–ELS¨ASSER THEOREM ISOPERIMETRIC PROBLEMS ON IN?NITE GRAPHS EUCLIDEAN TESSELLATIONS ISOPERIMETRIC PROBLEMS ON COMPLEXES MINIMUM SHADOW PROBLEMS STEINER OPERATIONS FOR MSP SCHEDULING PROBLEMS MORPHISMS FOR MWI PROBLEMS MWI-MORPHISMS APPLICATION I: THE PAIRWISE PRODUCT OF PETERSEN GRAPHS APPLICATION II: THE EIP ON THE 600-VERTEX PASSAGE TO THE LIMIT THE BOLLOBAS–LEADER THEOREM THE KLEITMAN–WEST PROBLEM VIP ON THE HAMMING GRAPH SAPOZHENKO’S PROBLEM THE EDGE-ISOPERIMETRIC PROBLEM 1 1 BASIC DE?NITIONS A GRAPH, G = (V, E, ?), CONSISTS OF A VERTEX-SET V , EDGE-SET E AND BOUNDARY- FUNCTION?: E ? V + V WHICHIDENTI?ESTHEPAIROFVERTICES(NOTNECESSARILY DISTINCT) INCIDENT TO EACH EDGE GRAPHS ARE OFTEN REPRESENTED BY DIAGRAMS WHERE VERTICES ARE POINTS, AND EDGES ARE CURVES CONNECTING THE PAIR OF INCIDENT VERTICES FOR ANY GRAPH G, AND S ?V , WE DE?NE (S) = {E ?E : ?(E) = {V, W} , V ?S & W /?S} , AND CALL IT THE EDGE-BOUNDARY OF S THEN GIVEN A GRAPH G, AND K ?Z+, THE EDGE-ISOPERIMETRIC PROBLEM (EIP) IS TO MINIMIZE | (S)| OVER ALL S ?V SUCH THAT |S| = K NOTE THAT | (S)| IS AN INVARIANT, I E IF ? : G ?H IS A GRAPH ISOMORPHISM, THEN ?S ?VG, | (? (S))| = | (S)| THUS SUBSETS OF VERTICES WHICH ARE EQUIVALENT UNDER AN AUTOMORPHISM WILL HAVE THE SAME EDGE-BOUNDARY LOOPS, I E EDGES INCIDENT TO JUST ONE VERTEX, ARE IRRELEVANT TO THE EIP SO WE SHALL IGNORE THEM MOST, BUT NOT ALL, OF OUR GRAPHS WILL BE ORDINARY GRAPHS, I E HAVING NO LOOPS AND NO MORE THAN ONE EDGE INCIDENT TO ANY PAIR OF VERTICES THE REPRESENTATION OF AN ORDINARY GRAPH MAY BE SHORTENED TO (V, E), WHERE E ? V , AND ?IS IMPLICITLY THE IDENTITY 1 2 EXAMPLES 1 2 1 KN, THE COMPLETE GRAPH ON N VERTICES KN HAS N VERTICES WITH E = V , I E THERE IS AN EDGE BETWEEN EVERY PAIR OF DISTINCTVERTICES FOREVERY S ?V SUCHTHAT|S| = K,| (S)| = |S × (V ?S)| = K (N ?K) SO THE EIP ON KN IS EASY: ANY K-SET IS A SOLUTION FIG 1 1 THE GRAPH OF Z4 1 2 2 ZN, THE N-CYCLE FOR ZN, V = {0, 1, , N ?1} AND {I, J} ?E IFF I ?J ?±1 (MOD N) THUS Z3= K3 AND Z4 HAS THE DIAGRAM OF FIG 1 1 WE NOW DEDUCE THE SOLUTION OF THE EIP FOR Z4 AND THEN ZN FROM THE FOLLOWING GENERAL REMARKS WHICH WILL BE USEFUL LATER: (1) (A) FOR |S| = K = 0, ON ANY GRAPH, THERE IS ONLY ONE SUBSET, THE EMPTY SET, ? THUS MIN|S|=0 | (S)| = | (?)| = 0 (B) FOR K = |V | = N, THERE IS ALSO ONLY ONE SUBSET, V, AND MIN|S|=N | (S)| = | (V )| = 0 (2) A GRAPH IS CALLED REGULAR OF DEGREE ? IF IT HAS EXACTLY ? EDGES INCIDENT TO EACH VERTEX ON A REGULAR GRAPH, IF |S| = K = 1 THEN | (S)| = ?, SO ANY SINGLETON IS A SOLUTION SET ZN IS REGULAR OF DEGREE 2; HOWEVER FOR N = 4 AND K = THERE ARE TWO SETS NOT EQUIVALENT UNDER THE SYMMETRIES OF ZN: {0, 1} AND {0, 2} ALL OTHER 2-SETS ARE EQUIVALENT TO ONE OF THESE TWO | ({0, 1})| = AND | ({0, 2})| = 4, SO MIN|S|=2 | (S)| = 2 (3) ?G AND ?S ?V , (V ?S) = (S) SO FOR K > 2|V |, MIN|S|=K | (S)| = MIN|S|=N?K | (S)| , WHERE N = |V | THIS COMPLETES OUR SOLUTION OF THE EXTERIOR EIP FOR Z4 IT IS SUMMARIZED IN THE TABLE K MIN|S|=K | (S)|