Gadget Construction and Structural Convergence

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F25%3A00635684" target="_blank" >RIV/67985807:_____/25:00635684 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216208:11320/25:10496037

Výsledek na webu

<a href="https://doi.org/10.1007/s00493-025-00140-8" target="_blank" >https://doi.org/10.1007/s00493-025-00140-8</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00493-025-00140-8" target="_blank" >10.1007/s00493-025-00140-8</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Gadget Construction and Structural Convergence

Popis výsledku v původním jazyce

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. 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. We show that, when restricting to the set of sentences, the application of gadget construction on elementarily convergent sequences yields an elementarily convergent sequence. On the other hand, we show counterexamples witnessing that a generalization to the full first-order convergence is not possible without additional assumptions. We give several different sufficient conditions to ensure the full 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.

Název v anglickém jazyce

Gadget Construction and Structural Convergence

Popis výsledku anglicky

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. 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. We show that, when restricting to the set of sentences, the application of gadget construction on elementarily convergent sequences yields an elementarily convergent sequence. On the other hand, we show counterexamples witnessing that a generalization to the full first-order convergence is not possible without additional assumptions. We give several different sufficient conditions to ensure the full 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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Combinatorica

ISSN

0209-9683

e-ISSN

1439-6912

Svazek periodika

45

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

35

Strana od-do

15

Kód UT WoS článku

001444705500002

EID výsledku v databázi Scopus

2-s2.0-105000163725