See by year See by month Jump to month

Bertalan Bodor: Pseudo-loop lemmas

Download as iCal file
Wednesday, 30. November 2022, 10:10 - 11:40
By a theorem of Siggers we know that for any finite structure A either K_3 (the triangle graph) has a primitive positive construction in A; or A has a polymorphism satisfying the following identity: s(x,y,x,z,y,z)=s(y,x,z,x,z,y), also known as a (6-ary) Siggers polymorphism. By the results of Bulatov and Zhuk we know that this statement also corresponds to a CSP complexity dichotomy: if A has a finite signature then in the former case CSP(A) is NP-complete and in the latter case it is in P. By a result of Barto and Pinsker the aforementioned algebraic dichotomy also has a variation for infinite structures: they showed that if A is an ω-categorical model-complete core which does not primitively positively interpret K_3 then it has a pseudo-Siggers polymorphism, i.e. a 6-ary polymorphism s which satisfies e_1(s(x,y,x,z,y,z))=e_2(s(y,x,z,x,z,y)) for some some endomorphisms e_1,e_2 of A. In my talk I will discuss some new techniques for proving this theorem which also allows us to show for instance that for ω-categorical model-complete cores all pseudo-loops conditions given by odd cycles are equivalent.
This is a joint work with Libor Barto, Marcin Kozik, Antoine Mottet, and Michael Pinsker.
 
The lecture will be in the Riesz lecture room.
 

Back

JEvents v3.1.8 Stable   Copyright © 2006-2013