Oscillation of harmonic functions for subordinate Brownian motion and its applications

In this paper, we establish an oscillation estimate of nonnegative harmonic functions for a pure-jump subordinate Brownian motion. The infinitesimal generator of such subordinate Brownian motion is an integro-differential operator. As an application, we give a probabilistic proof of the following form of relative Fatou theorem for such subordinate Brownian motion X$X$ in a bounded κ$\kappa$-fat open set; if u$u$ is a positive harmonic function with respect to X$X$ in a bounded κ$\kappa$-fat open set D$D$ and h$h$ is a positive harmonic function in D$D$ vanishing on D^c$D^c$, then the non-tangential limit of u/h$u/h$ exists almost everywhere with respect to the Martin-representing measure of h$h$.     

On the second neighborhood conjecture of Seymour for regular digraphs with almost optimal connectivity

The second neighborhood conjecture of Seymour says that every antisymmetric digraph has a vertex whose second neighborhood is not smaller than the first one. The Caccetta–Häggkvist conjecture says that every digraph with n$n$ vertices and minimum out-degree r$r$ contains a cycle of length at most ⌈n/r⌉$\lceil n/r\rceil$. We give a proof of the former conjecture for digraphs with out-degree r$r$ and connectivity r−1$r-1$, and of the second one for digraphs with connectivity r−1$r-1$ and r≥n/3$r\ge n/3$. The main tool is the isoperimetric method of Hamidoune.     

Iterative approximation of solutions of nonlinear equations of Hammerstein type

Suppose X$X$ is a real q$q$-uniformly smooth Banach space and F,K:X→X$F,K:X\to X$ are Lipschitz ?$?$-strongly accretive maps with D(K)=F(X)=X$D\left(K\right)=F\left(X\right)=X$. Let u^∗$u^{\ast }$ denote the unique solution of the Hammerstein equation u+KFu=0$u+KFu=0$. An iteration process recently introduced by Chidume and Zegeye is shown to converge strongly to u^∗$u^{\ast }$. No invertibility assumption is imposed on K$K$ and the operators K$K$ and F$F$ need not be defined on compact subsets of X$X$. Furthermore, our new technique of proof is of independent interest. Finally, some interesting open questions are included.     

On weighted Hilbert spaces and integration of functions of infinitely many variables

We study aspects of the analytic foundations of integration and closely related problems for functions of infinitely many variables _x1,_x2,…∈D$x_1,x_2,\dots \in D$. The setting is based on a reproducing kernel k$k$ for functions on D$D$, a family of non-negative weights _γu${\gamma }_u$, where u$u$ varies over all finite subsets of N$\mathbb{N}$, and a probability measure ρ$\rho$ on D$D$. We consider the weighted superposition K=_∑uγuku$K={\sum }_u{\gamma }_u{k}_u$ of finite tensor products _ku$k_u$ of k$k$. Under mild assumptions we show that K$K$ is a reproducing kernel on a properly chosen domain in the sequence space D^N$D^{\mathbb{N}}$, and that the reproducing kernel Hilbert space H(K)$H\left(K\right)$ is the orthogonal sum of the spaces H(_γuku)$H\left({\gamma }_u{k}_u\right)$. Integration on H(K)$H\left(K\right)$ can be defined in two ways, via a canonical representer or with respect to the product measure ρ^N${\rho }^{\mathbb{N}}$ on D^N$D^{\mathbb{N}}$. We relate both approaches and provide sufficient conditions for the two approaches to coincide.     

Approximation of solutions of Hammerstein equations with bounded strongly accretive nonlinear operators

Suppose X$X$ is a real q$q$-uniformly smooth Banach space and F,K:X→X$F,K:X\to X$ are bounded strongly accretive maps with D(K)=F(X)=X$D\left(K\right)=F\left(X\right)=X$. Let u^∗$u^{\ast }$ denote the unique solution of the Hammerstein equation u+KFu=0$u+KFu=0$. A new explicit coupled iteration process is shown to converge strongly to u^∗$u^{\ast }$. No invertibility assumption is imposed on K$K$ and the operators K$K$ and F$F$ need not be defined on compact subsets of X$X$. Furthermore, our new technique of proof is of independent interest. Finally, some interesting open questions are included.     

On the complexity of the bondage and reinforcement problems

