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.     

On the average distance property and certain energy integrals

One of our main results is the following: LetX be a compact connected subset of the Euclidean spaceR ⁿ andr(X, d ₂) the rendezvous number ofX, whered ₂ denotes the Euclidean distance inR ⁿ . (The rendezvous numberr(X, d ₂) is the unique positive real number with the property that for each positive integern and for all (not necessarily distinct)x ₁,x ₂,...,x _n inX, there exists somex inX such that .) Then there exists some regular Borel probability measure μ₀ onX such that the value of ∫ _X d ₂(x, y)dμ₀ (y) is independent of the choicex inX, if and only ifr(X, d ₂) = sup_μ ∫ _X ∫ _X d ₂(x, y)dμ(x)dμ(y), where the supremum is taken over all regular Borel probability measures μ onX.     

Distinguishing labeling of the actions of almost simple groups

Suppose Γ is a group acting on a set X, written as (Γ,X). An r-labeling f: X→{1,2, ..., r} of X is called distinguishing for (Γ,X) if for all σ∈Γ,σ≠1, there exists an element x∈X such that f(x)≠f(x ^σ ). The distinguishing number d(Γ,X) of (Γ,X) is the minimum r for which there is a distinguishing r-labeling for (Γ,X). If Γ is the automorphism group of a graph G, then d(Γ,V (G)) is denoted by d(G), and is called the distinguishing number of the graph G. The distinguishing set of Γ-actions is defined to be D*(Γ)={d(Γ,X): Γ acts on X}, and the distinguishing set of Γ-graphs is defined to be D(Γ)={d(G): Aut(G)≅Γ}. This paper determines the distinguishing set of Γ-actions and the distinguishing set of Γ-graphs for almost simple groups Γ.     

Reducing system of parameters and the Cohen-Macaulay property

Let R be a local ring and let (x ₁, …, x _r) be part of a system of parameters of a finitely generated R-module M, where r < dim_R M. We will show that if (y ₁, …, y _r) is part of a reducing system of parameters of M with (y ₁, …, y _r) M = (x ₁, …, x _r) M then (x ₁, …, x _r) is already reducing. Moreover, there is such a part of a reducing system of parameters of M iff for all primes P ε Supp M ∩ V _R(x ₁, …, x _r) with dim_R R/P = dim_R M − r the localization M _P of M at P is an r-dimensional Cohen-Macaulay module over R _P. Furthermore, we will show that M is a Cohen-Macaulay module iff y _d is a non zero divisor on M/(y ₁, …, y _d−1) M, where (y ₁, …, y _d) is a reducing system of parameters of M (d:= dim_R M).     

Approximation of the effective conductivity of ergodic media by periodization

 This paper is concerned with the approximation of the effective conductivity σ(A, μ) associated to an elliptic operator ∇ _xA (x,η)∇ _x where for xℝ ^d , d≥1, A(x,η) is a bounded elliptic random symmetric d×d matrix and η takes value in an ergodic probability space (X, μ). Writing A ^N (x, η) the periodization of A(x, η) on the torus T ^d _N of dimension d and side N we prove that for μ-almost all η

Two-point concentration in random geometric graphs

A random geometric graph G _n is constructed by taking vertices X ₁,…,X _n ∈ℝ ^d at random (i.i.d. according to some probability distribution ν with a bounded density function) and including an edge between X _i and X _j if ‖X _i -X _j ‖ < r where r = r(n) > 0. We prove a conjecture of Penrose ([14]) stating that when r=r(n) is chosen such that nr ^d = o(lnn) then the probability distribution of the clique number ω(G _n ) becomes concentrated on two consecutive integers and we show that the same holds for a number of other graph parameters including the chromatic number χ(G _n ). The author was partially supported by EPSRC, the Department of Statistics, Bekkerla-Bastide fonds, Dr. Hendrik Muller’s Vaderlandsch fonds, and Prins Bernhard Cultuurfonds.     

Random matrix products and applications to cellular automata

