univerzális algebra, gyenge többségi függvény, homomorfizmus probléma
Keywords in English
universal algebra, weak near-unanimity, constraint satisfaction problem
Discipline
Mathematics (Council of Physical Sciences)
100 %
Ortelius classification: Algebra
Panel
Mathematics and Computing Science
Department or equivalent
Bolyai Institute (University of Szeged)
Starting date
2008-10-01
Closing date
2011-10-31
Funding (in million HUF)
2.025
FTE (full time equivalent)
1.11
state
closed project
Summary in Hungarian
A pályázat célja egy új matematikai fogalom, a gyenge többségi függvény tulajdonságainak módszeres feltárása, és a kapott eredmények alkalmazása az elméleti számítástudományban, a gráfelméletben és az univerzális algebrában. Az első jelentős eredményt a gyenge többségi függvényekkel kapcsolatban csak 2006-ban fedezték fel (R. McKenzie és a pályázó kutató közös munkája), de már alkalmazták a 17-éves Bang-Jensen-Hell-sejtés bizonyításában, illetve Hell és Nešetřil egy 12-éve megjelent komplexitáselméleti problémájának megoldásában. Ezen és más eredmények rávilágítanak a klasszikus és univerzális algebra, a gráfelmélet és az algoritmikus komplexitáselmélet közötti szoros kapcsolatra. Mindezen szakterületek módszereinek és eszköztárának közös alkalmazásával szeretnék a következő kutatási témákban eredményt elérni:
(1) a dichotómiasejtés bizonyítása irányított fák és más irányított gráfosztályok esetén, (2) véges algebrák gyenge többségi függvényeinek leírása, és (3) többségi-kissebségi gyenge többségi függvénnyel rendelkező véges algebrák tanulmányozása
A tervezett kutatás részben külföldi kutatókkal való együttműködés keretében történik. A projekt során kapott eredményeket nemzetközi konferenciákon és nemzetközi matematikai folyóiratokban tesszük közzé.
Summary
The objective of the project is to systematically explore the properties of an emerging mathematical concept, called the weak near-unanimity operation, and to apply the obtained knowledge in theoretical computer science, graph theory and universal algebra. The first deep result on weak near-unanimity operations was discovered only in 2006 (in a joint paper of R. McKenzie and the principal investigator) but it was already employed to solve the 17-year-old Bang-Jensen and Hell conjecture and another problem in complexity theory posted 12 years ago by Hell and Nešetřil. These and other results highlight the strong bond between classical and universal algebra, graph theory and computational complexity theory. I intend to combine the ideas and methods of these fields to attack the following list of proposed research goals:
(1) solve the dichotomy conjecture for oriented trees and other classes of directed graphs, (2) describe the set of weak near-unanimity term operations of finite algebras, and (3) study finite algebras with a majority-minority weak near-unanimity operation.
A part of the research will be carried out in collaboration with mathematicians from abroad. The results of the project will be disseminated to the research community on international conferences and published in international mathematical journals.
Final report
Results in Hungarian
Az OTKA pályázatom benyújtása (2008. február 11) óta 8 cikkem jelent nemzetközi folyóiratokban, de ezek közül csak kettő cikk született a kutatási programban megadott témában a beszámolási időszak alatt, ezért a többi 6 megjelent cikket nem tüntettem fel a jelentésben. Ezen cikkeken kívül a kutatási tervnek megfelelően további 3 kézirat van publikálásra benyújtva, illetve egy kézirat született, amely nincsen még benyújtva. A kutatási időszakban összesen hat nemzetközi konferencián adtam elő, ezek közül négyen meghívott előadóként.
Az [1] cikkben egy irányított fákból álló speciális gráfosztályra, az úgynevezett speciális triádokra bizonyítjuk a homomorfizmus problémára vonatkozó dichotómia sejtés. A [2] cikkben algoritmust adunk arra, hogy láncok direkt szorzatában az azonos elemszámú ideálok melyikében maximális az elemek magasságának összege. A [3] kéziratban a korlátos szélességű és kevés részhatvánnyal rendelkező algebrákra vonatkozó kényszerkielégíthetőségi problémát megoldó algoritmusokat ötvöztem. A [4] kéziratban bebizonyítottuk a Valeriote sejtést reflexív irányított gráfokra. Az [5] kéziratban a Valeriote sejtés több ekvivalens megfogalmazását adtuk meg. A [6] kéziratban a CSP probléma egy teljesen új redukcióját vezettük be, amely segítségével újabb algebraosztályokra bizonyítható a dichotómia sejtés.
Results in English
Since the submission of my OTKA grant proposal (2008/08/11) I had eight articles appeared in international journals, but only two of them were on a topic listed in the project proposal. Therefore, I did not mention the other 6 in this report. Beside these articles I have 3 submitted manuscripts and one manuscript not jet submitted. During the three years of this research grant I have given 6 talks on international conferences, four of them were invited plenary talks.
In [1] we have proved the constraint satisfaction dichotomy conjecture for a special class of directed trees, for the class of special triads. In [2] we give an algorithm to determine the order ideal of a direct product of chains in which the number of elements equals a fixed integer and the sum of heights of elements is maximal. In [3] I have combined the algorithms solving the constraint satisfaction problem for bounded width algebras and for algebras of few subpowers. In [4] we have proved the Valeriote conjecture for reflexive directed graphs. In [5] we have given equivalent formulations of the Valeriote conjecture. in [6] we have introduced a completely new reduction of CSP problems that allowed the proof of the dichotomy conjecture for various new classes of algebras.
A kutatás helye megváltozott. Korábbi kutatóhely: Algebra és Számelmélet Tanszék (Szegedi Tudományegyetem), Új kutatóhely: Bolyai Intézet (Szegedi Tudományegyetem).
