Department of Algebra and Number Theory (Eötvös Loránd University)
Participants
Fried, Ervin Kun, Gábor Prohle, Péter Radeleczki, Sándor Schmidt, Tamás Szabó, Csaba
Starting date
2003-01-01
Closing date
2007-06-30
Funding (in million HUF)
9.265
FTE (full time equivalent)
0.00
state
closed project
Final report
Results in Hungarian
Keith Kearnes és Kiss Emil könyvükben a kongruenciaszelídítés néhány eredményét terjesztik ki nem lokálisan véges varietásokra. Jellemzik azokat a varietásokat, melyekben teljesül nemtriviális kongruencia-azonosság, a négyszögletes kommutátorral, tiltott részhálóval és Malcev-feltételekkel is. Belátják, hogy ha egy ilyen varietás reziduálisan kicsi, akkor moduláris.
A Constraint Satisfaction Problem vizsgálatában Kun Gábor derandomizálta Feder és Vardi tételét, miszerint a CSP és az MMSNP osztályok ekvivalensek. A kapott expander-gráf konstrukció kombinatorikai szempontból is igen értékes. Kun és Nesetril kategóriaelméleti eszközöket vezettek be az MMSNP osztály vizsgálatához. A CSP dichotomia-sejtése univerzális algebrai problémává fogalmazható át. Itt Kun Gábor Benoit Larose-zal, Kiss Emil Matthew Valeriote-tal ért el részeredményeket.
Horváth Gábor, Szabó Csaba és Vértesi Vera társszerzőkkel az azonosság-ellenőrzési probléma bonyolultságát vizsgálták. Megoldották a gyűrűk esetét, belátták, hogy nem feloldható csoportokra a probléma coNP-teljes, és eredményeket értek el félcsoportokra is. Módszerük gráfok szinezési problémáinak interpretálása. Kun és Vértesi belátták, hogy a varietás-tagsági probléma nehéz is lehet.
Kun és Szabó topologikus módszert találtak részben rendezések vizsgálatára, mely speciális termek polinomidejű konstrukciójára és a CSP vizsgálatára is alkalmas. Fried Ervin, Radeleczki Sándor és Schmidt Tamás hálóelméleti vizsgálatokat folytattak.
Results in English
Keith Kearnes and Emil Kiss in their book extend results of Tame Congruence Theory to non-locally finite varieties. They characterize varieties that satisfy a nontrivial congruence identity, by the rectangular commutator, by a forbidden sublattice, and by Maltsev conditions, and prove that if such a variety is residually small, then it is modular.
In his investigation of the Constraint Satisfaction Problem Gabor Kun derandomized a result of Feder and Vardi, stating that the classes CSP and MMSNP are random equivalent. His construction of expander-graphs is independently important in combinatorics. Kun and Nesetril introduced category-theoretic tools to investigate MMSNP. The dichotomy conjecture of CSP can be reformulated as a problem in Universal Algebra. Gabor Kun with Benoit Larose and Emil Kiss with Matthew Valeriote obtained partial
results here.
Gabor Horvath, Csaba Szabo and Vera Vertesi investigated the complexity of the identity-checking problem with coauthors. They settled the problem for rings, proved that it is coNP-complete for nonsolvable groups, and have results on semigroups. Their method is the interpretation of graph-coloring problems. Kun and Vertesi proved that the variety membership problem can be hard.
Kun and Szabo discovered a topological method to investigate posets, which allows the construction of special terms in polynomial time, and is related to CSP, too. Ervin Fried, Sandor Radeleczki and Tamas Schmidt worked on problems in lattices.
Brouwer A; Horváth G; Molnár-Sáska I; Szabó Cs: On the three-rowed Chomp, INTEGERS, Electronic Journal of Combinatorial Number Theory, 5:11 pages, 2005
Szabó Cs; Vértesi V: The complexity of checking identities for finite matrix rings, Algebra Universalis 51:439-445, 2004
Radeleczki S: On certain Classes of nondistributive L_n lattices, In: Contributions to General Algebra 14, Klagenfurt 2004, pp. 145-150, 2004
Gratzer G; Quackenbush RW; Schmidt ET: Congruence-preserving extensions of finite lattices into isoform lattices, Acta Sci Math (Szeged) 70:473-494, 2004
Földes S; Radeleczki S: On interval decomposition lattices, Discussiones Mathematicae, General Algebra and Applications 24:95-114, 2004
Szabó Cs; Erdélyi É: Applications of graph theory as a possibility of controlling agroecosystems, In: Duranovic S, Vranes S (ed) Safe food proceedings II, Novi Sad: Buducnost 2004 pp. 431-434, 2004
Szabó Cs; Seif S: Computational comlexity of checking identities in finite 0-simple and matix semigroups over finite fields, Semigroup Forum 72:207-222, 2006
Körtesi P; Radeleczki S; Szilágyi Sz: Congruences and isotone maps on partially ordered sets, Math. Pannonica 16:39-55, 2005
Radeleczki S: A note on the tolerance lattice of majority algebras, In: Contributions to General Algebra 16, Klagenfurt 2005, pp. 209-212, 2005
Kearnes KA; Kiss EW: The triangular principle is equivalent to the triangular scheme, Algebra Universalis 54:373-383, 2005
Chajda I; Radeleczki S: On congruences of algebras defined on sectionally pseudocomplemented lattices, Algebra and Model Theory 5, pp. 8-27, Conference Proceedings, Erlogol, Russia, 2005, Novosibirsk State University, 2006
Chajda I; Radeleczki S: Semilattices with sectionally antitone bijections, Novi Sad J. Math. 35:93-101, 2005
Szabó Cs: On rings with few orbits, Communications in Algebra 34:2251-2260, 2006
Szabó Cs; Kátai K: The free spectra of the variety generated by the 5 element Bandt-semigroup, Semigroup Forum 73:253-260, 2006
Kun G; Nesetril J: Lifts and shadows (NP and CSP for combinatorists), közlésre elfogadva: European Journal of Combinatorics, 2007
Kun G: Constraints, MMSNP and expander relational structures, benyújtva: Combinatorica, 2007
Kiss EW; Valeriote M: On tractability and congruence distributivity, Logical Methods in Computer Science 3:1-20, 2007
Idziak P; Kearnes K; Kiss E; Valeriote M: Definable principal congruences and solvability, közlésre elfogadva: Annals of Pure and Applied Logic, 2007
Horváth G; Lawrence J; Mérai L; Szabó Cs: The Complexity of the Equivalence Problem for Nonsolvable Groups, Bulletin of the London Mathematical Society 39:433-438, 2007
Kearnes KA; Kiss EW: The Shape of Congruence Lattices, benyújtva: Mem. Amer. Math. Soc., 2007
Kun G; Vértesi V: The membership problem in finite flat hypergraph algebras, International Journal of Algebra and Computation 17:449-459, 2007
Szabó Cs; Kun G: Jónsson terms and near-unanimity functions in finite posets, Order 20:291-298, 2004
Szabó Cs; Vértesi V: The complexity of the word-problem for finite matrix rings, Proc. Amer. Math. Soc. 132:3689-3695, 2004
Szabó Cs; Horváth G: The complexity of checking identities over finite groups, International Journal of Algebra and Computation 16:931-939, 2006
