Working Seminar on Formal Models, Discrete Structures, and Algorithms

Finitely describable combinatorial limits

Daniel Kráľ (Warwick)

When: Thursday March 5, 2:00pm

Where: room C417


Theory of combinatorial limits, which has opened new links between analysis, combinatorics, computer science, group theory and probability theory, offers tools to approximate large discrete objects. This talk will be focused on limits of permutations and graphs that can be finitely described. First, we will answer a question of Graham whether quasirandomness of permutations is finitely describable. In relation to applications in extremal combinatorics, Lovasz and Szegedy (2011) conjectured that every finitely forcible (describable) graph limit must be well-structured. We will disprove the conjecture using a new method for constructing finitely forcible combinatorial limits we developed.

The talk will be self-contained and no previous knowledge of the area is needed.