April 2021 – UTU Seminar in Discrete Mathematics

4.5.2021 Alexander Tiskin

Time: 4.5.2021 at 13:00

Speaker: Alexander Tiskin, St Petersburg University

Title: The surprising algebra of string comparison

Abstract:We consider the classical Longest Common Subsequence (LCS) problem on a pair of strings, also known as the Sequence Alignment problem in bioinformatics. The textbook solution for this problem is based on dynamic programming, and seems to be the only possible. We will show that this is not the case: a suitably generalised version of the LCS problem can be solved efficiently by a divide-and-conquer algorithm. In this alternative solution, subproblems are combined using a seemingly unrelated structure, known as the Hecke (or “sticky braid”) monoid, which can be defined via tropical matrix multiplication, and bears a close resemblance with the classical braid group. Such an approach is not only of theoretical interest, but also allows us to obtain efficient algorithms for approximate pattern matching on compressed strings without decompression, parallel string comparison, the maximum clique problem on circle graphs, as well as some real-life bioinformatics problems.

20.4.2021 Ville Salo

Time: 20.4.2021 at 13:00

Speaker: Ville Salo, University of Turku

Title: Self-simulable groups

Abstract: We say a group G simulates a subgroup H < G if every effective H-system on the Cantor set can be realized as a dynamical factor of the H-subaction of a tiling system on G. A theorem of Hochman shows that Z^3 simulates Z, and a theorem of Durand-Romashenko-Shen/Aubrun-Sablik shows that Z^2 simulates every effective subshift on Z. It is open whether any group simulates itself, but it is known that any such must be group is non-amenable and one-ended. We give the first examples of such self-simulable groups. The examples include almost all braid groups, [outer] automorphism groups of free groups, general linear groups over integers, Brin-Thompson groups nV, Burger-Mozes lattices, many right-angled Artin groups, and non-amenable branch groups. For almost all of these groups this also gives the first examples of strongly aperiodic tiling systems. In the talk, we give the necessary background, outline how self-simulation is obtained for the square of any non-abelian free group, and explain how to get the more interesting examples using closure properties.