Exploring Random-Graph Ensembles with Worms

• Wolfhard Janke (Institute for Theoretical Physics, Leipzig)

The loop-gas approach to lattice field theory provides an alternative, geometrical description in terms of linelike objects. The resulting statistical random-graph ensemble composed of loops and chains can be efficiently generated by Monte Carlo simulations using the so-called "worm" update algorithm. Concepts from percolation theory and the theory of self-avoiding random walks are used to describe estimators of physical observables that utilize the nature of the worm algorithm. The fractal structure of the random loops and chains as well as their scaling properties are studied. The general approach is illustrated for the O(1) loop model, or high-temperature series expansion of the Ising model, on a honeycomb lattice, with its known exact results for some quantitites providing valuable benchmarks.

Long-Range Percolation on the Hierarchial Lattice

• Pieter Trapman (Stockholm University)

The hierarchical lattice of order N, may be seen as the leaves of an infinite regular N-tree, in which the distance between two vertices is the distance to their most recent common ancestor in the tree. <br>We create a random graph by independent long-range percolation on the hierarchical lattice of order N: The probability that a pair of vertices at (hierarchical) distance R share an edge depends only on R and is exponentially decaying in R, furthermore the presence or absence of different edges are independent. <br>We give criteria for percolation (the presence of an infinite cluster) and we show that in the supercritical parameter domain, the infinite component is unique. Furthermore, we show the percolation probability (the density of the infinite cluster) is continuous in the model parameters, in particular, there is no percolation at criticality. <br>Joint work with Slavik Koval and Ronald Meester

Random Records and Cuttings in Split Trees

• Cecilia Holmgren (INRIA Rocquencout)

I will discuss the number of random records in an arbitrary split tree with <em>n</em> vertices (or equivalently, the number of random cuttings required to eliminate the tree). I will explain how a classical limit theorem for convergence of sums of triangular arrays to infinitely divisible distributions can be used to determine the distribution of this number. After normalization the distributions are shown to be asymptotically weakly 1-stable. This work is a generalization of my earlier results for the random binary search tree, which is one specific case of split trees. Other important examples of split trees include <em>m</em>-ary search trees, quadtrees, medians of <em>(2k+1)</em>-trees, simplex trees, tries and digital search trees.

Maximal Entropy Random Walk

• Zdzislaw Burda (Jagiellonian University)

We define a new class of random walk processes which maximize entropy. This maximal entropy random walk is equivalent to generic random walk if it takes place on a regular lattice, but it is not if the underlying lattice is irregular. In particular, we consider a lattice with weak dilution. We show that the stationary probability of finding a particle performing maximal entropy random walk localizes in the largest nearly spherical region of the lattice which is free of defects. This localization phenomenon, which is purely classical in nature, is explained in terms of the Lifshitz states of a certain random operator.

Random Networks and Epidemics

• Tom Britton (S)

Random networks may be used to describe the social structure in a community. "On" such a network one can model the spread of an infection. Questions of interest to study are for example: Can a big outbreak occur?, How large will it be?, What is the effect of introducing a given vaccination scheme? In the talk we will survey this area, with focus on effects of the underlying random network on the questions formulated above.

Susceptibility of Random Graphs

• Svante Janson (Stockholm University)

The susceptibility of a graph is the average size of the component containing a randomly chosen vertex. We discuss the susceptibility of some random graphs, including the standard "Erdös-Renyi" random graph G(n,p).

The Splitting Vertex Model

• Thordur Jonsson (University of Iceland)

We discuss a model of growing planar trees called the splitting vertex model which has preferential attachment trees as a special case and the alpha model of phylogenetic trees as a limiting case. We show how to calculate the distribution of vertex degrees and define structure functions which allow us to calculate the Hausdorff dimension in some cases. We further dicuss the "mass distribution" and the infinite volume limit.

Random Curves via Conformal Welding

• Antti Kuipiainen (University of Helsinki)

Optimization, games and replica symmetry

• Johan Wästlund (Chalmers)

