Random graphs

 

Gromov-Hausdorff Metric

In this paper, a general approach is presented for generalizing the Gromov-Hausdorff metric to consider metric spaces equipped with some additional structure. A special case is the Gromov-Hausdorff-Prokhorov metric which considers measured metric spaces. This abstract framework also unifies several existing generalizations which consider metric spaces equipped with a measure, a point, a closed subset, a curve or a tuple of such structures. It can also be useful for studying new examples of additional structures. The framework is provided both for compact metric spaces and for boundedly-compact pointed metric spaces. In addition, completeness and separability of the metric is proved under some conditions. This enables one to study random metric spaces equipped with additional structures, which is the main motivation of this work.

• A. Khezeli. ‘A Unified Framework for Generalizing the Gromov-Hausdorff Metric’. Probability Surveys, 20, (2023). Hal preprint

Record Graph of a Sequence with Stationary Increments

Consider a stationary sequence X=(X_n) of integer-valued random variables with mean m∈[−∞,∞]. Let S=(S_n) be the stochastic process with increments X and such that S0=0. For each time i, draw an edge from (i,S_i) to (j,S_j), where j>i is the smallest integer such that S_j≥S_i, if such a j exists. This defines the record graph of X. It is shown that if X is ergodic, then its record graph exhibits the following phase transitions when m ranges from −∞ to ∞. For m<0, the record graph has infinitely many connected components which are all finite trees. At m=0, it is either a one-ended tree or a two-ended tree. For m>0, it is a two-ended tree. The distribution of the component of 0 in the record graph is analyzed when X is an i.i.d. sequence of random variables whose common distribution is supported on {−1,0,1,…}, making S a skip-free to the left random walk. For this random walk, if m<0, then the component of 0 is a unimodular typically re-rooted Galton-Watson Tree. If m=0, then the record graph rooted at 0 is a one-ended unimodular random tree, specifically, it is a unimodular Eternal Galton-Watson Tree. If m>0, then the record graph rooted at 0 is a unimodularised bi-variate Eternal Kesten Tree. A unimodular random directed tree is said to be record representable if it is the component of 0 in the record graph of some stationary sequence. It is shown that every infinite unimodular ordered directed tree with a unique succession line is record representable. In particular, every one-ended unimodular ordered directed tree has a unique succession line and is thus record representable.

• F. Baccelli and B. Roy-Choudhury. ‘Genealogies of records of stochastic processes with stationary increments as unimodular trees.’ Under revision for Annales de l’IHP. ArXiv preprint https://arxiv.org/abs/2403.05657

Unimodular Random Measured Metric Spaces

Unimodular random measured metric spaces are a common generalization of various other notions. This includes the discrete cases like unimodular graphs and stationary point processes, as well as the non-discrete cases like stationary random measures and the continuum metric spaces arising as scaling limits of graphs. Several general results are proved on such spaces, e.g., on weak limits, re-rooting invariance, random walks, ergodic decomposition, amenability and balancing transport kernels. In addition, one can generalize the Palm theory of point processes and random measures to such unimodular spaces.

• A. Khezeli. ‘Unimodular Random Measured Metric Spaces and Palm Theory on Them.’ arXiv preprint arXiv:2304.02863. 2023. https://doi.org/10.48550/arXiv.2304.02863

Balancing Allocations

In this article, we show that every stationary random measure on ℝ^d that is essentially free (i.e., has no symmetries a.s.) admits a point process as a factor (i.e., as a measurable and translation-equivariant function of the measure). As a result, we improve the results of Last and Thorisson (2022) on the existence of a factor balancing allocation between ergodic pairs of stationary random measures Φ and Ψ with equal intensities. In particular, we prove that such an allocation exists if Φ is diffuse and either (Φ,Ψ) is essentially free or Φ assigns zero measure to every (d−1)-dimensional affine hyperplane. The main result is deduced from an existing result in descriptive set theory, that is, the existence of lacunary sections. We also weaken the assumption of being essentially free to the case where a discrete group of symmetries is allowed.

• A. Khezeli and S. Mellick. ‘On the existence of balancing allocations and factor point processes’, 2023 ArXiv paper. Accepted for publication in ALEA (Latin American Journal of Probability and Mathematical Statistics).

Doeblin graphs and coupling from the past for the null recurrent Markov chain

The Doeblin Graph of a countable state space Markov chain describes the joint pathwise evolutions of the Markov dynamics starting from all possible initial conditions, with two paths coalescing when they reach the same point of the state space at the same time. Its Bridge Doeblin subgraph only contains the paths starting from a tagged point of the state space at all possible times. In the irreducible, aperiodic, and positive recurrent case, the following results are known: the Bridge Doeblin Graph is an infinite tree that is unimodularizable. Moreover, it contains a single bi-infinite path, which allows one to build a perfect sample of the stationary state of the Markov chain. The present paper is focused on the null recurrent case. It is shown that when assuming irreducibility and aperiodicity again, the Bridge Doeblin Graph is either an infinite tree or a forest made of a countable collection of infinite trees. In the first case, the infinite tree in question has a single end, is not unimodularizable in general, but is always locally unimodular. These key properties are used to study the stationary regime of several measure-valued random dynamics on this Bridge Doeblin Tree. The most important ones are the taboo random dynamics, which admits as steady state a random measure with mean measure equal to the invariant measure of the Markov chain, and the potential random dynamics which is a random extension of the classical potential measure, with a mean measure equal to infinity at every point of the state space.

• F. Baccelli, M.-O. Haji-Mirsadeghi, and S. Khaniha, ‘Coupling from the Past for the Null Recurrent Markov Chain’, (April 2022). https://arxiv.org/abs/2203.13585

