International Workshop on Graph Limits 29 Jan-2 Feb 2018 Lyon (France)
 Main menu HELP @ Contact DESCRIPTION The International workshop on Graph Limits is part of the thematic semester "Graphs, groups and Dynamics" held in Lyon between September 2017 and February 2018. This workshop will follow directly an advanced school on graph limits.      Scientific committee Charles Bordenave Patrice Ossona de Mendez Jean-Sébastien Séréni Stéphan Thomassé Program   Tentative Schedule The room 1, place de l'école will open at 9h15 for discussion among participants. Each day, a slot at 16h, will be devoted to problem session/ progress report. The typical length of talk is 50' but speakers are welcome to shrink/expand. Extra talks/short communications are also welcome, please propose.   Monday 10h A. Shapira 11h D. Kral 14h L.M. Lovasz 15h M. Tointon 16h Open problems session.   Tuesday 10h G. Kun 11h R. Tessera 14h J. Hladky 15h X. Goaoc   Wednesday 10h A. Grzesik 11h A. Backhausz   Afternoon: If weather permits, we will have a walk in the "Vieux Lyon"   Thursday 10h O. Pikhurko 11h F. Pfender 14h  J. Volec 15h Y. Pehova   19h30 Diner Maison Gamboni   Friday 10h P. Ossona de Mendez 11h E. Csoka  13h30  Discussions  Abstracts Agnes Backhausz            On the graph limit approach to eigenvectors of random graphs Abstract: In a joint work with Balazs Szegedy, we used the graph limit approach to show that the empirical distribution of the approximate eigenvectors of random regular graphs is close to the Gaussian distribution. This result, the main ideas of our approach and some possible extensions for other families of random graphs would be presented in the talk.   Endre Csoka            Entropy inequalities on expanders Abstract: In the early 2000s Louis Bowen initiated a new era of entropy by introducing the f-invariant, and asymptotic entropy notion in regular trees, defying a decades-old belief that this is impossible. At the heart of his theory is an edge-vertex entropy inequality. This inequality has been the starting point of many recent results, including the Gamarnik-Sudan theorem on local algorithms and the Backhausz-Szegedy theorem about eigenvector delocalization. We will prove analogous inequalities in other Cayley graphs and finite graphs. Joint work with Balint Virag and Viktor Harangi.   Xavier Goaoc          Limits of order typesAbstract: I will discuss some geometric applications of ideas from the theory of graph limits, graphons and flag algebras. This is joint work with Alfredo Hubard, Rémi de Joannis de Verclos, Jean Sébastien Sereni, and Jan Volec. Andrzej Grzesik     Forcing cycles in directed graphs Abstract: Motivated by the well-known Caccetta-Haggkvist Conjecture, Kelly, Kuhn and Osthus made a conjecture on minimal semidegree forcing directed cycle of a given length and proved it for cycles of length not divisible by 3. In the talk we will present an overview of a proof of all the remaining cases of their conjecture. This is a join work with Roman Glebov and Jan Volec. Jan Hladky                    Comparing cut-distance and weak* convergence Abstract: The key theorem of Lovasz and Szegedy states that the set of cut-distance accumulation points of any sequence of graphons is nonempty. This theorem becomes a triviality when the cut-distance topology is replaced by the weak* topology. I will show how to get the former statement from the latter, thus relating the weak* topology and the cut-distance. Based on joint work with Dolezal (arxiv:1705.09160), and ongoing work with Dolezal, Grebik, Noel, Piguet, Rocha, Rozhon, Saumell. Dan Kral                    Uniqueness of optimal configurations in extremal combinatorics   Gabor Kun                Laszlo Miklos Lovasz                        Extremal graph theory and finite forcibility Abstract: We study the uniqueness of optimal solutions to extremal graph theory problems. Our main result is a counterexample to a conjecture of Lovasz. The conjecture is the following: every finite feasible set of subgraph density constraints can be extended further by a finite set of density constraints such that the resulting set is satisfied by a unique graphon (up to weak isomorphism).   Patrice Ossona de Mendez       Modeling limits Abstract: A sequence of graphs is FO-convergent if the probability of satisfaction of every first-order formula converges. A graph modeling is a graph, whose domain is a standard probability space, with the property that every definable set is Borel. It was known that FO-convergent sequences of graphs do not always admit a modeling limit, and it was conjectured that this is the case if the graphs in the sequence are sufficiently sparse. Precisely, two conjectures were proposed: 1) If a FO-convergent sequence of graphs is residual, that is, if for every integer $d$ the maximum relative size of a ball of radius $d$ in the graphs of the sequence tends to zero, then the sequence has a modeling limit. 2)  A monotone class of graphs $\mathcal C$ has the property that every FO-convergent sequence of graphs from $\mathcal C$ has a modeling limit if and only if $\mathcal C$ is nowhere dense, that is, if and only if for each integer $p$ there is $N(p)$ such that  the $p$th subdivision of the complete graph on $N(p)$ vertices does not belong to $\mathcal C$. In this talk we present the proof of  both conjectures. This solves some of the main problems in the area and among others provides an analytic characterization of the nowhere dense--somewhere dense dichotomy.   Yanitsa Pehova                Decomposing graphs into edges and triangles   Florian Pfender                Inducibility of cyclesAbstract: In 1975, Pippenger and Golumbic observed that the iterated balanced blow up of a graph gives a good lower bound for the maximal density of induced copies of that graph in any large graph. It was unclear if that bound is sharp for any graph other than trivial examples. They conjectured that cycles of length at least 5 will be such examples.Recently, Fox, Huang and Lee, and independently Yuster showed that almost all (large) graphs match this bound by studying random and pseudo random graphs. In this talk, we will further explore this question for cycles. With the help of flag algebras, we are able to answer the question fully for 5-cycles, and asymptotically for 6- and 7-cycles. We also have exact results when we restrict ourselves to triangle free graphs.   For longer cycles, Pippenger and Golumbic provided an upper bound that is off by a factor of 2e. Recently, this bound was improved by Hefetz and Tyomkyn to about 1.5e, and then further to 2 by Kral', Norin and Volec. We have a very short proof for the weaker bound of e which may give additional insights, and we also have bounds of 1.5 for directed cycles in directed graphs, and the exact bound for triangle free directed cycles. This is joint work with Bernard Lidicky.       Oleg Pikhurko         Stability via symmetrisationAbstract: We present a sufficient condition for the stability property ofextremal graph problems that can solved via Zykov's symmetrisation.Our criterion is stated in terms of the analytic limit version of theproblem. We show that, for example, it applies to the inducibilityproblem for an arbitrary complete bipartite graph B, which asks forthe maximum number of induced copies of B in an n-vertex graph.Joint work with Hong Liu, Maryam Sharifzadeh and Katherine Staden.       Asaf Shapira                    A Generalized Turán Problem and its Applications   Romain Tessera        Gromov-Hausdorff limits of rescaled Cayley graphsAbstract: In a joint work with Matthew Tointon, we study the large scale geometry of Cayley graphs (G,S) satisfying |S^n|
 Online user: 1