We consider the classic Moran process modeling the spread of genetic mutations, as extended to structured populations by (Nature, 2005). In this process, individuals are the vertices of a connected graph G. Initially, there is a single mutant vertex, chosen uniformly at random. In each step, a random vertex is selected for reproduction with a probability proportional to its fitness: mutants have fitness r > 1, while non-mutants have fitness 1. The vertex chosen to reproduce places a copy of itself to a uniformly random neighbor in G, replacing the individual that was there. The process ends when the mutation either reaches fixation (i.e., all vertices are mutants), or gets extinct. The principal quantity of interest is the probability with which each of the two outcomes occurs. A problem that has received significant attention recently concerns the existence of families of graphs, called strong amplifiers of selection, for which the fixation probability tends to 1 as the order n of the graph increases, and the existence of strong suppressors of selection, for which this probability tends to 0. For the case of directed graphs, it is known that both strong amplifiers and suppressors exist. For the case of undirected graphs, however, the problem has remained open, and the general belief has been that neither strong amplifiers nor suppressors exist. In this paper we disprove this belief, by providing the first examples of such graphs. The strong amplifier we present has fixation probability 1 − ˜ O(n^ −1 3), and the strong suppressor has fixation probability ˜O(n^−1 4). Both graph constructions are surprisingly simple. We also prove a general upper bound of 1 − ˜Ω(n^−1 3) on the fixation probability of any undirected graph. Hence, our strong amplifier is existentially optimal.
Several birth-and-death processes on graphs have been studied, beside the Moran process, which vary in the order in which the birth and death events occur in a step, and on whether the selection bias introduced by fitness is applied in the choice of the vertex that reproduces or the one that dies. The Voter model @cite_26 is a well-known such process. It has been observe that small differences in these processes have significant impact on the fixation probability @cite_13 @cite_4 @cite_11 . In particular, for dynamics where, unlike in Moran process, the vertex to die is chosen first, it is known that simple strong suppressors exits, such as the star @math with fixation probability @math , while there are no strong amplifiers @cite_19 . Although not elaborated in the current paper, our results carry over to the process where the vertex to reproduce is chosen uniformly at random, and its offspring replaces a neighbor chosen with probability inversely proportional to its fitness. This corresponds to a setting where advantageous mutants do not reproduce more often, but they live longer.
@cite_26 @cite_4 @cite_19 @cite_13 @cite_11
2552612746 2099414239 2963708029 2205121374 2139738313 2766269359 1789332325 2964124513 1553548137 2568440864 2045494719 2367313360 2079460424 2031810620 2013558775 2898008966 2040948450 2079681761 1825819013 2046985712
We consider the classic Moran process modeling the spread of genetic mutations, as extended to structured populations by (Nature, 2005). In this process, individuals are the vertices of a connected graph G. Initially, there is a single mutant vertex, chosen uniformly at random. In each step, a random vertex is selected for reproduction with a probability proportional to its fitness: mutants have fitness r > 1, while non-mutants have fitness 1. The vertex chosen to reproduce places a copy of itself to a uniformly random neighbor in G, replacing the individual that was there. The process ends when the mutation either reaches fixation (i.e., all vertices are mutants), or gets extinct. The principal quantity of interest is the probability with which each of the two outcomes occurs. A problem that has received significant attention recently concerns the existence of families of graphs, called strong amplifiers of selection, for which the fixation probability tends to 1 as the order n of the graph increases, and the existence of strong suppressors of selection, for which this probability tends to 0. For the case of directed graphs, it is known that both strong amplifiers and suppressors exist. For the case of undirected graphs, however, the problem has remained open, and the general belief has been that neither strong amplifiers nor suppressors exist. In this paper we disprove this belief, by providing the first examples of such graphs. The strong amplifier we present has fixation probability 1 − ˜ O(n^ −1 3), and the strong suppressor has fixation probability ˜O(n^−1 4). Both graph constructions are surprisingly simple. We also prove a general upper bound of 1 − ˜Ω(n^−1 3) on the fixation probability of any undirected graph. Hence, our strong amplifier is existentially optimal. Evolutionary models on graphs, as an extension of the Moran process, have two major implementations: birth–death (BD) models (or the invasion process) and death–birth (DB) models (or voter models). The isothermal theorem states that the fixation probability of mutants in a large group of graph structures (known as isothermal graphs, which include regular graphs) coincides with that for the mixed population. This result has been proved by (2005 Nature 433, 312–316. (doi:10.1038 nature03204)) in the case of BD processes, where mutants differ from the wild-types by their birth rate (and not by their death rate). In this paper, we discuss to what extent the isothermal theorem can be formulated for DB processes, proving that it only holds for mutants that differ from the wild-type by their death rate (and not by their birth rate). For more general BD and DB processes with arbitrary birth and death rates of mutants, we show that the fixation probabilities of mutants are different from those obtained in the mass-action populations. We focus on spatial lattices and show that the difference between BD and DB processes on one- and two-dimensional lattices is non-small even for large population sizes. We support these results with a generating function approach that can be generalized to arbitrary graph structures. Finally, we discuss several biological applications of the results. The Moran process, as studied by Lieberman, Hauert, and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlying graph where individuals correspond to vertices. Initially, one vertex (chosen uniformly at random) possesses a mutation, with fitness r > 1. All other individuals have fitness 1. During each step of the algorithm, an individual is chosen with probability proportional to its fitness, and its state (mutant or nonmutant) is passed on to an out-neighbour which is chosen uniformly at random. If the underlying graph is strongly connected, then the algorithm will eventually reach fixation, in which all individuals are mutants, or extinction, in which no individuals are mutants. An infinite family of directed graphs is said to be strongly amplifying if, for every r > 1, the extinction probability tends to 0 as the number of vertices increases. A formal definition is provided in the article. Strong amplification is a rather surprising property—it means that in such graphs, the fixation probability of a uniformly placed initial mutant tends to 1 even though the initial mutant only has a fixed selective advantage of r > 1 (independently of n). The name “strongly amplifying” comes from the fact that this selective advantage is “amplified.” Strong amplifiers have received quite a bit of attention, and proposed two potentially strongly amplifying families—superstars and metafunnels. Heuristic arguments have been published, arguing that there are infinite families of superstars that are strongly amplifying. The same has been claimed for metafunnels. In this article, we give the first rigorous proof that there is an infinite family of directed graphs that is strongly amplifying. We call the graphs in the family “megastars.” When the algorithm is run on an n-vertex graph in this family, starting with a uniformly chosen mutant, the extinction probability is roughly n − 1 2 (up to logarithmic factors). We prove that all infinite families of superstars and metafunnels have larger extinction probabilities (as a function of n). Finally, we prove that our analysis of megastars is fairly tight—there is no infinite family of megastars such that the Moran algorithm gives a smaller extinction probability (up to logarithmic factors). Also, we provide a counterexample which clarifies the literature concerning the isothermal theorem of This work extends what is known so far for a basic model of evolutionary antagonism in undirected networks (graphs). More specifically, this work studies the generalized Moran process, as introduced by Lieberman, Hauert, and Nowak [Nature, 433:312-316, 2005], where the individuals of a population reside on the vertices of an undirected connected graph. The initial population has a single mutant of a fitness value r (typically r>1), residing at some vertex v of the graph, while every other vertex is initially occupied by an individual of fitness 1. At every step of this process, an individual (i.e. vertex) is randomly chosen for reproduction with probability proportional to its fitness, and then it places a copy of itself on a random neighbor, thus replacing the individual that was residing there. The main quantity of interest is the fixation probability, i.e. the probability that eventually the whole graph is occupied by descendants of the mutant. In this work we concentrate on the fixation probability when the mutant is initially on a specific vertex v, thus refining the older notion of which studied the fixation probability when the initial mutant is placed at a random vertex. We then aim at finding graphs that have many "strong starts" (or many "weak starts") for the mutant. Thus we introduce a parameterized notion of selective amplifiers (resp. selective suppressors) of evolution. We prove the existence of strong selective amplifiers (i.e. for h(n)=Θ(n) vertices v the fixation probability of v is at least @math for a function c(r) that depends only on r), and the existence of quite strong selective suppressors. Regarding the traditional notion of fixation probability from a random start, we provide strong upper and lower bounds: first we demonstrate the non-existence of "strong universal" amplifiers, and second we prove the Thermal Theorem which states that for any undirected graph, when the mutant starts at vertex v, the fixation probability at least @math . This theorem (which extends the "Isothermal Theorem" of for regular graphs) implies an almost tight lower bound for the usual notion of fixation probability. Our proof techniques are original and are based on new domination arguments which may be of general interest in Markov Processes that are of the general birth-death type. The problem of finding birth–death fixation probabilities for configurations of normal and mutants on an N -vertex graph is formulated in terms of a Markov process on the 2 N -dimensional state space of possible configurations. Upper and lower bounds on the fixation probability after any given number of iterations of the birth–death process are derived in terms of the transition matrix of this process. Consideration is then specialized to a family of graphs called circular flows, and we present a summation formula for the complete bipartite graph, giving the fixation probability for an arbitrary configuration of mutants in terms of a weighted sum of the single-vertex fixation probabilities. This also yields a closed-form solution for the fixation probability of bipartite graphs. Three entropy measures are introduced, providing information about graph structure. Finally, a number of examples are presented, illustrating cases of graphs that enhance or suppress fixation probability for fitness r >1 as well as graphs that enhance fixation probability for only a limited range of fitness. Results are compared with recent results reported in the literature, where a positive correlation is observed between vertex degree variance and fixation probability for undirected graphs. We show a similar correlation for directed graphs, with correlation not directly to fixation probability but to the difference between fixation probability for a given graph and a complete graph. The Moran process, as studied by [10], is a stochastic process modeling the spread of genetic mutations in populations. In this process, agents of a two-type population (i.e. mutants and residents) are associated with the vertices of a graph. Initially, only one vertex chosen uniformly at random (u.a.r.) is a mutant, with fitness (r > 0 ), while all other individuals are residents, with fitness 1. In every step, an individual is chosen with probability proportional to its fitness, and its state (mutant or resident) is passed on to a neighbor which is chosen u.a.r. In this paper, we introduce and study for the first time a generalization of the model of [10] by assuming that different types of individuals perceive the population through different graphs defined on the same vertex set, namely (G_R = (V, E_R) ) for residents and (G_M = (V, E_M) ) for mutants. In this model, we study the fixation probability, namely the probability that eventually only mutants remain in the population, for various pairs of graphs. The Moran process models the spread of mutations in populations on graphs. We investigate the absorption time of the process, which is the time taken for a mutation introduced at a randomly chosen vertex to either spread to the whole population, or to become extinct. It is known that the expected absorption time for an advantageous mutation is O(n^4) on an n-vertex undirected graph, which allows the behaviour of the process on undirected graphs to be analysed using the Markov chain Monte Carlo method. We show that this does not extend to directed graphs by exhibiting an infinite family of directed graphs for which the expected absorption time is exponential in the number of vertices. However, for regular directed graphs, we show that the expected absorption time is Omega(n log n) and O(n^2). We exhibit families of graphs matching these bounds and give improved bounds for other families of graphs, based on isoperimetric number. Our results are obtained via stochastic dominations which we demonstrate by establishing a coupling in a related continuous-time model. The coupling also implies several natural domination results regarding the fixation probability of the original (discrete-time) process, resolving a conjecture of Shakarian, Roos and Johnson. © 2016 Wiley Periodicals, Inc. The Moran process models the spread of mutations in populations on graphs. We investigate the absorption time of the process, which is the time taken for a mutation introduced at a randomly chosen vertex to either spread to the whole population, or to become extinct. It is known that the expected absorption time for an advantageous mutation is O(n4) on an n-vertex undirected graph, which allows the behaviour of the process on undirected graphs to be analysed using the Markov chain Monte Carlo method. We show that this does not extend to directed graphs by exhibiting an infinite family of directed graphs for which the expected absorption time is exponential in the number of vertices. However, for regular directed graphs, we show that the expected absorption time is O(nlogn) and O(n2). We exhibit families of graphs matching these bounds and give improved bounds for other families of graphs, based on isoperimetric number. Our results are obtained via stochastic dominations which we demonstrate by establishing a coupling in a related continuous-time model. The coupling also implies several natural domination results regarding the fixation probability of the original (discrete-time) process, resolving a conjecture of Shakarian, Roos and Johnson. We analyze evolutionary dynamics on graphs, where the nodes represent individuals of a population. The links of a node describe which other individuals can be displaced by the offspring of the individual on that node. Amplifiers of selection are graphs for which the fixation probability is increased for advantageous mutants and decreased for disadvantageous mutants. A few examples of such amplifiers have been developed, but so far it is unclear how many such structures exist and how to construct them. Here, we show that almost any undirected random graph is an amplifier of selection for Birth-death updating, where an individual is selected to reproduce with probability proportional to its fitness and one of its neighbors is replaced by that offspring at random. If we instead focus on death-Birth updating, in which a random individual is removed and its neighbors compete for the empty spot, then the same ensemble of graphs consists of almost only suppressors of selection for which the fixation probability is decreased for advantageous mutants and increased for disadvantageous mutants. Thus, the impact of population structure on evolutionary dynamics is a subtle issue that will depend on seemingly minor details of the underlying evolutionary process. Evolutionary dynamics has been traditionally studied in the context of homogeneous populations, mainly described by the Moran process [P. Moran, Random processes in genetics, Proceedings of the Cambridge Philosophical Society 54 (1) (1958) 60-71]. Recently, this approach has been generalized in [E. Lieberman, C. Hauert, M.A. Nowak, Evolutionary dynamics on graphs, Nature 433 (2005) 312-316] by arranging individuals on the nodes of a network (in general, directed). In this setting, the existence of directed arcs enables the simulation of extreme phenomena, where the fixation probability of a randomly placed mutant (i.e., the probability that the offspring of the mutant eventually spread over the whole population) is arbitrarily small or large. On the other hand, undirected networks (i.e., undirected graphs) seem to have a smoother behavior, and thus it is more challenging to find suppressors amplifiers of selection, that is, graphs with smaller greater fixation probability than the complete graph (i.e., the homogeneous population). In this paper we focus on undirected graphs. We present the first class of undirected graphs which act as suppressors of selection, by achieving a fixation probability that is at most one half of that of the complete graph, as the number of vertices increases. Moreover, we provide some generic upper and lower bounds for the fixation probability of general undirected graphs. As our main contribution, we introduce the natural alternative of the model proposed in [E. Lieberman, C. Hauert, M.A. Nowak, Evolutionary dynamics on graphs, Nature 433 (2005) 312-316]. In our new evolutionary model, all individuals interact simultaneously and the result is a compromise between aggressive and non-aggressive individuals. We prove that our new model of mutual influences admits a potential function, which guarantees the convergence of the system for any graph topology and any initial fitness vector of the individuals. Furthermore, we prove fast convergence to the stable state for the case of the complete graph, as well as we provide almost tight bounds on the limit fitness of the individuals. Apart from being important on its own, this new evolutionary model appears to be useful also in the abstract modeling of control mechanisms over invading populations in networks. We demonstrate this by introducing and analyzing two alternative control approaches, for which we bound the time needed to stabilize to the ''healthy'' state of the system. An edge-Markovian process with birth-rate p and death-rate q generates sequences of graphs (G0,G1,G2,…) with the same node set [n] such that Gt is obtained from Gt−1 as follows: if e ∉ E(Gt−1) then e ∈ E(Gt) with probability p, and if e ∈ E(Gt−1) then e ∉ E(Gt) with probability q. (PODC 2008) analyzed thoroughly information dissemination in such dynamic graphs, by establishing bounds on their flooding time--flooding is the basic mechanism in which every node becoming aware of an information at step t forwards this information to all its neighbors at all forthcoming steps t∦ > t. In this paper, we establish tight bounds on the complexity of flooding for all possible birth rates and death rates, completing the previous results by Moreover, we note that despite its many advantages in term of simplicity and robustness, flooding suffers from its high bandwidth consumption. Hence we also show that flooding in dynamic graphs can be implemented in a more parsimonious manner, so that to save bandwidth, yet preserving efficiency in term of simplicity and completion time. For a positive integer k, we say that the flooding protocol is k-active if each node forwards an information only during the k time steps immediately following the step at which the node receives that information for the first time. We define the reachability threshold for the flooding protocol as the smallest integer k such that, for any source s ∈ [n], the k-active flooding protocol from s completes (i.e., reaches all nodes), and we establish tight bounds for this parameter. We show that, for a large spectrum of parameters p and q, the reachability threshold is by several orders of magnitude smaller than the flooding time. In particular, we show that it is even constant whenever the ratio p (p + q) exceeds log n n. Moreover, we also show that being active for a number of steps equal to the reachability threshold (up to a multiplicative constant) allows the flooding protocol to complete in optimal time, i.e., in asymptotically the same number of steps as when being perpetually active. These results demonstrate that flooding can be implemented in a practical and efficient manner in dynamic graphs. The main ingredient in the proofs of our results is a reduction lemma enabling to overcome the time dependencies in edge-Markovian dynamic graphs. Networks form an indispensable part of our lives. In particular, computer networks have ranked amongst the most influential networks in recent times. In such an ever-evolving and fast growing network, the primary concern is to understand and analyse different aspects of the network behaviour, such as the quality of service and efficient information propagation. It is also desirable to predict the behaviour of a large computer network if, for example, one of the computers is infected by a virus. In all of the aforementioned cases, we need protocols that are able to make local decisions and handle the dynamic changes in the network topology. Here, randomised algorithms are preferred because many deterministic algorithms often require a central control. In this thesis, we investigate three network-based randomised algorithms, threshold load balancing with weighted tasks, the pull-Moran process and the coalescing-branching random walk. Each of these algorithms has extensive applicability within networks and computational complexity within computer science. In this thesis we investigate threshold-based load balancing protocols. We introduce a generalisation of protocols in [2, 3] to weighted tasks. This thesis also analyses an evolutionary-based process called the death-birth update, defined here as the Pull-Moran process. We show that a class of strong universal amplifiers does not exist for the Pull-Moran process. We show that any class of selective amplifiers in the (standard) Moran process is a class of selective suppressors under the Pull-Moran process. We then introduce a class of selective amplifiers called Punk graphs. Finally, we improve the broadcasting time of the coalescing-branching (COBRA) walk analysed in [4], for random regular graphs. Here, we look into the COBRA approach as a randomised rumour spreading protocol. Evolutionary dynamics have been traditionally studied in the context of homogeneous or spatially extended populations1,2,3,4. Here we generalize population structure by arranging individuals on a graph. Each vertex represents an individual. The weighted edges denote reproductive rates which govern how often individuals place offspring into adjacent vertices. The homogeneous population, described by the Moran process3, is the special case of a fully connected graph with evenly weighted edges. Spatial structures are described by graphs where vertices are connected with their nearest neighbours. We also explore evolution on random and scale-free networks5,6,7. We determine the fixation probability of mutants, and characterize those graphs for which fixation behaviour is identical to that of a homogeneous population7. Furthermore, some graphs act as suppressors and others as amplifiers of selection. It is even possible to find graphs that guarantee the fixation of any advantageous mutant. We also study frequency-dependent selection and show that the outcome of evolutionary games can depend entirely on the structure of the underlying graph. Evolutionary graph theory has many fascinating applications ranging from ecology to multi-cellular organization and economics. Abstract At the heart of this article will be the study of a branching Brownian motion (BBM) with killing , where individual particles move as Brownian motions with drift − ρ , perform dyadic branching at rate β and are killed on hitting the origin. Firstly, by considering properties of the right-most particle and the extinction probability, we will provide a probabilistic proof of the classical result that the ‘one-sided’ FKPP travelling-wave equation of speed − ρ with solutions f : [ 0 , ∞ ) → [ 0 , 1 ] satisfying f ( 0 ) = 1 and f ( ∞ ) = 0 has a unique solution with a particular asymptotic when ρ 2 β , and no solutions otherwise. Our analysis is in the spirit of the standard BBM studies of [S.C. Harris, Travelling-waves for the FKPP equation via probabilistic arguments, Proc. Roy. Soc. Edinburgh Sect. A 129 (3) (1999) 503–517] and [A.E. Kyprianou, Travelling wave solutions to the K-P-P equation: alternatives to Simon Harris' probabilistic analysis, Ann. Inst. H. Poincare Probab. Statist. 40 (1) (2004) 53–72] and includes an intuitive application of a change of measure inducing a spine decomposition that, as a by product, gives the new result that the asymptotic speed of the right-most particle in the killed BBM is 2 β − ρ on the survival set. Secondly, we introduce and discuss the convergence of an additive martingale for the killed BBM, W λ , that appears of fundamental importance as well as facilitating some new results on the almost-sure exponential growth rate of the number of particles of speed λ ∈ ( 0 , 2 β − ρ ) . Finally, we prove a new result for the asymptotic behaviour of the probability of finding the right-most particle with speed λ > 2 β − ρ . This result combined with Chauvin and Rouault's [B. Chauvin, A. Rouault, KPP equation and supercritical branching Brownian motion in the subcritical speed area. Application to spatial trees, Probab. Theory Related Fields 80 (2) (1988) 299–314] arguments for standard BBM readily yields an analogous Yaglom-type conditional limit theorem for the killed BBM and reveals W λ as the limiting Radon–Nikodým derivative when conditioning the right-most particle to travel at speed λ into the distant future. We introduce stochastic time-dependency in evolving graphs: starting from an arbitrary initial edge probability distribution, at every time step, every edge changes its state (existing or not) according to a two-state Markovian process with probabilities p (edge birth-rate) and q (edge death-rate). If an edge exists at time t then, at time t+1, it dies with probability q. If instead the edge does not exist at time t, then it will come into existence at time t+1 with probability p. Such evolving graph model is a wide generalization of time-independent dynamic random graphs [6] and will be called edge-Markovian dynamic graphs. We investigate the speed of information dissemination in such dynamic graphs. We provide nearly tight bounds (which in fact turn out to be tight for a wide range of probabilities p and q) on the completion time of the flooding mechanism aiming to broadcast a piece of information from a source node to all nodes. In particular, we provide: i) A tight characterization of the class of edge-Markovian dynamic graphs where flooding time is constant and, thus, it does not asymptotically depend on the initial probability distribution. ii) A tight characterization of the class of edge-Markovian dynamic graphs where flooding time does not asymptotically depend on the edge death-rate q. The key to our investigation is an improved (and in a sense sharp) understanding of the survival time of the contact process on star graphs. Using these results, we show that for the contact process on Galton-Watson trees, when the offspring distribution (i) is subexponential the critical value for local survival @math and (ii) when it is geometric( @math ) we have @math , where the @math are much smaller than previous estimates. We also study the critical value @math for "prolonged persistence" on graphs with @math vertices generated by the configuration model. In the case of power law and stretched exponential distributions where it is known @math we give estimates on the rate of convergence. Physicists tell us that @math where @math is the maximum eigenvalue of the adjacency matrix. Our results show that this is not correct. Malecot's models of isolation by distance seem to assume random distribution in space, Poisson distribution of offspring number, and independent migration of individuals. These assumptions are inconsistent. By calculating the probability of joint occupancy of two locations at a distance x, it is shown that a haploid model embodying the latter two assumptions violates the first, forming larger and larger clumps of individuals separated by greater and greater distances. Thus the model is biologically irrelevant, even though it is possible to use it to calculate probabilities of genetic identity at different distances. The formation of these clumps is verified by computer simulation. The same phenomenon occurs in two- and three-dimensional models. In models of finite regions (a circle or a torus), the formation of clumps takes the form of the certainty of ultimate local extinction of the organism in each region. This does not occur if we hold the number of individuals on the circle or torus constant, but con... Individuals of different types, may it be genetic, cultural, or else, with different levels of fitness often compete for reproduction and survival. A fitter type generally has higher chances of disseminating their copies to other individuals. The fixation probability of a single mutant type introduced in a population of wild-type individuals quantifies how likely the mutant type spreads. How much the excess fitness of the mutant type increases its fixation probability, namely, the selection pressure, is important in assessing the impact of the introduced mutant. Previous studies mostly based on undirected and unweighted contact networks of individuals showed that the selection pressure depends on the structure of networks and the rule of reproduction. Real networks underlying ecological and social interactions are usually directed or weighted. Here we examine how the selection pressure is modulated by directionality of interactions under several update rules. Our conclusions are twofold. First, directionality discounts the selection pressure for different networks and update rules. Second, given a network, the update rules in which death events precede reproduction events significantly decrease the selection pressure than the other rules. The following question is due to Chatterjee and Varadhan 2011. Fix 0<p<r<1 and take G Gn,p, the Erdi¾?s-Renyi random graph with edge density p, conditioned to have at least as many triangles as the typical Gn,r. Is G close in cut-distance to a typical Gn,r? Via a beautiful new framework for large deviation principles in Gn,p, Chatterjee and Varadhan gave bounds on the replica symmetric phase, the region of p,r where the answer is positive. They further showed that for any small enough p there are at least two phase transitions as r varies. We settle this question by identifying the replica symmetric phase for triangles and more generally for any fixed d-regular graph. By analyzing the variational problem arising from the framework of Chatterjee and Varadhan we show that the replica symmetry phase consists of all p,r such that rd,hpr lies on the convex minorant of xi¾?hpx1 d where hp is the rate function of a binomial with parameter p. In particular, the answer for triangles involves hpx rather than the natural guess of hpx1 3 where symmetry was previously known. Analogous results are obtained for linear hypergraphs as well as the setting where the largest eigenvalue of G Gn,p is conditioned to exceed the typical value of the largest eigenvalue of Gn,r. Building on the work of Chatterjee and Diaconis 2012 we obtain additional results on a class of exponential random graphs including a new range of parameters where symmetry breaking occurs. En route we give a short alternative proof of a graph homomorphism inequality due to Kahn 2001 and Galvin and Tet ali 2004. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 109-146, 2015 Advances in neonatal care have improved the survival of infants born prematurely although these infants remain at increased risk of adverse neurodevelopmental outcome. The measurement of white matter structure and features of the cortical surface can help define biomarkers that predict this risk. The measurement of these structures relies upon accurate automated segmentation routines, but these are often confounded by neonatal-specific imaging difficulties including poor contrast, low resolution, partial volume effects and the presence of significant natural and pathological anatomical variability. In this work we develop and evaluate an adaptive preterm multi-modal maximum a posteriori expectation-maximisation segmentation algorithm (AdaPT) incorporating an iterative relaxation strategy that adapts the tissue proportion priors toward the subject data. Also incorporated are intensity non-uniformity correction, a spatial homogeneity term in the form of a Markov random field and furthermore, the proposed method explicitly models the partial volume effect specifically mitigating the neonatal specific grey and white matter contrast inversion. Spatial priors are iteratively relaxed, enabling the segmentation of images with high anatomical disparity from a normal population. Experiments performed on a clinical cohort of 92 infants are validated against manual segmentation of normal and pathological cortical grey matter, cerebellum and ventricular volumes. Dice overlap scores increase significantly when compared to a widely-used maximum likelihood expectation maximisation algorithm for pathological cortical grey matter, cerebellum and ventricular volumes. Adaptive maximum a posteriori expectation maximisation is shown to be a useful tool for accurate and robust neonatal brain segmentation.