Search

Let F (z 1 , ⋯ , z d) be the quotient of an analytic function with a product of linear functions. Working in the framework of analytic combinatorics in several variables, we compute asymptotic formulae for the Taylor coefficients of F using multivariate residues and saddle-point approximations. Because the singular set of F is the union of hyperplanes, we are able to make explicit the topological decompositions which arise in the multivariate singularity analysis. In addition to effective and explicit asymptotic results, we provide the first results on transitions between different asymptotic regimes, and provide the first software package to verify and compute asymptotics in non-smooth cases of analytic combinatorics in several variables. It is also our hope that this paper will serve as an entry to the more advanced corners of analytic combinatorics in several variables for combinatorialists. [ABSTRACT FROM AUTHOR]

On complex algebraic varieties, height functions arising in combinatorial applications fail to be proper. This complicates both the description and computation via Morse theory of key topological invariants. Here we establish checkable conditions under which the behavior at infinity may be ignored, and the usual theorems of classical and stratified Morse theory may be applied. This allows for simplified arguments in the field of analytic combinatorics in several variables, and forms the basis for new methods applying to problems beyond the reach of previous techniques. [ABSTRACT FROM AUTHOR]

We explore the survival function for percolation on Galton–Watson trees. Letting g(T, p) represent the probability a tree T survives Bernoulli percolation with parameter p, we establish several results about the behavior of the random function g (T , ·) , where T is drawn from the Galton–Watson distribution. These include almost sure smoothness in the supercritical region; an expression for the k th -order Taylor expansion of g (T , ·) at criticality in terms of limits of martingales defined from T (this requires a moment condition depending on k); and a proof that the k th order derivative extends continuously to the critical value. Each of these results is shown to hold for almost every Galton–Watson tree. [ABSTRACT FROM AUTHOR]

We study a coarsening process of one-dimensional cell complexes. We show that if cell boundaries move with velocities proportional to the difference in size of neighboring cells, then the average cell size grows at a prescribed exponential rate and the Poisson distribution is precisely invariant for the distribution of the whole process, rescaled in space by its average growth rate. We present numerical evidence toward the following universality conjecture: starting from any finite mean stationary renewal process, the system when rescaled by e converges to a Poisson point process. For a limited case, this makes precise what has been observed previously in experiments and simulations, and lays the foundation for a theory of universal asymptotic states of dynamical cell complexes. [ABSTRACT FROM AUTHOR]

We analyze several families of two-dimensional quantum random walks. The feasible region (the region where probabilities do not decay exponentially with time) grows linearly with time, as is the case with one-dimensional QRW. The limiting shape of the feasible region is, however, quite different. The limit region turns out to be an algebraic set, which we characterize as the rational image of a compact algebraic variety. We also compute the probability profile within the limit region, which is essentially a negative power of the Gaussian curvature of the same algebraic variety. Our methods are based on analysis of the space-time generating function, following the methods of Pemantle and Wilson (J. Comb. Theory, Ser. A 97(1):129-161, ). [ABSTRACT FROM AUTHOR]

Let X and Y be infinite graphs such that the automorphism group of X is nonamenable and the automorphism group of Y has an infinite orbit. We prove that there is no automorphism-invariant measure on the set of spanning trees in the direct product X×Y. This implies that the minimal spanning forest corresponding to i.i.d. edge-weights in such a product has infinitely many connected components almost surely. [ABSTRACT FROM AUTHOR]

Summary. We study the following growth model on a regular d-ary tree. Points at distance n adjacent to the existing subtree are added with probabilities proportional to α[sup -n] , where α < 1 is a positive real parameter. The heights of these clusters are shown to increase linearly with their total size; this complements known results that show the height increases only logarithmically when α ≧ 1. Results are obtained using stochastic monotonicity and regeneration results which may be of independent interest. Our motivation comes from two other ways in which the model may be viewed: as a problem in first-passage percolation, and as a version of diffusion-limited aggregation (DLA), adjusted so that “fingering” occurs. [ABSTRACT FROM AUTHOR]

Summary. We show that with probability 1, the trace B[0, 1] of Brownian motion in space, has positive capacity with respect to exactly the same kernels as the unit square. More precisely, the energy of occupation measure on B[0, 1] in the kernel f(∣x-y∣), is bounded above and below by constant multiples of the energy of Lebesgue measure on the unit square. (The constants are random, but do not depend on the kernel.) As an application, we give almost-sure asymptotics for the probability that an α-stable process approaches within ε of B[0, 1], conditional on B[0, 1]. The upper bound on energy is based on a strong law for the approximate self-intersections of the Brownian path. We also prove analogous capacity estimates for planar Brownian motion and for the zero-set of one-dimensional Brownian motion. [ABSTRACT FROM AUTHOR]

Summary. We consider random walks with a bias toward the root on the family tree T of a supercritical Galton–Watson branching process and show that the speed is positive whenever the walk is transient. The corresponding harmonic measures are carried by subsets of the boundary of dimension smaller than that of the whole boundary. When the bias is directed away from the root and the extinction probability is positive, the speed may be zero even though the walk is transient; the critical bias for positive speed is determined. [ABSTRACT FROM AUTHOR]

This paper considers a class of non-Markovian discrete-time random processes on a finite state space {1,..., d}. The transition probabilities at each time are influenced by the number of times each state has been visited and by a fixed a priori likelihood matrix, R, which is real, symmetric and nonnegative. Let S (n) keep track of the number of visits to state i up to time n, and form the fractional occupation vector, V( n), where $$v_i (n) = {{S_i (n)} \mathord{\left/ {\vphantom {{S_i (n)} {\left( {\sum\limits_{j = 1}^d {S_j (n)} } \right)}}} \right. \kern-\nulldelimiterspace} {\left( {\sum\limits_{j = 1}^d {S_j (n)} } \right)}}$$ . It is shown that V( n) converges to to a set of critical points for the quadratic form H with matrix R, and that under nondegeneracy conditions on R, there is a finite set of points such that with probability one, V( n)→ p for some p in the set. There may be more than one p in this set for which P(V( n)→ p)>0. On the other hand P(V( n)→ p)=0 whenever p fails in a strong enough sense to be maximum for H. [ABSTRACT FROM AUTHOR]

We consider the fractal percolation process on the unit square with fixed decimation parameter N and level-dependent retention parameters { p}; that is, for all k ⩾ 1, at the k th stage every retained square of side length N k is partitioned into N congruent subsquares, and each of these is retained with probability p. independent of all others. We show that if Π p =0 (i.e., if the area of the limiting set vanishes a.s.), then a.s. the limiting set contains no directed crossings of the unit square (a directed crossing is a path that crosses the unit square from left to right, and moves only up, down, and to the right). [ABSTRACT FROM AUTHOR]

Presents a study which focused on the Markov chain placed on random field of traps. Indication that the Markov chain's hypotheses are minimal; Indepth look at the trapping probabilities; Information on the Greens function; Methodology used to conduct the study; Results of the study.

Establishes recurrence criteria for sums of independent random variables which take values in Euclidean lattices in varying dimension. Statement of results; Proofs; Transient inhomogeneous random walk with fair bounded steps in one and two dimensions.