Geometry of Cuts and Metrics

1. Outline of the Book
Michel Marie Deza, Monique Laurent

2. Basic Definitions
Michel Marie Deza, Monique Laurent

3. Preliminaries on Distances
Michel Marie Deza, Monique Laurent

4. The Cut Cone and ℓ1-Metrics
Michel Marie Deza, Monique Laurent

5. The Correlation Cone and {0. 1}-Covariances
Michel Marie Deza, Monique Laurent

6. Conditions for L
1-Embeddability
Michel Marie Deza, Monique Laurent

7. Operations
Michel Marie Deza, Monique Laurent

8.
L
1-Metrics from Lattices, Semigroups and Normed Spaces
Michel Marie Deza, Monique Laurent

9. Metric Transforms of L
1-Spaces
Michel Marie Deza, Monique Laurent

10. Lipschitz Embeddings
Michel Marie Deza, Monique Laurent

11. Dimensionality Questions for ℓ
1-Embeddings
Michel Marie Deza, Monique Laurent

12. Examples of the Use of the L
1-Metric
Michel Marie Deza, Monique Laurent

13. Preliminaries on Lattices
Michel Marie Deza, Monique Laurent

14. Hypermetrics and Delaunay Polytopes
Michel Marie Deza, Monique Laurent

15. Delaunay Polytopes: Rank and Hypermetric Faces
Michel Marie Deza, Monique Laurent

16. Extreme Delaunay Polytopes
Michel Marie Deza, Monique Laurent

17. Hypermetric Graphs
Michel Marie Deza, Monique Laurent

18. Preliminaries on Graphs
Michel Marie Deza, Monique Laurent

19. Isometric Embeddings of Graphs into Hypercubes
Michel Marie Deza, Monique Laurent

20. Isometric Embeddings of Graphs into Cartesian Products
Michel Marie Deza, Monique Laurent

21.
ℓ
1-Graphs
Michel Marie Deza, Monique Laurent

22. Rigidity of the Equidistant Metric
Michel Marie Deza, Monique Laurent

23. Hypercube Embeddings of the Equidistant Metric
Michel Marie Deza, Monique Laurent

24. Recognition of Hypercube Embeddable Metrics
Michel Marie Deza, Monique Laurent

25. Cut Lattices, Quasi h-Distances and Hilbert Bases
Michel Marie Deza, Monique Laurent

26. Operations on Valid Inequalities and Facets
Michel Marie Deza, Monique Laurent

27. Triangle Inequalities
Michel Marie Deza, Monique Laurent

28. Hypermetric Inequalities
Michel Marie Deza, Monique Laurent

29. Clique-Web Inequalities
Michel Marie Deza, Monique Laurent

30. Other Valid Inequalities and Facets
Michel Marie Deza, Monique Laurent

31. Geometric Properties
Michel Marie Deza, Monique Laurent

Avainsanat: Mathematics, Combinatorics, Convex and Discrete Geometry, Number Theory, Math Applications in Computer Science