I will describe how properties of certain optimization problems on random graphs can be established by analyzing related two-person games.

Planar maps and continued fractions

• Jérémie Bouttier (CEA Saclay)

Planar maps (graphs embedded in the sphere) form a natural model for discrete (tessellated) random surfaces, used in the context of two-dimensional quantum gravity. Many questions about the geometry of random maps can be rephrased as enumeration problems. In this talk, I will present an unexpected connection between two such problems. <br>In the first problem, we consider maps with one boundary, whose generating function is the so-called disk amplitude. This quantity is well-studied, it is for instance expressible as a matrix integral, and computable using Tutte's/loop equations. <br>In the second problem, we consider maps with two marked points at a given distance, whose generating function is the so-called two-point function. Though it is one of the simplest metric-related observables, much less is known about it. <br>I will explain that, in a rather general class of maps, the disk amplitude and the two-point function are two facets of the same quantity, which has to be viewed respectively as a power series and as a continuous fraction. I will then explain how the known solution to the first problem yields the solution to the second problem.

Critical 2D Ising Model with Mixed Boundary Conditions

• Kalle Kytölä (University of Helsinki)

We consider the square lattice Ising model at its critical point in simply connected domains with a boundary. We split the boundary to a few pieces, and impose different boundary conditions on each. We are interested in the scaling limit in which a given domain is approximated by subgraphs of the square lattice with mesh size tending to zero. In the scaling limit conformal invariance properties are expected if the boundary conditions are combinations of plus, minus and free. A traditional interpretation of conformal invariance concerns correlation functions, and our first results are explicit expressions for some correlation functions of boundary spins in terms of the Riemann uniformizing map of the domain. <br>A different point of view to conformal invariance, initiated by Schramm, is to focus attention to random curves or interfaces. In the Ising model, Smirnov's work shows conformal invariance of two kinds of interfaces: an exploration path in the FK representation of Ising with plus-free boundary conditions tends to the chordal SLE(16/3) process, and a curve in the low temperature expansion with plus-minus boundary conditions tends to the chordal SLE(3) process. Our work uses Smirnov's first result to obtain a generalization of the second. The generalization concerns a curve in the low temperature expansion with free-plus-minus boundary conditions. We will show how the expressions for correlation functions identify the limit of this curve as a variant of SLE(3) called the dipolar SLE(3). This generalization was first conjectured by Bauer & Bernard & Houdayer. <br>The presentation is based on joint work with Clément Hongler (Université de Genève & Columbia University).

Random Curves, Scaling Limits and Loewner Evolutions

• Antti Kemppiainen (University of Helsinki)

Random curves arise naturally as interfaces in the 2D statistical physics and its lattice models. A general strategy to prove the convergence of a random discrete curve, as the lattice mesh goes to zero, is first to establish precompactness of the law giving the existence of subsequential scaling limits and then to prove the uniqueness. In this talk, I will introduce a sufficient condition that guarantees the precompactness and also that the limits are Loewner evolutions, i.e. they correspond to continuous Loewner driving processes. This framework of estimates is applicable in almost all proofs aiming to establish that an interface converges to a Schramm-Loewner evolution (SLE). In principle, it can be applied beyond SLE. <br>Joint work with Stanislav Smirnov, Université de Genève

Emergence of a Vertex of Infinite Degree in Non-Generic Trees

• Sigurdur Stefansson (Nordita)

I will introduce an equilibrium statistical mechanical model of trees with a local action which depends only on the degrees of vertices in the tree. Related models have been studied extensively, in different forms, by mathematicians with a history dating back to Galton and Watson in the 19th century who were interested in calculating the probability of the extinction of family names. Physicist became interested in the model in connection with simplicial gravity where they observed that a certain phase of the gravity model had tree-like features. The model has two phases which are called generic (fluid, elongated) and non-generic (condensed, crumpled) phase. I will review recent results on the generic phase and present new results on the non-generic phase which I worked on in my Ph.D. studies with Thordur Jonsson. We proved the existence of a Gibbs measure on infinite trees obtained as a weak limit of the finite volume measures and showed that in the infinite volume limit there arises exactly one vertex of infinite degree and the rest of the tree is distributed like a sub-critical Galton-Watson tree.

