A reminder: this is today.
On 20 February 2023 09:39:15 CET, Mykhaylo Tyomkyn tyomkyn@kam.mff.cuni.cz wrote:
Dear all,
There will be a noon seminar this Thursday, 23 February: a prize lecture given by Tomáš Hons, one of the two winners of the Jirka Matousek prize 2022. Please find the talk details below.
Best regards, Misha Tyomkyn.
Gadget construction and structural convergence Tomáš Hons (Matousek prize lecture) Charles University February 23, 2023, 12:20 in S6
Abstract Nešetřil and Ossona de Mendez recently proposed a new definition of graph convergence called structural convergence. The structural convergence framework is based on the probability of satisfaction of logical formulas from a fixed fragment of first-order formulas. The flexibility of choosing the fragment allows to unify the classical notions of convergence for sparse and dense graphs. Moreover, it is possible to generalize the graph convergence to convergence of arbitrary L-structures where L is a fixed language. Since the field is relatively young, the range of examples of convergent sequences is limited and only a few methods of construction are known. Our aim is to extend the variety of constructions by considering the gadget construction that appears, e.g., in studies of homomorphisms. In particular, the gadget construction is a natural way of transforming a given structure into a structure of a different language. We show that the gadget construction works well with the structural convergence when restricting to the set of sentences. For the general case, we show counterexamples witnessing that a generalization to the full first-order convergence is not possible without additional assumptions. Moreover, we give several different sufficient conditions to ensure the convergence; one of them states that the resulting sequence is first-order convergent if the replaced edges are dense in the original sequence of structures.
TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz