Modular Interval Spaces

Modular interval spaces represent a common generalization of Banach spaces of type L₁(μ) or B(X), of hyperconvex metric spaces, modular lattices, modular graphs, and median algebras. It turns out that several types of structures are susceptible for a notion capturing essential features of modularity in lattices, e.g., semilattices, multilattices, metric spaces, ternary algebras, and graphs. There is no perfect correspondence between modular structures of various types unless the existence of a neutral point is imposed. Modular structures with neutral points embed in modular lattices. Particular modular interval spaces (e.g., median spaces, or more generally, modular spaces in which intervals are lattices) can be characterized by forbidden subspaces.     

Sylvester–Gallai Theorem and Metric Betweenness

Sylvester conjectured in 1893 and Gallai proved some 40 years later that every finite set S of points in the plane includes two points such that the line passing through them includes either no other point of S or all other points of S. There are several ways of extending the notion of lines from Euclidean spaces to arbitrary metric spaces. We present one of them and conjecture that, with lines in metric spaces defined in this way, the Sylvester--Gallai theorem generalizes as follows: in every finite metric space there is a line consisting of either two points or all the points of the space. Then we present meagre evidence in support of this rash conjecture and finally we discuss the underlying ternary relation of metric betweenness.     

Regularity of quasi-minimizers on metric spaces

Using the theory of Sobolev spaces on a metric measure space we are able to apply calculus of variations and define p-harmonic functions as minimizers of the p-Dirichlet integral. More generally, we study regularity properties of quasi-minimizers of p-Dirichlet integrals in a metric measure space. Applying the De Giorgi method we show that quasi-minimizers, and in particular p-harmonic functions, satisfy Harnack's inequality, the strong maximum principle, and are locally H?lder continuous, if the space is doubling and supports a Poincaré inequality. Received: 12 May 2000 / Revised version: 20 April 2001     

Metric tangent spaces to Euclidean spaces

We prove that the metric spaces pretangent to a finite-dimensional Euclidean or unitary space E are isometric to E. As a consequence of this result, we describe the metric pretangent spaces at the nonsingular points of smooth surfaces. It is also proved that there exist the spaces pretangent to the Hilbert space l ₂ , which are not isometric to it.     

SMOOTHNESS PROPERTIES OF REAL-VALUED FUNCTIONS BASED ON THEIR OSCILLATION

Abstract

We consider the following two selection principles for topological spaces:

Principle 1: For each sequence of dense subsets, there is a sequence of points from the space, the n-th point coming from the n-th dense set, such that this set of points is dense in the space;

Principle 2: For each sequence of dense subsets, there is a sequence of finite sets, the n-th a subset of the n-th dense set, such that the union of these finite sets is dense in the space.

We show that for separable metric space X one of these principles holds for the space C_p (X) of realvalued continuous functions equipped with the pointwise convergence topology if, and only if, a corresponding principle holds for a special family of open covers of X. An example is given to show that these equivalences do not hold in general for Tychonoff spaces. It is further shown that these two principles give characterizations for two popular cardinal numbers, and that these two principles are intimately related to an infinite game that was studied by Berner and Juhász.     

Infinite Random Geometric Graphs

We introduce a new class of countably infinite random geometric graphs, whose vertices V are points in a metric space, and vertices are adjacent independently with probability p ? (0, 1){p \in (0, 1)} if the metric distance between the vertices is below a given threshold. For certain choices of V as a countable dense set in \mathbbRⁿ{\mathbb{R}^n} equipped with the metric derived from the L _∞-norm, it is shown that with probability 1 such infinite random geometric graphs have a unique isomorphism type. The isomorphism type, which we call GR _n , is characterized by a geometric analogue of the existentially closed adjacency property, and we give a deterministic construction of GR _n . In contrast, we show that infinite random geometric graphs in \mathbbR²{\mathbb{R}^{2}} with the Euclidean metric are not necessarily isomorphic.     

A cooperative location game based on the 1-center location problem