Let λ be the upper Lyapunov exponent corresponding to a product of i.i.d. randomm×m matrices (X _i) _i ^0/∞ over ℂ. Assume that theX _i's are chosen from a finite set {D ₀,D ₁...,D _t-1(ℂ), withP(X _i=D_j)>0, and that the monoid generated byD ₀, D₁,…, D_q−1 contains a matrix of rank 1. We obtain an explicit formula for λ as a sum of a convergent series. We also consider the case where theX _i's are chosen according to a Markov process and thus generalize a result of Lima and Rahibe [22]. Our results on λ enable us to provide an approximation for the numberN _≠0(F(x)ⁿ,r) of nonzero coefficients inF(x) ⁿ.(modr), whereF(x) ∈ ℤ[x] andr≥2. We prove the existence of and supply a formula for a constant α (<1) such thatN _≠0(F(x)ⁿ,r) ≈n ^α for “almost” everyn. Supported in part by FWF Project P16004-N05     

Quantitative form of the Luzin <Emphasis Type="Italic">C</Emphasis>-property

We prove the following statement, which is a quantitative form of the Luzin theorem on C-property: Let (X, d, μ) be a bounded metric space with metric d and regular Borel measure μ that are related to one another by the doubling condition. Then, for any function f measurable on X, there exist a positive increasing function η ∈ Ω (η(+0) = 0 and η(t)t ^−a decreases for a certain a > 0), a nonnegative function g measurable on X, and a set E ⊂ X, μE = 0 , for which

Bounds on Gromov hyperbolicity constant in graphs

