Random Graphs Publications

Topics

Dimensions of unimodular random discrete spaces

This work by F.Baccelli, M.-O. Haji-Mirsadeghi, and A. Khezeli, is focused on large scale properties of infinite graphs and discrete subsets of the Euclidean space. It presents two new notions of dimension, namely the unimodular Minkowski and Hausdorff dimensions, which are inspired by the classical Minkowski and Hausdorff dimensions. These dimensions are defined for unimodular discrete spaces, which are defined in this work as a class of random discrete metric spaces with a distinguished point called the origin. These spaces provide a common generalization to stationary point processes under their Palm version and unimodular random rooted graphs.
The main novelty is the use of unimodularity in the definitions where it suggests replacing the infinite sums pertaining to coverings by large balls by the expectation of certain random variables at the origin. In addition, the main manifestation of unimodularity, that is the mass transport principle, is the key element in the proofs and dimension evaluations.
These dimensions are connected to the growth rate of balls. In particular, versions of the mass distribution principle, Billingsley’s lemma, and Frostman’s lemma are established for unimodular discrete spaces.
The dimensions in question are explicitly evaluated or conjectured for a comprehensive set of examples pertaining to the theory of point processes, unimodular random graphs, and self-similarity.

On the Dimension of Unimodular Discrete Spaces, Part I: Definitions and Basic Properties
On the Dimension of Unimodular Discrete Spaces, Part II: Relations with Growth Rate

Publications

2017_1000869 2016-08-21_1000762

Dynamics on Unimodular Random Graphs

Fran├žois Baccelli, Mir-Omid Haji-Mirsadeghi, Ali Khezeli https://arxiv.org/abs/1608.05940
Download PDF
2016-04-27_1000640

A symmetry breaking transition in the edge/triangle network model

Charles Radin, Kui Ren and Lorenzo Sadun Arxiv 2016
Download PDF
2016-01-14_1000623

Point-Shift Foliation of a Point Process

Francois Baccelli and Mir-Omid Haji-Mirsadeghi ArXiv 2016
Download PDF
2015-09-18_1000522

Bipodal structure in oversaturated random graphs

R. Kenyon, C. Radin, K. Ren and L. Sadun ArXiv 2015
Download PDF
2015-06-16_1000329

Consistency thresholds for the planted bisection model

Elchanan Mossel, Joe Neeman and Allan Sly To appear in Symposium on the Theory of Computer Science 2015
Download PDF
2015-03-01_1000218

Singularities in the Entropy of Asymptotically Large Simple Graphs

Charles Radin and Lorenzo Sadun J. Stat. Phys. 158 (2015) 853-865
Download PDF
2014-06-18_1000333

Belief propagation, robust reconstruction, and optimal recovery of block models

Elchanan Mossel, Joe Neeman and Allan Sly Conference on Learning Theory 2014
Download PDF
2014-04-13_1000212

The Asymptotics of Large Constrained Graphs

Charles Radin, Kui Ren and Lorenzo Sadun J. Phys. A: Math. Theor. 47 (2014) 175001
Download PDF
2014-04-10_1000209

Multipodal Structure and Phase Transitions in Large Constrained Graphs

Richard Kenyon, Charles Radin, Kui Ren and Lorenzo Sadun ArXiv 2014
Download PDF
2000-01-01_1000992

Community Detection on Euclidean Random Graphs

Abishek Sankararaman and Fran├žois Baccelli ArXiv 2017
Download PDF