In this paper we introduce and analyze new classes of cooperative games related to facility location models defined on general metric spaces. The players are the customers (demand points) in the location problem and the characteristic value of a coalition is the cost of serving its members. Specifically, the cost in our games is the service radius of the coalition. We call these games the Minimum Radius Location Games (MRLG).We study the existence of core allocations and the existence of polynomial representations of the cores of these games, focusing on network spaces, i.e., finite metric spaces induced by undirected graphs and positive edge lengths, and on the ?_p metric spaces defined over R^d.     

Advances in metric embedding theory

Metric Embedding plays an important role in a vast range of application areas such as computer vision, computational biology, machine learning, networking, statistics, and mathematical psychology, to name a few. The mathematical theory of metric embedding is well studied in both pure and applied analysis and has more recently been a source of interest for computer scientists as well. Most of this work is focused on the development of bi-Lipschitz mappings between metric spaces. In this paper we present new concepts in metric embeddings as well as new embedding methods for metric spaces. We focus on finite metric spaces, however some of the concepts and methods are applicable in other settings as well.One of the main cornerstones in finite metric embedding theory is a celebrated theorem of Bourgain which states that every finite metric space on n points embeds in Euclidean space with distortion. Bourgain?s result is best possible when considering the worst case distortion over all pairs of points in the metric space. Yet, it is natural to ask: can an embedding do much better in terms of the average distortion? Indeed, in most practical applications of metric embedding the main criteria for the quality of an embedding is its average distortion over all pairs.In this paper we provide an embedding with constant average distortion for arbitrary metric spaces, while maintaining the same worst case bound provided by Bourgain?s theorem. In fact, our embedding possesses a much stronger property. We define the ?q-distortion of a uniformly distributed pair of points. Our embedding achieves the best possible ?q-distortion for all 1?q?∞simultaneously.The results are based on novel embedding methods which improve on previous methods in another important aspect: the dimension of the host space. The dimension of an embedding is of very high importance in particular in applications and much effort has been invested in analyzing it. However, no previous result improved the bound on the dimension which can be derived from Bourgain?s embedding. Our embedding methods achieve better dimension, and in fact, shed new light on another fundamental question in metric embedding, which is: whether the embedding dimension of a metric space is related to its intrinsic dimension? I.e., whether the dimension in which it can be embedded in some real normed space is related to the intrinsic dimension which is reflected by the inherent geometry of the space, measured by the space?s doubling dimension. The existence of such an embedding was conjectured by Assouad,⁴and was later posed as an open problem in several papers. Our embeddings give the first positive result of this type showing any finite metric space obtains a low distortion (and constant average distortion) embedding in Euclidean space in dimension proportional to its doubling dimension.Underlying our results is a novel embedding method. Probabilistic metric decomposition techniques have played a central role in the field of finite metric embedding in recent years. Here we introduce a novel notion of probabilistic metric decompositions which comes particularly natural in the context of embedding. Our new methodology provides a unified approach to all known results on embedding of arbitrary finite metric spaces. Moreover, as described above, with some additional ideas they allow to get far stronger results.The results presented in this paper⁵have been the basis for further developments both within the field of metric embedding and in other areas such as graph theory, distributed computing and algorithms. We present a comprehensive study of the notions and concepts introduced here and provide additional extensions, related results and some examples of algorithmic applications.     

Modulus and the Poincaré inequality on metric measure spaces

The purpose of this paper is to develop the understanding of modulus and the Poincaré inequality, as defined on metric measure spaces. Various definitions for modulus and capacity are shown to coincide for general collections of metric measure spaces. Consequently, modulus is shown to be upper semi-continuous with respect to the limit of a sequence of curve families contained in a converging sequence of metric measure spaces. Moreover, several competing definitions for the Poincaré inequality are shown to coincide, if the underlying measure is doubling. One such characterization considers only continuous functions and their continuous upper gradients, and extends work of Heinonen and Koskela. Applications include showing that the p-Poincaré inequality (with a doubling measure), for p1, persists through to the limit of a sequence of converging pointed metric measure spaces — this extends results of Cheeger. A further application is the construction of new doubling measures in Euclidean space which admit a 1-Poincaré inequality. Mathematics Subject Classification (2000):31C15, 46E35.     

