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”

Decomposition horizons: from graph sparsity to model-theoretic dividing lines

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10477017" target="_blank" >RIV/00216208:11320/23:10477017 - isvavai.cz</a>

  • Výsledek na webu

    <a href="https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-030" target="_blank" >https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-030</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-030" target="_blank" >10.5817/CZ.MUNI.EUROCOMB23-030</a>

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    Decomposition horizons: from graph sparsity to model-theoretic dividing lines

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

    Low treedepth decompositions are central to the structural characterizations of bounded expansion classes and nowhere dense classes, and the core of main algorithmic properties of these classes, including fixed-parameter (quasi) linear-time algorithms checking whether a fixed graph is an induced subgraph of the input graph. These decompositions have been extended to structurally bounded expansion classes and structurally nowhere dense classes, where low treedepth decompositions are replaced by low shrubdepth decompositions. In the emerging framework of a structural graph theory for hereditary classes of structures based on tools from model theory, it is natural to ask how these decompositions behave with the fundamental model theoretical notions of dependence (alias NIP) and stability. In this work, we prove that the model theoretical notions of NIP and stable classes are transported by decompositions.

  • Název v anglickém jazyce

    Decomposition horizons: from graph sparsity to model-theoretic dividing lines

  • Popis výsledku anglicky

    Low treedepth decompositions are central to the structural characterizations of bounded expansion classes and nowhere dense classes, and the core of main algorithmic properties of these classes, including fixed-parameter (quasi) linear-time algorithms checking whether a fixed graph is an induced subgraph of the input graph. These decompositions have been extended to structurally bounded expansion classes and structurally nowhere dense classes, where low treedepth decompositions are replaced by low shrubdepth decompositions. In the emerging framework of a structural graph theory for hereditary classes of structures based on tools from model theory, it is natural to ask how these decompositions behave with the fundamental model theoretical notions of dependence (alias NIP) and stability. In this work, we prove that the model theoretical notions of NIP and stable classes are transported by decompositions.

Klasifikace

  • Druh

    D - Stať ve sborníku

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

    2023

  • 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 statě ve sborníku

    Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications

  • ISBN

    978-80-280-0344-9

  • ISSN

    2788-3116

  • e-ISSN

  • Počet stran výsledku

    7

  • Strana od-do

    216-222

  • Název nakladatele

    Masaryk University Press

  • Místo vydání

    Masaryk University, Brno

  • Místo konání akce

    Praha

  • Datum konání akce

    28. 8. 2023

  • Typ akce podle státní příslušnosti

    WRD - Celosvětová akce

  • Kód UT WoS článku