Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs

In this paper, we present a simple factor 6 algorithm for approximating the optimal multiplicative distortion of embedding a graph metric into a tree metric (thus improving and simplifying the factor 100 and 27 algorithms of Bǎdoiu et al. (Proceedings of the eighteenth annual ACM–SIAM symposium on discrete algorithms (SODA 2007), pp. 512–521, 2007) and Bǎdoiu et al. (Proceedings of the 11th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2008), Springer, Berlin, pp. 21–34, 2008)). We also present a constant factor algorithm for approximating the optimal distortion of embedding a graph metric into an outerplanar metric. For this, we introduce a general notion of a metric relaxed minor and show that if G contains an α-metric relaxed H-minor, then the distortion of any embedding of G into any metric induced by a H-minor free graph is ≥α. Then, for H=K _2,3, we present an algorithm which either finds an α-relaxed minor, or produces an O(α)-embedding into an outerplanar metric.     

One-regular Normal Cayley Graphs on Dihedral Groups of Valency 4 or 6 with Cyclic Vertex Stabilizer

A graph G is one-regular if its automorphism group Aut（G） acts transitively and semiregularly on the arc set. A Cayley graph Cay（Г, S） is normal if Г is a normal subgroup of the full automorphism group of Cay（Г, S）. Xu, M. Y., Xu, J. （Southeast Asian Bulletin of Math., 25, 355-363 （2001）） classified one-regular Cayley graphs of valency at most 4 on finite abelian groups. Marusic, D., Pisanski, T. （Croat. Chemica Acta, 73, 969-981 （2000）） classified cubic one-regular Cayley graphs on a dihedral group, and all of such graphs turn out to be normal. In this paper, we classify the 4-valent one-regular normal Cayley graphs G on a dihedral group whose vertex stabilizers in Aut（G） are cyclic. A classification of the same kind of graphs of valency 6 is also discussed.     

The Patterson–Sullivan Embedding and Minimal Volume Entropy for Outer Space

Motivated by Bonahon’s result for hyperbolic surfaces, we construct an analogue of the Patterson–Sullivan–Bowen–Margulis map from the Culler–Vogtmann outer space CV (F _k ) into the space of projectivized geodesic currents on a free group. We prove that this map is a continuous embedding and thus obtain a new compactification of the outer space. We also prove that for every k ≥ 2 the minimum of the volume entropy of the universal covers of finite connected volume-one metric graphs with fundamental group of rank k and without degree-one vertices is equal to (3k − 3) log 2 and that this minimum is realized by trivalent graphs with all edges of equal lengths, and only by such graphs. Received: December 2005, Accepted: March 2006     

Hausdorff-Besicovitch Dimension of Graphs and <Emphasis Type="Italic">p</Emphasis>-Variation

A relationship between Hausdorff-Besicovitch dimension of graphs of trajectories and p-variation index is well known for many real-valued Levy processes (see, e.g., [10]). Here this relationship is extended to a class of subordinated processes used in econometrics. Printed in Lietuvos Matematikos Rinkinys, Vol. 45, No. 3, pp. 359–366, July–September, 2005.     

On Borell-Brascamp-Lieb Inequalities on Metric Measure Spaces

In this paper we introduce the notion of a Borell-Brascamp-Lieb inequality for metric measure spaces (M,d,m) denoted by BBL(K,N) for two numbers K,N ∈ ℝ with N ≥ 1. In the first part we prove that BBL(K,N) holds true on metric measure spaces satisfying a curvature-dimension condition CD(K,N) developed and studied by Lott and Villani in (Ann Math 169:903–991, 2007) as well as by Sturm in (Acta Math 196(1):133–177, 2006). The aim of the second part is to show that BBL(K,N) is stable under convergence of metric measure spaces with respect to the L ₂-transportation distance.     

Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs

The main question discussed in this paper is how well a finite metric space of size n can be embedded into a graph with certain topological restrictions. The existing constructions of graph spanners imply that any n -point metric space can be represented by a (weighted) graph with n vertices and n ^{1 +O(1/r)} edges, with distances distorted by at most r . We show that this tradeoff between the number of edges and the distortion cannot be improved, and that it holds in a much more general setting. The main technical lemma claims that the metric space induced by an unweighted graph H of girth g cannot be embedded in a graph G (even if it is weighted) of smaller Euler characteristic, with distortion less than g/4 - 3/2 . In the special case when |V(G)| =|V(H)| and G has strictly less edges than H , an improved bound of g/3 - 1 is shown. In addition, we discuss the case χ(G) < χ(H) - 1 , as well as some interesting higher-dimensional analogues. The proofs employ basic techniques of algebraic topology. Received September 26, 1995, and in revised form March 18, 1996.     

