Random cutting and records in deterministic and random trees

We study random cutting down of a rooted tree and show that the number of cuts is equal (in distribution) to the number of records in the tree when edges (or vertices) are assigned random labels. Limit theorems are given for this number, in particular when the tree is a random conditioned Galton–Watson tree. We consider both the distribution when both the tree and the cutting (or labels) are random and the case when we condition on the tree. The proofs are based on Aldous' theory of the continuum random tree. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Patterns in random permutations avoiding the pattern 321

We consider a random permutation drawn from the set of 321 ‐avoiding permutations of length n and show that the number of occurrences of another pattern σ has a limit distribution, after scaling by n^{m + ?} where m is the length of σ and ? is the number of blocks in it. The limit is not normal, and can be expressed as a functional of a Brownian excursion.     

Mathematical Consistency and Long-Term Behaviour of a Dynamical System with a Self-Organising Vector Field

Journal of Dynamics and Differential Equations - A dynamical system with a plastic self-organising velocity vector field was introduced in Janson and Marsden (Sci Rep 7:17007, 2017) as a...     

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.     

Long and short paths in uniform random recursive dags

In a uniform random recursive k-directed acyclic graph, there is a root, 0, and each node in turn, from 1 to n, chooses k uniform random parents from among the nodes of smaller index. If S _n is the shortest path distance from node n to the root, then we determine the constant σ such that S _n /log n→σ in probability as n→∞. We also show that max _1≤i≤n S _i /log n→σ in probability.     

Duality in inhomogeneous random graphs,and the cut metric

The classical random graph model G(n, c/n) satisfies a “duality principle”, in that removing the giant component from a supercritical instance of the model leaves (essentially) a subcritical instance. Such principles have been proved for various models; they are useful since it is often much easier to study the subcritical model than to directly study small components in the supercritical model. Here we prove a duality principle of this type for a very general class of random graphs with independence between the edges, defined by convergence of the matrices of edge probabilities in the cut metric. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 399–411, 2011     

Correlations for paths in random orientations of G(n,p) and G(n,m)

We study random graphs, both G( n,p) and G( n,m), with random orientations on the edges. For three fixed distinct vertices s,a,b we study the correlation, in the combine probability space, of the events $\{a\to s\}$ and $\{s\to b\}$ . For G(n,p), we prove that there is a $pc = 1/2$ such that for a fixed $p < pc$ the correlation is negative for large enough n and for $p > pc$ the correlation is positive for large enough n. We conjecture that for a fixed $n \ge 27$ the correlation changes sign three times for three critical values of p. For G(n,m) it is similarly proved that, with $p=m/({{n}\atop {2}})$ , there is a critical pc that is the solution to a certain equation and approximately equal to 0.7993. A lemma, which computes the probability of non existence of any $\ell$ directed edges in G(n,m), is thought to be of independent interest. We present exact recursions to compute \input amssym $\Bbb{P}(a\to s)$ and \input amssym $\Bbb{P}(a\to s, s\to b)$ . We also briefly discuss the corresponding question in the quenched version of the problem. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Generalized Stirling permutations, families of increasing trees and urn models

Bóna (2007) [6] studied the distribution of ascents, plateaux and descents in the class of Stirling permutations, introduced by Gessel and Stanley (1978) [13]. Recently, Janson (2008) [17] showed the connection between Stirling permutations and plane recursive trees and proved a joint normal law for the parameters considered by Bóna. Here we will consider generalized Stirling permutations extending the earlier results of Bóna (2007) [6] and Janson (2008) [17], and relate them with certain families of generalized plane recursive trees, and also (k+1)-ary increasing trees. We also give two different bijections between certain families of increasing trees, which both give as a special case a bijection between ternary increasing trees and plane recursive trees. In order to describe the (asymptotic) behaviour of the parameters of interests, we study three (generalized) Pólya urn models using various methods.     

Long Term Behaviour of a Reversible System of Interacting Random Walks

This paper studies the long-term behaviour of a system of interacting random walks labelled by vertices of a finite graph. We show that the system undergoes phase transitions, with different behaviour in various regions, depending on model parameters and properties of the underlying graph. We provide the complete classification of the long-term behaviour of the corresponding continuous time Markov chain, identifying whether it is null recurrent, positive recurrent, or transient. The proofs are partially based on the reversibility of the model, which allows us to use the method of electric networks. We also provide some alternative proofs (based on the Lyapunov function method and the renewal theory), which are of interest in their own right, since they do not require reversibility and can be applied to more general situations.