. Published in the following paper of the Annals of Applied Probability in 2024.

Circle Packing

In this work, a one-ended unimodular random planar triangulation is constructed that has no invariant circle packing; i.e., a circle packing such that its distribution is invariant under translations. This gives a negative answer to a problem posed by I. Benjamini and A. Timar (2019). A natural weaker problem is the existence, for unimodular graphs, of point-stationary circle packings, which are random circle packings that satisfy a certain mass transport principle. It is shown that this problem is related to the large scale properties of the circle packings and the answer is again negative. Two examples are provided with two different approaches: Using indistinguishability and approximation by finite graphs.

• A. Khezeli. ‘Counter examples to invariant circle packing’. Annales de l’Institut Henri Poincaré (B), Probabilités et Statistiques, volume 58 (November 2022). ArXiv preprint

Unimodular Hausdorff and Minkowski Dimensions

This work introduces two new notions of dimension, namely the unimodular Minkowski and Hausdorff dimensions, which are inspired from the classical analogous notions.

These dimensions are defined for unimodular discrete spaces, introduced in this work, which provide a common generalization to stationary point processes under their Palm version and unimodular random rooted graphs. The use of unimodularity in the definitions of dimension is novel. Also, a toolbox of results is presented for the analysis of these dimensions. In particular, analogues of Billingsley’s lemma and Frostman’s lemma are presented. These lemmas are instrumental in deriving upper bounds on dimensions, whereas lower bounds are obtained from specific coverings. The notions of unimodular Hausdorff measure and unimodular dimension function are also introduced. This toolbox is used to analyze the dimensions of a set of examples pertaining to point processes, branching processes, random graphs, random walks, and self-similar discrete random spaces.

The companion paper  is focused on the connections between these notions and the polynomial growth rate of the underlying space. It is shown that bounding the dimension is closely related to finding suitable equivariant weight functions (i.e., measures) on the underlying discrete space. The main results are unimodular versions of the mass distribution principle, Billingsley’s lemma and Frostman’s lemma, which allow one to derive upper bounds on the unimodular Hausdorff dimension from the growth rate of suitable equivariant weight functions. These results allow one to compute or bound both types of unimodular dimensions in a large set of examples in the theory of point processes, unimodular random graphs, and self-similarity. Further results of independent interest are also presented, like a version of the max-flow min-cut theorem for unimodular one-ended trees and a weak form of pointwise ergodic theorems for all unimodular discrete spaces.

• F. Baccelli., M.-O. Haji-Mirsadeghi, and A. Khezeli, “Unimodular Hausdorff and Minkowski Dimensions”. Electronic Journal of Probability, 26, 1-64, 2021. EJP paper

Random Binary Trees

It is known that the size of the largest common subtree (i.e., the maximum agreement subtree) of two independent random binary trees with n given labeled leaves is of order between n^0.366 and n^1/2. A. Khezeli improved the lower bound to order n^0.4464 by constructing a common subtree recursively and by proving a lower bound for its asymptotic growth. The construction is a modification of an algorithm proposed by D. Aldous by splitting the tree at the centroid and by proceeding recursively.

• A. Khezeli, ‘An Improved Lower Bound on the Largest Common Subtree of Random Leaf-Labeled Binary Trees’, HAL (2022). URL : https://hal.inria.fr/hal-03924930. Published in the SIAM Journal on Discrete Mathematics, 38, pp. 2530-2541, (2024)

Matrix reconstruction and directed random graphs

This work of Charles Bordenave (Aix-Marseille University), Simon Coste and Raj Rao Nadakuditi (University of Michigan at Ann Arbor) introduces a new and promising spectral method for statistical reconstruction tasks such as matrix completion, based on the analysis of the asymptotic behaviour of the eigenvalues of random graphs in the difficult, very sparse regime.

The underlying random graph is the simplest possible example of a directed random graph G: on n vertices, each of the n^2 possible bonds is present with probability d/n where d is a fixed parameter, accounting for the mean degree of each vertex. This graph converges in a weak sense towards a possibly infinite, directed random graph : the directed Poisson-Galton-Watson tree. We are interested in the eigenvalues of the adjacency matrix A of such graph, with possible weights arising from Hermitian hidden matrix P with low rank. The eigenvalues of A do not bring a rich information on the model, since they are mostly polluted by the highest degrees of G. However, if we randomly split A into A_1 + A_2, it turns out that the eigenvalues of the (non-Hermitian) matrix A_1*A_2 capture a substantial amount of information related to the SVD of P. More precisely, we show the existence of an asymptotic threshold t, which depends only on P and d, such that every eigenvalue of A_1*A_2 greater than t is asymptotically equal to the eigenvalues of P*P, and the associated eigenvectors are aligned as well. This allowed us to perform statistical reconstruction with weak recovery even in the regime where d is really smaller than log n, which was the information-theoretic limit for exact reconstruction well known in the literature.

Key elements in this analysis are some fine concentration analysis for functionals of random graphs: some observables defined on the graph G can efficiently be coupled with their counterparts on the limiting GW tree, and can be formulated as Kesten-Stigum martingales. While computing the expectation or variance of such observables on G is not doable, the corresponding computations on the limiting GW tree are exactly solvable.

Finding similar procedures for higher-order random graphs (eg, random tensors / tensor completion) is a promising future direction ; the extension of our results for inhomogeneous random graphs was recently done in a work by Massoulié and Stephan.

• C. Bordenave, S. Coste and R. R. Nadakuditi. ‘Detection thresholds in very sparse matrix completion’. Found. Comput. Math., 23(5):1619–1743 (2023). Posted on https://arxiv.org/abs/2005.06062