Workshop: Structural Limits

The workshop will be centered about structural limits and should consist mainly from disscussions after some introductry talks.

The program starts at 10am (Monday-Wednesday) and 2pm (Monday-Tuesday), feel free to join.

Participants:

• Miklos Abert
• Sam Brunfeld
• Endre Csoka
• Gábor Elek
• Peter Frenkel
• Aranka Hrusková
• Matej Konecny
• Konrad Krolicki
• Gabor Kun
• Patrice Ossona de Mendez
• David Hartman
• Tomas Hons
• Laszlo Lovasz
• Jarik Nesetril
• Balazs Szegedy
• László Tóth
• Vilas Winstein

Report

Budapest May 25-28.
Structural Limits.

This DYNASNET miniworkshop was initiated by J. Nesetril and P. Ossona de Mendez and it was organized in Erdos centre in Budapest.
It was attended by Prague group representatives (Konecny, Hartman,Ossona de Mendez, Braunfeld, Hons) and most mebers of Bdapest group.

The scientific program included a short course (4 lectures) by Ossona de Mendez. This was complemented by short lectures by L. Lovasz, B. Szgedy (on Markov spaces which generalize graphops, which generalize S-graphons, which in turn
generalize graphons) and S. Braunfeld. There was time for disscussions which were very fruitful and led to some interesting development.

Here is the abstract of Ossona de Mendez minicourse:

Structural Limits

In this series of talks, we survey the contributions and intakes of a model-theoretic approach to limits of structures.
Structural convergence consists in the convergence, for each formula in a fixed fragment of first-order logic (FO), of the satisfaction probability of the formula when checked on a tuple of independently and uniformly chosen random elements (or, more generally, on iid elements). Bridges with classical notions of convergence, impacts of the selected fragment of FO driving the convergence as well as the essential importance of the chosen representation of the structures are exemplified through a number of examples, including permutations (represented either as a bijection or as two linear orders).  Three general representation theorems are given. The first one represents structural limits as  (Borel) probability distributions on the Stone space dual to the convergence driving fragment of FO, which are invariant under a special action group, generalizing in particular Aldous? exchangeable graph approach. In this setting, structural convergence is equivalent to the weak convergence of associated probability measures.
In the second theorem, the limits are represented using Loeb measures on the ultraproduct of the structures in the sequence. Though as is this result may seem highly theoretical, it finds a practical application by ensuring the consistency of some theory in Friedman?s extension of first-order logic, thus opening the way to the third representation theorem. This last representation is twofold: in a general setting, it ensures the existence of a measured Borel limit object (modeling) when the convergence is driven by (a bit more than) the fragment of single-variable formulas.

From this general version is deduced that a similar limit object exists for full structural convergence (i.e. FO-driven convergence) when the structures in the sequence are bound to a nowhere dense class of structures.
This minicourse is based on several papers of J. Nesetril and P. Ossona de Mendez (Memoires of AMS, J. Symbolic Logic, Random Str. and Algorithms).