Trees and ultrametric Möbius structures

We define the concept of an ultrametric Möbius space (Z,M) and show that the boundary at infinity of a nonelementary geodesically complete tree is naturally an ultrametric Möbius space. In addition, we construct to a given ultrametric Möbius space (Z,M) a nonelementary geodesically complete tree, unique up to isometry, with (Z,M) being its boundary at infinity. This yields a one-to-one correspondence.     

Generic elements in isometry groups of Polish ultrametric spaces

This paper presents a study of generic elements in full isometry groups of Polish ultrametric spaces. We obtain a complete characterization of Polish ultrametric spaces X whose isometry group Iso(X) has a neighborhood basis at the identity consisting of open subgroups with ample generics. It also gives a characterization of the existence of an open subgroup in Iso(X) with a comeager conjugacy class.We also study the transfinite sequence defined by the projection of a Polish ultrametric space X on the ultrametric space of orbits of X under the action of Iso(X).     

On stochastic generation of ultrametrics in high-dimensional Euclidean spaces

We present a proof of the theorem which states that a matrix of Euclidean distances on a set of specially distributed random points in the n-dimensional Euclidean space R ⁿ converges in probability to an ultrametric matrix as n → ∞. Values of the elements of an ultrametric distance matrix are completely determined by variances of coordinates of random points. Also we present a probabilistic algorithm for generation of finite ultrametric structures of any topology in high-dimensional Euclidean space. Validity of the algorithm is demonstrated by explicit calculations of distance matrices and ultrametricity indexes for various dimensions n.     

Competitive clustering algorithms based on ultrametric properties

We propose in this paper two new competitive unsupervised clustering algorithms: the first algorithm deals with ultrametric data, it has a computational cost of O(n). The second algorithm has two strong features: it is fast and flexible on the processed data type as well as in terms of precision. The second algorithm has a computational cost, in the worst case, of O(n²), and in the average case, of O(n). These complexities are due to exploitation of ultrametric distance properties. In the first method, we use the order induced by an ultrametric in a given space to demonstrate how we can explore quickly data proximity. In the second method, we create an ultrametric space from a sample data, chosen uniformly at random, in order to obtain a global view of proximities in the data set according to the similarity criterion. Then, we use this proximity profile to cluster the global set. We present an example of our algorithms and compare their results with those of a classic clustering method.     

The immersion of ultrametric spaces into Hahn spaces

In this paper we prove that there is an immersion of every ultrametric space X into a Hahn space associated to X. It is not assumed that the set of distances of X is totally ordered.     

Dimension zero at all scales

We consider the notion of dimension in four categories: the category of (unbounded) separable metric spaces and (metrically proper) Lipschitz maps, and the category of (unbounded) separable metric spaces and (metrically proper) uniform maps. A unified treatment is given to the large scale dimension and the small scale dimension. We show that in all categories a space has dimension zero if and only if it is equivalent to an ultrametric space. Also, 0-dimensional spaces are characterized by means of retractions to subspaces. There is a universal zero-dimensional space in all categories. In the Lipschitz Category spaces of dimension zero are characterized by means of extensions of maps to the unit 0-sphere. Any countable group of asymptotic dimension zero is coarsely equivalent to a direct sum of cyclic groups. We construct uncountably many examples of coarsely inequivalent ultrametric spaces.     

Multidimensional ultrametric pseudodifferential equations

We develop an analysis of wavelets and pseudodifferential operators on multidimensional ultrametric spaces which are defined as products of locally compact ultrametric spaces. We introduce bases of wavelets, spaces of generalized functions and the space D′₀(X) of generalized functions on a multidimensional ultrametric space. We also consider some family of pseudodifferential operators on multidimensional ultrametric spaces. The notions of Cauchy problem for ultrametric pseudodifferential equations and of ultrametric characteristics are introduced. We prove an existence theorem and describe all solutions for the Cauchy problem (an analog of the Kovalevskaya theorem).     

Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem

We introduce a randomized iterative fragmentation procedure for finite metric spaces, which is guaranteed to result in a polynomially large subset that is D-equivalent to an ultrametric, where D ∈ (2,∞) is a prescribed target distortion. Since this procedure works for D arbitrarily close to the nonlinear Dvoretzky phase transition at distortion 2, we thus obtain a much simpler probabilistic proof of the main result of [3], answering a question from [12], and yielding the best known bounds in the nonlinear Dvoretzky theorem. Our method utilizes a sequence of random scales at which a given metric space is fragmented. As in many previous randomized arguments in embedding theory, these scales are chosen irrespective of the geometry of the metric space in question. We show that our bounds are sharp if one utilizes such a “scale-oblivious” fragmentation procedure.     

Markov Chains on Graded Posets

We consider two types of discrete-time Markov chains where the state space is a graded poset and the transitions are taken along the covering relations in the poset. The first type of Markov chain goes only in one direction, either up or down in the poset (an up chain or down chain). The second type toggles between two adjacent rank levels (an up-and-down chain). We introduce two compatibility concepts between the up-directed transition probabilities (an up rule) and the down-directed (a down rule), and we relate these to compatibility between up-and-down chains. This framework is used to prove a conjecture about a limit shape for a process on Young’s lattice. Finally, we settle the questions whether the reverse of an up chain is a down chain for some down rule and whether there exists an up or down chain at all if the rank function is not bounded.     

Ultrametric Cantor sets and growth of measure

