Original title: Využití gadgetové konstrukce pro strukturální konvergenci
Translated title: Using gadget construction in structural convergence
Authors: Hons, Tomáš ; Hartman, David (advisor) ; Ossona de Mendez, Patrice (referee) ; Pultr, Aleš (referee)
Document type: Master’s theses
Year: 2023
Language: cze
Abstract: [cze] [eng]
Strukturální konvergence je framework konvergence grafů a relačních struktur zalo- žený na počítání pravděpodobnosti splnění formulí predikátové logiky. V práci navrhu- jeme gadgetovou konstrukci, která nalezla uplatnění v mnoha oblastech matematiky, jako metodu výroby konvergentních posloupností relačních struktur. Pro elementární a lokální konvergenci studujeme chování posloupnosti struktur vytvořených gadgetovou konstrukcí z konvergentních poslouností základních struktur a gadgetů. Ukazujeme, že elementární konvergence je vždy zachována, zatímco v případě lokální konvergence je potřeba dalších předpokladů, což ilustrujeme řadou příkladů. Dokazujeme několik postačujících podmínek pro zachování lokální konvergence. Jedna z nich říká, že posloupnost vytvořených struk- tur je lokálně konvergentní, pokud v posloupnosti základních struktur byly nahrazované hrany husté. Představené postačující podmínky částečně komplementujeme inverzními větami. 1 Structural convergence is a framework for convergence of graphs and relational struc- tures based on the probability of satisfaction of first-order formulas. We consider gadget construction, which is a ubiquitous tool in many areas of mathematics, as a method for constructing convergent sequences of structures. Both for elementary and local conver- gence, we investigate the behavior of a sequence created by gadget construction from convergent sequences of base structures and gadgets. We show that elementary conver- gence is always preserved while additional assumptions are necessary for local convergence as witnessed by several examples. We give various different conditions that ensure local convergence. One of them states that the resulting sequence is local convergent if the replaced edges are dense in the sequence of base structures. The sufficient conditions are partially complemented by inverse theorems. 1
Keywords: structural convergence|gadget construction|graph limits|model theory; strukturální kovergence|gadgetová konstrukce|grafové limity|teorie modelů

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/185007

Permalink: http://www.nusl.cz/ntk/nusl-535725


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses