Abstract list
Manan Bhatia, Small deviation estimates and small ball probabilities for geodesics in last passage percolation
The planar exponential last passage percolation model is an important integrable model in the (1+1) dimensional KPZ universality class. In this talk, we first introduce the model and describe its connections to the totally asymmetric simple exclusion process (TASEP). The model has a natural definition of geodesics as paths of extremal weight, and it is interesting to ask about the geometric behaviour of these geodesics. We look at some known results about the transversal fluctuation of the geodesics and the coalescence property enjoyed by them. Subsequently, we discuss small deviation estimates, both one-point and small ball, for the behaviour of the geodesic as a random path and conclude by briefly indicating their proofs.
This talk is based on arXiv:2101.01717, which is joint work with Riddhipratim Basu.
Giovanni Brigati, Time averages for kinetic Fokker-Planck equations
We consider kinetic Fokker-Planck (or Vlasov-Fokker-Planck) equations on the torus with Maxwellian or fat tail local equilibria. Results based on weak norms have recently been achieved by S. Armstrong and J.-C. Mourrat in case of Maxwellian local equilibria. Using adapted Poincar ́e and Lions-type inequali- ties, we develop an explicit and constructive method for estimating the decay rate of time averages of norms of the solutions, which covers various regimes corresponding to subexponential, exponential and superexponential (including Maxwellian) local equilibria. As a consequence, we also derive hypocoercivity estimates, which are compared to similar results obtained by other techniques.
Suman Chakraborty, Sparse random graphs with many triangles
It is well known that sparse random graphs (where the number of edges is of the order of the number of vertices) contain only a small number of triangles. On the other hand, many networks observed in real life are sparse but contain a large number of triangles. Motivated by this we investigate the following questions: how (un)likely is it that a sparse random graph will contain a large number of triangles? How does the graph look like when it contains a large number of triangles? We also study another related question: what is the probability that in a sparse random graph large number of vertices will be part of some triangle? We will discuss these questions and some possible applications (if time permits).
The talk is based on joint ongoing work with Frank den Hollander and Remco van der Hofstad.
Barbara Dembin, The time constant for Bernoulli percolation is Lipschitz continuous strictly above pc
We consider the standard model of i.i.d. first passage percolation on Zd given a distribution G on [0,+∞] (+∞ is allowed). When G([0,+∞[)>pc(d), it is known that the time constant μG exists. We are interested in the regularity properties of the map G → μG. We study the specific case of distributions of the form Gp=p𝛿1+(1-p)𝛿∞ for p>pc(d). In this case, the travel time between two points is equal to the length of the shortest path between the two points in a bond percolation of parameter p. We can show that the function p → μGp is Lipschitz continuous on every interval [p0,1], where p0>pc(d).
This is a joint work with Raphaël Cerf.
Jens Fischer, An interpretation of random network dynamics as generalized exclusion processes
Exclusion processes belong to the classical examples of interacting particle systems arising from various problems in physics. In this talk I am going to present a way to exploit the intuitiveness of this model to approach models of dynamic random networks, with a fixed number of vertices and edges and moving edges, quantitatively. I will use as an illustrative example a reduced version of the echo chamber model in discrete time. Our results consist of convergence behaviours of this model, phase transitions based on the underlying parameters and the geometry of the underlying graph as well as a characterization of the stationary distribution.Under the overarching topic of finite Markov chains I will focus on combinatorial aspects, graph theoretic questions as well as links to computer science which arise naturally in this context and which underline the benefits of combining methods from these different fields.
Luca Ganassali, Statistical and Computational limits for sparse graph alignment
Random graph alignment refers to recovering the underlying vertex correspondence between two random graphs with correlated edges. This can be viewed as an average-case and noisy version of the well-known graph isomorphism problem. For correlated Erdős-Rényi random graphs, we will give insights on the fundamental limits for this problem, pinning down statistical thresholds for exact or partial recovery of the planted structure. From the computational point of view we are interested in designing and analyzing efficient (polynomial-time) algorithms to reconstruct efficiently the underlying alignment: in a sparse regime, we exhibit an local rephrasing of the planted alignment problem as a correlation detection problem in trees, which helps deriving a belief propagation algorithm for our initial task.
Based on joint works with Laurent Massoulié and Marc Lelarge: arXiv:2002.01258,arXiv:2102.02685, arXiv:2107.07623.
Ivailo Hartarsky, Coalescing and branching simple exclusion process and Fredrickson-Andersen models
Consider independent continuous time random walks on a graph coalescing when they meet. Additionally, let each particle create an additional particle at each of its empty neighbours at a fixed rate. This process, which we call CBSEP, and its dual, the biased voter model, have been studied since the 70s.
We are interested in the delicate near-critical regime with birth rate going to 0 as the graph size increases. In this setting, we establish precise results for the mixing of CBSEP in the logarithmic Sobolev sense on general finite graphs. Exploiting a new connection between CBSEP and the Fredrickson-Andersen 1-spin facilitated kinetically constrained model (FA-1f), this strengthens and extends recent results of Pillai and Smith for the mixing time of FA-1f on the torus.
On a very different note, a generalised version of CBSEP turns out to be instrumental for studying the FA-2f model. With its help, we determine the exact leading order of the relaxation time of FA-2f on Zd for all d>1, greatly improving previously available results.
Based on joint works with Fabio Martinelli and Cristina Toninelli.
arXiv:2006.01426, arXiv:2012.02557
Fu-Hsuan Ho, Efficiency approximation of the Gibbs measure of branching random walk
In this talk, I will present a recent work with my supervisor Pascal Maillard (arXiv:2107.11465) on efficiently approximating the branching random walk Gibbs measures. We proved that there exists a critical value βc such that in the subcritical regime, one can approximate the Gibbs measure in polynomial time. We also provided a supplementary result of hardness in the supercritical regime. If time permits, I will mention a bit how one might proceed to generalize the results to other models.
Alexis Kagan, Ranges of random walks in random environment on trees
We consider the randomly biased random walk on trees and focus on the boundary case for the underlying branching potential. The range Rn of the walk is the number of vertices visited by the walk up to the time n. It is known that Rn behaves in n/ log n with high probability. I will present general results and some explicit examples for the range with both constraints on the trajectories of the walk and on the trajectories of the underlying branching potential. Based on joint work with Pierre Andreoletti.
Vinay Kumar, A Probabilistic Brodcast Mechanism on Random Geometric Graphs
We consider the problem of energy-efficient broadcasting on homogeneous random geometric graphs (RGGs) within a large finite box around the origin. A source node at the origin encodes k data packets of information into n > k coded packets and transmits them to all its one-hop neighbors. The encoding is such that, any node that receives at least k out of the n coded packets can retrieve the original k data packets. Every other node in the network follows a probabilistic forwarding protocol; upon reception of a previously unreceived packet, the node forwards it with probability p and does nothing with probability 1-p. We are interested in the minimum forwarding probability which ensures that a large fraction of nodes can decode the information from the source. We deem this a near-broadcast. The performance metric of interest is the expected total number of transmissions at this minimum forwarding probability, where the expectation is over both the forwarding protocol as well as the realization of the RGG. In comparison to probabilistic forwarding with no coding, our treatment of the problem indicates that, with a judicious choice of n, it is possible to reduce the expected total number of transmissions while ensuring a near-broadcast. Techniques from continuum percolation and ergodic theory are used to characterize the probabilistic broadcast algorithm.
Joint work with Navin Kashyap and D. Yogeshwaran.
Lyuben Lichev, The jump of the clique chromatic number of random graphs
The clique chromatic number of a graph is the smallest number of colors in a vertex coloring so that no maximal clique is monochromatic (ignoring isolated vertices). In 2016 McDiarmid, Mitsche and Pralat noted that around p ≈ n-1/2 the clique chromatic number of the random graph Gn,p changes by nΩ(1) when we increase the edge-probability p by no(1), but left the details of this surprising `jump' phenomenon as an open problem.The goal of the talk will be to explain how to resolve this polynomial `jump' of the clique chromatic number of the random graph Gn,p around edge-probability p ≈ n-1/2.
This talk is based on a joint work with Dieter Mitsche and Lutz Warnke.
Nandan Malhotra, Preferential Attachment Trees with Fitness
Preferential Attachment graphs are scale-free growing graphs used to model numerous real-world networks. We study directed Preferential Attachment Trees with fitness. We analyse the dependence of the asymptotic degree distribution on the additive fitness function by studying three regimes, namely the sublinear, linear and superlinear behaviour of the total fitness function. We also obtain almost sure convergence results for degree sequences scaled by an appropriate factor and for the maximal degree scaled by the same factor.
Azadeh Parvaneh, The non-plananr drainage networks with dependence and its scaling limit
In recent years, the convergence to the Brownian web (BW) for different systems of coalescing random walks has been considered in several papers. The Z^2 graph of the collection of the coalescing simple symmetric random walks was the first model for which, under a diffusive scaling, the convergence to the BW was obtained. Later there were extensions for other collections of coalescing random walks with possible crossing paths and/or with different sizes of jumps. In this talk, we focus on two discrete models, both of which are non-planar and with jumps which are dependent. We show that each of these models, under diffusive scaling, converges to the BW. To obtain this, we first obtain a Markovian renewal structure of the paths of the graph and then study the coalescence time of any two paths. Our method allows us to relax the condition required by Coletti and Valle (2014) in their study of the diffusive scaling limit of a generalized Howard's model of drainage.
Joint work with Prof. Rahul Roy (Indian Statistical Institute, Delhi Centre).
Pavel Tesemnikov, On the asymptotics for the minimal distance between extreme vertices in a generalised Barak — Erdos graph
Consider a random graph with a non-random set of vertices labelled by nonnegative integers and a random set of oriented edges: an edge from vertex i to vertex j is presented in the graph with probability pj-i, where pk = 0 for any k <= 0. Such a graph is referred to as generalised Barak — Erdos random graph. We are interested in exploring the asymptotic behaviour of the minimal path length between the vertices 0 and n depending on the asymptotics for pn, as n grows to infinity.
Harriet Walsh, New fermion models from map enumeration
We consider a family of maps, or graphs embedded in surfaces, which are enumerated by Hurwitz numbers. These numbers are partition functions for random integer partitions under certain deformations of the Plancherel measure, which correspond to free fermion models. The same measures were studied by Diaconis and Shahshahani in the context of random walks on the symmetric group, and were related to tau-functions of the Toda lattice integrable hierarchy by Okounkov. We find limit shapes of large random partitions and approximate asymptotics for unconnected Hurwitz numbers in new regimes. From this, we study the asymptotic enumeration of connected maps with high genus. Based on ongoing joint work with Guillaume Chapuy and Baptiste Louf.