Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10422246" target="_blank" >RIV/00216208:11320/20:10422246 - isvavai.cz</a>

  • Výsledek na webu

    <a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=Q~AWcwuUkW" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=Q~AWcwuUkW</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1090/memo/1272" target="_blank" >10.1090/memo/1272</a>

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth

  • Popis výsledku v původním jazyce

    In this paper we introduce a general framework for the study of limits of relational structures and graphs in particular, which is based on a combination of model theory and (functional) analysis. We show how the various approaches to graph limits fit to this framework and that they naturally appear as &quot;tractable cases&quot; of a general theory. As an outcome of this, we provide extensions of known results. We believe that this puts these into a broader context. The second part of the paper is devoted to the study of sparse structures. First, we consider limits of structures with bounded diameter connected components and we prove that in this case the convergence can be &quot;almost&quot; studied component-wise. We also propose the structure of limit objects for convergent sequences of sparse structures. Eventually, we consider the specific case of limits of colored rooted trees with bounded height and of graphs with bounded tree-depth, motivated by their role as &quot;elementary bricks&quot; these graphs play in decompositions of sparse graphs, and give an explicit construction of a limit object in this case. This limit object is a graph built on a standard probability space with the property that every first-order definable set of tuples is measurable. This is an example of the general concept of modeling we introduce here. Our example is also the first &quot;intermediate class&quot; with explicitly defined limit structures where the inverse problem has been solved.

  • Název v anglickém jazyce

    A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth

  • Popis výsledku anglicky

    In this paper we introduce a general framework for the study of limits of relational structures and graphs in particular, which is based on a combination of model theory and (functional) analysis. We show how the various approaches to graph limits fit to this framework and that they naturally appear as &quot;tractable cases&quot; of a general theory. As an outcome of this, we provide extensions of known results. We believe that this puts these into a broader context. The second part of the paper is devoted to the study of sparse structures. First, we consider limits of structures with bounded diameter connected components and we prove that in this case the convergence can be &quot;almost&quot; studied component-wise. We also propose the structure of limit objects for convergent sequences of sparse structures. Eventually, we consider the specific case of limits of colored rooted trees with bounded height and of graphs with bounded tree-depth, motivated by their role as &quot;elementary bricks&quot; these graphs play in decompositions of sparse graphs, and give an explicit construction of a limit object in this case. This limit object is a graph built on a standard probability space with the property that every first-order definable set of tuples is measurable. This is an example of the general concept of modeling we introduce here. Our example is also the first &quot;intermediate class&quot; with explicitly defined limit structures where the inverse problem has been solved.

Klasifikace

  • Druh

    J<sub>imp</sub> - Článek v periodiku v databázi Web of Science

  • CEP obor

  • OECD FORD obor

    10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Návaznosti výsledku

  • Projekt

  • Návaznosti

    I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Ostatní

  • Rok uplatnění

    2020

  • 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ů

Údaje specifické pro druh výsledku

  • Název periodika

    Memoirs of the American Mathematical Society

  • ISSN

    0065-9266

  • e-ISSN

  • Svazek periodika

    263

  • Číslo periodika v rámci svazku

    1272

  • Stát vydavatele periodika

    US - Spojené státy americké

  • Počet stran výsledku

    109

  • Strana od-do

    1-109

  • Kód UT WoS článku

    000516766100001

  • EID výsledku v databázi Scopus

    2-s2.0-85080910455