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 types
Abstract: 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 cycles
Abstract: 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 symmetrisation
Abstract: We present a sufficient condition for the stability property of
extremal graph problems that can solved via Zykov's symmetrisation.
Our criterion is stated in terms of the analytic limit version of the
problem. We show that, for example, it applies to the inducibility
problem for an arbitrary complete bipartite graph B, which asks for
the 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 graphs
Abstract: In a joint work with Matthew Tointon, we study the large scale geometry of Cayley graphs (G,S) satisfying |S^n|<Cn^D|S| for some fixed, large enough n.
We show that it is quasi-isometric to some connected Lie group N equipped with a left-invariant sub-Finsler metric, where the multiplicative constant only depends on C and D, and the additive constant (the error term) is small in comparison to n. Moreover we give sharp bounds on the dimension and the homogeneous dimension of N.
Based on this analysis, we recover and strengthen a theorem of Tao describing the growth function of (G,S) for scales larger than n. Our main application is a quantitative version of a scaling-limit theorem due to Benjamini, Finucane and Tessera.
Matthew Tointon Approximate groups and persistence of polynomial growth.
Jan Volec On large multipartite subgraphs of H-free graphs.
Abstract: A long-standing conjecture of Erdos states that any n-vertex triangle-free graph can be made bipartite by deleting at most n^2/25 edges. In this talk, we study how many edges need to be removed from an H-free graph for a general graph H. Generalizing a result of Sudakov for 4-colorable graphs H, we show that if H is 6-colorable then G can be made bipartite by deleting at most 4n^2/25 edges. Moreover, this amount is needed only in the case G is a complete 5-partite graph with balanced parts. As one of the steps in the proof, we use a strengthening of a result of Furedi on stability of Turan's theorem. This is a joint work with P. Hu, B. Lidicky, T. Martins-Lopez and S. Norin.
