On a semi-Markov generalization of the random walk

The semi-Markov process studied here is a generalized random walk on the non-negative integers with zero as a reflecting barrier, in which the time interval between two consecutive jumps is given an arbitrary distribution H(t). Our process is identical with the Markov chain studied by Miller [6] in the special case when H(t)=U₁(t), the Heaviside function with unit jump at t=1. By means of a Spitzer-Baxter type identity, we establish criteria for transience, positive and null recurrence, as well as conditions for exponential ergodicity. The results obtained here generalize those of [6] and some classical results in random walk theory [10].     

Martin Boundary of a Fine Domain and a Fatou-Naïm-Doob Theorem for Finely Superharmonic Functions

Let Γ be a graph with the doubling property for the volume of balls and P a reversible random walk on Γ. We introduce H¹ Hardy spaces of functions and 1-forms adapted to P and prove various characterizations of these spaces. We also characterize the dual space of H¹ as a BMO-type space adapted to P. As an application, we establish H¹ and H¹- L¹ boundedness of the Riesz transform.     

Sina?ˇ's condition for real valued Lévy processes

We prove that the upward ladder height subordinator H associated to a real valued Lévy process ξ has Laplace exponent φ that varies regularly at ∞ (respectively, at 0) if and only if the underlying Lévy process ξ satisfies Sina?ˇ's condition at 0 (respectively, at ∞). Sina?ˇ's condition for real valued Lévy processes is the continuous time analogue of Sina?ˇ's condition for random walks. We provide several criteria in terms of the characteristics of ξ to determine whether or not it satisfies Sina?ˇ's condition. Some of these criteria are deduced from tail estimates of the Lévy measure of H, here obtained, and which are analogous to the estimates of the tail distribution of the ladder height random variable of a random walk which are due to Veraverbeke and Grübel.     

Classifying bicrossed products of two Sweedler’s Hopf algebras

We continue the study started recently by Agore, Bontea and Militaru in “Classifying bicrossed products of Hopf algebras” (2014), by describing and classifying all Hopf algebras E that factorize through two Sweedler’s Hopf algebras. Equivalently, we classify all bicrossed products H ₄ ? H ₄. There are three steps in our approach. First, we explicitly describe the set of all matched pairs (H ₄,H ₄, ?, ?) by proving that, with the exception of the trivial pair, this set is parameterized by the ground field k. Then, for any λ ∈ k, we describe by generators and relations the associated bicrossed product, \({H_{16,\lambda }}\) . This is a 16-dimensional, pointed, unimodular and non-semisimple Hopf algebra. A Hopf algebra E factorizes through H ₄ and H ₄ if and only if E ? H ₄ ? H ₄ or \(E \cong {H_{16,\lambda }}\) . In the last step we classify these quantum groups by proving that there are only three isomorphism classes represented by: H ₄ ? H ₄, H _16,0 and H _16,1 ? D(H ₄), the Drinfel’d double of H ₄. The automorphism group of these objects is also computed: in particular, we prove that Aut_Hopf (D(H ₄)) is isomorphic to a semidirect product of groups, k ^× ? ?₂.     

Relative colorings of graphs

In this paper, the notion of relative chromatic number χ(G, H) for a pair of graphs G, H, with H a full subgraph of G, is formulated; namely, χ(G, H) is the minimum number of new colors needed to extend any coloring of H to a coloring of G. It is shown that the four color conjecture (4CC) is equivalent to the conjecture (R4CC) that χ(G, H) ≤ 4 for any (possibly empty) full subgraph H of a planar graph G and also to the conjecture (CR3CC) that χ(G, H) ≤ 3 if H is a connected and nonempty full subgraph of planar G. Finally, relative coloring theorems on surfaces other than the plane or sphere are proved.     

An approximation algorithm for the hamiltonian walk problem on maximal planar graphs

