### Topics

#### 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.

#### Rigidity 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.

#### 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, 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. Murphy has studied point-shifts of point processes on topological groups at length.