A class of ultrametric Cantor sets (C, d _u ) introduced recently (S. Raut and D. P. Datta, Fractals 17, 45–52 (2009)) is shown to enjoy some novel properties. The ultrametric d _u is defined using the concept of relative infinitesimals and an inversion rule. The associated (infinitesimal) valuation which turns out to be both scale and reparametrization invariant, is identified with the Cantor function associated with a Cantor set $ \tilde C $ \tilde C , where the relative infinitesimals are supposed to live in. These ultrametrics are both metrically as well as topologically inequivalent compared to the topology induced by the usual metric. Every point of the original Cantor set C is identified with the closure of the set of gaps of $ \tilde C $ \tilde C . The increments on such an ultrametric space is accomplished by following the inversion rule. As a consequence, Cantor functions are reinterpreted as locally constant functions on these extended ultrametric spaces. An interesting phenomenon, called growth of measure, is studied on such an ultrametric space. Using the reparametrization invariance of the valuation it is shown how the scale factors of a Lebesgue measure zero Cantor set might get deformed leading to a deformed Cantor set with a positive measure. The definition of a new valuated exponent is introduced which is shown to yield the fatness exponent in the case of a positive measure (fat) Cantor set. However, the valuated exponent can also be used to distinguish Cantor sets with identical Hausdorff dimension and thickness. A class of Cantor sets with Hausdorff dimension log₃ 2 and thickness 1 are constructed explicitly.     

An alternative definition of coarse structures

Roe [J. Roe, Lectures on Coarse Geometry, University Lecture Series, vol. 31, Amer. Math. Soc., Providence, RI, 2003] introduced coarse structures for arbitrary sets X by considering subsets of X×X. In this paper we introduce large scale structures on X via the notion of uniformly bounded families and we show their equivalence to coarse structures on X. That way all basic concepts of large scale geometry (asymptotic dimension, slowly oscillating functions, Higson compactification) have natural definitions and basic results from metric geometry carry over to coarse geometry.     

From Isomorphic Rooted Trees to Isometric Ultrametric Spaces

For every finite ultrametric space X we can put in correspondence its representing tree T_X. We found conditions under which the isomorphism of representing trees T_X and T_Y implies the isometricity of ultrametric spaces X and Y having the same range of distances.     

On the Gomory–Hu Inequality

It was proved by R. Gomory and T. Hu in 1961 that, for every finite nonempty ultrametric space (X, d), the inequaliy \( \left| {\mathrm{Sp}(X)} \right|\leq \left| X \right|-1 \), where Sp(X) = {d(x, y) : x, y ∈ X, x ≠ y} , holds. We characterize the spaces X for which the equality is attained by the structural properties of some graphs and show that the set of isometric types of such X is dense in the Gromov–Hausdorff space of the isometric types of compact ultrametric spaces.     

On the universal ultrametric space

An ultrametric space in which any separable ultrametric space can be isometrically imbedded is constructed. We describe the method for isometric imbedding of any separable ultrametric space intol ₁,l ₂ andc ₀ based on the application of this universal space.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 12, pp. 1700–1706, December, 1994.     

The comb representation of compact ultrametric spaces

We call a comb a map f: I → [0,∞), where I is a compact interval, such that {f ≥ ε} is finite for any ε > 0. A comb induces a (pseudo)-distance \({\overline d _f}\) on {f = 0} defined by \({\overline d _f}\left( {s,t} \right) = {\max _{\left( {s \wedge t,s \vee t} \right)}}f\). We describe the completion \(\overline I \) of {f = 0} for this metric, which is a compact ultrametric space called the comb metric space.Conversely, we prove that any compact, ultrametric space (U, d) without isolated points is isometric to a comb metric space. We show various examples of the comb representation of well-known ultrametric spaces: the Kingman coalescent, infinite sequences of a finite alphabet, the p-adic field and spheres of locally compact real trees. In particular, for a rooted, locally compact real tree defined from its contour process h, the comb isometric to the sphere of radius T centered at the root can be extracted from h as the depths of its excursions away from T.     

A heat equation on some adic completions of ℚ and ultrametric analysis

For each finite set S of prime numbers there exists a unique completion ? _S of ?, which is a second countable, locally compact and totally disconnected topological ring. This topological ring has a natural ultrametric that allows to define a pseudodifferential operator D ^α and to study an abstract heat equation on the Hilbert space L ²(? _S ). The fundamental solution of this equation is a normal transition function of a Markov process on ? _S . The techniques developed provides a general framework for these kind of problems on different ultrametric groups.     

Characterizations of adjacency on the branching polyhedron

Given two distinct branchings of a directed graph G, we present several conditions which are equivalent to the corresponding incidence vectors of the branchings being adjacent on the branching polyhedron of G. The proof of these equivalences uses a “shrinking algorithm” which will determine in O(n²) time and space whether or not the incidence vectors are adjacent.     

Derived equivalences and Serre duality for Gorenstein algebras

We introduce a notion of Gorenstein algebras of codimension c and demonstrate that Serre duality theory plays an essential role in the theory of derived equivalences for Gorenstein algebras.     

Ultrametric subsets with large Hausdorff dimension

It is shown that for every ε∈(0,1), every compact metric space (X,d) has a compact subset S?X that embeds into an ultrametric space with distortion O(1/ε), and $$\dim_H(S)\geqslant (1-\varepsilon)\dim_H(X),$$ where dim _H (?) denotes Hausdorff dimension. The above O(1/ε) distortion estimate is shown to be sharp via a construction based on sequences of expander graphs.     

Trees and ultrametric spaces: a categorical equivalence

There is a well-known correspondence between infinite trees and ultrametric spaces that comes from considering the end space of the tree. The correspondence is interpreted here as an equivalence between two categories, one of which encodes the geometry of trees at infinity and the other encodes the micro-geometry of complete ultrametric spaces.