Quantum Geometry and a New Scaling Limit for Random Matrix Models

• Jan Ambjørn (MBI)

We define a new scaling limit for hermitian random matrix models, closer to the classical limit V'(x)=0. The "random surface" interpretation of the limit is discussed and it is shown that the 2d causal dynamical model can be identified with the classical limit of a certain matrix model.

Reconstruction of Graphs

• Bhalchandra Thatte (Oxford University)

Abstract: Ulam (1942) conjectured that each unlabelled simple finite graph on 3 or more vertices can be constructed from the collection of its unlabelled induced proper subgraphs. I will introduce Ulam's conjecture and some related problems, and survey a few results. I will then discuss a result by Bollobás on reconstructing almost all graphs. My current interest is in a variant of Ulam's problem for population pedigrees (ancestral histories of populations). I will discuss my attempts to prove results analogous to Bollobás's result.

Stochastic quantization and the sum over topologies in causal string field theory

• Stefan Zohren (Oxford University)

Fundamental Structures of M(brane) Theory

• Jens Hoppe (KTH, Stockholm)

Order-disorder transition in random graphs

• Piotr Bialas (Jagiellonian University, Cracow)

Abstract: I will present a simple model of graphs that exhibits a phase transition between and ordered phase (regular graphs or order 3 or 4) to an unordered phase (3-4 graphs). I will discuss the behaviour of the correlation functions near the transition.

Registration and breakfast

The Fate of Leaders in Growing Networks

• Jean-Marc Luck (CEA Saclay)

Stochastic models of growing networks are used to describe complex networks such as the airline network or the Internet. New nodes (airports, sites) enter the system one at a time and attach to one earlier node according to some rule. The leader at any time is the node with largest degree (busiest airport, most popular website). We have addressed various questions concerning the sequence of leaders: What is the typical number of changes of lead, of distinct leaders, up to a given time? What is the probability that a leader keeps the lead for a given time lapse, forever? To be specific we have considered a model introduced by Bianconi and Barabasi where the attachment probability to a given node is proportional to its degree (rich-get-richer feature) and to an intrinsic quality or fitness (fit-get-richer feature). Node fitnesses are modelled as activated quenched random variables. The model may exhibit a condensed phase below some finite critical temperature. The statistics of leaders and related quantities will be discussed in various regimes. Based on work in collaboration with Godreche and Grandclaude.

Coffee

Freezing Transition in Decaying Burgers Turbulence and Random Matrix Dualities

• Yan Fyodorov (Nottingham University)

