How Close to Regular Must a Semicomplete Multipartite Digraph Be to Secure Hamiltonicity?

 Let D be a semicomplete multipartite digraph, with partite sets V ₁, V ₂,…, V _c, such that |V ₁|≤|V ₂|≤…≤|V _c|. Define f(D)=|V(D)|−3|V _c|+1 and . We define the irregularity i(D) of D to be max|d ⁺(x)−d ⁻(y)| over all vertices x and y of D (possibly x=y). We define the local irregularity i _l(D) of D to be max|d ⁺(x)−d ⁻(x)| over all vertices x of D and we define the global irregularity of D to be i _g(D)=max{d ⁺(x),d ⁻(x) : x∈V(D)}−min{d ⁺(y),d ⁻(y) : y∈V(D)}. In this paper we show that if i _g(D)≤g(D) or if i _l(D)≤min{f(D), g(D)} then D is Hamiltonian. We furthermore show how this implies a theorem which generalizes two results by Volkmann and solves a stated problem and a conjecture from [6]. Our result also gives support to the conjecture from [6] that all diregular c-partite tournaments (c≥4) are pancyclic, and it is used in [9], which proves this conjecture for all c≥5. Finally we show that our result in some sense is best possible, by giving an infinite class of non-Hamiltonian semicomplete multipartite digraphs, D, with i _g(D)=i(D)=i _l(D)=g(D)+?≤f(D)+1. Revised: September 17, 1998     

Riemann surfaces in fibered polynomial hulls

Let Δ be the closed unit disk in C, let Γ be the circle, let Π: Δ×C→Δ be projection, and letA(Δ) be the algebra of complex functions continuous on Δ and analytic in int Δ. LetK be a compact set in C² such that Π(K)=Γ, and letK _λ≠{w∈C|(λ,w)∈K}. Suppose further that (a) for every λ∈Γ,K _λ is the union of two nonempty disjoint connected compact sets with connected complement, (b) there exists a function Q(λ,w)≠(w-R(λ))²-S(λ) quadratic in w withR,S∈A(Δ) such that for all λ∈Γ, {w∈C|Q(λ,w)=0}υ intK _λ, whereS has only one zero in int Δ, counting multiplicity, and (c) for every λ∈Γ, the map ω→Q(λ,ω) is injective on each component ofK _λ. Then we prove that К/K is the union of analytic disks 2-sheeted over int Δ, where К is the polynomial convex hull ofK. Furthermore, we show that БК/K is the disjoint union of such disks.     

BMO-scale of distribution on ℝ n

Let S′ be the class of tempered distributions. For ƒ ∈ S′ we denote by J ^−α ƒ the Bessel potential of ƒ of order α. We prove that if J ^−α ƒ ∈ BMO, then for any λ ∈ (0, 1), J ^−α (f)_λ ∈ BMO, where (f)_λ = λ⁻ⁿ f(φ(λ⁻¹)), φ ∈ S. Also, we give necessary and sufficient conditions in order that the Bessel potential of a tempered distribution of order α > 0 belongs to the VMO space.     

The geodetic numbers of graphs and digraphs

For every two vertices u and v in a graph G,a u-v geodesic is a shortest path between u and v.Let I(u,v)denote the set of all vertices lying on a u-v geodesic.For a vertex subset S,let I(S) denote the union of all I(u,v)for u,v∈S.The geodetic number g(G)of a graph G is the minimum cardinality of a set S with I(S)=V(G).For a digraph D,there is analogous terminology for the geodetic number g(D).The geodetic spectrum of a graph G,denoted by S(G),is the set of geodetic numbers of all orientations of graph G.The lower geodetic number is g~-(G)=minS(G)and the upper geodetic number is g~ (G)=maxS(G).The main purpose of this paper is to study the relations among g(G),g~-(G)and g~ (G)for connected graphs G.In addition,a sufficient and necessary condition for the equality of g(G)and g(G×K_2)is presented,which improves a result of Chartrand,Harary and Zhang.     

Growth and Hölder conditions for the sample paths of Feller processes

