Dan Kral (Masaryk University)

Graph limits

The theory of graph limits provides analytic tools to represent and study large networks/graphs. The theory has led to new views on a wide range of topics in mathematics and computer science, and opened new links between analysis, combinatorics, ergodic theory, group theory and probability theory.

We introduce this rapidly developing area of combinatorics and discuss several problems from extremal combinatorics when viewed through lenses of graph limits. In particular, we will present a counterexample to a conjecture of Lovász concerning finitely forcible optima, which was one of the two most cited conjectures in the theory of combinatorial limits. At the end of the talk, we will briefly discuss the relation of graph limits and the stochastic block model, a random graph model widely used in network science, and we then conclude with several open problems related to the presented notions

Serte Donderwinkel (Rijksuniversiteit Groningen)

Enumerating score sequences via integrated random walks

A score sequence of length $n$ is a non-decreasing sequence that can occur as the sequence of in-degrees of an orientation of the edges of the complete graph on $n$ vertices. We let $S_n$ be the number of score sequences of length $n$. The first bounds on $S_n$ were found by Erd\H{o}s and Moser in the sixties. The order of $S_n$ was obtained by Kim and Pittel (2000), who built on the work of Winston and Kleitman (1984). We improve their result and show that $S_n=(1+o(1))C4^n/n^{5/2}$. We rephrase the question in terms of a question on integrated random walks, that we then answer. This talk is based on joint work with Brett Kolesnik.

Fernando de Oliveira Filho (TU Delft)

Bounds for Grothendieck’s constant and the integrality gap of MAXCUT

I will describe infinite-dimensional convex optimization problems whose optimal values are the Grothendieck constant in fixed dimension or the integrality gap of MAXCUT in fixed dimension. There problems characterize the corresponding constants, and can be used to compute bounds for them.