BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Eurandom - ECPv5.0.1//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:VTIMEZONE
TZID:UTC
BEGIN:STANDARD
TZOFFSETFROM:+0000
TZOFFSETTO:+0000
TZNAME:UTC
DTSTART:20200101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;VALUE=DATE:20200406
DTEND;VALUE=DATE:20200410
DTSTAMP:20200219T001324
CREATED:20190613T065326Z
LAST-MODIFIED:20200210T081621Z
UID:2733-1586131200-1586476799@www.eurandom.tue.nl
SUMMARY:Graph Limits
DESCRIPTION:Summary\nThe workshop will address both the basic theory and the applications of graph limits\, focusing on graphons and graphexes\, as well as various applications. In the last few years several beautiful and exciting developments have taken place in this area. It is therefore time to bring together researchers from different fields\, including probability theory\, combinatorics\, statistics and algorithmics. \nThe workshop will run from Monday morning 09.00 am till Thursday afternoon 17.00 pm \nSponsors\n \nOrganisers\n\n\n\nChristian Borgs\nUniversity of California\, Berkeley\n\n\nJennifer Chayes\nUniversity of California\, Berkeley\n\n\nSouvik Dhara\nMIT Mathematics and Microsoft Research\n\n\nRemco van der Hofstad\nNETWORKS (TU Eindhoven)\n\n\nFrank den Hollander\nNETWORKS (Leiden University)\n\n\nViresh Patel\nNETWORKS (University of Amsterdam)\n\n\n\nSpeakers\n\n\n\nSiva Athreya\nIndian Statistical Institute\, Bangalore\n\n\nMorgane Austern\nMicrosoft Research\n\n\nAgnes Backhausz\nEötvös Loránd University\n\n\nSourav Chatterjee\nStanford University\n\n\nPéter Csikvári\nEötvös Loránd University\n\n\nJan Hladky\nCzech Academy of Sciences\n\n\nOlga Klopp\nCNRS\n\n\nDaniel Kral\nMasaryk University and University of Warwick\n\n\nJoonkyung Lee\nUniversität Hamburg\n\n\nLászló Lovász\nEötvös Loránd University\n\n\nAsaf Nachmias\nTel Aviv University\n\n\nSofia Olhede\nUniversity College London\n\n\nKavita Ramanan\nBrown University\n\n\nAdrian Roellin\nNational University of Singapore\n\n\nSubhabrata Sen\nHarvard University\n\n\nJoel Spencer\nNew York University\n\n\nJan Volec\nMasaryk University\n\n\nMei Yin\nDenver University\n\n\nChristina Lee Yu\nCornell University\n\n\nIlias Zadik\nNew York University\n\n\n\nAbstracts\nSiva Athreya \nGraphon dynamics from population genetics\nIn this talk we shall discuss a natural class of dynamics in dense networks arising from resampling in multi-type populations. We consider sequence of finite graphs whose dynamics are governed by the empirical type distribution of the whole population at that time and in the large-population-size limit this dynamics converges to a random process in the space of graphons. This is joint work with Frank den Hollander and Adrian Rollin \n \nAgnes Backhausz \nAction convergence of graphs and random matrices\nThe notion of action convergence was proposed to find limit objects for certain sequences of (either deterministic or random) graphs and matrices\, which are far from being sparse and dense as well. This approach unifies several concepts of graph limit theory (e.g. local-global convergence of bounded degree graphs\, and dense graph convergence)\, associates limit objects to graph sequences of intermediate density (e.g. hypercubes). Moreover\, it can be applied to solve problems about the eigenvectors of random sign matrices (in which all entries are independent\, but the norm of the matrix is much smaller than the norm of the adjacency matrix of an Erdos--Renyi graph). The goal of the talk is to present this convergence notion\, the limit objects (which are bounded operators of a special form\, and general representations of graphons and graphings) and connections to random matrices. Joint work with Balazs Szegedy. \n \nOlga Klopp \nLink Prediction in Sparse Graphon Model\nOur work focuses on the study of networks generated under the sparse graphon model with missing observations. In this setting\, the problem of es- timating the matrix of connections probabilities is of particular interest. Our results find a natural application in predicting the existence of non-observed edges\, a commonly encountered problem called link prediction. Interaction net- works are often incomplete\, as detecting interactions can require significant experimental effort. Instead of exhaustively testing for every connection\, we deduce the pairs of agents which are most likely to interact based on the relations already recorded and on available covariates. When these estimations are precise enough\, testing for these interactions would enable scientists to establish the network topology while substantially reducing the costs. \n \nDaniel Kral \nUniqueness of combinatorial limits\nWe will present several results concerning combinatorial structures that are determined by finitely many density constraints. First\, we will show that such graph limits can have arbitrarily complex structure in a strong sense. We use this result to provide a counterexample to a conjecture of Lovasz that optimal solutions to extremal graph theory problems can be made asymptotically unique by introducing finitely many additional constraints.\nAt the end of the talk\, we focus on limits corresponding to quasirandom combinatorial structures. For graphs\, it is well-known that quasirandomness is characterized by the edge density and the density of C_4. An analogous result holds for permutation: a permutation is quasirandom if and only if the density of every 4-pattern is 1/24+o(1). We strengthen the results by showing that a permutation is quasirandom if and only if the sum of the densities of eight specific 4-patterns is 1/3+o(1)\, and we characterize all sets of 4-patterns with this property.\n(joint with T. Chan\, J. Cooper\, A. Grzesik\, L. M. Lovasz\, T. Martins\, J. Noel\, Y. Pehova\, M. Sharifzadeh\, J. Sosnovec and J. Volec) \n \nJoonkyung Lee \nConvex graphon parameters and graph norms\nSidorenko's conjecture states that the number of copies of a bipartite graph H in a graph G is asymptotically minimised when G is a quasirandom graph. A notorious example where this conjecture remains open is when H=K_{5\,5}∖C_{10}. It was even unknown whether this graph possesses the strictly stronger\, weakly norming property.\nWe take a step towards understanding the graph K_{5\,5}∖C_{10} by proving that it is not weakly norming. More generally\, we show that 'twisted' blow-ups of cycles\, which include K_{5\,5}∖C_{10} and C_{6}□K_{2}\, are not weakly norming. This answers two questions of Hatami. The method relies on the analysis of Hessian matrices defined by graph homomorphisms\, by using the equivalence between the (weakly) norming property and convexity of graph homomorphism densities. We also prove that K_{t\,t} minus a perfect matching\, proven to be weakly norming by Lovász\, is not norming for every t>3.\n(joint work with Bjarne Schülke) \n \nLászló Lovász \nLimits of graph sequences of intermediate density\nConvergence and limit objects have been defined mainly in the two extreme cases: dense graphs and bunded-degree graphs. The intermediate cases have attracted considerable interest\, but it has been difficult to obtain satisfactory results. Recently it has emerged that Markov chains on measurable spaces\, perhaps endowed with some additional structure like a measure on the underlying set\, can capture many limiting properties of growing graph sequences. Furthermore\, one can extend several graph theoretical concepts and basic theorems (on flows\, harmonic functions\, mixing of random walks\, etc.) to this general setting.\n(joint work with Agnes Backhausz\, David Kunszenti-Kovács\, and Balazs Szegedy) \n \nAdrian Roellin \nHigher-order fluctuations in dense graph limit theory\nDense graph limit theory is now a well-established approach to describe the structure of large dense networks. While this theory is mainly concerned with the first-order behaviour of graphs in the same way as the Law of Large Numbers describes the first order behaviour of sums of random variables in classical limit theory\, a theory to describe second or even higher-order fluctuations around those first order limits has not yet been developed. However\, we argue that the tools to understand these fluctuations have already been around since the 90s\, although in the more abstract form of generalised U-statistics. We discuss how this theory can be used to describe fluctuations of large graphs\, and we complements these results with rates of convergence using Stein’s method and with generalisations that go beyond the framework of generalised U-statistics\, but which are still relevant to dense graph limit theory. \n \nSubhabrata Sen \nLarge deviations for dense random graphs: beyond mean-field\nIn a seminal paper\, Chatterjee and Varadhan derived an LDP for the dense Erdös-Rényi random graph\, viewed as a random graphon. This directly provides LDPs for continuous functionals such as subgraph counts\, spectral norms\, etc. In contrast\, very little is understood about this problem if the underlying random graph is inhomogeneous or constrained. In this talk\, we will take some preliminary steps in this direction\, and study large deviations for uniform random graphs with given degrees.\n(joint work with Souvik Dhara) \n \nJoel Spencer \n(Some) Finitely Forcible Graphon\nQuasirandomness is a robust concept which is implied by the "correct" counts of edges and 4-cycles for G(n\,p). We discuss the seminal work of Chung\, Graham and Wilson. We give a relatively simple argument that random multipartite graphs are finitely forcible. \n \nMei Yin \nPerspectives on exponential random graphs\nExponential random graphs are powerful in the study of modern networks. By representing a complex global configuration through a set of tractable local features\, these models seek to capture a wide variety of common network tendencies. This talk will look into the asymptotic structure of weighted exponential random graphs and formulate a quantitative theory of phase transitions. The main techniques that we use are variants of statistical physics. Based on joint work with multiple collaborators. \nMore information will follow as it becomes available. \nRegistration\nLink to registration form \n \n
URL:https://www.eurandom.tue.nl/event/graph-limits/
LOCATION:MF 11-12 (4th floor MetaForum Building\, TU/e)
CATEGORIES:Workshop
END:VEVENT
END:VCALENDAR