Edge-reinforced random walk on one-dimensional periodic graphs

In the present paper, linearly edge-reinforced random walk is studied on a large class of one-dimensional periodic graphs satisfying a certain reflection symmetry. It is shown that the edge-reinforced random walk is recurrent. Estimates for the position of the random walker are given. The edge-reinforced random walk has a unique representation as a random walk in a random environment, where the random environment is given by random weights on the edges. It is shown that these weights decay exponentially in space. The distribution of the random weights equals the distribution of the asymptotic proportion of time spent by the edge-reinforced random walker on the edges of the graph. The results generalize work of the authors in Merkl and Rolles (Ann Probab 33(6):2051–2093, 2005; 35(1):115–140, 2007) and Rolles (Probab Theory Related Fields 135(2):216–264, 2006) to a large class of graphs and to periodic initial weights with a reflection symmetry.     

Number of edges in inhomogeneous random graphs

We study the number of edges in the inhomogeneous random graph when vertex weights have an infinite mean and show that the number of edges is O(n log n). Central limit theorems for the number of edges are also established.     

The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph

The minimal weight of a spanning tree in a complete graph K_n with independent, uniformly distributed random weights on the edges is shown to have an asymptotic normal distribution. The proof uses a functional limit extension of results by Barbour and Pittel on the distribution of the number of tree components of given sizes in a random graph.     

Critical random graphs and the structure of a minimum spanning tree

We consider the complete graph on n vertices whose edges are weighted by independent and identically distributed edge weights and build the associated minimum weight spanning tree. We show that if the random weights are all distinct, then the expected diameter of such a tree is Θ(n^1/3). This settles a question of Frieze and Mc‐Diarmid (Random Struct Algorithm 10 (1997), 5–42). The proofs are based on a precise analysis of the behavior of random graphs around the critical point. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Minimal functions on the random graph

We show that there is a system of 14 non-trivial finitary functions on the random graph with the following properties: Any non-trivial function on the random graph generates one of the functions of this system by means of composition with automorphisms and by topological closure, and the system is minimal in the sense that no subset of the system has the same property. The theorem is obtained by proving a Ramsey-type theorem for colorings of tuples in finite powers of the random graph, and by applying this to find regular patterns in the behavior of any function on the random graph. As model-theoretic corollaries of our methods we rederive a theorem of Simon Thomas classifying the first-order closed reducts of the random graph, and prove some refinements of this theorem; also, we obtain a classification of the maximal reducts closed under primitive positive definitions, and prove that all reducts of the random graph are model-complete.     

The CRT is the scaling limit of random dissections

Abstract–We study the graph structure of large random dissections of polygons sampled according to Boltzmann weights, which encompasses the case of uniform dissections or uniform p‐angulations. As their number of vertices n goes to infinity, we show that these random graphs, rescaled by , converge in the Gromov–Hausdorff sense towards a multiple of Aldous' Brownian tree when the weights decrease sufficiently fast. The scaling constant depends on the Boltzmann weights in a rather amusing and intriguing way, and is computed by making use of a Markov chain which compares the length of geodesics in dissections with the length of geodesics in their dual trees. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 304–327, 2015     

Sandwiching random graphs: universality between random graph models

The goal of this paper is to establish a connection between two classical models of random graphs: the random graph G(n,p) and the random regular graph G_d(n). This connection appears to be very useful in deriving properties of one model from the other and explains why many graph invariants are universal. In particular, one obtains one-line proofs of several highly non-trivial and recent results on G_d(n).     

A one-dimensional version of the random interlacements

We base ourselves on the construction of the two-dimensional random interlacements (Comets et al., 2016) to define the one-dimensional version of the process. For this, we consider simple random walks conditioned on never hitting the origin. We compare this process to the conditional random walk on the ring graph. Our results are the convergence of the vacant set on the ring graph to the vacant set of one-dimensional random interlacements, a central limit theorem for the interlacements’ local time and the convergence in law of the local times of the conditional walk on the ring graph to the interlacements’ local times.     

The random planar graph process

We consider the following variant of the classical random graph process introduced by Erd?s and Rényi. Starting with an empty graph on n vertices, choose the next edge uniformly at random among all edges not yet considered, but only insert it if the graph remains planar. We show that for all ε > 0, with high probability, θ(n²) edges have to be tested before the number of edges in the graph reaches (1 + ε)n. At this point, the graph is connected with high probability and contains a linear number of induced copies of any fixed connected planar graph, the first property being in contrast and the second one in accordance with the uniform random planar graph model. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Grids in random graphs

Threshold probabilities for the existence in a random graph on n vertices of a graph isomorphic to a given graph of order Cn and average degree at least three are investigated. In particular it is proved that the random graph G(n, p) on n vertices with edge probability contains a square grid on En/2 vertices. © 1994 John Wiley & Sons, Inc.     

