BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Eurandom - ECPv4.6.7//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Eurandom
X-ORIGINAL-URL:https://www.eurandom.tue.nl
X-WR-CALDESC:Events for Eurandom
BEGIN:VEVENT
DTSTART;VALUE=DATE:20170911
DTEND;VALUE=DATE:20170916
DTSTAMP:20171217T113644
CREATED:20170802T114739Z
LAST-MODIFIED:20170908T094920Z
UID:562-1505088000-1505519999@www.eurandom.tue.nl
SUMMARY:Randomness and Graphs : Processes and Structures
DESCRIPTION:Sponsored by: \n \n \n \nIn the most general formulation\, a random geometric graph is what you get if you take a random set of points in some metric space and you join pairs of points depending on some rule (which may include additional randomness). A special case is the Gilbert model where we take n points uniformly at random in the square (or d-dimensional hypercube) and connect two points if the distance is less than r. The model is named after E.N. Gilbert who defined a very similar model in 1961.\nImage and caption by Tobias Müller (http://www.staff.science.uu.nl/~muell001/). \n \n\nSummary\nOrganizers\nSpeakers\nProgramme\nAbstracts\nRegistration\nPractical Information\n\nSummary\nThe aim of this workshop is to bring together researchers to discuss the latest developments in various topics at the interface of probability\, combinatorics\, and algorithms including amongst others:\n– Random graphs and matrices\n– Threshold phenomena\n– Discrete random processes and algorithms on graphs \nOrganizers\n\n\n\nLuca Avena\nLeiden University\n\n\nJop Briët\nCWI\n\n\nRemco van der Hofstad\nTU Eindhoven\n\n\nTim Hulshof\nTU Eindhoven\n\n\nJúlia Komjáthy\nTU Eindhoven\n\n\nViresh Patel\nUniversity of Amsterdam\n\n\nGuus Regts\nUniversity of Amsterdam\n\n\n\nSpeakers\n\n\n\nPeter Allen\nLondon School of Economics\, Abstract\n\n\nGraham Brightwell\nLondon School of Economics\n\n\nElisabetta Candellero\nUniversity of Warwick\, Abstract\n\n\nMia Deijfen\nStockholm University\, Abstract\n\n\nCharilaos Efthymiou\nGoethe Universitat\, Abstract\n\n\nNikolaos Fountoulakis\n University of Birmingham\, Abstract\n\n\nDavid Gamarnik\nMIT\, Abstract\n\n\nAlexandre Gaudilliere\nCNRS\, Abstract\n\n\nChristina Goldschmidt\nUniversity of Oxford\, Abstract\n\n\nMark Jerrum\nQueen Mary\, University of London\, Abstract\n\n\nRoss Kang\nRadboud University Nijmegen\, Abstract\n\n\nMalwina Luczak\nQueen Mary\, University of London\, Abstract\n\n\nJason Miller\nUniversity of Cambridge\, Abstract\n\n\nTobias Muller\nUtrecht University\, Abstract\n\n\nGuillem Perarnau\nUniversity of Birmingham\, Abstract\n\n\nWill Perkins\nUniversity of Birmingham\, Abstract\n\n\nBalázs Ráth\nBudapest University of Technology and Economics\, Abstract\n\n\nSanchayan Sen\nMcGill University\, Abstract\n\n\nPerla Sousi\nUniversity of Cambridge\, Abstract\n\n\nJoel Spencer\nCourant Institute (New York)\, Abstract\n\n\nAlexandre Stauffer\nUniversity of Bath\, Abstract\n\n\nDaniel Valesin\nUniversity of Groningen\, Abstract\n\n\nLutz Warnke\nGeorgia Institute of Technology\, Abstract\n\n\n\nProgramme\n(preliminary) \nTime schedule Randomness……… \n \nAbstracts\nPeter Allen\nA simple proof of Shamir’s conjecture\nI will present a simplified proof of Shamir’s conjecture\, using some ideas from Johannson\, Kahn and Vu and some new ideas.\n(joint work with Julia Boettcher\, Ewan Davies\, Matthew Jenssen\, Yoshiharu Kohayakawa and Barnaby Roberts) \nElisabetta Candellero\nPercolation and isoperimetric inequalities\nIn this talk we will discuss some relations between percolation on a given graph G and its geometry. There are several interesting questions relating various properties of G such as growth (or dimension) and the process of percolation on it. In particular we will look for conditions under which its critical percolation threshold is non-trivial\, that is: p_c(G) is strictly between zero and one. In a very influential paper on this subject\, Benjamini and Schramm asked whether it was true that for every graph satisfying dim(G) > 1\, one has p_c(G) < 1. We will explain this question in detail and present some recent results that have been obtained in this direction. This talk is based on a joint work with Augusto Teixeira (IMPA\, Rio de Janeiro\, Brazil). \nMia Deijfen\nCows on the move\nConsider an epidemic that spread in a population of moving particles on Z^d. The particles may infect each other upon direct contact\, but may also be infected via contaminated locations. We formulate a simple model incorporating this phenomenon and demonstrate that the presence of site contamination may have an impact on the epidemic spread. Specifically\, site contamination can cause a subcritical model to become supercritical\, and measures aimed at controlling site contamination thereby has the potential to suppress large outbreaks. We also discuss a number of open problems for the model\, and other versions of it. \nDavid Gamarnik\n(Arguably) Hard on Average Constraint Satisfaction Problems\nMany randomly generated constraint satisfaction problems exhibit an apparent gap between the optimal value\, which can be estimated by non-constructive means\, and the best values achievable by fast (polynomial time) algorithms. Through a combined efforts of mathematicians\, computer scientists and statistical physicists\, it became apparent that a potential and in some cases a provable obstruction for designing algorithms bridging this gap is an intricate geometry of nearly optimal solutions\, in particular the presence of a certain Overlap Gap Property (OGP). In this talk we demonstrate how for many such problems\, the onset of the OGP phase transition indeed nearly coincides with algorithmically hard regimes. Our examples will include the problem of finding a largest independent set of a graph\, finding a largest cut in a random hypergrah\, random NAE-K-SAT problem\, the problem of finding a largest submatrix of a random matrix\, and high-dimensional sparse linear regression problem in statistics.\n(joint work with Wei-Kuo Chen\, Quan Li\, Dmitry Panchenko\, Mustazee Rahman\, Madhu Sudan and Ilias Zadik) \nAlexandre Gaudilleire\nIntertwining wavelets\nWe use random spanning forests on arbitrary finite graphs to build approximate solutions of Markov process intertwining equations\, with localized linking measures\, that allow for defining a coarse grained version of the original network together with some “wavelet basis”. The associated multiresolution scheme leads to a numerically stable algorithm for compression and analysis of signals that are defined on the given graph.\n(joint work with L. Avena\, F. Castel and C. Mélot) \nCharis Efthymiou\nImproved bounds for sampling colorings of sparse random graphs\nWe study the mixing properties of the single-site Markov chain known as the Glauber dynamics for sampling k-colorings of a sparse random graph G(n\,d/n) for constant d. The best known rapid mixing results for general graphs are in terms of the maximum degree \Delta of the input graph G and hold when k>11\Delta/6 for all G. Improved results hold when k>\alpha\Delta for graphs with girth =>5 and \Delta sufficiently large where \alpha\approx 1.7632… is the root of \alpha=\exp(1/\alpha); further improvements on the constant \alpha hold with stronger girth and maximum degree assumptions.\nFor sparse random graphs the maximum degree is a function of n and the goal is to obtain results in terms of the expected degree d. The following rapid mixing results for G(n\,d/n) hold with high probability over the choice of the random graph for sufficiently large constant d. Mossel and Sly (2009) proved rapid mixing for constant k\, and Efthymiou (2014) improved this to k linear in~d. The condition was improved to k>3d by Yin and Zhang (2016) using non-MCMC methods.\nHere we prove rapid mixing when k>\alpha d where $\alpha\approx 1.7632… is the same constant as above. Moreover we obtain O(n^{3}) mixing time of the Glauber dynamics\, while in previous rapid mixing results the exponent was an increasing function in d. As in previous results for random graphs our proof analyzes an appropriately defined block dynamics to “hide” high-degree vertices. One new aspect in our improved approach is utilizing so-called local uniformity properties for the analysis of block dynamics. To analyze the “burn-in” phase we prove a concentration inequality for the number of disagreements propagating in large blocks.\n(joint work with Tom Hayes\, Daniel Stefankovic and Eric Vigoda) \nNikolaos Fountoulakis\nPercolation on random graphs with given degrees revisited\nWe consider the standard bond percolation process on a random graph with given degrees. We would like to sample a random graph uniformly at random from the set of all simple graphs with a given degree sequence. Thereafter\, its edges are deleted randomly and independently with probability 1−p. The question we consider is whether there a critical value p_c for the probability p\, such that when p crosses p_c a giant component emerges. We will give a rough characterisation of which degree sequences have such a critical value that is bounded away from 0\, as the order of the random graph grows. To this end\, we will avoid the use of the classic configuration model (and the restrictions it incurs)\, but make use of a recent approach developed by Joos\, Perarnau\, Rautenbach and Reed (Probability Theory and Related Fields\, to appear – also in proceedings of FOCS ’16). In particular\, this allows us to deal with degree sequences that have very heavy tails. (This is joint work with F. Joos and G. Perarnau.) \nChristina Goldschmidt\nVoronoi cells in the Brownian continuum random tree\n(and other unicellular continuum random maps)\nTake a uniform random tree with n vertices and select k of those vertices independently and uniformly at random; call them sites. (We assume that n is large and k is fixed\, so that with high probability the sites are distinct.) Find the associated Voronoi cells: for each vertex in the tree\, assign it to the cell of the site (or sites) which is closest in the graph distance. Now consider the vector of the proportions of the vertices lying in each of the k cells. We prove that this vector converges in distribution to the Dirichlet(1\,1\,…\,1) distribution (that is\, it is asymptotically uniform on the (k-1)-dimensional simplex). In fact\, this is most easily formulated as a result about the scaling limit of the uniform random tree\, namely the Brownian continuum random tree: if we pick k independent sites from the mass measure of the tree\, their Voronoi cells have masses which are jointly Dirichlet(1\,1\,…\,1) distributed. An analogue of this result also holds for (the scaling limit of) uniform unicellular random maps on surfaces of arbitrary genus.\n(joint work (in progress) with Louigi Addario-Berry\, Omer Angel\, Guillaume Chapuy and Éric Fusy) \nMark Jerrum\nRandom cluster dynamics for the Ising model is rapidly mixing\nWe show that the mixing time of Glauber (single edge update) dynamics for the random cluster model at q=2 is bounded by a polynomial in the size of the underlying graph. As a consequence\, the Swendsen-Wang algorithm for the ferromagnetic Ising model at any temperature has the same polynomial mixing time bound. \nRoss Kang\nGuarantees of sparse or dense subgraphs\nRamsey showed that any large enough graph contains a set of k vertices that forms a clique or a stable set. Quantitative estimates of “large enough” have underpinned the entire field of probabilistic/extremal graph theory. We consider a natural generalisation where we are happy with subsets that are dense (clique-like) or sparse (stable set-like) enough. More precisely\, how large must a graph be for it to always contain a set of k vertices that induces a subgraph either of minimum degree at least c(k-1) or of maximum degree at most (1-c)(k-1)? Something remarkable happens at c=1/2 and we investigate this phenomenon thoroughly\, partially answering a question of Erdos and Pach.\n(joint works with Eoin Long\, Janos Pach\, Viresh Patel and Guus Regts) \nMalwina Luczak\nExtinction time for the weaker of two competing stochastic SIS logistic epidemics\nWe consider a simple stochastic model for the spread of a disease caused by two virus strains in a closed homogeneously mixing population of size N. In our model\, the spread of each strain is described by the stochastic logistic SIS epidemic process in the absence of the other strain\, and we assume that there is perfect cross-immunity between the two virus strains\, that is\, individuals infected by one strain are temporarily immune to re-infections and infections by the other strain. For the case where one strain has a strictly larger basic reproductive ratio than the other\, and the stronger strain on its own is supercritical (that is\, its basic reproductive ratio is larger than 1)\, we derive precise asymptotic results for the distribution of the time when the weaker strain disappears from the population\, that is\, its extinction time. We further consider what happens when the difference between the two reproductive ratios may tend to 0.\n(joint work with Fabio Lopes) \nJason Miller\nConvergence of percolation on uniform quadrangulations\nLet Q be a uniformly random quadrangulation with simple boundary decorated by a critical (p=3/4) face percolation configuration. We prove that the chordal percolation exploration path on Q between two marked boundary edges converges in the scaling limit to SLE(6) on the Brownian disk (equivalently\, a Liouville quantum gravity surface). The topology of convergence is the Gromov-Hausdorff-Prokhorov-uniform topology\, the natural analog of the Gromov-Hausdorff topology for curve-decorated metric measure spaces. Our method of proof is robust and\, up to certain technical steps\, extends to any percolation model on a random planar map which can be explored via peeling. (joint work with E. Gwynne) \nTobias Muller\nLogic and random graphs\nWe say that a graph property is expressible in the “first order language of graphs” if it can be written as a logic sentence using the universal and existential quantifiers with variables ranging over the nodes of the graph\, the usual connectives AND\, OR\, NOT\, parentheses and the relations = and ~\, where x ~ y means that x and y share an edge. For example\, the property that G contains a triangle can be written as exists x\,y\,z : (x ~ y) AND (x ~ z) AND (y ~ z). A classical result of Glebskii et al. 1969 and indepently Fagin 1976 states that if one samples a graph on n vertices uniformly at random from all such graphs then every first order expressible graph property holds with probability tending to either zero or one (as n tends to infinity). Since then\, first order expressible properties have been studied extensively on the most commonly studied model of random graphs\, the Erdos-Renyi model. A number of very attractive and surprising results have been obtained\, and by now\nwe have a fairly full description of the behaviour of first order expressible properties on this model. After describing some of these results\, time permitting\, I will discuss some recent and ongoing work where we try to see what happens both in other models of random graphs (such as random planar graphs\, random perfect graphs\, random geometric graphs\, …) and when one considers other (i.e. “higher order”) logics.\n(joint works with S. Haber\, P. Heinig\, T. Luczak\, M. Noy\, A. Taraz) \nGuillem Perarnau\nManifolds are rare\nConsider a random triangulation obtained by randomly gluing all the facets of n tetrahedra by pairs. Gromov asked for the probability that the resulting triangulated topological space is homeomorphic to a 3-sphere. This question is motivated by the connections between general triangulations and quantum gravity theory. We show that the probability that a random coloured triangulation is homeomorphic to a 3-manifold is n−5n/6\, up to an exponential factor. Our result improves the previous bounds on the number of triangulated 3-spheres. It also generalises to manifolds of any dimension d ≥ 3\, unveiling some topological properties of the configuration model.\n(joint work with Guillaume Chapuy) \nWill Perkins\nPhase transitions and the cavity method \nOriginally developed by statistical physicists to understand the behavior of glassy materials\, the powerful but non-rigorous cavity method has subsequently been used to describe in great detail phase transitions in random graphs and random computational problems. Using random graph coloring and the stochastic block model as running examples\, I will describe how the cavity method pinpoints the condensation and information theoretic thresholds respectively\, and present some of the mathematical tools we can use to make the method rigorous in these cases.\n(joint work with Amin Coja-Oghlan\, Florent Krzakala\, and Lenka Zdeborova) \nBalázs Ráth\nA moment-generating formula for Erdős-Rényi component sizes \nThe central result of the talk is a new simple formula characterizing the distribution of the size of the connected component of a fixed vertex in the Erdős-Rényi random graph which allows one to give elementary proofs of some results of\n(a) Federico\, van der Hofstad\, den Hollander and Hulshof as well as Janson and Luczak about the susceptibility in the subcritical graph and\n(b) the central limit theorem of Barraez\, Boucheron and De La Vega for the size of the giant component in the supercritical graph. \nSanchayan Sen\nGeometry of probabilistic structures constructed on random regular graphs\nThe intrinsic geometry of several probabilistic structures constructed on different underlying discrete systems are believed to be universal. But mathematical results making this rigorous have been proven only very recently. We discuss two such recent results.\n(a) The minimal spanning tree (MST) constructed by assigning exchangeable weights to the edges of a random -regular graph: We prove scaling of distance which supports a prediction for the strong disorder regime. We further show that its scaling limit exists and has the same law as the scaling limit of the MST of the complete graph up to a scaling factor of \, and in particular\, is compact and has Minkowski dimension almost surely. Joint work with Louigi Addario-Berry.\n(b) The vacant set left by a random walk run on a random -regular graph when : We show that around the point of phase transition\, the components of the vacant set asymptotically behave like components of the complete graph under critical percolation\, i.e.\, the critical Erdos-Renyi random graph. This answers a question posed by Cerny and Teixeira.\nOur approach forms the main technical bedrock for the broader program of developing general universality theorems for such structures. We also discuss related open problems.\n(joint work with Shankar Bhamidi) \nPerla Sousi\nRandom walks on dynamical percolation\nWe study the behaviour of random walk on dynamical percolation. In this model\, the edges of a graph are either open or closed and refresh their status at rate μ\, while at the same time a random walker moves on G at rate 1\, but only along edges which are open. On the d-dimensional torus with side length n\, when the bond parameter is subcritical\, the mixing times for both the full system and random walker were determined by Peres\, Stauffer and Steif. I will talk about the supercritical case\, which was left open\, but can be analysed using evolving sets.\n(joint work with Y. Peres and J. Steif) \nJoel Spencer\nErdos-Renyi Revisited\nThe “double jump” at np=1 shown by Paul Erdos and Alfred Renyi nearly sixty years ago remains a bedrock of our studies of threshold phenomenon. The perspectives on their discovery\, however\, have changed over the decades.\nIn this semi-expository talk the speaker will discuss the various approaches to understanding of this “mother of all phase transitions.” \nAlexandre Stauffer\nMulti-particle diffusion limited aggregation\nWe consider a stochastic aggregation model on Z^d. Start with an infinite collection of particles located at the vertices of the lattice\, with at most one particle per vertex\, and initially distributed according to the product Bernoulli measure with parameter $\mu\in(0\,1)$. In addition\, there is an aggregate\, which initially consists of only one particle placed at the origin. Non-aggregated particles move as continuous time simple symmetric random walks obeying the exclusion rule\, whereas aggregated particles do not move. The aggregate grows indefinitely by attaching particles to its surface whenever a particle attempts to jump onto it. Our main result states that if on Z^d\, d at least 2\, the initial density of particles \mu is large enough\, then with positive probability the aggregate grows with positive speed.\n(joint work with Vladas Sidoravicius) \n \nDaniel Valesin\nPercolation on the stationary distribution of the voter model on Z^d\nThe voter model on $\Z^d$ is a particle system that serves as a rough model for changes of opinions among social agents or\, alternatively\, competition between biological species occupying space. When the model is considered in dimension 3 or higher\, its set of (extremal) stationary distributions is equal to a family of measures $\mu_\alpha$\, for $\alpha$ between 0 and 1. A configuration sampled from $\mu_alpha$ is a field of 0’s and 1’s on $\Z^d$ in which the density of 1’s is $\alpha$. We consider such a configuration from the point of view of site percolation on $\Z^d$. We prove that in dimensions 5 and higher\, the probability of existence of an infinite percolation cluster exhibits a phase transition in $\alpha$. If the voter model is allowed to have long range\, we prove the same result for dimensions 3 and higher; we also prove that\, if the range is taken to infinity\, then the critical percolation parameter converges to that of Bernoulli site percolation.\n(joint work with Balázs Ráth) \nLutz Warnke\nThe phase transition in the random d-process\nOne of the most interesting features of Erdös-Rényi random graphs is the `percolation phase transition’\, where the global structure intuitively changes from only small components to a single giant component plus small ones.\nIn this talk we discuss the percolation phase transition in the random d-process\, which corresponds to a natural algorithmic model for generating random regular graphs that differs from the usual configuration model (starting with an empty graph on n vertices\, the random d-process evolves by sequentially adding new random edges so that the maximum degree remains at most d).\nOur results on the phase transition solve a problem of Wormald from 1997\, and verify a conjecture of Balinska and Quintas from 1990.\n(joint work with Nick Wormald) \n \nRegistration\nRegistration for the workshop is free\, but compulsory: REGISTRATION FORM \nPractical Information\n● Venue\nEurandom\, Mathematics and Computer Science Dept\, TU Eindhoven\, \nDe Groene Loper 5\, 5612 AE EINDHOVEN\, The Netherlands \nEurandom is located on the campus of Eindhoven University of Technology\, in the MetaForum building\, 4th floor (more about the building). The university is located at 10 minutes walking distance from Eindhoven main railway station (take the exit north side and walk towards the tall building on the right with the sign TU/e).\nAccessibility TU/e campus and map. \n● Accommodation\nFor speakers\, we will take care of accommodation. Other attendees must make their own arrangements. \nOur preferred hotel is The Student Hotel Eindhoven. They offer 10% discount if you book with promocode\, please follow the link TSHE . \nFor hotels around the university\, please see: Hotels (please note: prices listed are “best available”). \nMore hotel options can be found on Tourist Information Eindhoven. \n● Travel\nFor those arriving by plane\, there is a convenient direct train connection between Amsterdam Schiphol airport and Eindhoven. This trip will take about one and a half hour. For more detailed information\, please consult the NS travel information pages. \nMany low cost carriers also fly to Eindhoven Airport. There is a bus connection to the Eindhoven central railway station from the airport. (Bus route number 401) For details on departure times consult Public Transport. \nThe University can be reached easily by car from the highways leading to Eindhoven. For details: Route and map TU/e campus. \n● Conference facilities \nConference room\, MetaForum Building “MF11 & 12”.\nThe meeting-room is equipped with a data projector\, an overhead projector\, a projection screen and a blackboard. Please note that speakers and participants giving an oral presentation are kindly requested to bring their own laptop or their presentation on a memory stick. \n● Conference Secretariat\nUpon arrival\, participants should register with the workshop officer\, and collect their name badges. The workshop officer will be present for the duration of the conference\, taking care of the administrative aspects and the day-to-day running of the conference: registration\, issuing certificates and receipts\, etc. \n● Cancellation\nShould you need to cancel your participation\, please contact Patty Koorn\, the Workshop Officer. \n● Contact\nMrs. Patty Koorn\, Workshop Officer\, Eurandom/TU Eindhoven\, koorn@eurandom.tue.nl \n
URL:https://www.eurandom.tue.nl/event/randomness-and-graphs-processes-and-structures/
LOCATION:Metaforum\, Eindhoven\, Netherlands
CATEGORIES:Workshop
END:VEVENT
END:VCALENDAR