The geometry of graphs and some of its algorithmic applications

In this paper we explore some implications of viewing graphs asgeometric objects. This approach offers a new perspective on a number of graph-theoretic and algorithmic problems. There are several ways to model graphs geometrically and our main concern here is with geometric representations that respect themetric of the (possibly weighted) graph. Given a graphG we map its vertices to a normed space in an attempt to (i) keep down the dimension of the host space, and (ii) guarantee a smalldistortion, i.e., make sure that distances between vertices inG closely match the distances between their geometric images. In this paper we develop efficient algorithms for embedding graphs low-dimensionally with a small distortion. Further algorithmic applications include:

1. A simple, unified approach to a number of problems on multicommodity flows, including the Leighton-Rao Theorem [37] and some of its extensions. We solve an open question in this area, showing that the max-flow vs. min-cut gap in thek-commodities problem isO(logk). Our new deterministic polynomial-time algorithm finds a (nearly tight) cut meeting this bound.
2. For graphs embeddable in low-dimensional spaces with a small distortion, we can find low-diameter decompositions (in the sense of [7] and [43]). The parameters of the decomposition depend only on the dimension and the distortion and not on the size of the graph.
3. In graphs embedded this way, small balancedseparators can be found efficiently.

Given faithful low-dimensional representations of statistical data, it is possible to obtain meaningful and efficientclustering. This is one of the most basic tasks in pattern-recognition. For the (mostly heuristic) methods used in the practice of pattern-recognition, see [20], especially chapter 6. Our studies of multicommodity flows also imply that every embedding of (the metric of) ann-vertex, constant-degree expander into a Euclidean space (of any dimension) has distortion Ω(logn). This result is tight, and closes a gap left open by Bourgain [12].     

A Lower Bound on the Distortion of Embedding Planar Metrics into Euclidean Space

We exhibit a simple infinite family of series-parallel graphs that cannot be metrically embedded into Euclidean space with distortion smaller than

Assouad-Nagata dimension of locally finite groups and asymptotic cones

In this paper we study two problems concerning Assouad-Nagata dimension:

(1)

Is there a metric space of positive asymptotic Assouad-Nagata dimension such that all of its asymptotic cones are of Assouad-Nagata dimension zero? (Dydak and Higes, 2008 [11, Question 4.5]).

(2)

Suppose G is a locally finite group with a proper left invariant metric dG. If dimAN(G,dG)>0, is dimAN(G,dG) infinite? (Brodskiy et al., preprint [6, Problem 5.3]).

The first question is answered positively. We provide examples of metric spaces of positive (even infinite) Assouad-Nagata dimension such that all of its asymptotic cones are ultrametric. The metric spaces can be groups with proper left invariant metrics.The second question has a negative solution. We show that for each n there exists a locally finite group of Assouad-Nagata dimension n. As a consequence this solves for non-finitely generated countable groups the question about the existence of metric spaces of finite asymptotic dimension whose asymptotic Assouad-Nagata dimension is larger but finite.     

Limitations to Fréchet’s metric embedding method

Fréchet’s classical isometric embedding argument has evolved to become a major tool in the study of metric spaces. An important example of a Fréchet embedding is Bourgain's embedding [4]. The authors have recently shown [2] that for every ε>0, anyn-point metric space contains a subset of size at leastn ^1−ε which embeds into ℓ₂ with distortion . The embedding used in [2] is non-Fréchet, and the purpose of this note is to show that this is not coincidental. Specifically, for every ε>0, we construct arbitrarily largen-point metric spaces, such that the distortion of any Fréchet embedding into ℓ_p on subsets of size at leastn ^1/2+ε is Ω((logn)^1/p ). Supported in part by a grant from the Israeli National Science Foundation. Supported in part by a grant from the Israeli National Science Foundation. Supported in part by the Landau Center.     

Measured descent: a new embedding method for finite metrics