Let (A,D(A)) be the infinitesimal generator of a Feller semigroup such that C _c ^∞(ℝ ⁿ )⊂D(A) and A|C _c ^∞(ℝ ⁿ ) is a pseudo-differential operator with symbol −p(x,ξ) satisfying |p(•,ξ)|_∞≤c(1+|ξ|²) and |Imp(x,ξ)|≤c ₀Rep(x,ξ). We show that the associated Feller process {X _t } _{t ≥0} on ℝ ⁿ is a semimartingale, even a homogeneous diffusion with jumps (in the sense of [21]), and characterize the limiting behaviour of its trajectories as t→0 and ∞. To this end, we introduce various indices, e.g., β_∞ ^x :={λ>0:lim _{|ξ|→∞ | x − y |≤2/|ξ|}|p(y,ξ)|/|ξ|^λ=0} or δ_∞ ^x :={λ>0:liminf _{|ξ|→∞ | x − y |≤2/|ξ| |ε|≤1}|p(y,|ξ|ε)|/|ξ|^λ=0}, and obtain a.s. (ℙ ^x ) that lim _{t →0} t ^−1/λ _{s ≤ t} |X _s −x|=0 or ∞ according to λ>β_∞ ^x or λ<δ_∞ ^x . Similar statements hold for the limit inferior and superior, and also for t→∞. Our results extend the constant-coefficient (i.e., Lévy) case considered by W. Pruitt [27]. Received: 21 July 1997 / Revised version: 26 January 1998     

On commutativity of two unary digraph operations: Subdividing and line-digraphing

For a digraph D, let L(D) and S(D) denote its line digraph and subdivision digraph, respectively. The motivation of this paper is to solve the digraph equation L(S(D))=S(L(D)). We show that L(S(D)) and S(L(D)) are cospectral if and only if D and L(D) have the same number of arcs. Further, we characterize the situation that L(S(D)) and S(L(D)) are isomorphic. Our approach introduces the new notion, the proper image D^* of a digraph D, and a new type of connectedness for digraphs. The concept D^* plays an important role in the main result of this paper. It is also useful in other aspects of the study of line digraphs. For example, L(D) is connected if and only if D^* is connected; L(D) is functional (contrafunctional) if and only if D^* is functional (contrafunctional). Some related results are also presented.     

Convergence Rates of Best N-term Galerkin Approximations for a Class of Elliptic sPDEs

Deterministic Galerkin approximations of a class of second order elliptic PDEs with random coefficients on a bounded domain D⊂ℝ ^d are introduced and their convergence rates are estimated. The approximations are based on expansions of the random diffusion coefficients in L ²(D)-orthogonal bases, and on viewing the coefficients of these expansions as random parameters y=y(ω)=(y _i (ω)). This yields an equivalent parametric deterministic PDE whose solution u(x,y) is a function of both the space variable x∈D and the in general countably many parameters y.     

T-Colorings and T-Edge Spans of Graphs

 Suppose G is a graph and T is a set of non-negative integers that contains 0. A T-coloring of G is an assignment of a non-negative integer f(x) to each vertex x of G such that |f(x)−f(y)|∉T whenever xy∈E(G). The edge span of a T-coloring−f is the maximum value of |f(x) f(y)| over all edges xy, and the T-edge span of a graph G is the minimum value of the edge span of a T-coloring of G. This paper studies the T-edge span of the dth power C ^d _n of the n-cycle C _n for T={0, 1, 2, …, k−1}. In particular, we find the exact value of the T-edge span of C _n ^d for n≡0 or (mod d+1), and lower and upper bounds for other cases. Received: May 13, 1996 Revised: December 8, 1997     

Conjugacy classes and finite p-groups

Let G be a finite p-group, where p is a prime number, and a ∈ G. Denote by Cl(a) = {gag⁻¹| g ∈ G} the conjugacy class of a in G. Assume that |Cl(a)| = pⁿ. Then Cl(a) Cl(a⁻¹) = {xy | x ∈ Cl(a), y ∈ Cl(a⁻¹)} is the union of at least n(p − 1) + 1 distinct conjugacy classes of G. Received: 16 December 2004     

The solution of characteristic value-vector problems by Newton's method

LetT(λ) be a bounded linear operator in a Banach spaceX for eachλ in the scalar fieldS. The characteristic value-vector problemT(λ)x = 0 with a normalization conditionφ x = 1, whereφ ε X ^*, is formulated as a nonlinear problem inX xS:P(y) ≡ (T(λ)x, φ x - 1) = 0,y= (X, A). Newton's method and the Kantorovič theorem are applied. For this purpose, representations and criteria for existence ofP′(y)⁻¹ are obtained. The continuous dependence onT of characteristic values and vectors is investigated. A numerical example withT(λ) =A +λB +λ ² C is presented. Sponsored by the Mathematics Research Center, United States Army, Madison, Wisconsin, under Contract No.: DA-31-124-ARO-D-462.     

