 |
Algebraic invariants of omega-categorical structures
|
Help 
Print 
|
Here you can view and search the projects funded by NKFI since 2004
Back »
|
| |
Details of project |
|
|
| Identifier |
125160 |
| Type |
PD |
| Principal investigator |
Pongrácz, András |
| Title in Hungarian |
Omega-kategorikus struktúrák algebrai invariánsai |
| Title in English |
Algebraic invariants of omega-categorical structures |
| Keywords in Hungarian |
Algebra, modellelmélet, Ramsey, omega-kategorikus, automorfizmus, endomorfizmus, polimorfizmus, csoport, monoid, klón, számítástudomány, bonyolultság |
| Keywords in English |
Algebra, model theory, Ramsey, omega-categorical, automorphism, endomorphism, polymorphism, group, monoid, clone, computer science, complexity |
| Discipline |
| Mathematics (Council of Physical Sciences) | 100 % | | Ortelius classification: Algebra |
|
| Panel |
Mathematics and Computing Science |
| Department or equivalent |
Department of Algebra and Number Theory (University of Debrecen) |
| Starting date |
2017-09-01 |
| Closing date |
2020-08-31 |
| Funding (in million HUF) |
15.219 |
| FTE (full time equivalent) |
2.10 |
| state |
closed project |
Summary in Hungarian A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.
A pályázat a modellelmélet, az algebra és a bonyolultságelmélet határterületén helyezkedik el.
Célunk omega-kategorikus struktúrák reduktjainak és bővítéseinek megértése. Egy sejtés szerint minden véges nyelv feletti homogén relációs struktúra elsőrendben bővíthető egy olyan omega-kategorikus struktúrává, melynek véges részstruktúráinak rendszerére teljesül a Ramsey-tétel. Ennek igazolásával nagy előrelépést tennénk a reduktok vizsgálatában (Thomas-sejtés), az automorfizmuscsoportok univerzális minimális folyamának meghatározásában (Kechris, Pestov és Todorcevic tétele alapján), és az omega-kategorikus struktúrák CSP-ire vonatkozó dichotómiasejtésben (a polimorfizmusklón segítségével). A sejtést egy új szemlélettel közelítenénk meg, mely az omega-kategorikus struktúrák másodrendű típusainak vizsgálatán alapul. A konkrét struktúrák közül érdeklődésre tart számot egy olyan homogén, sűrű, szemilineáris rendezés reduktjainak meghatározása, mely mindenhol kétfelé ágazik el.
Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.
- Thomas-sejtés: minden véges nyelv feletti homogén relációs struktúrának véges sok reduktja van elsőrendű átdefiniálhatóság erejéig.
- Bodirsky-Pinsker sejtés: minden véges nyelv feletti homogén relációs struktúrának van omega-kategorikus Ramsey bővítése.
- Megvizsgáljuk a homogén, sűrű, szemilineáris rendezés reduktjait, mely mindenhol kétfelé ágazik el, ezzel igazolva a dichotómiatételt a CSP-k megfelelő részosztályára.
- Omega-kategorikus struktúrák másodrendű típusainak vizsgálata, ezek kapcsolata a fenti sejtésekkel.
- Ramsey-bővítések, Ramsey-fokok, Ramsey-számok meghatározása különböző konkrét esetekben.
- Rekonstruálhatósági kérdések vizsgálata, pl. a racionális számok rendezésének endomorfizmusmonoidjára, polimorfizmusklónjára, és a Bar-klónra.
- Keresünk egy egyszerű azonosságot, ami kizárja, hogy a polimorfizmusklón a triviális klónba képezhető legyen homomorf módon, és szükségképpen teljesül ha nincs ilyen homomorfizmus.
- Kiterjesztett CSP problémák vizsgálata többféle kvantort megengedve, pl. a véletlen gráfon vagy a racionális számok rendezéséből definiálható struktúrákon.
- Egyéb algebrai invariánsokkal és struktúrákkal kapcsolatos kombinatorikai és leszámlálási problémák vizsgálata.
Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!
A tervezett kutatás három különböző matematikai tudományág, a modellelmélet, az algebra és a bonyolultságelmélet határterületén zajlik. Így az eredmények is több matematikai terület gyarapodását eredményezhetik.
A homogén struktúrák témakörben elért bármely eredmény a modellelméletet (közelebb kerülni a Thomas-sejtés vagy a Bodirsky-Pinsker sejtés bizonyításához) és az elméleti számítástudományt (végtelen célstruktúrájú CSP-k visszavezetése véges célstruktúrájúakra) is előbbre viszi. Hosszú távú célunk, hogy olyan modellelméleti módszereket dolgozzunk ki, melyek mindkét tudományterületen alkalmazhatóak, és hogy további kapcsolatot teremtsünk a két terület között. A bonyolultságelméletben felmerülő kérdéseknek rendre vannak gyakorlati alkalmazásai: a polinomidőben megoldható problémák elemzésével érdekes gyors algoritmusokat kapunk fontos problémákra. Jelen tudásunk szerint az NP-teljes problémák megoldására nincs gyors algoritmus, csak közelítő eredmények kaphatók a gyakorlatban elfogadható időn belül. Fontos, hogy egy számítási feladat előtt tisztában legyünk vele, hogy gyors algoritmust érdemes-e keresni, vagy meg kell elégednünk a közelítő eredménnyel. Erre kínál megoldást az univerzális algebrai megközelítés.
A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.
Az utóbbi két évtizedben egyre nagyobb szerep jut az algebrai módszereknek algoritmikus-, bonyolultságelméleti- és számítástudományi kérdésekben. Kutatásainkban az algebrában és modellelméletben felmerülő, valamint az algebrai módszerekkel megfogható számítási problémákat és e problémák bonyolultságelméleti megközelítését vizsgáljuk. Elsősorban általános és klasszikus algebrai módszereket igénylő kérdésekkel foglalkozunk.
Ilyen a végtelen homogén struktúrák (pl: véletlen gráf) és azok reduktjainak és bővítéseinek vizsgálata. Számos klasszikus számítási probléma (pl. gráfok 3-színezhetősége vagy irányított gráfok körmentességének eldöntése) egységesen kezelhető ilyen struktúrák segítségével, lehetővé téve ezek bonyolultságának egyidejű meghatározását, akár végtelen soknak is egyszerre.
| Summary Summary of the research and its aims for experts
Describe the major aims of the research for experts.
One goal is to understand reducts and expansions of omega-categorical structures. It is conjectured that every homogeneous relational structure in a finite language can be expanded to an omega-categorical Ramsey structure. This result would be highly applicable in the classification of reducts of structures (Thomas conjecture), in computing the universal minimal flow of automorphism groups (by a theorem of Kechris, Pestov and Todorcevic), and in the dichotomy conjecture for CSPs of omega-categorical structures (by analysing the polymorphism clone). We approach the conjecture with a new perspective, by studying second-order types of omega-categorical structures. We also test the general conjectures on certain concrete structures, e.g., reducts of the universal, homogeneous, binary branching, dense semilinear order are of particular interest.
What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.
- Thomas conjecture: every homogeneous relational structure in a finite language has finitely many reducts up to first-order interdefinability.
- Bodirsky-Pinsker conjecture: every homogeneous relational structure in a finite language has an omega-categorical Ramsey expansion.
- Classification of reducts of the universal, homogeneous, binary branching, dense semilinear order, thereby verifying a special case of the dichotomy conjecture.
- Investigation of second order types over omega-categorical structures, and connections of these with the above conjectures.
- Determining Ramsey expansions, Ramsey degrees, Ramsey numbers in certain concrete cases.
- We study reconstruction notions for omega-categorical structures. Among others, the endomorphism monoid and polymorphism clone of the order of the rational numbers and the Bar clone seem particularly interesting.
- Searching for clone identities that are obstructions of the existence of a homomorphism to the trivial clone.
- Investigating the complexity of extended CSP problems where different quantifiers are allowed, e.g., for reducts of the random graph or the order of the rational numbers.
- Studying combinatorial and enumerative problems related to algebraic invariants and structures.
What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.
Any result in the theory of homogeneous structures (Thomas conjecture, Bodirsky-Pinsker conjecture) would be beneficial for theoretical computer science (CSPs of omega-categorical structures), as well. On the long run, we plan to develop methods that are useful for both areas and to find further connections between them.
All computational complexity problems have potential practical applications: polynomial-time solvable problems provide interesting fast algorithms. The state-of-the-art methods for solving NP-complete problems are slow, only approximations are available in a reasonable amount of time. Hence, it is important to know if a computational problem is hard, so that we do not waste time looking for fast algorithms to solve it. By using the universal algebraic method, this is sometimes possible.
Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.
In the past two decades, there are more and more algebraic methods applied in algorithmic problems, complexity questions and computer science. Our research focuses on those computational problems (and their complexity) that are related to algebra and model theory. We are primarily working on problems whose investigation require general and classical algebraic methods.
The investigation of reducts and expansions of infinite homogeneous structures (e.g., random graph) is such a topic. Numerous classical computational problems (e.g., 3-colourability of graphs or acyclicity of digraphs) can be treated in a universal way, making it possible to simultaneously determine the complexity of such problems, possibly infinitely many of them at once.
|
|
|
|
|
|
|
|
|
|
