Teorie modelů, strukturální kombinatorika a algoritmy
Cíle projektu
Budeme studovat nově vznikající souvislosti teorie modelů a strukturální teorie grafů. Teorie modelů dává skupinu konceptů a nástrojů pro analýzu složitosti nekonečných struktur, které mají analogie i v analýze konečných strktur. Dlouhou dobu tyto metody vypadaly jen podobné, ale nedávné výsledky ukazují, že techniky teorie modelů lze aplikovat na konečné problémy a dostat tak klíčove definice strukturální teorie grafů. Tento přístup dává nové nástroje a techniky k dokazování výsledků v oblasti. Hlavní hypotéza, na kterou se zaměříme, je algoritmického charakteru: identifikuje určitou vlastnost, pocházející z teorie modelů, jako podmínku charakterizující třídy grafů, na kterých lze efektivně řešit širokou škálu algoritmických problémů (konkrétně ty, které jsou vyjádřitelné v prvním řádu logiky). Zatímco většina odborníků v oblasti přistupuje problému z kombinatorického hlediska, my plánujeme využít expertízu v oblasti teorie modelů. Zároveň plánujeme zjistit, jak se kombinatorické koncepty mohou vztáhnout zpět na problémy z teorie modelů.
Klíčová slova
model theorystabilityNIPgraph decompositionsfixed-parameter tractability
Veřejná podpora
Poskytovatel
Grantová agentura České republiky
Program
JUNIOR STAR
Veřejná soutěž
SGA0202400003
Hlavní účastníci
Univerzita Karlova / Matematicko-fyzikální fakulta
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
24-12591M
Alternativní jazyk
Název projektu anglicky
Model theory, structural combinatorics, and algorithms
Anotace anglicky
Our research will study the emerging connections between model theory and structural graph theory. Model theory provides a collection of concepts and tools for analyzing the complexity of infinite structures, and these are mirrored in the analysis of finite structures. For some time, this similarity seemed only analogical, but recent results have shown that the model-theoretic machinery can be finitized, and doing so recovers key definitions from structural graph theory and provides new and unified tools for proving results about them. The main conjecture that serves to focus our efforts is algorithmic in nature: it identifies a certain model-theoretic property as characterizing the graph classes on which a wide swath of algorithmic problems (namely, those expressible in first-order logic) can be efficiently solved. While most researchers active in the area approach from the combinatorial viewpoint, we plan to use our expertise to take a model-theoretic approach to this problem, and also to see how the combinatorial concepts can feed back into model theory.
Vědní obory
Kategorie VaV
ZV - Základní výzkum
OECD FORD - hlavní obor
10101 - Pure mathematics
OECD FORD - vedlejší obor
—
OECD FORD - další vedlejší obor
—
CEP - odpovídající obory
(dle převodníku)BA - Obecná matematika
Termíny řešení
Zahájení řešení
1. 1. 2024
Ukončení řešení
31. 12. 2028
Poslední stav řešení
B - Běžící víceletý projekt
Poslední uvolnění podpory
29. 2. 2024
Dodání dat do CEP
Důvěrnost údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Systémové označení dodávky dat
CEP25-GA0-GM-R
Datum dodání záznamu
21. 2. 2025
Finance
Celkové uznané náklady
14 077 tis. Kč
Výše podpory ze státního rozpočtu
14 077 tis. Kč
Ostatní veřejné zdroje financování
0 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
0 tis. Kč
Základní informace
Uznané náklady
14 077 tis. Kč
Statní podpora
14 077 tis. Kč
100%
Poskytovatel
Grantová agentura České republiky
OECD FORD
Pure mathematics
Doba řešení
01. 01. 2024 - 31. 12. 2028