Let G=(V,E)$G=(V,E)$ be a graph. A subset D⊆V$D\subseteq V$ is a dominating set if every vertex not in D$D$ is adjacent to a vertex in D$D$. A dominating set D$D$ is called a total dominating set if every vertex in D$D$ is adjacent to a vertex in D$D$. The domination (resp. total domination) number of G$G$ is the smallest cardinality of a dominating (resp. total dominating) set of G$G$. The bondage (resp. total bondage) number of a nonempty graph G$G$ is the smallest number of edges whose removal from G$G$ results in a graph with larger domination (resp. total domination) number of G$G$. The reinforcement (resp. total reinforcement) number of G$G$ is the smallest number of edges whose addition to G$G$ results in a graph with smaller domination (resp. total domination) number. This paper shows that the decision problems for the bondage, total bondage, reinforcement and total reinforcement numbers are all NP-hard.     

A unified proof of Brooks’ theorem and Catlin’s theorem

Brooks’ theorem is a fundamental result in the theory of graph coloring. Catlin proved the following strengthening of Brooks’ theorem: Let d$d$ be an integer at least 3, and let G$G$ be a graph with maximum degree d$d$. If G$G$ does not contain _Kd+1$K_{d+1}$ as a subgraph, then G$G$ has a d$d$-coloring in which one color class has size α(G)$\alpha \left(G\right)$. Here α(G)$\alpha \left(G\right)$ denotes the independence number of G$G$. We give a unified proof of Brooks’ theorem and Catlin’s theorem.     

Strongly quasi-Hamiltonian-connected semicomplete multipartite digraphs

A semicomplete multipartite or semicomplete c$c$-partite digraph D$D$ is a biorientation of a c$c$-partite graph. A semicomplete multipartite digraph D$D$ is called strongly quasi-Hamiltonian-connected, if for any two distinct vertices x$x$ and y$y$ of D$D$, there is a path P$P$ from x$x$ to y$y$ such that P$P$ contains at least one vertex from each partite set of D$D$.     

Differential inequalities and equations in Banach spaces with a cone

A class of second-order abstract dissipative evolution differential operators D$D$ with 0∈kerD$0\in kerD$ is shown for which the fact that a non-zero t?u(t)$t?u\left(t\right)$ belongs to a cone and −Du$-Du$ to a dual cone may hold only on time intervals whose length is less than or equal to a defined number. Then oscillatory functions are dealt with in the framework of Banach spaces with a cone and conditions for the existence of a uniform oscillatory time for solutions of the equation Du=0$Du=0$ are given.     

On probabilistic results for the discrepancy of a hybrid-Monte Carlo sequence

In many applications it has been observed that hybrid-Monte Carlo sequences perform better than Monte Carlo and quasi-Monte Carlo sequences, especially in difficult problems. For a mixed s$s$-dimensional sequence m$m$, whose elements are vectors obtained by concatenating d$d$-dimensional vectors from a low-discrepancy sequence q$q$ with (s−d)$(s-d)$-dimensional random vectors, probabilistic upper bounds for its star discrepancy have been provided. In a paper of G. Ökten, B. Tuffin and V. Burago [G. Ökten, B. Tuffin, V. Burago, J. Complexity 22 (2006), 435–458] it was shown that for arbitrary ε>0$\epsilon >0$ the difference of the star discrepancies of the first N$N$ points of m$m$ and q$q$ is bounded by ε$\epsilon$ with probability at least 1−2exp(−ε²N/2)$1-2exp(-{\epsilon }^{2}N/2)$ for N$N$ sufficiently large. The authors did not study how large N$N$ actually has to be and if and how this actually depends on the parameters s$s$ and ε$\epsilon$. In this note we derive a lower bound for N$N$, which significantly depends on s$s$ and ε$\epsilon$. Furthermore, we provide a probabilistic bound for the difference of the star discrepancies of the first N$N$ points of m$m$ and q$q$, which holds without any restrictions on N$N$. In this sense it improves on the bound of Ökten, Tuffin and Burago and is more helpful in practice, especially for small sample sizes N$N$. We compare this bound to other known bounds.     

Weak convergence of censored and reflected stable processes

It is shown that if a sequence of open n$n$-sets _Dk$D_k$ increases to an open n$n$-set D$D$ then reflected stable processes in _Dk$D_k$ converge weakly to the reflected stable process in D$D$ for every starting point x$x$ in D$D$. The same result holds for censored α$\alpha$-stable processes for every x$x$ in D$D$ if D$D$ and _Dk$D_k$ satisfy the uniform Hardy inequality. Using the method in the proof of the above results, we also prove the weak convergence of reflected Brownian motions in unbounded domains.     

A note on distance-regular graphs with a small number of vertices compared to the valency

