Model theory, structural combinatorics, and algorithms
Project goals
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.
Keywords
model theorystabilityNIPgraph decompositionsfixed-parameter tractability
Public support
Provider
Czech Science Foundation
Programme
—
Call for proposals
SGA0202400003
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Contest type
VS - Public tender
Contract ID
24-12591M
Alternative language
Project name in Czech
Teorie modelů, strukturální kombinatorika a algoritmy
Annotation in Czech
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ů.
Scientific branches
Solution timeline
Realization period - beginning
Jan 1, 2024
Realization period - end
Dec 31, 2028
Project status
B - Running multi-year project
Latest support payment
Feb 29, 2024
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP25-GA0-GM-R
Data delivery date
Feb 21, 2025
Finance
Total approved costs
14,077 thou. CZK
Public financial support
14,077 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Recognised costs
14 077 CZK thou.
Public support
14 077 CZK thou.
0%
Provider
Czech Science Foundation
OECD FORD
Pure mathematics
Solution period
01. 01. 2024 - 31. 12. 2028