THE SECOND EXPONENT SET OF PRIMITIVE DIGRAPHS

51.IntroductionandNotationsLetD=(V,E)beadigraphandL(D)denotethesetofcyclelengthsofD.ForuEVandintegeri21,letfo(u):={vEVIthereedestsadirectedwalkoflengthifromutov}.WedelveRo(u):={u}.Letu,vEV.IfN (v)=N (v)andN--(v)=N--(v),thenwecanvacopyofu.LotDbeaprimitivedigraphand7(D)denotetheexponentofD.In1950,H.WielandtI61foundthat7(D)5(n--1)' 1andshowedthatthereisapiquedigraphthatattainsthisbound.In1964,A.L.DulmageandN.S.Mendelsohn[2]ObservedthattherearegapsintheexponentsetEd={ry(D)IDEPD.}…     

Correlation structure of intermittency in the parabolic Anderson model

Consider the Cauchy problem ∂u(x, t)/∂t = ℋu(x, t) (x∈ℤ^d, t≥ 0) with initial condition u(x, 0) ≡ 1 and with ℋ the Anderson Hamiltonian ℋ = κΔ + ξ. Here Δ is the discrete Laplacian, κ∈ (0, ∞) is a diffusion constant, and ξ = {ξ(x): x∈ℤ ^d } is an i.i.d.random field taking values in ℝ. G?rtner and Molchanov (1990) have shown that if the law of ξ(0) is nondegenerate, then the solution u is asymptotically intermittent. In the present paper we study the structure of the intermittent peaks for the special case where the law of ξ(0) is (in the vicinity of) the double exponential Prob(ξ(0) > s) = exp[−e ^{s /θ}] (s∈ℝ). Here θ∈ (0, ∞) is a parameter that can be thought of as measuring the degree of disorder in the ξ-field. Our main result is that, for fixed x, y∈ℤ ^d and t→∈, the correlation coefficient of u(x, t) and u(y, t) converges to ∥w _ρ∥⁻² _ℓ2Σ_{z ∈ℤd} w _ρ(x+z)w _ρ(y+z). In this expression, ρ = θ/κ while w _ρ:ℤ^d→ℝ⁺ is given by w _ρ = (v _ρ)^{⊗ d} with v _ρ: ℤ→ℝ⁺ the unique centered ground state (i.e., the solution in ℓ²(ℤ) with minimal l ²-norm) of the 1-dimensional nonlinear equation Δv + 2ρv log v = 0. The uniqueness of the ground state is actually proved only for large ρ, but is conjectured to hold for any ρ∈ (0, ∞). empty It turns out that if the right tail of the law of ξ(0) is thicker (or thinner) than the double exponential, then the correlation coefficient of u(x, t) and u(y, t) converges to δ _{x, y} (resp.the constant function 1). Thus, the double exponential family is the critical class exhibiting a nondegenerate correlation structure. Received: 5 March 1997 / Revised version: 21 September 1998     

Convolution properties of some classes of analytic functions

Let A denote the class of functions which are analytic in |z|<1 and normalized so that f(0)=0 and f′(0)=1, and let R(α, β)⊂A be the class of functions f such thatRe[f′(z)+αzf″(z)]>β,Re α>0, β<1. We determine conditions under which (i) f ∈ R(α₁, β₁), g ∈ R(α₂, β₂) implies that the convolution f×g of f and g is convex; (ii) f ∈ R(0, β₁), g ∈ R(0, β₂) implies that f×g is starlike; (iii) f≠A such that f′(z)[f(z)/z]^μ-1 ≺ 1 + λz, μ>0, 0<λ<1, is starlike, and (iv) f≠A such that f′(z)+αzf″(z) ≺ 1 + λz, α>0, δ>0, is convex or starlike. Bibliography: 16 titles. Published inZapiski Nauchnykh Seminarov POMI, Vol. 226, 1996, pp. 138–154.     

Differential sobordination and Bazilevič functions