A hamiltonian walk of a graph is a shortest closed walk that passes through every vertex at least once, and the length is the total number of traversed edges. The hamiltonian walk problem in which one would like to find a hamiltonian walk of a given graph is NP-complete. The problem is a generalized hamiltonian cycle problem and is a special case of the traveling salesman problem. Employing the techniques of divide-and-conquer and augmentation, we present an approximation algorithm for the problem on maximal planar graphs. The algorithm finds, in O(p²) time, a closed spanning walk of a given arbitrary maximal planar graph, and the length of the obtained walk is at most $\text{3}\text{2}$(p ? 3) if the graph has p (≥ 9) vertices. Hence the worst-case bound is $\text{3}\text{2}$.     

The Green Ring of Drinfeld Double D(H 4)

In this paper, we study the Green ring (or the representation ring) of Drinfeld quantum double D(H ₄) of Sweedler’s four-dimensional Hopf algebra H ₄. We first give the decompositions of the tensor products of finite dimensional indecomposable modules into the direct sum of indecomposable modules over D(H ₄). Then we describe the structure of the Green ring r(D(H ₄)) of D(H ₄) and show that r(D(H ₄)) is generated, as a ring, by infinitely many elements subject to a family of relations.     

The Spectrum Meta(H > T, λ) for Some Subgraphs H and T of K 4

Let Meta(H > T, λ) denote the set of all integers v such that there exists a (H > T)-GM _λ (v). In this paper, the set Meta(H > T, λ) will be completely determined for the following 21 pairs (H, T) = (H ₁, P ₂), (H ₂, 2P ₂), (H ₃, P ₃) and (H ₄, P ₄), where \({P_2 \subset H_1 \subseteq K_4, H_2 \in \{K_4, C_4, K_3+e, P_4\} = {\mathcal {H}}, H_3 \in {\mathcal {H}} \cup \{K_3, K_{1,3} \}}\) and \({H_4 \in \{K_4, C_4\}}\) .     

The complexity of crossed products

Let H be a finite-dimensional Hopf algebra, let A be a finite-dimensional algebra measured by H, and let A # _σ H be a crossed product. In this paper, we first show that if H is semisimple as well as its dual H*, then the complexity of A # _σ H is equal to that of A. Furthermore, we prove that the complexity of a finite-dimensional Hopf algebra H is equal to the complexity of the trivial module _H k. As an application, we prove that the complexity of Sweedler’s 4-dimensional Hopf algebra H ₄ is equal to 1.     

Hitting times with taboo for a random walk

For a symmetric homogeneous and irreducible random walk on the d-dimensional integer lattice, which have a finite variance of jumps, we study passage times (taking values in [0,??]) determined by a starting point x, a hitting state y, and a taboo state z. We find the probability that these passage times are finite, and study the distribution tail. In particular, it turns out that, for the above-mentioned random walks on ? ^d except for a simple random walk on ?, the order of the distribution tail decrease is specified by dimension d only. In contrast, for a simple random walk on ?, the asymptotic properties of hitting times with taboo essentially depend on mutual location of the points x, y, and z. These problems originated in recent study of a branching random walk on ? ^d with a single source of branching.     

Some properties of random walk paths

For random walk on the d-dimensional integer lattice we consider again the problem of deciding when a set is recurrent, that is visited infinitely often with probability one by the random walk in question. Some special cases are considered, among them the following: for d = 2, what sequences (n_j) have the property that with probability one the random walk visits the origin for infinitely many n_j. A related problem, which is however not a special case of the recurrence problem, is to decide for what sequences (n_j) the states visited by the random walk at times n_j are all distinct, with only a finite number of exceptions. This problem is dealt with in the final part of the paper.     

Crossing velocities for an annealed random walk in a random potential

We consider a random walk in an i.i.d. non-negative potential on the d-dimensional integer lattice. The walk starts at the origin and is conditioned to hit a remote location y on the lattice. We prove that the expected time under the annealed path measure needed by the random walk to reach y grows only linearly in the distance from y to the origin. In dimension 1 we show the existence of the asymptotic positive speed.     

