Los Angeles Combinatorics and Complexity Seminar: On the size of finite rational matrix semigroups

Tuesday, November 10, 2020 at 10:15am to 10:45am

This is a past event.
Virtual Event

Christoph Haase, UCL, London, UK

Abstract: Given a finite set of $n \times n$ integer matrices $\mathcal M$ that generate a finite multiplicative semigroup $\overline{\mathcal M}$, I am going to present a recent result showing that any $M \in \overline{\mathcal M}$ is a product of at most $2^{O(n^2 \log n)}$ elements from $\mathcal M$. This bound immediately implies a bound on the cardinality of $\overline{\mathcal M}$.

I will provide a non-technical proof sketch demonstrating how the aforementioned bound can be obtained. In addition, I will discuss the history of this problem, its motivation, which is rooted in automata theory, related results that have appeared over the last decades, and open challenges.

The talk is based on joint work with Georgina Bumpus, Stefan Kiefer, Paul-Ioan Stoienescu and Jonathan Tanner from Oxford, which appeared at ICALP'20

Dial-In Information

Zoom Meeting: https://ucla.zoom.us/j/96564290758
Meeting ID: 965 6429 0758
Passcode: Please see your email for the passcode to join via Zoom
Warning: You must be registered under your name to be admitted.

Event Type

Lecture / Talk / Workshop

Add this to your calendar

Recent Activity