In this note we study distance-regular graphs with a small number of vertices compared to the valency. We show that for a given α>2$\alpha >2$, there are finitely many distance-regular graphs Γ$\Gamma$ with valency k$k$, diameter D≥3$D\ge 3$ and v$v$ vertices satisfying v≤αk$v\le \alpha k$ unless (D=3$D=3$ and Γ$\Gamma$ is imprimitive) or (D=4$D=4$ and Γ$\Gamma$ is antipodal and bipartite). We also show, as a consequence of this result, that there are finitely many distance-regular graphs with valency k≥3$k\ge 3$, diameter D≥3$D\ge 3$ and _c2≥εk$c_2\ge \epsilon k$ for a given 0<ε<1$0<\epsilon <1$ unless (D=3$D=3$ and Γ$\Gamma$ is imprimitive) or (D=4$D=4$ and Γ$\Gamma$ is antipodal and bipartite).     

Asymptotic average shadowing property on compact metric spaces

We prove that if for a continuous map f$f$ on a compact metric space X$X$, the chain recurrent set, R(f)$R\left(f\right)$ has more than one chain component, then f$f$ does not satisfy the asymptotic average shadowing property. We also show that if a continuous map f$f$ on a compact metric space X$X$ has the asymptotic average shadowing property and if A$A$ is an attractor for f$f$, then A$A$ is the single attractor for f$f$ and we have A=R(f)$A=R\left(f\right)$. We also study diffeomorphisms with asymptotic average shadowing property and prove that if M$M$ is a compact manifold which is not finite with dimM=2$dimM=2$, then the C¹$C^1$ interior of the set of all C¹$C^1$ diffeomorphisms with the asymptotic average shadowing property is characterized by the set of Ω$\Omega$-stable diffeomorphisms.     

Multidimensional extension of the Morse–Hedlund theorem

A celebrated result of Morse and Hedlund, stated in 1938, asserts that a sequence x$x$ over a finite alphabet is ultimately periodic if and only if, for some n$n$, the number of different factors of length n$n$ appearing in x$x$ is less than n+1$n+1$. Attempts to extend this fundamental result, for example, to higher dimensions, have been considered during the last fifteen years. Let d≥2$d\ge 2$. A legitimate extension to a multidimensional setting of the notion of periodicity is to consider sets of Z^d${\mathbb{Z}}^d$ definable by a first order formula in the Presburger arithmetic 〈Z;<,+〉$〈\mathbb{Z};<,+〉$. With this latter notion and using a powerful criterion due to Muchnik, we exhibit a complete extension of the Morse–Hedlund theorem to an arbitrary dimension d$d$ and characterize sets of Z^d${\mathbb{Z}}^d$ definable in 〈Z;<,+〉$〈\mathbb{Z};<,+〉$ in terms of some functions counting recurrent blocks, that is, blocks occurring infinitely often.     

Fixed point theorems for Reich type contractions on metric spaces with a graph

Let (X,d)$(X,d)$ be a metric space endowed with a graph G$G$ such that the set V(G)$V\left(G\right)$ of vertices of G$G$ coincides with X$X$. We define the notion of G$G$-Reich type maps and obtain a fixed point theorem for such mappings. This extends and subsumes many recent results which were obtained for other contractive type mappings on ordered metric spaces and for cyclic operators.     

Partial rigidity of degenerate CR embeddings into spheres

In this paper, we study degenerate CR embeddings f$f$ of a strictly pseudoconvex hypersurface M⊂Cⁿ⁺¹$M\subset {\mathbb{C}}^{n+1}$ into a sphere S$\mathbb{S}$ in a higher dimensional complex space C^N+1${\mathbb{C}}^{N+1}$. The degeneracy of the mapping f$f$ will be characterized in terms of the ranks of the CR second fundamental form and its covariant derivatives. In 2004, the author, together with X. Huang and D. Zaitsev, established a rigidity result for CR embeddings f$f$ into spheres in low codimensions. A key step in the proof of this result was to show that degenerate mappings are necessarily contained in a complex plane section of the target sphere (partial rigidity). In the 2004 paper, it was shown that if the total rank d$d$ of the second fundamental form and all of its covariant derivatives is <n$<n$ (here, n$n$ is the CR dimension of M$M$), then f(M)$f\left(M\right)$ is contained in a complex plane of dimension n+d+1$n+d+1$. The converse of this statement is also true, as is easy to see. When the total rank d$d$ exceeds n$n$, it is no longer true, in general, that f(M)$f\left(M\right)$ is contained in a complex plane of dimension n+d+1$n+d+1$, as can be seen by examples. In this paper, we carry out a systematic study of degenerate CR mappings into spheres. We show that when the ranks of the second fundamental form and its covariant derivatives exceed the CR dimension n$n$, then partial rigidity may still persist, but there is a “defect” k$k$ that arises from the ranks exceeding n$n$ such that f(M)$f\left(M\right)$ is only contained in a complex plane of dimension n+d+k+1$n+d+k+1$. Moreover, this defect occurs in general, as is illustrated by examples.