Asymptotics of the transition probabilities of the simple random walk on self-similar graphs

It is shown explicitly how self-similar graphs can be obtained as `blow-up' constructions of finite cell graphs . This yields a larger family of graphs than the graphs obtained by discretising continuous self-similar fractals.

For a class of symmetrically self-similar graphs we study the simple random walk on a cell graph , starting at a vertex of the boundary of . It is proved that the expected number of returns to before hitting another vertex in the boundary coincides with the resistance scaling factor.

Using techniques from complex rational iteration and singularity analysis for Green functions, we compute the asymptotic behaviour of the -step transition probabilities of the simple random walk on the whole graph. The results of Grabner and Woess for the Sierpinski graph are generalised to the class of symmetrically self-similar graphs, and at the same time the error term of the asymptotic expression is improved. Finally, we present a criterion for the occurrence of oscillating phenomena of the -step transition probabilities.

     

Harnack inequalities and difference estimates for random walks with infinite range

Difference estimates and Harnack inequalities for mean zero, finite variance random walks with infinite range are considered. An example is given to show that such estimates and inequalities do not hold for all mean zero, finite variance random walks. Conditions are then given under which such results can be proved.Research supported by the National Science Foundation.     

Local Limit Theorems for Sequences of Simple Random Walks on Graphs

In this article, local limit theorems for sequences of simple random walks on graphs are established. The results formulated are motivated by a variety of random graph models, and explanations are provided as to how they apply to supercritical percolation clusters, graph trees converging to the continuum random tree and the homogenisation problem for nested fractals. A subsequential local limit theorem for the simple random walks on generalised Sierpinski carpet graphs is also presented.      

Lower bounds for covering times for reversible Markov chains and random walks on graphs

For simple random walk on aN-vertex graph, the mean time to cover all vertices is at leastcN log(N), wherec>0 is an absolute constant. This is deduced from a more general result about stationary finite-state reversible Markov chains. Under weak conditions, the covering time for such processes is at leastc times the covering time for the corresponding i.i.d. process.     

LOWER BOUNDS FOR SUP＋INF AND SUP＊INF AND AN EXTENSION OF CHEN-LIN RESULT IN DIMENSION 3

We give two results about Harnack type inequalities. First, on Riemannian surfaces, we have an estimate of type sup ＋ inf. The second result concern the solutions of prescribed scalar curvature equation on the unit ball of Rn with Dirichlet condition. Next, we give an inequality of type （supK ^u）^2s-1 × infπu ≤ c for positive solutions of △u = V u^5 on Ω belong toR^3, where K is a compact set of Ω and V is s-Holderian, s ∈] - 1/2, 1]. For the case s = 1/2 and Ω = S3, we prove that, if minΩ u 〉 m 〉 0 （for some particular constant m 〉 0）, and the H¨olderian constant A of V tends to 0 （in certain meaning）, we have the uniform boundedness of the supremum of the solutions of the previous equation on any compact set of Ω.     

Lower bounds for combinatorial problems on graphs

Nontrivial lower bounds are given for the computation time of various combinatorial problems on graphs under a linear or algebraic decision tree model. An $\text{Ω(n}{}^3\text{log}\text{n)}$ bound is obtained for a “travelling salesman problem” on a weighted complete graph of n vertices. Moreover it is shown that the same bound is valid for the “subgraph detection problem” with respect to property P if P is hereditary and determined by components. Thus an $\text{Ω(n}{}^3\text{log}\text{n)}$ bound is established in a unified way for a rather large class of problems.     

A random environment for linearly edge-reinforced random walks on infinite graphs

We consider linearly edge-reinforced random walk on an arbitrary locally finite connected graph. It is shown that the process has the same distribution as a mixture of reversible Markov chains, determined by time-independent strictly positive weights on the edges. Furthermore, we prove bounds for the random weights, uniform, among others, in the size of the graph.      

Estimates for transition probabilities on a compact manifold

The purpose of this note is to describe a procedure for transferring familiar estimates for transition probabilities on RN to transition probabilities on compact manifolds.     

Persistence probabilities for stationary increment processes

We study the persistence probability for processes with stationary increments. Our results apply to a number of examples: sums of stationary correlated random variables whose scaling limit is fractional Brownian motion; random walks in random sceneries; random processes in Brownian scenery; and the Matheron–de Marsily model in ${\mathbb{Z}}^2$ with random orientations of the horizontal layers. Using a new approach, strongly related to the study of the range, we obtain an upper bound of the optimal order in general and improved lower bounds (compared to previous literature) for many specific processes.     

Harnack and mean value inequalities on graphs

We prove a Harnack inequality for positive harmonic functions on graphs which is similar to a classical result of Yau on Riemannian manifolds. Also, we prove a mean value inequality of nonnegative subharmonic functions on graphs.     

Lower bounds for weak sense of direction

A graph with n vertices and maximum degree Δ cannot be given weak sense of direction using less than Δ colours. It is known that n colours are always sufficient, but it has been conjectured that just Δ+1 are really needed. On the contrary, we show that for sufficiently large n there are graphs requiring Δ+Ω((nloglogn)/logn) colours. Moreover, we prove that, in terms of the maximum degree, colours are necessary.     

The infection time of graphs

Consider k particles, 1 red and k-1 white, chasing each other on the nodes of a graph G. If the red one catches one of the white, it “infects” it with its color. The newly red particles are now available to infect more white ones. When is it the case that all white will become red? It turns out that this simple question is an instance of information propagation between random walks and has important applications to mobile computing where a set of mobile hosts acts as an intermediary for the spread of information.In this paper we model this problem by k concurrent random walks, one corresponding to the red particle and k-1 to the white ones. The infection timeT_k of infecting all the white particles with red color is then a random variable that depends on k, the initial position of the particles, the number of nodes and edges of the graph, as well as on the structure of the graph.In this work we develop a set of probabilistic tools that we use to obtain upper bounds on the (worst case w.r.t. initial positions of particles) expected value of T_k for general graphs and important special cases. We easily get that an upper bound on the expected value of T_k is the worst case (over all initial positions) expected meeting timem^* of two random walks multiplied by . We demonstrate that this is, indeed, a tight bound; i.e. there is a graph G (a special case of the “lollipop” graph), a range of values k<n (such that ) and an initial position of particles achieving this bound.When G is a clique or has nice expansion properties, we prove much smaller bounds for T_k. We have evaluated and validated all our results by large scale experiments which we also present and discuss here. In particular, the experiments demonstrate that our analytical results for these expander graphs are tight.     

Lower bounds for the maximal Lyapunov exponent

Upper bounds for the maximal Lyapunov exponent,E, of a sequence of matrix-valued random variables are easy to come by asE is the infimum of a real-valued sequence. We shall show that under irreducibility conditions similar to those needed to prove the Perron-Frobenius theorem, one can find sequences which increase toE. As a byproduct of the proof we shall see that we may replace the matrix norm with the spectral radius when computingE in such cases. Finally, a sufficient condition for transience of random walk in a random environment is given.     

Lower bounds on the pathwidth of some grid-like graphs

We present proofs of lower bounds on the node search number of some grid-like graphs including two-dimensional grids, cylinders, tori and a variation we call “orb-webs”. Node search number is equivalent to pathwidth and vertex separation, which are all important graph parameters. Since matching upper bounds are not difficult to obtain, this implies that the pathwidth of these graphs is easily computed, because the bounds are simple functions of the graph dimensions. We also show matching upper and lower bounds on the node search number of equidimensional tori which are one less than the obvious upper bound.     

Lower bounds for matrices on block weighted sequence spaces I

In this paper we consider some matrix operators on block weighted sequence spaces l _p (w, F). The problem is to find the lower bound of some matrix operators such as Hausdorff and Hilbert matrices on l _p (w, F). This study is an extension of papers by G. Bennett, G.J.O. Jameson and R. Lashkaripour.      

Lower bounds for randomized direct search with isotropic sampling

Randomized direct-search methods for the optimization of a function f:Rⁿ→R that is given by a black box for f-evaluations are investigated. These iterative methods generate new candidate solutions by adding isotropically distributed vectors to the current candidate solution. Lower bounds on the number of f-evaluations necessary for reducing the approximation error in the search space are proved.     

Lower bounds on the signed domination numbers of directed graphs

A numerical invariant of directed graphs concerning domination which is named signed domination number γ_S is studied in this paper. We present some sharp lower bounds for γ_S in terms of the order, the maximum degree and the chromatic number of a directed graph.     

Lower bounds on signed edge total domination numbers in graphs

The open neighborhood N _G (e) of an edge e in a graph G is the set consisting of all edges having a common end-vertex with e. Let f be a function on E(G), the edge set of G, into the set {−1, 1}. If for each e ∈ E(G), then f is called a signed edge total dominating function of G. The minimum of the values , taken over all signed edge total dominating function f of G, is called the signed edge total domination number of G and is denoted by γ _st ′(G). Obviously, γ _st ′(G) is defined only for graphs G which have no connected components isomorphic to K ₂. In this paper we present some lower bounds for γ _st ′(G). In particular, we prove that γ _st ′(T) ⩾ 2 − m/3 for every tree T of size m ⩾ 2. We also classify all trees T with γ _st ′(T). Research supported by a Faculty Research Grant, University of West Georgia.     

Lower bounds on the signed total k-domination number of graphs

Let G be a graph with vertex set V(G). For any integer k ≥ 1, a signed total k-dominating function is a function f: V(G) → {?1, 1} satisfying ∑_x∈N(v)f(x) ≥ k for every v ∈ V(G), where N(v) is the neighborhood of v. The minimum of the values ∑_v∈V(G)f(v), taken over all signed total k-dominating functions f, is called the signed total k-domination number. In this note we present some new sharp lower bounds on the signed total k-domination number of a graph. Some of our results improve known bounds.     

Lower bounds on the maximum number of non-crossing acyclic graphs

This paper is a contribution to the problem of counting geometric graphs on point sets. More concretely, we look at the maximum numbers of non-crossing spanning trees and forests. We show that the so-called double chain point configuration of $N$ points has $\Omega \left(12.52^N\right)$ non-crossing spanning trees and $\Omega \left(13.61^N\right)$ non-crossing forests. This improves the previous lower bounds on the maximum number of non-crossing spanning trees and of non-crossing forests among all sets of $N$ points in general position given by Dumitrescu, Schulz, Sheffer and Tóth (2013). Our analysis relies on the tools of analytic combinatorics, which enable us to count certain families of forests on points in convex position, and to estimate their average number of components. A new upper bound of $O\left(22.12^N\right)$ for the number of non-crossing spanning trees of the double chain is also obtained.