We devise a new embedding technique, which we call measured descent, based on decomposing a metric space locally, at varying speeds, according to the density of some probability measure. This provides a refined and unified framework for the two primary methods of constructing Fréchet embeddings for finite metrics, due to Bourgain (1985) and Rao (1999). We prove that any n-point metric space (X, d) embeds in Hilbert space with distortion where α_X is a geometric estimate on the decomposability of X. As an immediate corollary, we obtain an distortion embedding, where λ_X is the doubling constant of X. Since λ_X ≤ n, this result recovers Bourgain’s theorem, but when the metric X is, in a sense, “low-dimensional,” improved bounds are achieved. Our embeddings are volume-respecting for subsets of arbitrary size. One consequence is the existence of (k, O(log n)) volume-respecting embeddings for all 1 ≤ k ≤ n, which is the best possible, and answers positively a question posed by U. Feige. Our techniques are also used to answer positively a question of Y. Rabinovich, showing that any weighted n-point planar graph embeds in with O(1) distortion. The O(log n) bound on the dimension is optimal, and improves upon the previously known bound of O((log n)²). Received: April 2004 Accepted: August 2004 Revision: December 2004 J.R.L. Supported by NSF grant CCR-0121555 and an NSF Graduate Research Fellowship.     

On Average Distortion of Embedding Metrics into the Line

We introduce and study the notion of the average distortion of a nonexpanding embedding of one metric space into another. Less sensitive than the multiplicative metric distortion, the average distortion captures well the global picture and, overall, is a quite interesting new measure of metric proximity, related to the concentration of measure phenomenon. The paper mostly deals with embeddings into the real line with a low (as much as it is possible) average distortion. Our main technical contribution is that the shortest-path metrics of special (e.g., planar, bounded treewidth, etc.) undirected weighted graphs can be embedded into the line with constant average distortion. This has implications, e.g., on the value of the MinCut–MaxFlow gap in uniform-demand multicommodity flows on such graphs. A preliminary version of this paper has appeared at STOC’03, pp. 156–162. Supported in part by a grant ISF-247-02-10.5.     

Volume in General Metric Spaces

A central question in the geometry of finite metric spaces is how well can an arbitrary metric space be “faithfully preserved” by a mapping into Euclidean space. In this paper we present an algorithmic embedding which obtains a new strong measure of faithful preservation: not only does it (approximately) preserve distances between pairs of points, but also the volume of any set of \(k\) points. Such embeddings are known as volume preserving embeddings. We provide the first volume preserving embedding that obtains constant average volume distortion for sets of any fixed size. Moreover, our embedding provides constant bounds on all bounded moments of the volume distortion while maintaining the best possible worst-case volume distortion. Feige, in his seminal work on volume preserving embeddings defined the volume of a set \(S = \{v_1, \ldots , v_k \}\) of points in a general metric space: the product of the distances from \(v_i\) to \(\{ v_1, \dots , v_{i-1} \}\) , normalized by \(\tfrac{1}{(k-1)!}\) , where the ordering of the points is that given by Prim’s minimum spanning tree algorithm. Feige also related this notion to the maximal Euclidean volume that a Lipschitz embedding of \(S\) into Euclidean space can achieve. Syntactically this definition is similar to the computation of volume in Euclidean spaces, which however is invariant to the order in which the points are taken. We show that a similar robustness property holds for Feige’s definition: the use of any other order in the product affects volume \(^{1/(k-1)}\) by only a constant factor. Our robustness result is of independent interest as it presents a new competitive analysis for the greedy algorithm on a variant of the online Steiner tree problem where the cost of buying an edge is logarithmic in its length. This robustness property allows us to obtain our results on volume preserving embedding.     

The Euclidean Distortion of Complete Binary Trees

   Abstract. Bourgain [1] showed that every embedding of the complete binary tree of depth n into l ₂ has metric distortion ≥