Random walk on a discrete Heisenberg group

We use the estimate of paths in Z ² enclosing a null algebraic area to compute correction terms on the random walk on certain discrete Heisenberg groups. We obtain that the probability to return at the origin of the simple random walk on this group is $\frac{1}{4n^{2}}+O(\frac{1}{n^{3}})$ .     

Large deviations for local time fractional Brownian motion and applications

Let be a fractional Brownian motion of Hurst index H∈(0,1) with values in R, and let be the local time process at zero of a strictly stable Lévy process of index 1<α?2 independent of WH. The α-stable local time fractional Brownian motion is defined by ZH(t)=WH(Lt). The process ZH is self-similar with self-similarity index and is related to the scaling limit of a continuous time random walk with heavy-tailed waiting times between jumps [P. Becker-Kern, M.M. Meerschaert, H.P. Scheffler, Limit theorems for coupled continuous time random walks, Ann. Probab. 32 (2004) 730-756; M.M. Meerschaert, H.P. Scheffler, Limit theorems for continuous time random walks with infinite mean waiting times, J. Appl. Probab. 41 (2004) 623-638]. However, ZH does not have stationary increments and is non-Gaussian. In this paper we establish large deviation results for the process ZH. As applications we derive upper bounds for the uniform modulus of continuity and the laws of the iterated logarithm for ZH.     

Netlike partial cubes II. Retracts and netlike subgraphs

First we show that the class of netlike partial cubes is closed under retracts. Then we prove, for a subgraph G of a netlike partial cube H, the equivalence of the assertions: G is a netlike subgraph of H; G is a hom-retract of H; G is a retract of H. Finally we show that a non-trivial netlike partial cube G, which is a retract of some bipartite graph H, is also a hom-retract of H if and only if G contains at most one convex cycle of length greater than 4.     

ℓ-distant Hamiltonian walks in Cartesian product graphs

We introduce and study a generalisation of Hamiltonian cycles: an ℓ-distant Hamiltonian walk in a graph G of order n is a cyclic ordering of its vertices in which consecutive vertices are at distance ℓ. Conditions for a Cartesian product graph to possess such an ℓ-distant Hamiltonian walk are given and more specific results are presented concerning toroidal grids.     

A note on multitype branching process with bounded immigration in random environment

In this paper, we study the total number of progeny, W, before regenerating of multitype branching process with immigration in random environment. We show that the tail probability of |W| is of order t-κ as t→∞, with κ some constant. As an application, we prove a stable law for (L-1) random walk in random environment, generalizing the stable law for the nearest random walk in random environment (see "Kesten, Kozlov, Spitzer: A limit law for random walk in a random environment. Compositio Math., 30, 145-168 (1975)").     

Level crossing probabilities II: Polygonal recurrence of multidimensional random walks

In part I we proved for an arbitrary one-dimensional random walk with independent increments that the probability of crossing a level at a given time n is O(n−1/2). In higher dimensions we call a random walk ‘polygonally recurrent’ if there is a bounded set, hit by infinitely many of the straight lines between two consecutive sites a.s. The above estimate implies that three-dimensional random walks with independent components are polygonally transient. Similarly a directionally reinforced random walk on Z³ in the sense of Mauldin, Monticino and von Weizsäcker [R.D. Mauldin, M. Monticino, H. von Weizsäcker, Directionally reinforced random walks, Adv. Math. 117 (1996) 239-252] is transient. On the other hand, we construct an example of a transient but polygonally recurrent random walk with independent components on Z².     

Local asymptotics for the time of first return to the origin of transient random walk

We consider a transient random walk on Z^d which is asymptotically stable, without centering, in a sense which allows different norming for each component. The paper is devoted to the asymptotics of the probability of the first return to the origin of such a random walk at time n.