Random Graphs


Order parameters of dense phases

Dense phases of emergent systems, such as constrained complex networks,
exhibit distinct characteristics, the most studied being broken symmetry.
However for practical purposes “rigidity”, the resistance to change, is
also of wide interest. There are difficulties analyzing rigidity since
when perturbed a system can easily move out of its phase. A new approach to
overcome this contradiction has been initiated by David Aristoff and
Charles Radin: see the discussion in Quanta Magazine. Another characteristic of dense phases are their nonspherical `Wulff’ shapes, polyhedral for ordinary crystals. This is examined in this expository paper by Charles Radin. In a different direction, the process of
nucleation is a dynamical signature of the creation of a dense phase, which can appear even in systems far removed from ordinary atomic materials, as shown in this paper by Frank Rietz, Charles Radin, Harry Swinney and Matthias Schroeter. All the above characteristics make essential use of finite systems, a nonstandard approach to understanding emergent phases.

Phases and phase transitions in complex networks

In the phenomenon of emergence, a system of many interacting objects
exhibits the collective behavior of one or more “phases”, which are
only detectable or even meaningful for the system as a whole. This is
an organizing principle widely used in biology, physics and indeed all
the sciences: crystals, hurricanes, animal flocking etc. One wants to
understand the spontaneous appearance of phases in systems of large
size, in particular to determine a mechanism of some generality. A
convenient framework for such an analysis is large networks with
constraints. Such an analysis has been undertaken by the group of
Richard Kenyon, Charles Radin, Kui Ren and Lorenzo Sadun, on entropy singularities, the edge/triangle system I, the edge/triangle system II, multipodal structure,
order-disorder transitions and oversaturated networks. There is also a related asymptotic analysis of large permutations undertaken by the group of Richard Kenyon, Daniel Kral, Charles Radin and Peter Winkler: permutations with fixed pattern densities, and a review of phases in general combinatorial systems.

Point maps on point processes

A compatible point-shift f maps, in a translation invariant way, each point of a stationary point process N to some point of N. It is fully determined by its associated point-map, g, which gives the image of the origin by f. The initial question studied by Mir-Omid Haji-Mirsadeghi and François Baccelli is whether there exist probability measures which are left invariant by the translation of -g. The point map probabilities of N are defined from the action of the semigroup of point-map translations on the space of Palm probabilities, and more precisely from the compactification of the orbits of this semigroup action. If the point-map probability is uniquely defined, and if it satisfies certain continuity properties, it then provides a solution to the initial question. Point-map probabilities are shown to be a strict generalization of Palm probabilities: when the considered point-shift f is bijective, the point-map probability of N boils down to the Palm probability of N. When it is not bijective, there exist cases where the point-map probability of N is absolutely continuous with respect to its Palm probability, but there also exist cases where it is singular with respect to the latter.

Each such point-shift defines a random graph on the points of the point process. The connected components of this graph can be split into a collection of foils, which are the analogue of the stable manifold of the point-shift dynamics.
The same authors give a general classification of point-shifts in terms of the cardinality of the foils of these connected components. There are three types: F/F, I/F and I/I as shown in the paper Point-Shift Foliation of a Point Process.

Using the framework of Günter Last, James Murphy has extended the cardinality classification to the case of point processes on unimodular groups. J. Murphy has studied point-shifts of point processes on topological groups at length.

Vertex Shifts on Random Graphs


Ali Khezeli, Mir-Omid Haji-Mirsadeghi and François Baccelli studied dynamics on the vertices of a random graph in the paper Dynamics on Unimodular Graphs. The first result of the paper is a classification of vertex-shifts on unimodular random networks. Each such vertex-shift partitions the vertices into a collection of connected components and foils, as in the case of point-shifts on point processes.
The classification is based on the cardinality of the connected components and foils. Up to an event of zero probability, there are three types of foliations in a connected component: F/F (with finitely many finite foils), I/F (infinitely many finite foils), and I/I (infinitely many infinite foils).
An infinite connected component of the graph of a vertex-shift on a random network forms an infinite directed tree with one selected end which is referred to as an Eternal Family Tree. An Eternal Family Tree contains a subtree which is a stochastic generalization of a branching process. In a unimodular Eternal Family Tree, the subtree in question is a generalization of a critical branching process. In a $\sigma$-invariant Eternal Family Tree, the subtree is a generalizisation of a non-necessarily critical branching process. The latter trees allow one to analyze dynamics on networks which are not necessarily unimodular.


James Murphy

Read More »

Ali Khezeli

Department of Mathematics, Sharif University of Technology
Read More »

Lorenzo Sadun

Department of Mathematics, UT Austin
Read More »

Rachel Ward

Department of Mathematics, UT Austin
Read More »

Charles Radin

Department of Mathematics, UT Austin
512 471 0174
Read More »

Sujay Sanghavi

Department of Electrical and Computer Engineering, UT Austin
512 475 9798
Read More »

Sanjay Shakkottai

Department of Electrical and Computer Engineering, UT Austin
512 471 5376
Read More »

Joe Neeman

Department of Electrical and Computer Engineering and Department of Mathematics, UT Austin
Read More »

Mir Omid Haji Mirsadeghi 2013-2015

Department of Mathematics, Sharif University of Technology. Visiting Scholar, Department of Mathematics, UT Austin
Read More »

Ngoc Mai Tran

Department of Mathematics, UT Austin
Read More »

François Baccelli

Department of Mathematics and Deparment of Electrical and Computer Engineering, UT Austin
512 471 17 54
Read More »


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

A symmetry breaking transition in the edge/triangle network model

Charles Radin, Kui Ren and Lorenzo Sadun Arxiv 2016
Download PDF

Point-Shift Foliation of a Point Process

Francois Baccelli and Mir-Omid Haji-Mirsadeghi ArXiv 2016
Download PDF

Bipodal structure in oversaturated random graphs

R. Kenyon, C. Radin, K. Ren and L. Sadun ArXiv 2015
Download PDF

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

Singularities in the Entropy of Asymptotically Large Simple Graphs

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

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

Elchanan Mossel, Joe Neeman and Allan Sly Conference on Learning Theory 2014
Download PDF

The Asymptotics of Large Constrained Graphs

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

Multipodal Structure and Phase Transitions in Large Constrained Graphs

Richard Kenyon, Charles Radin, Kui Ren and Lorenzo Sadun ArXiv 2014
Download PDF