Teorie modelů, strukturální kombinatorika a algoritmy

JUNIOR STAR - GAČR GM24-12591M [Registrované výsledky] 2024 - 2028

Hlavní řešitel: Samuel Walker Braunfeld, Ph.D.

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 struktur. 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íčové 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ů.

Cíl projektu

  1. Plánujeme rozvíjet interakce teorie modelů a strukturální teorie grafů. Specificky chceme vyřešit (nebo o řešení se pokusit) hypotézu o třídách grafů umožňující efektivní algoritmy.