If X is a geodesic metric space and x ₁,x ₂,x ₃ ∈ X, a geodesic triangle T = {x ₁,x ₂,x ₃} is the union of the three geodesics [x ₁ x ₂], [x ₂ x ₃] and [x ₃ x ₁] in X. The space X is δ-hyperbolic (in the Gromov sense) if any side of T is contained in a δ-neighborhood of the union of two other sides, for every geodesic triangle T in X. If X is hyperbolic, we denote by δ(X) the sharp hyperbolicity constant of X, i.e. $\delta(X)=\inf\{\delta\ge 0: \, X \, \text{ is $\delta(X)=\inf\{\delta\ge 0: \, X \, \text{ is In this paper we relate the hyperbolicity constant of a graph with some known parameters of the graph, as its independence number, its maximum and minimum degree and its domination number. Furthermore, we compute explicitly the hyperbolicity constant of some class of product graphs.     

A topological position of the set of continuous maps in the set of upper semicontinuous maps

Let (X, ρ) be a metric space and ↓USCC(X) and ↓CC(X) be the families of the regions below all upper semi-continuous compact-supported maps and below all continuous compact-supported maps from X to I = [0, 1], respectively. With the Hausdorff-metric, they are topological spaces. In this paper, we prove that, if X is an infinite compact metric space with a dense set of isolated points, then (↓USCC(X), ↓CC(X)) ≈ (Q, c0 ∪ (Q \ Σ)), i.e., there is a homeomorphism h :↓USCC(X) → Q such that h(↓CC(X)) = c0 ∪ (Q \ Σ...     

On some Fano manifolds of large pseudoindex

In this paper we classify pairs (X,ℰ) with ℰ ample vector bundle of rank r on a smooth variety X of dimension n= 2r−1 such that K _X + det ℰ=? _x . Received: 7 April 2000     

On the coincidence of the canonical embeddings of a metric space into a Banach space

Recall the two classical canonical isometric embeddings of a finite metric space X into a Banach space. That is, the Hausdorff–Kuratowsky embedding x → ρ(x, ⋅) into the space of continuous functions on X with the max-norm, and the Kantorovich–Rubinshtein embedding x → δ _x (where δ _x , is the δ-measure concentrated at x) with the transportation norm. We prove that these embeddings are not equivalent if |X| > 4. Bibliography: 2 titles. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 360, 2008, pp. 153–161.     

On the hot spots of a catalytic super-Brownian motion

Consider the catalytic super-Brownian motion X ^ϱ (reactant) in ℝ ^d , d≤3, which branching rates vary randomly in time and space and in fact are given by an ordinary super-Brownian motion ϱ (catalyst). Our main object of study is the collision local time L = L _[ϱ,Xϱ] (d(s,x) )of catalyst and reactant. It determines the covariance measure in themartingale problem for X ^ϱ and reflects the occurrence of “hot spots” of reactant which can be seen in simulations of X ^ϱ. In dimension 2, the collision local time is absolutely continuous in time, L(d(s,x) ) = ds K _s (dx). At fixed time s, the collision measures K _s (dx) of ϱ _s and X _s ^ϱ have carrying Hausdorff dimension 2. Spatial marginal densities of L exist, and, via self-similarity, enter in the long-term randomergodic limit of L (diffusiveness of the 2-dimensional model). We alsocompare some of our results with the case of super-Brownian motions withdeterministic time-independent catalysts. Received: 2 December 1998 / Revised version: 2 February 2001 / Published online: 9 October 2001     

Oscillation for almost continuity

Let X be a topological space and (Y,d) be a metric space. If f: X → Y is a function then there is a function a _f : X → [0, ∞] such that f is almost continuous at x if and only if a _f (x) = 0. Some properties of this function are investigated. Supported by grant VEGA 2/6087/26 and APVT-51-006904.     

The smallest degree sum that yields potentially Kr,r-graphic sequences

We consider a variation of a classical Turán-type extremal problem as follows: Determine the smallest even integer σ(K_r,r,n) such that every n-term graphic sequence π = (d₁,d₂,...,d_n) with term sum σ(π) = d₁ + d₂ + ... + d_n ≥ σ(K_r,r,n) is potentially K_r,r-graphic, where K_r,r is an r × r complete bipartite graph, i.e. π has a realization G containing K_r,r as its subgraph. In this paper, the values σ(K_r,r,n) for even r and n ≥ 4r² - r - 6 and for odd r and n ≥ 4r² + 3r - 8 are determined.     

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.     

Densities generated by equivalent measures

In the family of all measures equivalent to the Borel measure μ defined in a metric space X, we look for measures generating the same density points (preserving μ-density at fixed point x ₀ ∈ X).     

Some path properties of generalized Lévy sheet

Let X(t) be an N parameter generalized Lévy sheet taking values in ℝ^d with a lower index α, ℜ = {(s, t] = ∏ _i=1 ^N (s _i, t _i], s _i < t _i}, E(x, Q) = {t ∈ Q: X(t) = x}, Q ∈ ℜ be the level set of X at x and X(Q) = {x: ∃t ∈ Q such that X(t) = x} be the image of X on Q. In this paper, the problems of the existence and increment size of the local times for X(t) are studied. In addition, the Hausdorff dimension of E(x, Q) and the upper bound of a uniform dimension for X(Q) are also established.     

Some characterizations and properties of the “distance to ill-posedness” and the condition measure of a conic linear system

A conic linear system is a system of the form?P(d): find x that solves b - Ax∈C _Y , x∈C _X ,? where C _X and C _Y are closed convex cones, and the data for the system is d=(A,b). This system is“well-posed” to the extent that (small) changes in the data (A,b) do not alter the status of the system (the system remains solvable or not). Renegar defined the “distance to ill-posedness”, ρ(d), to be the smallest change in the data Δd=(ΔA,Δb) for which the system P(d+Δd) is “ill-posed”, i.e., d+Δd is in the intersection of the closure of feasible and infeasible instances d’=(A’,b’) of P(·). Renegar also defined the “condition measure” of the data instance d as C(d):=∥d∥/ρ(d), and showed that this measure is a natural extension of the familiar condition measure associated with systems of linear equations. This study presents two categories of results related to ρ(d), the distance to ill-posedness, and C(d), the condition measure of d. The first category of results involves the approximation of ρ(d) as the optimal value of certain mathematical programs. We present ten different mathematical programs each of whose optimal values provides an approximation of ρ(d) to within certain constants, depending on whether P(d) is feasible or not, and where the constants depend on properties of the cones and the norms used. The second category of results involves the existence of certain inscribed and intersecting balls involving the feasible region of P(d) or the feasible region of its alternative system, in the spirit of the ellipsoid algorithm. These results roughly state that the feasible region of P(d) (or its alternative system when P(d) is not feasible) will contain a ball of radius r that is itself no more than a distance R from the origin, where the ratio R/r satisfies R/r≤c ₁ C(d), and such that r≥ and R≤c ₃ C(d), where c ₁,c ₂,c ₃ are constants that depend only on properties of the cones and the norms used. Therefore the condition measure C(d) is a relevant tool in proving the existence of an inscribed ball in the feasible region of P(d) that is not too far from the origin and whose radius is not too small. Received November 2, 1995 / Revised version received June 26, 1998?Published online May 12, 1999