A new inductive approach for counting dimension in large scale

We introduce the notion of large scale dimensiongrad as a large scale invariant of asymptotic resemblance spaces. Consequently it can be considered as a large scale invariant of metric spaces. The large scale dimensiongrad is a way of counting dimension in large scale but it is different from asymptotic dimension in general, as we show in the paper, too.     

On the Optimality of Gluing over Scales

We show that for every α>0, there exist n-point metric spaces (X,d) where every “scale” admits a Euclidean embedding with distortion at most α, but the whole space requires distortion at least \(\varOmega (\sqrt {\alpha\log n})\). This shows that the scale-gluing lemma (Lee in SODA’05: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 92–101, Society for Industrial and Applied Mathematics, Philadelphia, 2005) is tight and disproves a conjecture stated there. This matching upper bound was known to be tight at both endpoints, i.e., when α=Θ(1) and α=Θ(log?n), but nowhere in between.More specifically, we exhibit n-point spaces with doubling constant λ requiring Euclidean distortion \(\varOmega (\sqrt{\log\lambda\log n})\), which also shows that the technique of “measured descent” (Krauthgamer et al. in Geom. Funct. Anal. 15(4):839–858, 2005) is optimal. We extend this to L _p spaces with p>1, where one requires distortion at least Ω((log?n)^1/q (log?λ)^1?1/q ) when q=max?{p,2}, a result which is tight for every p>1.     

Embeddings of Riemannian manifolds with finite eigenvector fields of connection Laplacian

We study the problem asking if one can embed manifolds into finite dimensional Euclidean spaces by taking finite number of eigenvector fields of the connection Laplacian. This problem is essential for the dimension reduction problem in manifold learning. In this paper, we provide a positive answer to the problem. Specifically, we use eigenvector fields to construct local coordinate charts with low distortion, and show that the distortion constants depend only on geometric properties of manifolds with metrics in the little Hölder space \(c^{2,\alpha }\). Next, we use the coordinate charts to embed the entire manifold into a finite dimensional Euclidean space. The proof of the results relies on solving the elliptic system and providing estimates for eigenvector fields and the heat kernel and their gradients. We also provide approximation results for eigenvector field under the \(c^{2,\alpha }\) perturbation.     

Dimension zero vs measure zero

The following problem is discussed: If is a topological space of universal measure zero, does it have also dimension zero? It is shown that in a model of set theory it is so for separable metric spaces and that under the Martin's Axiom there are separable metric spaces of positive dimension yet of universal measure zero. It is also shown that for each finite measure in a metric space there is a zero-dimensional subspace that has full measure. Similar questions concerning perfectly meager sets and other types of small sets are also discussed.

     

A universal reflexive space for the class of uniformly convex Banach spaces

We show that there exists a separable reflexive Banach space into which every separable uniformly convex Banach space isomorphically embeds. This solves problems raised by J. Bourgain [B] in 1980 and by W. B. Johnson in 1977 [Jo]. We also give intrinsic characterizations of separable reflexive Banach spaces which embed into a reflexive space with a block q-Hilbertian and/or a block p-Besselian finite dimensional decomposition. Dedicated to the memory of V. I. Gurarii Research supported by the National Science Foundation.     

Measure Density and Extension of Besov and Triebel–Lizorkin Functions

We show that a domain is an extension domain for a Haj?asz–Besov or for a Haj?asz–Triebel–Lizorkin space if and only if it satisfies a measure density condition. We use a modification of the Whitney extension where integral averages are replaced by median values, which allows us to handle also the case \(0<p<1\). The necessity of the measure density condition is derived from embedding theorems; in the case of Haj?asz–Besov spaces we apply an optimal Lorentz-type Sobolev embedding theorem which we prove using a new interpolation result. This interpolation theorem says that Haj?asz–Besov spaces are intermediate spaces between \(L^p\) and Haj?asz–Sobolev spaces. Our results are proved in the setting of a metric measure space, but most of them are new even in the Euclidean setting, for instance, we obtain a characterization of extension domains for classical Besov spaces \(B^s_{p,q}\), \(0<s<1\), \(0<p<\infty \), \(0<q\le \infty \), defined via the \(L^p\)-modulus of smoothness of a function.     