Grüss-type and Ostrowski-type inequalities in approximation theory

We discuss the Grüss inequalities on spaces of continuous functions defined on a compact metric space. Using the least concave majorant of the modulus of continuity, we obtain the Grüss inequality for the functional L(f) = H(f; x), where H:C[a, b] → C[a, b] is a positive linear operator and x ∈ [a, b] is fixed. We apply this inequality in the case of known operators, e.g., the Bernstein operator, the Hermite–Fejér interpolation operator, and convolution-type operators. Moreover, we deduce Grüss-type inequalities using the Cauchy mean-value theorem, thus generalizing results of Chebyshev and Ostrowski. The Grüss inequality on a compact metric space for more than two functions is given, and an analogous Ostrowski-type inequality is obtained. The latter, in turn, leads to one further version of the Grüss inequality. In the appendix, we prove a new result concerning the absolute first-order moments of the classic Hermite–Fejér operator.     

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.     

On the isoperimetric problem in the Heisenberg group ℍ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

It has been recently conjectured that, in the context of the Heisenberg group ℍⁿ endowed with its Carnot–Carathéodory metric and Haar measure, the isoperimetric sets (i.e., minimizers of the ℍ-perimeter among sets of constant Haar measure) could coincide with the solutions to a “restricted” isoperimetric problem within the class of sets having finite perimeter, smooth boundary, and cylindrical symmetry. In this paper, we derive new properties of these restricted isoperimetric sets, which we call Heisenberg bubbles. In particular, we show that their boundary has constant mean ℍ-curvature and, quite surprisingly, that it is foliated by the family of minimal geodesics connecting two special points. In view of a possible strategy for proving that Heisenberg bubbles are actually isoperimetric among the whole class of measurable subsets of ℍⁿ, we turn our attention to the relationship between volume, perimeter, and ε-enlargements. In particular, we prove a Brunn–Minkowski inequality with topological exponent as well as the fact that the ℍ-perimeter of a bounded, open set F⊂ℍⁿ of class C² can be computed via a generalized Minkowski content, defined by means of any bounded set whose horizontal projection is the 2n-dimensional unit disc. Some consequences of these properties are discussed. Mathematics Subject Classification (2000) 28A75, 22E25, 49Q20     

Locally Well-Dominated and Locally Independent Well-Dominated Graphs

 In this article we present characterizations of locally well-dominated graphs and locally independent well-dominated graphs, and a sufficient condition for a graph to be k-locally independent well-dominated. Using these results we show that the irredundance number, the domination number and the independent domination number can be computed in polynomial time within several classes of graphs, e.g., the class of locally well-dominated graphs. Received: September 13, 2001 Final version received: May 17, 2002 RID="*" ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093) RID="†" ID="†" Supported by RUTCOR RID="*" ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093) 05C75, 05C69 Acknowledgments. The authors thank the referees for valuable suggestions.     

Young Measures as Measurable Functions and Their Applications to Variational Problems

In this paper, we give a systematic exposition of our approach to the Young measure theory. This approach is based on characterzation of these objects as measurable functions into a compact metric space with a metric of integral form. We explain advantages of this approach in the study of the behavior of integral functionals on weakly convergent sequences. Bibliography: 38 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 310, 2004, pp. 191–212.     

The embedding of line graphs associated to the zero-divisor graphs of commutative rings

Let R be a commutative ring with identity and denote Γ(R) for its zero-divisor graph. In this paper, we study the minimal embedding of the line graph associated to Γ(R), denoted by L(Γ(R)), into compact surfaces (orientable or non-orientable) and completely classify all finite commutative rings R such that the line graphs associated to their zero-divisor graphs have genera or crosscaps up to two.     

Potential Theoretic Approach to Rendezvous Numbers

We analyze relations between various forms of energies (reciprocal capacities), the transfinite diameter, various Chebyshev constants and the so-called rendezvous or average number. The latter is originally defined for compact connected metric spaces (X,d) as the (in this case unique) nonnegative real number r with the property that for arbitrary finite point systems {x ₁, …, x _n } ⊂ X, there exists some point x ∈ X with the average of the distances d(x,x _j ) being exactly r. Existence of such a miraculous number has fascinated many people; its normalized version was even named “the magic number” of the metric space. Exploring related notions of general potential theory, as set up, e.g., in the fundamental works of Fuglede and Ohtsuka, we present an alternative, potential theoretic approach to rendezvous numbers.     

