|
|
1 | (10) |
|
1.1 Outline of Part I. Measure Aspects: XXX(1)-Embeddability and Probability |
|
|
2 | (2) |
|
1.2 Outline of Part II. Hypermetric Spaces: an Approach via Geometry of Numbers |
|
|
4 | (2) |
|
1.3 Outline of Part III. Embeddings of Graphs |
|
|
6 | (1) |
|
1.4 Outline of Part IV. Hypercube Embeddings and Designs |
|
|
7 | (1) |
|
1.5 Outline of Part V. Facets of the Cut Cone and Polytope |
|
|
8 | (3) |
|
|
11 | (12) |
|
|
11 | (3) |
|
|
14 | (4) |
|
2.3 Algorithms and Complexity |
|
|
18 | (1) |
|
|
19 | (4) |
Part I. Measure Aspects: XXX(1)-Embeddability and Probability |
|
23 | (144) |
|
3. Preliminaries on Distances |
|
|
27 | (10) |
|
3.1 Distance Spaces and XXX(p)-Spaces |
|
|
27 | (5) |
|
3.2 Measure Spaces and L(p)-Spaces |
|
|
32 | (5) |
|
4. The Cut Cone and XXX(1)-Metrics |
|
|
37 | (16) |
|
4.1 The Cut Cone and Polytope |
|
|
37 | (2) |
|
|
39 | (4) |
|
4.3 Realizations, Rigidity, Size and Scale |
|
|
43 | (5) |
|
|
48 | (3) |
|
4.5 An Application to Statistical Physics |
|
|
51 | (2) |
|
5. The Correlation Cone and {0,1}-Covariances |
|
|
53 | (14) |
|
5.1 The Correlation Cone and Polytope |
|
|
53 | (2) |
|
5.2 The Covariance Mapping |
|
|
55 | (3) |
|
|
58 | (3) |
|
|
61 | (6) |
|
6. Conditions for L(1)-Embeddability |
|
|
67 | (26) |
|
6.1 Hypermetric and Negative Type Conditions |
|
|
67 | (6) |
|
6.1.1 Hypermetric and Negative Type Inequalities |
|
|
67 | (4) |
|
6.1.2 Hypermetric and Negative Type Distance Spaces |
|
|
71 | (1) |
|
6.1.3 Analogues for Covariances |
|
|
72 | (1) |
|
6.2 Characterization of L(2)-Embeddability |
|
|
73 | (9) |
|
6.2.1 Schoenberg's Result and Cayley-Menger Determinants |
|
|
74 | (4) |
|
|
78 | (2) |
|
6.2.3 Further Characterizations |
|
|
80 | (2) |
|
6.3 A Chain of Implications |
|
|
82 | (4) |
|
6.4 An Example: The Spherical Distance Space |
|
|
86 | (5) |
|
6.5 An Example: Kalmanson Distances |
|
|
91 | (2) |
|
|
93 | (12) |
|
7.1 The Gate Extension Operation |
|
|
93 | (1) |
|
7.2 The Antipodal Extension Operation |
|
|
94 | (3) |
|
7.3 The Spherical Extension Operation |
|
|
97 | (1) |
|
7.4 An Example: The Cocktail-Party Graph |
|
|
98 | (3) |
|
7.5 The Direct Product and Tensor Product Operations |
|
|
101 | (2) |
|
|
103 | (2) |
|
8. L(1)-Metrics from Lattices, Semigroups and Normed Spaces |
|
|
105 | (8) |
|
8.1 L(1)-Metrics from Lattices |
|
|
105 | (2) |
|
8.2 L(1)-Metrics from Semigroups |
|
|
107 | (2) |
|
8.3 L(1)-Metrics from Normed Spaces |
|
|
109 | (4) |
|
9. Metric Transforms of L(1)-Spaces |
|
|
113 | (12) |
|
9.1 The Schoenberg Transform |
|
|
115 | (3) |
|
9.2 The Biotope Transform |
|
|
118 | (2) |
|
|
120 | (5) |
|
|
125 | (14) |
|
10.1 Embeddings with Distortion |
|
|
125 | (5) |
|
10.2 The Negative Type Condition for Lipschitz Embeddings |
|
|
130 | (2) |
|
10.3 An Application for Approximating Multicommodity Flows |
|
|
132 | (7) |
|
11. Dimensionality Questions for XXX(1)-Embeddings |
|
|
139 | (22) |
|
11.1 XXX(1)-Embeddings in Fixed Dimension |
|
|
139 | (17) |
|
11.1.1 The Order of Congruence of the XXX(1)-Space |
|
|
141 | (4) |
|
11.1.2 A Canonical Decomposition for Distances |
|
|
145 | (3) |
|
11.1.3 Embedding Distances in the XXX(1)-Plane |
|
|
148 | (8) |
|
11.2 On the Minimum XXX(p)-Dimension |
|
|
156 | (5) |
|
12. Examples of the Use of the L(1)-Metric |
|
|
161 | (6) |
|
12.1 The L(1)-Metric in Probability Theory |
|
|
161 | (1) |
|
12.2 The l(1)-Metric in Statistical Data Analysis |
|
|
162 | (1) |
|
12.3 The l(1)-Metric in Computer Vision and Pattern Recognition |
|
|
163 | (4) |
Part II. Hypermetric Spaces: an Approach via Geometry of Numbers |
|
167 | (108) |
|
13. Preliminaries on Lattices |
|
|
175 | (18) |
|
|
175 | (2) |
|
13.2 Lattices and Delaunay Polytopes |
|
|
177 | (12) |
|
|
177 | (2) |
|
13.2.2 Delaunay Polytopes |
|
|
179 | (3) |
|
13.2.3 Basic Facts on Delaunay Polytopes |
|
|
182 | (2) |
|
13.2.4 Construction of Delaunay Polytopes |
|
|
184 | (3) |
|
|
187 | (2) |
|
13.3 Finiteness of the Number of Types of Delaunay Polytopes |
|
|
189 | (4) |
|
14. Hypermetrics and Delaunay Polytopes |
|
|
193 | (24) |
|
14.1 Connection between Hypermetrics and Delaunay Polytopes |
|
|
193 | (6) |
|
14.2 Polyhedrality of the Hypermetric Cone |
|
|
199 | (7) |
|
14.3 Delaunay Polytopes in Root Lattices |
|
|
206 | (5) |
|
14.4 On the Radius of Delaunay Polytopes |
|
|
211 | (6) |
|
15. Delaunay Polytopes: Rank and Hypermetric Faces |
|
|
217 | (18) |
|
15.1 Rank of a Delaunay Polytope |
|
|
217 | (5) |
|
15.2 Delaunay Polytopes Related to Faces |
|
|
222 | (8) |
|
|
222 | (4) |
|
15.2.2 Hypermetric Facets |
|
|
226 | (4) |
|
15.3 Bounds on the Rank of Basic Delaunay Polytopes |
|
|
230 | (5) |
|
16. Extreme Delaunay Polytopes |
|
|
235 | (16) |
|
16.1 Extreme Delaunay Polytopes and Equiangular Sets of Lines |
|
|
236 | (3) |
|
16.2 The Schlafli and Gosset Polytopes are Extreme |
|
|
239 | (5) |
|
16.3 Extreme Delaunay Polytopes in the Leech Lattice XXX(24) |
|
|
244 | (1) |
|
16.4 Extreme Delaunay Polytopes in the Barnes-Wall Lattice XXX(16) |
|
|
245 | (3) |
|
16.5 Extreme Delaunay Polytopes and Perfect Lattices |
|
|
248 | (3) |
|
|
251 | (24) |
|
17.1 Characterizing Hypermetric and XXX(1)-Graphs |
|
|
252 | (10) |
|
17.2 Hypermetric Regular Graphs |
|
|
262 | (7) |
|
17.3 Extreme Hypermetric Graphs |
|
|
269 | (6) |
Part III. Isometric Embeddings of Graphs |
|
275 | (56) |
|
18. Preliminaries on Graphs |
|
|
279 | (4) |
|
19. Isometric Embeddings of Graphs into Hypercubes |
|
|
283 | (14) |
|
19.1 Djokovic's Characterization |
|
|
283 | (3) |
|
19.2 Further Characterizations |
|
|
286 | (7) |
|
|
293 | (4) |
|
20. Isometric Embeddings of Graphs into Cartesian Products |
|
|
297 | (16) |
|
20.1 Canonical Metric Representation of a Graph |
|
|
297 | (8) |
|
20.2 The Prime Factorization of a Graph |
|
|
305 | (1) |
|
20.3 Metric Decomposition of Bipartite Graphs |
|
|
306 | (2) |
|
|
308 | (5) |
|
|
313 | (18) |
|
21.1 Results on l(1)-Graphs |
|
|
313 | (3) |
|
21.2 Construction of G via the Atom Graph |
|
|
316 | (6) |
|
|
322 | (3) |
|
21.4 More about l(1)-Graphs |
|
|
325 | (6) |
Part IV. Hypercube Embeddings and Designs |
|
331 | (64) |
|
22. Rigidity of the Equidistant Metric |
|
|
335 | (6) |
|
23. Hypercube Embeddings of the Equidistant Metric |
|
|
341 | (12) |
|
23.1 Preliminaries on Designs |
|
|
341 | (9) |
|
23.1.1 (r, XXX, n)-Designs and BIBD's |
|
|
341 | (3) |
|
23.1.2 Intersecting Systems |
|
|
344 | (1) |
|
23.2 Embeddings of 2t1(n) and Designs |
|
|
345 | (2) |
|
23.3 The Minimum h-Size of 2t1(n) |
|
|
347 | (3) |
|
23.4 All Hypercube Embeddings of 2t1(n) for Small n,t |
|
|
350 | (3) |
|
24. Recognition of Hypercube Embeddable Metrics |
|
|
353 | (28) |
|
|
354 | (3) |
|
24.2 Generalized Bipartite Metrics |
|
|
357 | (5) |
|
24.3 Metrics with Few Values |
|
|
362 | (8) |
|
24.3.1 Distances with Values 2a, b (b odd) |
|
|
363 | (2) |
|
24.3.2 Distances with Values a,b,a+b (a,b odd) |
|
|
365 | (2) |
|
24.3.3 Distances with Values b,2a,b+2a (b odd, b less than 2a) |
|
|
367 | (3) |
|
24.4 Truncated Distances of Graphs |
|
|
370 | (5) |
|
24.4.1 The Class of Graphs H(k) |
|
|
372 | (3) |
|
24.5 Metrics with Restricted Extremal Graph |
|
|
375 | (6) |
|
25. Cut Lattices, Quasi h-Distances and Hilbert Bases |
|
|
381 | (14) |
|
|
381 | (4) |
|
|
385 | (6) |
|
25.3 Hilbert Bases of Cuts |
|
|
391 | (4) |
Part V. Facets of the Cut Cone and Polytope |
|
395 | (156) |
|
26. Operations on Valid Inequalities and Facets |
|
|
401 | (20) |
|
26.1 Cut and Correlation Vectors |
|
|
401 | (2) |
|
26.2 The Permutation Operation |
|
|
403 | (1) |
|
26.3 The Switching Operation |
|
|
403 | (7) |
|
26.3.1 Switching: A General Definition |
|
|
403 | (2) |
|
26.3.2 Switching: Cut Polytope versus Cut Cone |
|
|
405 | (4) |
|
26.3.3 The Symmetry Group of the Cut Polytope |
|
|
409 | (1) |
|
26.4 The Collapsing Operation |
|
|
410 | (3) |
|
26.5 The Lifting Operation |
|
|
413 | (3) |
|
26.6 Facets by Projection |
|
|
416 | (5) |
|
27. Triangle Inequalities |
|
|
421 | (24) |
|
27.1 Triangle Inequalities for the Correlation Polytope |
|
|
423 | (1) |
|
27.2 Rooted Triangle Inequalities |
|
|
424 | (6) |
|
27.2.1 An Integer Programming Formulation for Max-Cut |
|
|
425 | (1) |
|
27.2.2 Volume of the Rooted Semimetric Polytope |
|
|
426 | (2) |
|
|
428 | (2) |
|
27.3 Projecting the Triangle Inequalities |
|
|
430 | (5) |
|
27.3.1 The Semimetric Polytope of a Graph |
|
|
431 | (3) |
|
27.3.2 The Cut Polytope for Graphs with no K(5)-Minor |
|
|
434 | (1) |
|
27.4 An Excursion to Cycle Polytopes of Binary Matroids |
|
|
435 | (10) |
|
27.4.1 Preliminaries on Binary Matroids |
|
|
436 | (2) |
|
27.4.2 The Cycle Cone and the Cycle Polytope |
|
|
438 | (3) |
|
27.4.3 More about Cycle Spaces |
|
|
441 | (4) |
|
28. Hypermetric Inequalities |
|
|
445 | (22) |
|
28.1 Hypermetric Inequalities: Validity |
|
|
445 | (2) |
|
|
447 | (6) |
|
28.3 Separation of Hypermetric Inequalities |
|
|
453 | (4) |
|
|
457 | (6) |
|
28.4.1 A Positive Semidefinite Relaxation for Max-Cut |
|
|
459 | (4) |
|
|
463 | (4) |
|
29. Clique-Web Inequalities |
|
|
467 | (20) |
|
29.1 Pure Clique-Web Inequalities |
|
|
467 | (3) |
|
29.2 General Clique-Web Inequalities |
|
|
470 | (2) |
|
29.3 Clique-Web Inequalities: Validity and Roots |
|
|
472 | (5) |
|
|
477 | (4) |
|
29.5 Separation of Clique-Web Inequalities |
|
|
481 | (2) |
|
29.6 An Example of Proof for Clique-Web Facets |
|
|
483 | (4) |
|
30. Other Valid Inequalities and Facets |
|
|
487 | (24) |
|
30.1 Suspended-Tree Inequalities |
|
|
487 | (5) |
|
30.2 Path-Block-Cycle Inequalities |
|
|
492 | (4) |
|
30.3 Circulant Inequalities |
|
|
496 | (1) |
|
30.4 The Parachute Inequality |
|
|
497 | (5) |
|
30.4.1 Roots and Fibonacci Numbers |
|
|
498 | (2) |
|
30.4.2 Generalizing the Parachute Inequality |
|
|
500 | (2) |
|
30.5 Some Sporadic Examples |
|
|
502 | (1) |
|
30.6 Complete Description of CUT(n) and CUT(n) for nXXX7 |
|
|
503 | (3) |
|
|
506 | (5) |
|
|
511 | (40) |
|
31.1 Disproval of a Conjecture of Borsuk Using Cuts |
|
|
512 | (2) |
|
31.2 Inequalities for Angles of Vectors |
|
|
514 | (1) |
|
31.3 The Positive Semidefinite Completion Problem |
|
|
515 | (12) |
|
|
516 | (6) |
|
31.3.2 Characterizing Graphs with Excluded Induced Wheels |
|
|
522 | (5) |
|
31.4 The Euclidean Distance Matrix Completion Problem |
|
|
527 | (7) |
|
|
529 | (2) |
|
31.4.2 Links Between the Two Completion Problems |
|
|
531 | (3) |
|
31.5 Geometry of the Elliptope |
|
|
534 | (5) |
|
31.6 Adjacency Properties |
|
|
539 | (7) |
|
31.6.1 Low Dimension Faces |
|
|
539 | (3) |
|
|
542 | (4) |
|
31.7 Distance of Facets to the Barycentrum |
|
|
546 | (3) |
|
|
549 | (2) |
Bibliography |
|
551 | (24) |
Notation Index |
|
575 | (4) |
Subject Index |
|
579 | |