We tackle the problem of a combinatorial classification of finite metric spaces via their fundamental polytopes, as suggested by Vershik in 2010. In this paper we consider a hyperplane arrangement associated to every split pseudometric and, for tree-like metrics, we study the combinatorics of its underlying matroid. We give explicit formulas for the face numbers of fundamental polytopes and Lipschitz polytopes of all tree-like metrics, and we characterize the metric trees for which the fundamental polytope is simplicial.
Lipschitz polytopes of finite metric spaces are weighted digraph polyhedra in the sense of Joswig and Loho @cite_20 , who give some general results about dimension, face structure and projections [ 2.1, 2.2, 2.6] JL but mostly focus on the case of braid cones'' which does not apply to our context. We close by mentioning that the polyhedra considered, e.g., in the above-mentioned work of Hirai [Formula (4.1)] Hirai are different from the Lipschitz polytopes we consider here: in fact, such polyhedra are (translated) zonotopes for all split-decomposable metrics [Remark 4.10] Hirai , while -- for instance -- the Lipschitz polytope of any split-decomposable metric on @math points is only a zonotope if the associated split system is compatible.
@cite_20
1968429800 2964067385 2036959865 2069572385
We study the quantitative geometry of graphs in terms of their genus, using the structure of certain "cut graphs," i.e. subgraphs whose removal leaves a planar graph. In particular, we give optimal bounds for random partitioning schemes, as well as various types of embeddings. Using these geometric primitives, we present exponentially improved dependence on genus for a number of problems like approximate max-flow min-cut theorems, approximations for uniform and nonuniform Sparsest Cut, treewidth approximation, Laplacian eigenvalue bounds, and Lipschitz extension theorems and related metric labeling problems. We list here a sample of these improvements. All the following statements refer to graphs of genus g, unless otherwise noted. • We show that such graphs admit an O(log g)-approximate multi-commodity max-flow min-cut theorem for the case of uniform demands. This bound is optimal, and improves over the previous bound of O(g) [KPR93, FT03]. For general demands, we show that the worst possible gap is O(log g + CP), where CP is the gap for planar graphs. This dependence is optimal, and already yields a bound of O(log g + √log n), improving over the previous bound of O(√g log n) [KLMN04]. • We give an O(√log g)-approximation for the uniform Sparsest Cut, balanced vertex separator, and treewidth problems, improving over the previous bound of O(g) [FHL05]. • If a graph G has genus g and maximum degree D, we show that the kth Laplacian eigenvalue of G is (log g)2 · O(kgD n), improving over the previous bound of g2·O(kgD n) [KLPT09]. There is a lower bound of Ω(kgD n), making this result almost tight. • We show that if (X, d) is the shortest-path metric on a graph of genus g and S ⊆ X, then every L-Lipschitz map f: S → Z into a Banach space Z admits an O(L log g)-Lipschitz extension f: X → Z. This improves over the previous bound of O(Lg) [LN05], and compares to a lower bound of Ω(L√log g). In a related way, we show that there is an O(log g)-approximation for the 0-extension problem on such graphs, improving over the previous O(g) bound. • We show that every n-vertex shortest-path metric on a graph of genus g embeds into L2 with distortion O(log g + √log n), improving over the previous bound of O(√g log n). Our result is asymptotically optimal for every dependence g = g(n). This paper is about the combinatorics of finite point configurations in the tropical projective space or, dually, of arrangements of finitely many tropical hyperplanes. Moreover, arrangements of finitely many tropical halfspaces can be considered via coarsenings of the resulting polyhedral decompositions of Rd. This leads to natural cell decompositions of the tropical projective space TPmind−1. Our method is to employ a known class of ordinary convex polyhedra naturally associated with weighted digraphs. This way we can relate to and use results from combinatorics and optimization. One outcome is the solution of a conjecture of Develin and Yu (2007). We study the metric properties of finite subsets of L1. The analysis of such metrics is central to a number of important algorithmic problems involving the cut structure of weighted graphs, including the Sparsest Cut Problem, one of the most compelling open problems in the field of approximation algorithms. Additionally, many open questions in geometric non-linear functional analysis involve the properties of finite subsets of L1.We present some new observations concerning the relation of L1 to dimension, topology, and Euclidean distortion. We show that every n-point subset of L1 embeds into L2 with average distortion O(√log n), yielding the first evidence that the conjectured worst-case bound of O(√log n) is valid. We also address the issue of dimension reduction in Lp for p ∈ (1, 2). We resolve a question left open by M. Charikar and A. Sahai [Dimension reduction in the l1 norm, in: Proceedings of the 43rd Annual IEEE Conference on Foundations of Computer Science, ACM, 2002, pp. 251-260] concerning the impossibility of dimension reduction with a linear map in the above cases, and we show that a natural variant of the recent example of Brinkman and Charikar [On the impossibility of dimension reduction in l1, in: Proceedings of the 44th Annual IEEE Conference on Foundations of Computer Science, ACM, 2003, pp. 514-523], cannot be used to prove a lower bound for the non-linear case. This is acomplished by exhibiting constant-distortion embeddings of snowflaked planar metrics into Euclidean space. This paper addresses two problems lying at the intersection of geometric analysis and theoretical computer science: The non-linear isomorphic Dvoretzky theorem and the design of good approximate distance oracles for large distortion. We introduce the notion of Ramsey partitions of a finite metric space, and show that the existence of good Ramsey partitions implies a solution to the metric Ramsey problem for large distortion (a.k.a. the non-linear version of the isomorphic Dvoretzky theorem, as introduced by Bourgain, Figiel, and Milman in BFM86 ). We then proceed to construct optimal Ramsey partitions, and use them to show that for every @math , every @math -point metric space has a subset of size @math which embeds into Hilbert space with distortion @math . This result is best possible and improves part of the metric Ramsey theorem of Bartal, Linial, Mendel and Naor BLMN05 , in addition to considerably simplifying its proof. We use our new Ramsey partitions to design approximate distance oracles with a universal constant query time, closing a gap left open by Thorup and Zwick in TZ05 . Namely, we show that for every @math point metric space @math , and @math , there exists an @math -approximate distance oracle whose storage requirement is @math , and whose query time is a universal constant. We also discuss applications of Ramsey partitions to various other geometric data structure problems, such as the design of efficient data structures for approximate ranking.