LetM(z)=z ⁿ +…,N(z)=z ⁿ +… be analytic in the unit disc Δ and let λ(z)=N(z)/zN′(z). The classical result of Sakaguchi-Libera shows that Re(M′(z)/N′(z))<0 implies Re(M(z)/N(z))>0 in Δ whenever Re(λ(z))>0 in Δ. This can be expressed in terms of differential subordination as follows: for anyp analytic in Δ, withp(0)=1,p(z)+λ(z)zp′(z)<1+z/1−z impliesp(z)<1+z/1−z, for Reλ(z)>0,z∈Δ. In this paper we determine different type of general conditions on λ(z),h(z) and ϕ(z) for which one hasp(z)+λ(z)zp′(z)<h(z) impliesp(z)<ϕ(z)<h(z) z∈Δ. Then we apply the above implication to obtain new theorems for some classes of normalized analytic funotions. In particular we give a sufficient condition for an analytic function to be starlike in Δ.     

Characterization of polyanalytic functions by meromorphic extensions from chains of circles

Let C _t = {z ∈ ℂ: |z − c(t)| = r(t), t ∈ (0, 1)} be a C ¹-family of circles in the plane such that lim _t→0+ C _t = {a}, lim _t→1− C _t = {b}, a ≠ b, and |c′(t)|² + |r′(t)|² ≠ 0. The discriminant set S of the family is defined as the closure of the set {c(t) + r(t)w(t), t ∈ [0, 1]}, where w = w(t) is the root of the quadratic equation ̅c′(t)w ² + 2r′(t)w + c′(t) = 0 with |w| < 1, if such a root exists.     

Probabilities of high excursions of Gaussian fields

Let {ξ(t), t ∈ T} be a differentiable (in the mean-square sense) Gaussian random field with E ξ(t) ≡ 0, D ξ(t) ≡ 1, and continuous trajectories defined on the m-dimensional interval T ì \mathbbR^m T \subset {\mathbb{R}^m} . The paper is devoted to the problem of large excursions of the random field ξ. In particular, the asymptotic properties of the probability P = P{−v(t) < ξ(t) < u(t), t ∈ T}, when, for all t ∈ T, u(t), v(t) ⩾ χ, χ → ∞, are investigated. The work is a continuation of Rudzkis research started in [R. Rudzkis, Probabilities of large excursions of empirical processes and fields, Sov. Math., Dokl., 45(1):226–228, 1992]. It is shown that if the random field ξ satisfies certain smoothness and regularity conditions, then P = e^−Q  + Qo(1), where Q is a certain constructive functional depending on u, v, T, and the matrix function R(t) = cov(ξ′(t), ξ′(t)).     

Lower bounds at infinity of solutions of partial differential equations in the exterior of a proper cone

An extension of a classical theorem of Rellich to the exterior of a closed proper convex cone is proved: Let Γ be a closed convex proper cone inR ⁿ and −Γ′ be the antipodes of the dual cone of Γ. Let be a partial differential operator with constant coefficients inR ⁿ, whereQ(ζ)≠0 onR ⁿ−iΓ′ andP _i is an irreducible polynomial with real coefficients. Assume that the closure of each connected component of the set {ζ∈R ⁿ−iΓ′;P _j(ζ)=0, gradP _j(ζ)≠0} contains some real point on which gradP _j≠0 and gradP _j∉Γ∪(−Γ). LetC be an open cone inR ⁿ−Γ containing both normal directions at some such point, and intersecting each normal plane of every manifold contained in {ξ∈R ⁿ;P(ξ)=0}. Ifu∈ℒ′∩L _loc ² (R ⁿ−Γ) and the support ofP(−i∂/∂x)u is contained in Γ, then the condition implies that the support ofu is contained in Γ.     

Noise sensitivity of Boolean functions and applications to percolation

It is shown that a large class of events in a product probability space are highly sensitive to noise, in the sense that with high probability, the configuration with an arbitrary small percent of random errors gives almost no prediction whether the event occurs. On the other hand, weighted majority functions are shown to be noise-stable. Several necessary and sufficient conditions for noise sensitivity and stability are given. Consider, for example, bond percolation on ann+1 byn grid. A configuration is a function that assigns to every edge the value 0 or 1. Let ω be a random configuration, selected according to the uniform measure. A crossing is a path that joins the left and right sides of the rectangle, and consists entirely of edges ℓ with ω(ℓ)=1. By duality, the probability for having a crossing is 1/2. Fix an ɛ ∈ (0, 1). For each edge ℓ, let ω′(ℓ)=ω(ℓ) with probability 1 − ɛ, and ω′(ℓ)=1 − ω(ℓ) with probability ɛ, independently of the other edges. Letp(τ) be the probability for having a crossing in ω, conditioned on ω′ = τ. Then for alln sufficiently large,P{τ : |p(τ) − 1/2| > ɛ}<ɛ.