1,720,991 research outputs found
First passage percolation in hostile environment is not monotone
Full text linkWe study a natural growth process with competition, modeled by two first
passage percolation processes, and , spreading on a graph.
starts at the origin and spreads at rate , whereas
starts from a random set of \emph{inactive seeds} distributed as Bernoulli
percolation of parameter . A seed of gets activated
when one of the two processes attempts to occupy its location, and from this
moment onwards spreads at some fixed rate . In previous works~[17,
3, 7] it has been shown that when both or are small enough,
then \emph{survives} (i.e., it occupies an infinite set of vertices)
with positive probability. It might seem intuitive that decreasing or
is beneficial to . However, we prove that, in general, this is
indeed false by constructing a graph for which the probability that
survives is not a monotone function of or , implying the
existence of multiple phase transitions. This behavior contrasts with other
natural growth processes such as the -type Richardson model.Comment: 42 pages, 6 figure
Abelian oil and water dynamics does not have an absorbing-state phase transition
Full text linkThe oil and water model is an interacting particle system with two types of particles and a dynamics that conserves the number of particles, which belongs to the so-called class of Abelian networks. Widely studied processes in this class are sandpiles models and activated random walks, which are known (at least for some choice of the underlying graph) to undergo an absorbing-state phase transition. This phase transition characterizes the existence of two regimes, depending on the particle density: a regime of fixation at low densities, where the dynamics converges towards an absorbing state and each particle jumps only finitely many times, and a regime of activity at large densities, where particles jump infinitely often and activity is sustained indefinitely. In this work we show that the oil and water model is substantially different than sandpiles models and activated random walks, in the sense that it does not undergo an absorbing-state phase transition and is in the regime of fixation at all densities. Our result works in great generality: for any graph that is vertex transitive and for a large class of initial configurations
Growing uniform planar maps face by face
Full text linkWe provide “growth schemes” for inductively generating uniform random
-angulations of the sphere with
faces, as well as uniform random simple triangulations of the sphere with
faces. In the case of
-angulations, we provide a way to insert a new face at a random location in a uniform
-angulation with
faces in such a way that the new map is precisely a uniform
-angulation with
faces. Similarly, given a uniform simple triangulation of the sphere with
faces, we describe a way to insert two new adjacent triangles so as to obtain a uniform simple triangulation of the sphere with
faces. The latter is based on a new bijective presentation of simple triangulations that relies on a construction by Poulalhon and Schaeffer
Random lattice triangulations: Structure and algorithms
Full text linkThe paper concerns lattice triangulations, that is, triangulations of the in- teger points in a polygon in R2 whose vertices are also integer points. Lattice triangulations have been studied extensively both as geometric objects in their own right and by virtue of applications in algebraic geometry. Our focus is on random triangulations in which a triangulation σ has weight λ|σ|, where λ is a positive real parameter, and |σ| is the total length of the edges in σ. Empirically, this model exhibits a “phase transition” at λ = 1 (correspond- ing to the uniform distribution): for λ < 1 distant edges behave essentially independently, while for λ > 1 very large regions of aligned edges appear. We substantiate this picture as follows. For λ < 1 sufficiently small, we show that correlations between edges decay exponentially with distance (suitably defined), and also that the Glauber dynamics (a local Markov chain based on flipping edges) is rapidly mixing (in time polynomial in the number of edges in the triangulation). This dynamics has been proposed by several authors as an algorithm for generating random triangulations. By contrast, for λ > 1 we show that the mixing time is exponential. These are apparently the first rigorous quantitative results on the structure and dynamics of random lattice triangulations
Dynamics of lattice triangulations on thin rectangles
Full text linkWe consider random lattice triangulations of n×k rectangular regions with weight λ|σ| where λ > 0 is a parameter and |σ| denotes the total edge length of the triangulation. When λ ∈ (0, 1) and k is fixed, we prove a tight upper bound of order n2 for the mixing time of the edge-flip Glauber dynamics. Combined with the previously known lower bound of order exp(Ω(n2)) for λ > 1 [3], this establishes the existence of a dynamical phase transition for thin rectangles with critical point at λ = 1
Coexistence of competing first passage percolation on hyperbolic graphs
Full text linkWe study a natural growth process with competition, which was recently introduced to analyze MDLA, a challenging model for the growth of an aggregate by diffusing particles. The growth process consists of two first-passage percolation processes and , spreading with rates and lambda>0 respectively, on a graph .
starts from a single vertex at the origin , while the initial configuration of consists of infinitely many seeds distributed according to a product of Bernoulli measures of parameter mu>0 on .
starts spreading from time 0, while each seed of only starts spreading after it has been reached by either or .
A fundamental question in this model, and in growth processes with competition in general, is whether the two processes coexist (i.e., both produce infinite clusters) with positive probability. We show that this is the case when is vertex transitive, non-amenable and hyperbolic, in particular, for any lambda>0 there is a mu_0=mu_0(G,lambda)>0 such that for all the two processes coexist with positive probability. This is the first non-trivial instance where coexistence is established for this model.
We also show that produces an infinite cluster almost surely for any positive , establishing fundamental differences with the behavior of such processes on
Mobile geometric graphs:Detection, coverage and percolation
Full text linkWe consider the following dynamic Boolean model introduced by van den Berg et al. (Stoch. Process. Appl. 69:247–257, 1997). At time 0, let the nodes of the graph be a Poisson point process in Rd with constant intensity and let each node move independently according to Brownian motion. At any time t, we put an edge between every pair of nodes whose distance is at most r. We study three fundamental problems in this model: detection (the time until a target point—fixed or moving—is within distance r of some node of the graph); coverage (the time until all points inside a finite box are detected by the graph); and percolation (the time until a given node belongs to the infinite connected component of the graph). We obtain precise asymptotics for these quantities by combining ideas from stochastic geometry, coupling and multi-scale analysis
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
