Kongruenciák és Malcev-feltételek = Congruences and Mal'tsev conditions

Kiss, Emil and Fried, Ervin and Kun, Gábor and Prőhle, Péter and Radeleczki, Sándor and Schmidt, Tamás and Szabó, Csaba (2008) Kongruenciák és Malcev-feltételek = Congruences and Mal'tsev conditions. Project Report. OTKA.

Preview

PDF 43671_ZJ1.pdf Download (84kB)

Abstract

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. | 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.

Actions (login required)

Edit Item