Freezing transition with decreasing temperature is a generic property of equilibrium statistical mechanics models whose random energy landscapes are logarithmically correlated in space. The extreme value statistics plays an important role in elucidating the nature of such a transition. In the present work we reveal a similar transition to take place in one-dimensional decaying Burgers turbulence with a power-law correlated random profile of Gaussian-distributed initial velocities < v(x; 0)v(x'; 0) > ~ |x -x'|^{-2}, with the role of temperature played by viscosity. The low-viscosity phase exhibits non-Gaussian one-point probability density of velocities, continuously dependent on viscosity, reflecting a spontaneous one step replica symmetry breaking (RSB) in the associated statistical mechanics problem. We obtain the low orders cumulants analytically. Our results, which are checked numerically, are based on combining insights in the mechanism of the freezing transition in random logarithmic potentials with an extension of duality relations discovered recently in Random Matrix Theory. The presentation is based on the work Y.V. Fyodorov, P. Le Doussal and A. Rosso Europh. Lett. v.90 (2010) 60004.

Lunch

Non-equilibrium Phenomena in Random Matrix Theory

• Maciej Nowak (Jagiellonian University)

We identify non-equilibrium phenomena alike formation of the spectral shock waves in the random matrix models driven by an external parameter. We provide explicit examples in the case of additive and mutiplicative matrix analogs of the Brownian walk.

Extreme Value Statistics of Non-intersecting Brownian Motions: From Random Matrices to 2d Yang-Mills Theory on the Sphere

• Gregory Schehr (Universite Paris-sud)

Non-intersecting random walkers (or "vicious walkers") have been studied in various physical situations, ranging from polymer physics to wetting and melting transitions and more recently in connection with random matrix theory or stochastic growth processes. In this talk, I will present a method based on path integrals associated to free Fermions models to study such statistical systems. I will use this method to calculate exactly the cumulative distribution function (CDF) of the maximal height of p vicious walkers with a wall (excursions) and without a wall (bridges). In the case of excursions, I will show that the CDF is identical to the partition function of 2d Yang Mills theory on a sphere with the gauge group Sp(2p). Taking advantage of a large p analysis achieved in that context, I will show that the CDF, properly shifted and scaled, converges to the Tracy-Widom distribution for beta = 1, which describes the fluctuations of the largest eigenvalue of Random Matrices in the Gaussian Orthogonal Ensemble.

Coffee

Random Convex Hulls and Extreme Value Statistics

• Satya Majumdar (Universite Paris-sud)

On shock's statistics in "Tetris" Game

• Sergei Nechaev (LPTMS Paris XI)

We consider a (1 + 1)-dimensional ballistic deposition pro- cess with next-nearest neighbor interaction, which belongs to the KPZ universality class, and introduce for this discrete model a variational formulation similar to that for the randomly forced continuous Burgers equation. This allows to identify the characteristic structures in the bulk of a growing aggregate ("clusters" and "crevices") with minimizers and shocks in the Burgers turbulence. We find scaling laws that characterize the ballistic deposition patterns in the bulk: the "thinning" of the forest of clusters with increasing height, and the size distribution of clusters. The corresponding critical exponents are computed using the analogy with the Burgers turbulence.

Coffee

Cut-offs and Maximal Degrees in Scale-free Networks

• Bartlomiej Waclaw (University of Edinburgh)

I will dis cuss how various models of scale-free networks approach their limiting properties when the size of the network grows. I will show that subleading corrections to the scaling of the position of the cutoff are strong even for networks of order 10^9 nodes, and that a logarithmic correction to the scaling is observed for some graphs when the degree distribution follows a power law k^(-3). I will also study the distribution of the maximal degree and show that it may have a different scaling than the cutoff and, moreover, it approaches the thermodynamic limit much faster. Finally, I will present some results on the cutoff function and the distribution of the maximal degree in equilibrated networks.

Lunch

Ikea Networks and Metabolic Organisation

• Petter Minnhagen (University of Umeå)

A simple general null-model, the Ikea network, is described and its properties are investigated. This network is argued to be the appropriate network for a random assembling of links, such that both which link is attached to which and the time- order are all distinct random possibilities. From this point of view it is the extreme opposite of preferential attachment. This network is discussed in the context of metabolic networks, where the metabolism of an organism is reduced to a network of substances. The striking agreement between the Ikea net- work and the metabolic networks implies that the null model catches the overall features. Using the network structure measures clustering and assortativity, a small difference is nevertheless identified and is argued to imply a possible evolutionary pressure. However, this difference is only manifested in a slight difference in the degree distribution and seemingly not in any particular network design.

"Explosive percolation" Transition is actually Continuous

• Sergey Dorogovtsev (University of Aveiro)

We present the theory of explosive percolation. Recently a discontinuous percolation transition was reported in a new "explosive percolation" problem for irreversible systems [D. Achlioptas, R. M. D'Souza, and J. Spencer, Science 323, 1453 (2009)] in striking contrast to ordinary percolation. We show that the "explosive percolation" transition is actually a continuous, second order phase transition though with a uniquely small critical exponent of the percolation cluster size. Thus there is no explosion at the "explosive percolation" transition. Using a wide class of representative models, we describe the unusual scaling properties of this transition and find a set of its scaling functions and critical exponents and dimensions. In particular, we find that the upper critical dimensions for such phase transitions are remarkably low. [1] R. A. da Costa, S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, arXiv:1009.2534. [2] S. N. Dorogovtsev, Lectures on Complex Networks (Oxford University Press, Oxford, 2010).

Cellular Automata and Epidemics

• Philippe Chassaing (Institut Elie Cartan)

We consider a family of cellular automata modelling the random spreading of a disease on the real line. The space-time random geometry keeping track of the spreading exhibits strange symmetries. Joint work with L. Gerin, M. Krikun, S. Popov.

Correlations in Random Trees

• Piotr Bialas (Jagiellonian University)

I will explicitly calculate the distance dependent correlation functions in a maximal entropy ensemble of random trees and show that correlations remain disassortative at all distances and vanish only as a second inverse power of the distance. I will discuss in detail the example of scale-free trees where the diverging second moment of the degree distribution leads to some interesting phenomena.

Coffee

Correlations in Randomly Oriented Graphs

• Svante Linusson (KTH Stockholm)

Consider a graph G and orient the edges independently with equal probabilities for the two directions. Let a; s; b be three distinct vertices and consider the events {s to a}, that there is a directed path from s to a, and {s to b}. It feels intuitively clear that these events are positively correlated, which also can be proven to be true for any graph. In fact, it is true also if we first condition that there is no directed path from s to t for any other vertex t in G, which is perhaps less clear intuitively. If we instead consider the paths {a to s} and {s to b} one might first guess that these should be negatively correlated, but this does not hold in general. I will present results for some special classes of graphs and for random graphs G(n; p) and G(n;m). This is joint work with Sven Erick Alm and Svante Janson.

Lunch

Real-space Condensation and Extreme Value Statistics

• Martin Evans (University of Edinburgh)

In this talk I shall review the phenomenon of real-space con- densation wherein a finite fraction of interacting particles moving on a lattice condense onto a single site. The phenomenon has manifestations in a number of complex systems e.g. clustering in granular systems and wealth condensation in macroeconomies. The phenomenon can be understood by considering models with particularly simple stationary states which have a factorised form. To this end I shall review necessary and sufficient conditions for factorised stationary states in a simple class of models. Then the condensation can be analysed and understood in terms of large deviations of sums of random variables and extreme value statistics. Finally, I shall consider generalisations such as multiple condensates and entropy driven condensation in systems of polydisperse hard spheres.

Information Geometry and the ASEP

• Desmond Johnston (Heriot-Watt University)

The application of information geometric ideas to statistical mechanics using a metric on the space of states, as pioneered by Ruppeiner and Weinhold, provides an alternative approach to characterizing phase transitions. We ask whether such methods might be applied to non- equilibrium models and take the non-equilibrium steady states of the asymmetric exclusion process (ASEP) as a test case.

Coffee

Quantum graphity and random walks on graphs

• Klas Markström (University of Umeå)

I will discuss the different quantum graphity models and their relation to the structure of random graphs and random walks. The original quantum graphity models are toy models for quantum gravity and later versions of the model include randomly walking particles interacting with the dynamics of the geometry.

Dynamic cavity method to compute marginals of non-equilibrium steady states

• Erik Aurell (KTH Stockholm)

The cavity method or, in computer science, Belief Propagation, is an efficient method to approximately compute marginals of equilibrium probability distributions e.g. magnetizations in spin glasses. The method is exact if the underlying graph of interactions is a tree, and generally expected to be accurate if that graph is locally tree-like. We have investigated a similar approximation scheme for the diluted asymmmetric Ising spin glass with synchronous or sequential update rules. The cavity method can be formally set up in this context, but requires an additional assumption of stationarity to be computationally feasible: the approach is hence limited to steady (but non-equilibrium) states. I will present the dynamic cavity method, and numerical results for a few examples. This is joint work with Hamed Mahmoudi (Helsinki), other recent relevant contributions are Neri & Bolle (2009) and Montanari (2009).

Computer Simulations of Macromolecular Systems

• Wolfhard Janke (Leipzig Univeristy)

Folding, aggregation and crystallization of proteins and polymers, interaction between proteins and membranes as well as adsorption of organic soft matter to inorganic solid substrates belong to the most interesting challenges in understanding the structure and function of complex macromolecules. Recent advances of computer simulations in generalized ensembles combined with new analysis methodologies can provide valuable insight into the processes on multiple scales governing the self-assembly in such systems. After a brief survey of approaches with different resolution, I will focus on mesoscopic models and present results from recent simulations of crystallization, aggregation and adsorption phenomena of macromolecules.

Adaptation in a varying fitness landscape

• Silvio Franz (IPTMS)

Several pathogens use evolvability as a survival strategy against acquired immunity of the host. Despite their high variability in time, some of them exhibit quite low variability within the population at any given time, a somehow paradoxical behavior often called the evolving quasispecies. In this paper we introduce a simplified model of an evolving viral population in which the effects of the acquired immunity of the host are represented by the decrease of the fitness of the corresponding viral strains, depending on the frequency of the strain in the viral population. The model exhibits evolving quasispecies behavior in a certain range of its parameters, and suggests how punctuated evolution can be induced by a simple feedback mechanism.

Tree and dynamics of the influenza virus

• Michael Lässig (Universität Köln)

The seasonal influenza A virus has been systematically observed for over 40 years. Coalescent trees spanning this period can be constructed from influenza sequence data. How can the underlying evolution of influenza be inferred from the shape of such trees? In this talk, I show how this process is shaped by a competition between different viral strains and by stochastic fluctuations.

Coffee

Asymptotic distribution for the size of a near critical epidemic

• Anders Martin-Löf (Stockholm University)

The so called S-I-S model for the spread of an infection in a finite population is studied, and it is shown that there is a critical value of the infection rate below which the epidemic is small and above which it is large. Moreover, in the near critical case there is a critical scaling giving rise to a limit distribution for the size which can be calculated analytically with the help of Airy functions.

Statistics for clustering in gene expression data: from statistical significance to biological relevance

• Marta Luksza (Universität Köln)

Clustering is used widely to infer putative functional relationships between data elements. An example is gene expression clusters arising through common biological pathways or shared modes of regulation. In this talk, we discuss elements of a statistical theory of clustering. First, data sets often contain dependencies between the components of data vectors, for example between experimental conditions in gene expression data. How can such genuine correlations be disentangled from the spurious ones that arise due to presence of clusters? Second, even unrelated objects can form cluster-like structures, simply due to random density fluctuations. How can we distinguish such random clusters from a signal of functional correlations? We discuss how to compute a cluster p-value, using a mapping of clustering to statistical mechanics of disordered systems. In an application to gene expression data, we find a remarkable link between the statistical significance of a cluster and the functional relationships between its genes.

Lunch

Linear model of gene activity with nonlinear constraints

• Stefan Thurner (University of Vienna)

Fractional Brownian motion in presence of absorbing boundaries

• Kay Wiese (LPTENS)

Fractional Brownian motion is a Gaussian process x(t) with zero mean and two-time correlations of the form &lt;x(t₁)x(t₂)&gt; = D(t₁^2H + t₂^2H - |t₁-t₂|^2H), where H, with 0&lt;H&lt;1 is called the Hurst exponent. For H=&frac12;, x(t) is a Brownian motion, while for H&#8800;&frac12;, x(t) is a non-Markovian process. Here we study x(t) in presence of an absorbing boundary at the origin and focus on the probability density P+(x, t) for the process to arrive at x at time t, starting near the origin at time 0, given that it has never crossed the origin. It has a scaling form P₊(x, t)&#8764;t^HR₊(x t^H). Our objective is to compute the scaling function R₊(y), which up to now was only known for the Markov case H=&frac12;. We develop a systematic perturbation theory around this limit, setting H=&frac12;+&epsilon;, to calculate the scaling function R₊(y) to first order in t. We find that R₊(y) &#8764; y as y &#8594; 0 (near the absorbing boundary), while R+(y)&#8764;y^&gamma; exp(y²/2) as y &#8594; &#8734;, with &phi;=1-4&epsilon;+O(&epsilon²) and &gamma;=1-2&epsilon;+O(&epsilon²). Our t-expansion result confirms the scaling relation &phi;=(1H)/H. We verify our findings via numerical simulations for H=2/3. The tools developed here are versatile, powerful, and adaptable to different situations.

Coffee

Model gene regulatory networks under mutation-selection balance

• Marcin Zagorski (Jagiellonian University)

Gene regulatory networks typically have low in-degrees, whereby any given gene is regulated by few of the genes in the network. They also tend to have broad distributions for the out-degree. What mechanisms might be responsible for these degree distributions? Starting with an accepted framework of the binding of transcription factors to DNA, we consider a simple model of gene regulatory dynamics. There, we show that selection for a target expression pattern leads to the emergence of minimum connectivities compatible with the selective constraint. As a consequence, these gene networks have low in-degree, and functionality is parsimonious, i.e., is concentrated on a sparse number of interactions as measured for instance by their essentiality. Furthermore, we find that mutations of the transcription factors drive the networks to have broad out-degrees. Finally, these classes of models are evolvable, i.e., significantly different genotypes can emerge gradually under mutation-selection balance.

Network aspects of chromosome interactomes

• Erik Aurell (KTH Stockholm)

DNA is folded into increasingly complex yet highly mobile structures to organize the chromosomes. In this talk I will describe work with Rolf Ohlsson’s lab at KI where we have tried to quantify whether chromosome-chromosome interactions are random or not, and (if it is not) can we say something about the network structure of such interactions. The key experimental technique is high throughput sequencing of both read (short segements) known to interact with a known bait sequence, as well as chimeric reads containing pieces from different locations, in addition to the bait.

Random walks and paradoxical diffusion

• Ewa Gudowska-Nowak (Jagiellonian University)

Commonly, normal diffusive behavior is characterized by a linear dependence of the second central moment on time, &lt;x²(t)&gt; &prop; t, while anomalous behavior is expected to show a different time dependence, &lt;x²(t)&gt; &prop; t^&delta;; with &delta;&lt;1 for subdiffusive and &delta;&gt;1 for superdiffusive motions. I will demonstrate that this kind of qualification, if applied straightforwardly, may be misleading: There are anomalous transport motions revealing perfectly "normal" diffusive character &lt;x²(t)&gt; &prop; t, yet being non-Markov and non-Gaussian in nature. Consequences of this paradoxical diffusion for biophysical research will be briefly discussed.

Simple models for scale dependent spectral dimension

• John Wheater (University of Oxford)

Recent work on various models of quantum gravity suggests that they exhibit scale dependence of the spectral dimension. One of these models, the causal dynamical triangulation, is based on an ensemble of random graphs which suggests that this behaviour may be more generic. We discuss how such a property may be formulated rigorously and show that there are indeed well-defined ensembles of random graphs in which the scale dependence of the spectral dimension can be demonstrated.

Coffee

Power blackouts and the domino effect: real-life examples and modeling

• Ingve Simonsen (NTNU, Trondheim)

Our contemporary societies rely more and more on a steady and reliable power supply for their well-functioning. During the last few decades a number of large-scale power blackouts have been witnessed around the world, and this has caused major concerns among politicians and citizens. In this talk we will mention a few major power blackouts and discuss the sequence of events and why they occurred. These empirical examples show that major power blackouts often are results of a cascading of failures (a "Domino effect"). We will introduce a generic (random walk) model for the study of cascading failures in networks, and investigate the impact of transient dynamics caused by the redistribution of loads after an initial network failure (triggering event). It is found that considering instead the stationary states, as has been done in the past, may dramatically overestimate (by 80-95%) the robustness of the network. This is due to the transient oscillations or overshooting in the loads, when the flow dynamics adjusts to the new (remaining) network structure. Consequently, additional parts of the network may be overloaded and therefore fail before the stationary state is reached. The dynamical effects are strongest on links in the neighborhood of broken links. This can cause failure waves in the network along neighboring links, while the evaluation of the stationary solution predicts a different order of link failures.

A dynamical phase transition in a model for evolution with migration

• Bartlomiej Waclaw (University of Edinburgh)

Migration between different habitats is ubiquitous among biological populations. Here I will discuss a simple model for evolution of asexual organisms in two different habitats coupled by one-way migration as well as the network of possible mutations. This gives rise to clusters of closely related genotypes — "quasispecies". The habitats are assumed to have different fitness landscapes, i.e., organisms which are well-adapted in the primary habitat are likely to be maladapted in the secondary habitat. The model undergoes a dynamical phase transition: at a critical value of the migration rate, the time to reach the steady state diverges. Above the transition, the population is dominated by immigrants from the primary habitat. Below the transition, the genetic composition of the population is highly non-trivial, with multiple coexisting "quasispecies" which are not native to either habitat. Using results from localization theory, I will show that the critical migration rate may be very small — demonstrating that evolutionary outcomes can be very sensitive to even a small amount of migration.

Lunch

Epidemic thresholds for a static and dynamic small-world network

• Jeremi Ochab (Universität Leipzig)

The aim of the study was to compare the epidemic spread on static and dynamic small-world networks. The network was constructed as a 2-dimensional Watts-Strogatz model, and the dynamics involved rewiring shortcuts in every time step of the epidemic spread. The model of the epidemic is SIR with latency time of 3 time steps. The behaviour of the epidemic was checked over the range of shortcut probability per underlying bond &phi;=0-0.5. The quantity of interest was percolation threshold for the epidemic spread, for which numerical results were checked against an approximate analytical model. We find a significant lowering of percolation thresholds for the dynamic network in the parameter range given. The result shows that the behaviour of the epidemic on dynamic network is that of a static small world with the number of shortcuts increased by 20.7 &#177; 1.4%, while the overall qualitative behaviour stays the same. We derive corrections to the analytical model which account for the effect. For both dynamic and static small-world we observe suppression of the average epidemic size dependence on network size in comparison with finite-size scaling known for regular lattice. We also study the effect of dynamics for several rewiring rates relative to latency time of the disease.

Some identifiability questions on reconstructing population pedigrees

• Bhalchandra Thatte (Oxford University)

A pedigree of a population of individuals is a finite directed acyclic graph in which each vertex has indegree 0 or 2. The sink vertices in a pedigree are living individuals and sources are the founders of a population. Suppose founders are assigned random sequences over an alphabet &Sigma; (e.g. DNA sequences over the alphabet A,T,G,C). The sequences evolve under a stochastic model of mutations and recombinations. Thus the model and the pedigree induce a probability distribution on the sequences of living individuals. Given such a distribution, can we construct the pedigree (up to isomorphism)? I will talk about my recent work on this problem.

Coffee

Random matrices, spin decoherence and random walks

• Francois David (CEA, Saclay)

I present a simple very general random matrix model for quantum spins interacting with a large external system. It allows to study and illustrate in a simple framework various quantum-to-classical phenomena: the decoherence dynamics, the emergence of the classical phase space for a quantum system, quantum and classical diffusion in phase space, the conditions for non-Markovian and Markovian behaviors.

Wine and snacks

Counting triangulations via discrete Morse theory

• Bruno Benedetti (TU Berlin)

In 1995 Durhuus and Jonsson introduced the class of locally constructible (LC) triangulations and showed that there are at most exponentially many LC 3- spheres with N tetrahedra. Such upper bounds are crucial for the convergence of the dynamical triangulations model in discrete quantum gravity. We show that any simply connected manifold of dimension different than four admits an LC triangulation. However, plenty of non-LC d-spheres exist for each d>2. Also, we show how discrete Morse theory yields exponential cutoffs for the class of all triangulations of manifolds with N facets.