Embedding the planar structure of 4-dimensional linear spaces into projective spaces

It is known that a linear spaces of dimensiond has at least as many hyperplanes as points with equality if it is a (possibly degenerate) projective space. If there are only a few more hyperplanes than points, then the linear space can still be embedded in a projective space of the same dimension. But even if the difference between the number of hyperplanes and points is too big to ensure an embedding, it seems likely that the linear space is closely related to a projective space. We shall demonstrate this in the cased=4.     

Convexity in finite metric spaces

A subsetS of a metric space (X,d) is calledd-convex if for any pair of pointsx,y S each pointz X withd(x,z) +d(z,y) =d(x,y) belongs toS. We give some results and open questions concerning isometric and convexity-preserving embeddings of finite metric spaces into standard spaces and the number ofd-convex sets of a finite metric space.     

On tangent cones of Alexandrov spaces with curvature bounded below

The tangent cones of an inner metric Alexandrov space with finite Hausdorff dimension and a lower curvature bound are always inner metric spaces with nonnegative curvature. In this paper we construct an infinite-dimensional inner metric Alexandrov space of nonnegative curvature which has in one point a tangent cone whose metric is not an inner metric. Received: 20 October 1999 / Revised version: 8 May 2000     

On cohomology of finitely generated function groups

Let Γ be a non-elementary finitely generated Kleinian group with region of discontinuity Ω. Letq be an integer,q ≥ 2. The group Λ acts on the right on the vector space Π_2q?2 of polynomials of degree less than or equal to 2q ? 2 via Eichler action. We note by A_qq(Ω, Λ) the space of cusp forms for Λ of weight (?2q) and the space of parabolic cohomology classes by PH¹ (Λ, Π2q?2). Bers introduced an anti-linear map $$\beta _q^* :A^q \left( {\Omega ,\Gamma } \right) - - - \to PH^1 \left( {\Gamma ,\Omega _{2q - 2} } \right)$$ . We try to determine the class of Kleinian groups for which the Bers map is surjective. We show that the Bers map is surjective for geometrically finite function groups. We also obtain a characterization of geometrically finite function groups. As an application, we reprove theorems of Maskit on inequalities involving the dimension of the space of cusp forms supported on an invariant component and the dimension of the space of cusp forms supported on the other components for finitely generated function groups. We also show all these inequalities are equalities for geometrically finiteB-groups.     

Rechtseiträume

Rectangular spaces are defined to be incidence spaces on which an equivalence relation is defined on the linesB and a congruence relation is defined on the point pairsP ² which is compatible with the relation and the incidence structure. Every rectangular space which contains a line with only a finite number of points is a euclidean space. In any regtangular space of characteristic 2 there exists a unique reflection on each line. Thus, as in the case of rectangular planes, rectangular spaces of arbitrary dimension and of characteristic 2 can be characterized in terms of commutative kinematic spaces with involutory automorphisms.Our main result is the theorem which states that any rectangular space of characteristic 2 can be embedded into a euclidean space of equal dimension. From this embedding property we conclude that every rectangular space of characteristic 2 can be described as a subgeometry of a vector space supplied with a quadratic form. Finally we present examples of rectangular spaces of arbitrary dimension which are not euclidean spaces.

---

---

Herrn Prof. H. Karzel und Herrn Prof. H. Wähling in Dank gewidmet

---

Diese Arbeit ist in einer anderen Form in meiner Habilitationsschrift Zur Theorie der Rechtseiträume unter besonderer Berücksichtigung des ebenen Falles (Technische Universität München 1987) enthalten.