[ Home ]   [ Current ]   [ Archive ]

Seminar za Logiku, Algebru, DIskretnu Matematiku i teorijsko računarstvo
Logic, Algebra, DIscrete Mathematics and Theoretical Computer Science Seminars

Školska 2024/25. / Academic year 2024/25

24/10/2024

Zoltán Vidnyánszky (ELTE, Budapest, Hungary): Homomorphism problems with infinite templates

The CSP dichotomy of Bulatov and Zhuk is a celebrated theorem of computer science: it states that given a finite structure H, deciding whether a structure G admits a homomorphism to G is either easy (in P) or hard (NP-complete).

We will discuss two infinitary versions of this theorem. First, following Thornton, in the Borel context. Here a striking difference from the finite world emerges: we will show that solving linear equations over a finite field is already hard (\Sigma^1_2--complete).

Second, assuming only ZF, we will consider the relationship of the H-compactness properties, that is, the statement that for every G if every finite substructure of G admits a homomorphism to H then so is G. Here we show that there exists a model M of ZF, such that M models H-compactness iff the H-homomorphism problem is easy. These results do not use the Bulatov-Zhuk Dichotomy.

09/10/2024

Vladimir Tasić (University of New Brunswick, Fredericton, Canada): Brouwer-Weyl continuum throught 3D glasses: Geometry, computation, general relativity

Abstract (pdf)

26/09/2024

Robert D. Gray (University of East Anglia, Norwich, UK): The geometry of the word problem for groups and inverse monoids

The most fundamental algorithmic problem in algebra is the word problem, which asks whether there is an algorithm that takes two expressions over a set of generators and decides whether they represent the same element. Despite the huge advances that have been made in this area over the past century, there are still many basic questions about the word problem, and related algorithmic problems, for finitely presented groups and monoids that remain open.

Important work of Ivanov, Margolis, Meakin, and Stephen in the 1990s and 2000s shows how algorithmic problems for groups and monoids can be related to corresponding questions about finitely presented inverse monoids. This is a natural class that lies between groups and monoids, and corresponds to the abstract study of partial symmetries. There is a powerful range of geometric methods for studying inverse monoids such as the Scheiblich/Munn description of free inverse monoids and Stephen's procedure for constructing Schutzenberger graphs.

In this talk I'll explain these connections, and discuss recent advances in our understanding of the behaviour of the geometry of Cayley graphs of inverse monoids, and how this has been used to prove new and unexpected results about their algorithmic and algebraic properties.

[ Home ]   [ Current ]   [ Archive ]