GEOMETRY OF CUTS AND METRICS
CONTENTS 1 OUTLINE OF THE BOOK 1 1 OUTLINE OF PART I MEASURE ASPECTS: ?1-EMBEDDABILITY AND PROB- ABILITY 1 2 OUTLINE OF PART II HYPERMETRIC SPACES: AN APPROACH VIA GEOM- ETRY OF NUMBERS 1 3 OUTLINE OF PART III EMBEDDINGS OF GRAPHS 1 4 OUTLINE OF PART IV HYPERCUBE EMBEDDINGS AND DESIGNS 1 5 OUTLINE OF PART V FACETS OF THE CUT CONE AND POLYTOPE 2 BASIC DE?NITIONS 2 1 GRAPHS 2 2 POLYHEDRA 2 3 ALGORITHMS AND COMPLEXITY 2 4 MATRICES PART I MEASURE ASPECTS: ?1-EMBEDDABILITY AND PROBABILITY 3 PRELIMINARIES ON DISTANCES 3 1 DISTANCE SPACES AND ?P-SPACES 3 2 MEASURE SPACES AND LP-SPACES 4 THE CUT CONE AND ?1-METRICS 4 1 THE CUT CONE AND POLYTOPE 4 2 ?1-SPACES 4 3 REALIZATIONS, RIGIDITY, SIZE AND SCALE 4 4 COMPLEXITY QUESTIONS 4 5 AN APPLICATION TO STATISTICAL PHYSICS 5 THE CORRELATION CONE AND {0, 1}-COVARIANCES 5 1 THE CORRELATION CONE AND POLYTOPE 5 2 THE COVARIANCE MAPPING 5 3 COVARIANCES 5 4 THE BOOLE PROBLEM I 6 CONDITIONS FOR L1-EMBEDDABILITY 6 1 HYPERMETRIC AND NEGATIVE TYPE CONDITIONS 6 1 1 HYPERMETRIC AND NEGATIVE TYPE INEQUALITIES 6 1 2 HYPERMETRIC AND NEGATIVE TYPE DISTANCE SPACES 6 1 3 ANALOGUES FOR COVARIANCES 6 2 CHARACTERIZATION OF L2-EMBEDDABILITY 6 2 1 SCHOENBERG’S RESULT AND CAYLEY-MENGER DETERMINANTS 6 2 2 MENGER’S RESULT 6 2 3 FURTHER CHARACTERIZATIONS 6 3 A CHAIN OF IMPLICATIONS 6 4 AN EXAMPLE: THE SPHERICAL DISTANCE SPACE 6 5 AN EXAMPLE: KALMANSON DISTANCES 7 OPERATIONS 7 1 THE GATE EXTENSION OPERATION 7 2 THE ANTIPODAL EXTENSION OPERATION 7 3 THE SPHERICAL EXTENSION OPERATION 7 4 AN EXAMPLE: THE COCKTAIL-PARTY GRAPH 7 5 THE DIRECT PRODUCT AND TENSOR PRODUCT OPERATIONS 7 6 THE 1-SUM OPERATION 8 L1-METRICS FROM LATTICES, SEMIGROUPS AND NORMED SPACES 8 1 L1-METRICS FROM LATTICES 8 2 L1-METRICS FROM SEMIGROUPS 8 3 L1-METRICS FROM NORMED SPACES 9 METRIC TRANSFORMS OF L1-SPACES 9 1 THE SCHOENBERG TRANSFORM 9 2 THE BIOTOPE TRANSFORM 9 3 THE POWER TRANSFORM 10 LIPSCHITZ EMBEDDINGS 10 1 EMBEDDINGS WITH DISTORTION 10 2 THE NEGATIVE TYPE CONDITION FOR LIPSCHITZ EMBEDDINGS 10 3 AN APPLICATION FOR APPROXIMATING MULTICOMMODITY FLOWS 11 DIMENSIONALITY QUESTIONS FOR ?1-EMBEDDINGS 11 1 ?1-EMBEDDINGS IN FIXED DIMENSION 11 1 1 THE ORDER OF CONGRUENCE OF THE ?1-SPACE 11 1 2 A CANONICAL DECOMPOSITION FOR DISTANCES 11 1 3 EMBEDDING DISTANCES IN THE ?1-PLANE 11 2 ON THE MINIMUM ?P-DIMENSION 12 EXAMPLES OF THE USE OF THE L1-METRIC 12 1 THE L1-METRIC IN PROBABILITY THEORY 12 2 THE ?1-METRIC IN STATISTICAL DATA ANALYSIS 12 3 THE ?1-METRIC IN COMPUTER VISION AND PATTERN RECOGNITION PART II HYPERMETRIC SPACES: AN APPROACH VIA GEOMETRY OF NUMBERS 13 PRELIMINARIES ON LATTICES 13 1 DISTANCE SPACES 13 2 LATTICES AND DELAUNAY POLYTOPES 13 2 1 LATTICES 13 2 2 DELAUNAY POLYTOPES 13 2 3 BASIC FACTS ON DELAUNAY POLYTOPES 13 2 4 CONSTRUCTION OF DELAUNAY POLYTOPES 13 2 5 ADDITIONAL NOTES 13 3 FINITENESS OF THE NUMBER OF TYPES OF DELAUNAY POLYTOPES 14 HYPERMETRICS AND DELAUNAY POLYTOPES 14 1 CONNECTION BETWEEN HYPERMETRICS AND DELAUNAY POLYTOPES 14 2 POLYHEDRALITY OF THE HYPERMETRIC CONE 14 3 DELAUNAY POLYTOPES IN ROOT LATTICES 14 4 ON THE RADIUS OF DELAUNAY POLYTOPES 15 DELAUNAY POLYTOPES: RANK AND HYPERMETRIC FACES 15 1 RANK OF A DELAUNAY POLYTOPE 15 2 DELAUNAY POLYTOPES RELATED TO FACES 15 2 1 HYPERMETRIC FACES 15 2 2 HYPERMETRIC FACETS 15 3 BOUNDS ON THE RANK OF BASIC DELAUNAY POLYTOPES 16 EXTREME DELAUNAY POLYTOPES 16 1 EXTREME DELAUNAY POLYTOPES AND EQUIANGULAR SETS OF LINES 16 2 THE SCHL¨A?I AND GOSSET POLYTOPES ARE EXTREME 16 3 EXTREME DELAUNAY POLYTOPES IN THE LEECH LATTICE ?24 16 5 EXTREME DELAUNAY POLYTOPES AND PERFECT LATTICES 17 HYPERMETRIC GRAPHS 17 1 CHARACTERIZING HYPERMETRIC AND ?1-GRAPHS 17 2 HYPERMETRIC REGULAR GRAPHS 17 3 EXTREME HYPERMETRIC GRAPHS PART III ISOMETRIC EMBEDDINGS OF GRAPHS 18 PRELIMINARIES ON GRAPHS 19 ISOMETRIC EMBEDDINGS OF GRAPHS INTO HYPERCUBES 19 1 DJOKOVIC’S CHARACTERIZATION 19 2 FURTHER CHARACTERIZATIONS 19 3 ADDITIONAL NOTES 20 ISOMETRIC EMBEDDINGS OF GRAPHS INTO CARTESIAN PRODUCTS 20 1 CANONICAL METRIC REPRESENTATION OF A GRAPH 20 2 THE PRIME FACTORIZATION OF A GRAPH 20 3 METRIC DECOMPOSITION OF BIPARTITE GRAPHS 20 4 ADDITIONAL NOTES 21 ?1-GRAPHS 21 1 RESULTS ON ?1-GRAPHS 21 2 CONSTRUCTION OF BG VIA THE ATOM GRAPH 21 3 PROOFS 21 4 MORE ABOUT ?1-GRAPHS PART IV HYPERCUBE EMBEDDINGS AND DESIGNS 22 RIGIDITY OF THE EQUIDISTANT METRIC 23 HYPERCUBE EMBEDDINGS OF THE EQUIDISTANT METRIC 23 1 PRELIMINARIES ON DESIGNS 23 1 1 (R, ?, N)-DESIGNS AND BIBD’S 23 1 2 INTERSECTING SYSTEMS 23 2 EMBEDDINGS OF 2T11N AND DESIGNS 23 3 THE MINIMUM H-SIZE OF 2T11N 23 4 ALL HYPERCUBE EMBEDDINGS OF 2T11N FOR SMALL N, T 24 RECOGNITION OF HYPERCUBE EMBEDDABLE METRICS 24 1 PRELIMINARY RESULTS 24 2 GENERALIZED BIPARTITE METRICS 24 3 METRICS WITH FEW VALUES 24 3 1 DISTANCES WITH VALUES 2A, B (B ODD) 24 3 2 DISTANCES WITH VALUES A, B, A + B (A,B ODD) 24 3 3 DISTANCES WITH VALUES B, 2A, B + 2A (B ODD, B < 2A) 24 4 TRUNCATED DISTANCES OF GRAPHS 24 4 1 THE CLASS OF GRAPHS HK 24 5 METRICS WITH RESTRICTED EXTREMAL GRAPH 25 CUT LATTICES, QUASI H-DISTANCES AND HILBERT BASES 25 1 CUT LATTICES 25 2 QUASI H-DISTANCES 25 3 HILBERT BASES OF CUTS PART V FACETS OF THE CUT CONE AND POLYTOPE 26 OPERATIONS ON VALID INEQUALITIES AND FACETS 26 1 CUT AND CORRELATION VECTORS 26 2 THE PERMUTATION OPERATION 26 3 THE SWITCHING OPERATION 26 3 1 SWITCHING: A GENERAL DE?NITION 26 3 2 SWITCHING: CUT POLYTOPE VERSUS CUT CONE 26 3 3 THE SYMMETRY GROUP OF THE CUT POLYTOPE 26 4 THE COLLAPSING OPERATION 26 5 THE LIFTING OPERATION 26 6 FACETS BY PROJECTION 27 TRIANGLE INEQUALITIES 27 1 TRIANGLE INEQUALITIES FOR THE CORRELATION POLYTOPE 27 2 ROOTED TRIANGLE INEQUALITIES 27 2 1 AN INTEGER PROGRAMMING FORMULATION FOR MAX-CUT 27 2 2 VOLUME OF THE ROOTED SEMIMETRIC POLYTOPE 27 2 3 ADDITIONAL NOTES 27 3 PROJECTING THE TRIANGLE INEQUALITIES 27 3 1 THE SEMIMETRIC POLYTOPE OF A GRAPH 27 3 2 THE CUT POLYTOPE FOR GRAPHS WITH NO K5-MINOR 27 4 AN EXCURSION TO CYCLE POLYTOPES OF BINARY MATROIDS 27 4 1 PRELIMINARIES ON BINARY MATROIDS 27 4 2 THE CYCLE CONE AND THE CYCLE POLYTOPE 27 4 3 MORE ABOUT CYCLE SPACES 28 HYPERMETRIC INEQUALITIES 28 1 HYPERMETRIC INEQUALITIES: VALIDITY 28 2 HYPERMETRIC FACETS 28 3 SEPARATION OF HYPERMETRIC INEQUALITIES 28 4 GAP INEQUALITIES 28 4 1 A POSITIVE SEMIDE?NITE RELAXATION FOR MAX-CUT 28 5 ADDITIONAL NOTES 29 CLIQUE-WEB INEQUALITIES 29 1 PURE CLIQUE-WEB INEQUALITIES 29 2 GENERAL CLIQUE-WEB INEQUALITIES 29 3 CLIQUE-WEB INEQUALITIES: VALIDITY AND ROOTS 29 4 CLIQUE-WEB FACETS 29 5 SEPARATION OF CLIQUE-WEB INEQUALITIES 29 6 AN EXAMPLE OF PROOF FOR CLIQUE-WEB FACETS 30 OTHER VALID INEQUALITIES AND FACETS 30 1 SUSPENDED-TREE INEQUALITIES 30 2 PATH-BLOCK-CYCLE INEQUALITIES 30 3 CIRCULANT INEQUALITIES 30 4 THE PARACHUTE INEQUALITY 30 4 1 ROOTS AND FIBONACCI NUMBERS 30 4 2 GENERALIZING THE PARACHUTE INEQUALITY 30 5 SOME SPORADIC EXAMPLES N FOR N ?7 30 7 ADDITIONAL NOTES 31 GEOMETRIC PROPERTIES 31 1 DISPROVAL OF A CONJECTURE OF BORSUK USING CUTS 31 2 INEQUALITIES FOR ANGLES OF VECTORS 31 3 THE POSITIVE SEMIDE?NITE COMPLETION PROBLEM 31 3 1 RESULTS 31 3 2 CHARACTERIZING GRAPHS WITH EXCLUDED INDUCED WHEELS 31 4 THE EUCLIDEAN DISTANCE MATRIX COMPLETION PROBLEM 31 4 1 RESULTS 31 4 2 LINKS BETWEEN THE TWO COMPLETION PROBLEMS 31 5 GEOMETRY OF THE ELLIPTOPE 31 6 ADJACENCY PROPERTIES 31 6 1 LOW DIMENSION FACES 31 6 2 SMALL POLYTOPES 31 7 DISTANCE OF FACETS TO THE BARYCENTRUM 31 8 SIMPLEX FACETS BIBLIOGRAPHY CHAPTER 1 OUTLINE OF THE BOOK THIS CHAPTER GIVES AN OVERVIEW OF THE TOPICS TREATED IN THIS BOOK THE CEN- TRAL OBJECTS IN THE BOOK ARE POLYTOPES AND CONES RELATED TO CUTS AND METRICS INTERESTING PROBLEMS CONCERNING THESE POLYHEDRA ARISE IN MANY DI?ERENT AREAS OF MATHEMATICS AND ITS APPLICATIONS SURPRISINGLY, THESE POLYHEDRA HAVE BEEN CONSIDERED INDEPENDENTLY BY A NUMBER OF AUTHORS WITH VARIOUS MATHEMATICAL BACKGROUNDS AND MOTIVATIONS ONE OF OUR OBJECTIVES IS TO SHOW ON THE ONE HAND, THE RICHNESS AND DIVERSITY OF THE RESULTS IN CONNECTION WITH THESE POLYHEDRA, AND ON THE OTHER HAND, HOW THEY CAN BE TREATED IN A UNI?ED WAY AS VARIOUS ASPECTS OF A COMMON SET OF OBJECTS RESEARCH ON CUTS AND METRICS PRO?TS GREATLY FROM THE VARIETY OF SUBJECTS WHERE THE PROBLEMS ARISE OBSERVATIONS MADE IN DI?ERENT AREAS BY INDEPENDENT AUTHORS TURN OUT TO BE EQUIVALENT, FACTS ARE NOT ISOLATED, AND VIEWS FROM DI?ERENT PERSPECTIVES PROVIDE NEW INTERPRETATIONS, CONNECTIONS AND INSIGHTS THIS BOOK IS SUBDIVIDED INTO ?VE PARTS, EACH TREATING SEEMINGLY DIVERSE TOPICS NAMELY, PARTS I TO V CONTAIN RESULTS RELEVANT TO THE FOLLOWING AREAS: 1 THE THEORY OF METRICS; MORE PRECISELY, ISOMETRIC EMBEDDINGS INTO THE BANACH ?1-SPACE, 2 THE GEOMETRY OF NUMBERS; MORE PRECISELY, LATTICES AND DELAUNAY POLYTOPES, 3 GRAPH THEORY; MORE PRECISELY, THE HYPERCUBE AND ITS ISOMETRIC SUBGRAPHS, 4 DESIGN THEORY; MORE PRECISELY, THE DESIGNS ARISING IN CONNECTION WITH THE VARIOUS HYPERCUBE EMBEDDINGS OF THE EQUIDISTANT METRIC, TOGETHER WITH COMPLEXITY ASPECTS OF THE HYPERCUBE EMBEDDABILITY PROBLEM, 5 GEOMETRY OF POLYHEDRA; MORE PRECISELY, GEOMETRIC QUESTIONS ON THE CUT AND METRIC POLYHEDRA (E G , DESCRIPTION OF THEIR FACETS, ADJACENCIES, SYMME- TRIES, ETC ); APPLICATIONS TO THE SOLUTION OF SOME PROBLEMS SUCH AS BORSUK’S PROBLEM, OR COMPLETION PROBLEMS FOR POSITIVE SEMIDE?NITE MATRICES AND EUCLIDEAN DISTANCE MATRICES WE HAVE MADE EACH OF THE ?VE PARTS AS SELF-CONTAINED AS POSSIBLE FOR THIS REASON, SOME NOTIONS AND DE?NITIONS MAY BE REPEATED IN DI?ERENT PARTS IF THEY ARE CENTRAL THERE IN PRINCIPLE, A READER WHO IS INTERESTED, FOR INSTANCE, ONLY IN THE ASPECTS OF GEOMETRY OF NUMBERS OF CUTS MAY CONSULT PART II WITHOUT ANY PRIOR READING OF N) IF AND ONLY IF THERE EXIST A MEASURE SPACE (RESP A PROBABILITY SPACE) (?, A, µ) AND N EVENTS A1, , AN ?A SUCH THAT D(I, J) = µ(AI?AJ) FOR ALL I, J ?VN 1 1 OUTLINE OF PART I (SEE SECTION 4 2 FOR THE ABOVE RESULTS ) THERE IS ANOTHER SET OF POLYHEDRA THAT ARE CLOSELY RELATED TO CUT POLYHEDRA AND FOR WHICH THE ABOVE INTERPRETATION IN TERMS OF MEASURE SPACES TAKES A NICE FORM GIVEN A SUBSET S OF VN, ITS CORRELATION VECTOR ?(S) IS DE?NED BY ?(S)IJ =