Potential Theoretic Approach to Rendezvous Numbers

We analyze relations between various forms of energies (reciprocal capacities), the transfinite diameter, various Chebyshev constants and the so-called rendezvous or average number. The latter is originally defined for compact connected metric spaces (X,d) as the (in this case unique) nonnegative real number r with the property that for arbitrary finite point systems {x ₁, …, x _n } ⊂ X, there exists some point x ∈ X with the average of the distances d(x,x _j ) being exactly r. Existence of such a miraculous number has fascinated many people; its normalized version was even named “the magic number” of the metric space. Exploring related notions of general potential theory, as set up, e.g., in the fundamental works of Fuglede and Ohtsuka, we present an alternative, potential theoretic approach to rendezvous numbers.     

L 1→ L q Poincaré Inequalities for 0 < q < 1 Imply Representation Formulas

Given two doubling measures μ and ν in a metric space (S, ρ) of homogeneous type, let B ₀⊂S be a given ball. It has been a well-known result by now (see [1–4]) that the validity of an L ¹→L ¹ Poincaré inequality of the following form: for all metric balls B⊂B ₀⊂S, implies a variant of representation formula of fractional integral type: for ρ-a.e. x∈B ₀, One of the main results of this paper shows that an L ¹ to L ^q Poincaré inequality for some 0 < q < 1, i.e., for all metric balls B⊂B ₀, will suffice to imply the above representation formula. As an immediate corollary, we can show that the weak-type condition, also implies the same formula. Analogous theorems related to high-order Poincaré inequalities and Sobolev spaces in metric spaces are also proved. Received December 27, 2000, Accepted May 28, 2001     

关于度量及纲函数的Hausdorff测度的两个反例

本文研究了度量空间中Hausdorff测度与度量及纲函数的关系.利用拓扑学及Hausdorff测度论中一些性质,构造了两反例来说明存在不等价纲函数g,h和某一紧度量空间(ρ,X),使得Hρ,g与Hρ,h对此紧度量空间等价等问题.这些反例有助于从另一个角度理解文胜友、文志英[4]中主要结果.     

A Poincar�� Inequality for Orlicz�CSobolev Functions with Zero Boundary Values on Metric Spaces

We prove a Poincaré inequality for Orlicz–Sobolev functions with zero boundary values in bounded open subsets of a metric measure space. This result generalizes the (p, p)-Poincaré inequality for Newtonian functions with zero boundary values in metric measure spaces, as well as a Poincaré inequality for Orlicz–Sobolev functions on a Euclidean space, proved by Fuchs and Osmolovski (J Anal Appl (Z.A.A.) 17(2):393–415, 1998). Using the Poincaré inequality for Orlicz–Sobolev functions with zero boundary values we prove the existence and uniqueness of a solution to an obstacle problem for a variational integral with nonstandard growth.     

Distance and routing labeling schemes for non-positively curved plane graphs

Distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the distance between any two vertices u and v can be determined efficiently (e.g., in constant or logarithmic time) by merely inspecting the labels of u and v, without using any other information. Similarly, routing labeling schemes are schemes that label the vertices of a graph with short labels in such a way that given the label of a source vertex and the label of a destination, it is possible to compute efficiently (e.g., in constant or logarithmic time) the port number of the edge from the source that heads in the direction of the destination. In this paper we show that the three major classes of non-positively curved plane graphs enjoy such distance and routing labeling schemes using O(log²n) bit labels on n-vertex graphs. In constructing these labeling schemes interesting metric properties of those graphs are employed.     

Behavior of Gaussian beams in an anisotropic medium with interface

A region that consists of two parts with anisotropic Riemannian metrics is considered. The metric has a jump on the interface. Asymptotic solutions of the wave equation, reflected and transmitted from the interface, i.e., Gaussian beams (“quasiphotons”), are constructed. Bibliography: 7 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 324, 2005, pp. 77–109.     

Characterization of Orlicz–Sobolev space

We give a new characterization of the Orlicz–Sobolev space W ^1,Ψ(R ⁿ ) in terms of a pointwise inequality connected to the Young function Ψ. We also study different Poincaré inequalities in the metric measure space.