Lattice bandwidth of random graphs

The bandwidth of a random graph has been well studied. A natural generalization of bandwidth involves replacing the path as host graph by a multi-dimensional lattice. In this paper we investigate the corresponding behavior for random graphs.     

The product representation of a locally dependent random graph

Directed graphs with random black and white colourings of edges such that the colours of edges from different vertices are mutually independent are called locally dependent random graphs. Two random graphs are equivalent if they cannot be distinguished from percolation processes on them if only the vertices are seen. A necessary and sufficient condition is given for when a locally dependent random graph is equivalent to a product random graph; that is one in which the edges can be grouped in such a way that within each group the colours of the edges are equivalent and between groups they are independent. As an application the random graph corresponding to a spatial general epidemic model is considered.     

Geometry of the vacant set left by random walk on random graphs,Wright's constants,and critical random graphs with prescribed degrees

We provide an explicit algorithm for sampling a uniform simple connected random graph with a given degree sequence. By products of this central result include: (1) continuum scaling limits of uniform simple connected graphs with given degree sequence and asymptotics for the number of simple connected graphs with given degree sequence under some regularity conditions, and (2) scaling limits for the metric space structure of the maximal components in the critical regime of both the configuration model and the uniform simple random graph model with prescribed degree sequence under finite third moment assumption on the degree sequence. As a substantive application we answer a question raised by ?erný and Teixeira study by obtaining the metric space scaling limit of maximal components in the vacant set left by random walks on random regular graphs.     

Topological properties of the one dimensional exponential random geometric graph

In this article we study the one‐dimensional random geometric (random interval) graph when the location of the nodes are independent and exponentially distributed. We derive exact results and limit theorems for the connectivity and other properties associated with this random graph. We show that the asymptotic properties of a graph with a truncated exponential distribution can be obtained using the exponential random geometric graph. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Coalescent random walks on graphs

Inspired by coalescent theory in biology, we introduce a stochastic model called “multi-person simple random walks” or “coalescent random walks” on a graph G. There are any finite number of persons distributed randomly at the vertices of G. In each step of this discrete time Markov chain, we randomly pick up a person and move it to a random adjacent vertex. To study this model, we introduce the tensor powers of graphs and the tensor products of Markov processes. Then the coalescent random walk on graph G becomes the simple random walk on a tensor power of G. We give estimates of expected number of steps for these persons to meet all together at a specific vertex. For regular graphs, our estimates are exact.     

Constructing a perfect matching is in random NC

We show that the problem of constructing a perfect matching in a graph is in the complexity class Random NC; i.e., the problem is solvable in polylog time by a randomized parallel algorithm using a polynomial-bounded number of processors. We also show that several related problems lie in Random NC. These include:

1. Constructing a perfect matching of maximum weight in a graph whose edge weights are given in unary notation;
2. Constructing a maximum-cardinality matching;
3. Constructing a matching covering a set of vertices of maximum weight in a graph whose vertex weights are given in binary;
4. Constructing a maximums-t flow in a directed graph whose edge weights are given in unary.

     

Counting trees with random walks

We give a simple proof of Tutte’s matrix-tree theorem, a well-known result providing a closed-form expression for the number of rooted spanning trees in a directed graph. Our proof stems from placing a random walk on a directed graph and then applying the Markov chain tree theorem to count trees. The connection between the two theorems is not new, but it appears that only one direction of the formal equivalence between them is readily available in the literature. The proof we now provide establishes the other direction. More generally, our approach is another example showing that random walks can serve as a powerful glue between graph theory and Markov chain theory, allowing formal statements from one side to be carried over to the other.     

A strong law of large numbers for random biased connected graphs

We consider a class of random connected graphs with random vertices and random edges in which the randomness of the vertices is determined by a continuous probability distribution and the randomness of the edges is determined by a connection function. We derive a strong law of large numbers on the total lengths of all random edges for a random biased connected graph that is a generalization of a directed k-nearest-neighbor graph.     

Further results on random cubic planar graphs

We provide precise asymptotic estimates for the number of several classes of labeled cubic planar graphs, and we analyze properties of such random graphs under the uniform distribution. This model was first analyzed by Bodirsky and coworkers. We revisit their work and obtain new results on the enumeration of cubic planar graphs and on random cubic planar graphs. In particular, we determine the exact probability of a random cubic planar graph being connected, and we show that the distribution of the number of triangles in random cubic planar graphs is asymptotically normal with linear expectation and variance. To the best of our knowledge, this is the first time one is able to determine the asymptotic distribution for the number of copies of a fixed graph containing a cycle in classes of random planar graphs arising from planar maps.