A New Class of Graphs That Satisfies the Chen‐Chvátal Conjecture

A well‐known combinatorial theorem says that a set of n non‐collinear points in the plane determines at least n distinct lines. Chen and Chvátal conjectured that this theorem extends to metric spaces, with an appropriated definition of line. In this work, we prove a slightly stronger version of Chen and Chvátal conjecture for a family of graphs containing chordal graphs and distance‐hereditary graphs.     

Weighted BMOA spaces and composition operators

This article provides information on p-logarithmic s-Carleson measure characterization of the weighted BMOA spaces. Also, the boundedness and compactness of composition operators from Bloch-type space and weighted Bloch space to weighted BMOA space are discussed.     

Graph-Theoretic Approach to Stochastic Integrals with Clifford Algebras

Given a fixed probability space (Ω,ℱ,ℙ) and m≥1, let X(t) be an L²(Ω) process satisfying necessary regularity conditions for existence of the mth iterated stochastic integral. For real-valued processes, these existence conditions are known from the work of D. Engel. Engel’s work is extended here to L²(Ω) processes defined on Clifford algebras of arbitrary signature (p,q), which reduce to the real case when p=q=0. These include as special cases processes on the complex numbers, quaternion algebra, finite fermion algebras, fermion Fock spaces, space-time algebra, the algebra of physical space, and the hypercube. Next, a graph-theoretic approach to stochastic integrals is developed in which the mth iterated stochastic integral corresponds to the limit in mean of a collection of weighted closed m-step walks on a growing sequence of graphs. Combinatorial properties of the Clifford geometric product are then used to create adjacency matrices for these graphs in which the appropriate weighted walks are recovered naturally from traces of matrix powers. Given real-valued L²(Ω) processes, Hermite and Poisson-Charlier polynomials are recovered in this manner.     

Nonlinear structure of some classical quasi-Banach spaces and -spaces

We investigate the Lipschitz structure of ℓ_p and L_p for 0<p<1 as quasi-Banach spaces and as metric spaces (with the metric induced by the p-norm) and show that they are not Lipschitz isomorphic. We prove that the -space L₀ is not uniformly homeomorphic to any other L_p space, that the L_p spaces for 0<p<1 embed isometrically into one another, and reduce the problem of the uniform equivalence amongst L_p spaces to their Lipschitz equivalence as metric spaces.     

Moser iteration for (quasi)minimizers on metric spaces

We study regularity properties of quasiminimizers of the p-Dirichlet integral on metric measure spaces. We adapt the Moser iteration technique to this setting and show that it can be applied without an underlying differential equation. However, we have been able to run the Moser iteration fully only for minimizers. We prove Caccioppoli inequalities and local boundedness properties for quasisub- and quasisuperminimizers. This is done in metric spaces equipped with a doubling measure and supporting a weak (1, p)-Poincaré inequality. The metric space is not required to be complete. We also provide an example which shows that the dilation constant from the weak Poincaré inequality is essential in the condition on the balls in the Harnack inequality. This fact seems to have been overlooked in the earlier literature on nonlinear potential theory on metric spaces.     

The diameter of inhomogeneous random graphs

In this paper, we study the diameter of inhomogeneous random graphs that are induced by irreducible kernels . The kernels we consider act on separable metric spaces and are almost everywhere continuous. We generalize results known for the Erdős–Rényi model G(n, p) for several ranges of p. We find upper and lower bounds for the diameter of in terms of the expansion factor and two explicit constants that depend on the behavior of the kernel over partitions of the metric space.     

Amenability,locally finite spaces,and bi-lipschitz embeddings

We define the isoperimetric constant for any locally finite metric space and we study the property of having isoperimetric constant equal to zero. This property, called Small Neighborhood property, clearly extends amenability to any locally finite space. Therefore, we start making a comparison between this property and other notions of amenability for locally finite metric spaces that have been proposed by Gromov, Lafontaine and Pansu, by Ceccherini-Silberstein, Grigorchuk and de la Harpe and by Block and Weinberger. We discuss possible applications of the property SN in the study of embedding a metric space into another one. In particular, we propose three results: we prove that a certain class of metric graphs that are isometrically embeddable into Hilbert spaces must have the property SN. We also show, by a simple example, that this result is not true replacing property SN with amenability. As a second result, we prove that many spaces with uniform bounded geometry having a bi-lipschitz embedding into Euclidean spaces must have the property SN. Finally, we prove a Bourgain-like theorem for metric trees: a metric tree with uniform bounded geometry and without property SN does not have bi-lipschitz embeddings into finite-dimensional Hilbert spaces.     

Geometric graph properties of the spatial preferred attachment model

The spatial preferred attachment (SPA) model is a model for networked information spaces such as domains of the World Wide Web, citation graphs, and on-line social networks. It uses a metric space to model the hidden attributes of the vertices. Thus, vertices are elements of a metric space, and link formation depends on the metric distance between vertices. We show, through theoretical analysis and simulation, that for graphs formed according to the SPA model it is possible to infer the metric distance between vertices from the link structure of the graph. Precisely, the estimate is based on the number of common neighbours of a pair of vertices, a measure known as co-citation. To be able to calculate this estimate, we derive a precise relation between the number of common neighbours and metric distance. We also analyse the distribution of edge lengths, where the length of an edge is the metric distance between its end points. We show that this distribution has three different regimes, and that the tail of this distribution follows a power law.     

On quasi-contraction mappings of Ćirić and Fisher type via ω-distance

Kada, Suzuki, and Takahashi introduced and studies the concept of ω- distance in fixed point theory. In this paper, we generalize and unify ?iri?’ and Fisher fixed points results for quasi-contractions on metric space to ω-distance on complete metric spaces. We also extend some results of Kada, Suzuki and Takahashi, and Suzuki. Our methods of proofs are new and even simpler than the corresponding methods in metric spaces.     

Quantitative property A, Poincaré inequalities, Lp-compression and Lp-distortion for metric measure spaces

We introduce a quantitative version of Property A in order to estimate the L ^p -compressions of a metric measure space X. We obtain various estimates for spaces with sub-exponential volume growth. This quantitative property A also appears to be useful to yield upper bounds on the L ^p -distortion of finite metric spaces. Namely, we obtain new optimal results for finite subsets of homogeneous Riemannian manifolds. We also introduce a general form of Poincaré inequalities that provide constraints on compressions, and lower bounds on distortion. These inequalities are used to prove the optimality of some of our results.      

Reproducing kernel approximation in weighted Bergman spaces: Algorithm and applications

In this paper, we present algorithms of preorthogonal adaptive Fourier decomposition (POAFD) in weighted Bergman spaces. POAFD, as has been studied, gives rise to sparse approximations as linear combinations of the corresponding reproducing kernels. It is found that POAFD is unavailable in some weighted Hardy spaces that do not enjoy the boundary vanishing condition; as a result, the maximal selections of the parameters are not guaranteed. We overcome this difficulty with two strategies. One is to utilize the shift operator while the other is to perform weak POAFD. In the cases when the reproducing kernels are rational functions, POAFD provides rational approximations. This approximation method may be used to 1D signal processing. It is, in particular, effective to some Hardy H^p space functions for p not being equal to 2. Weighted Bergman spaces approximation may be used in system identification of discrete time‐varying systems. The promising effectiveness of the POAFD method in weighted Bergman spaces is confirmed by a set of experiments. A sequence of functions as models of the weighted Hardy spaces, being a wider class than the weighted Bergman spaces, are given, of which some are used to illustrate the algorithm and to evaluate its effectiveness over other Fourier type methods.