Asymptotische Aspekte und Automaten in Gruppentheorie

Das Forschungsprojekt betrifft mehrere Themen im mathematischen Bereich der geometrischen Gruppentheorie. Im Geiste der modernen Forschung in der geometrischen Gruppentheorie, die vor allem durch die Arbeiten von Gromov ab den 1980er Jahren geprägt wurde, ist es eines unserer Ziele, die möglichen Verbindungen zwischen diesen Themen zu erforschen, da diese schon zu einigen sehr interessanten Ergebnissen geführt haben. Eine interessante Klasse von Gruppen, in denen Graphen in einem algebraischen Kontext erscheinen, ist die der Automatengruppen. Diese Gruppen werden von Automaten erzeugt und wirken durch Automorphismen auf Wurzelbäumen. Sie wurden in den frühen 1980er Jahren eingeführt, als Grigorchuk das erste Beispiel für eine Gruppe mit intermediären Wachstum konstruiert hat (ein von Milnor gestelltes Problem). Es stellte sich heraus, dass sehr einfache Automaten Gruppen mit exotischen Eigenschaften, die in klassisch definierten Gruppen schwer zu finden sind, erzeugen können. Nekrashevych unterstreicht eine sehr überraschende Verbindung zwischen solchen Gruppen und komplexer Dynamik, die zur Lösung schwieriger Probleme in der Dynamik durch algebraische Methoden führte. Wir planen die Bedingungen, unter denen eine Automatengruppe endlich präsentiert ist zu finden und einige geometrische Eigenschaften der entsprechenden Schreiergraphen zu beschreiben (in Bezug auf Wachstum, die Anzahl der Enden, das Isomorphie-Problem). Durch die Interpretation der Schreiergraphen in Form von vollständigen Automaten, wollen wir die Klasse der von ihnen anerkannten Sprachen studieren. Wenn eine Präsentation einer Gruppe gegeben ist, kann man ihr einen Graph zuordnen (den Cayleygraph) und geometrische, algorithmische und dynamische Aspekte der Gruppe durch diesen Graphen studieren. Die asymptotischen isoperimetrischen Funktionen auf Cayleygraphen beziehen sich auf das asymptotische Verhältnis zwischen dem Rand oder Durchmessern von Teilgraphen, und ihren Volumen. Wir wollen eine dieser asymptotischen Funktionen, die bisher noch nicht so sehr untersucht wurde, die mittlere Dehn-Funktion, durch Irrfahrten erforschen. Eine andere asymptotische Funktion, die Cheeger-Konstante, die über Anwendungen in Computer-Netzwerken verfügt, ist auf Graphen analog Riemannschen Mannigfaltigkeiten definiert. Allerdings bezieht sich die Definition auf Präsentationen von Gruppen und unser Ziel ist, auf Gruppen zu definieren und zu berechnen. Außerdem wollen wir untersuchen, welche Arten von Sprachen und Automaten gute algorithmische Eigenschaften habenundfür die ErweiterungderKlasse der graphenautomatischen-Gruppen geeignet sind.

Das Projekt behandelt Themen aus dem Bereich der geometrischen Gruppentheorie. Das Ziel war eine besser Beschreibung der Zusammenhänge zwischen algebraischen Eigenschaften von Strukturen wie (typischerweise von endlichen Automaten erzeugten) Gruppen und Halbgruppen, ihrer Beschreibung durch Graphen (Schreiergraphen oder Orbitalgraphen), und den Eigenschaften der von diesen Automaten erzeugten Sprachen. Insbesondere lag der Schwerpunkt auf Themen, die von algebraischen, kombinatorischen und probabilistischen Gesichtspunkten aus behandelt werden können und Mitglieder mit verschiedenem Hintergrund wirkten mit. Alle Teilnehmer bearbeiteten zusammen das Haupthema, nämlich die Frage der Synchronisierung zirkulärer Automaten (mit hoher Wahrscheinlichkeit) im Sinne der Cerny-Vermutung. Cerny hat 1964 explizite Schranke für die Länge des kürzesten synchronisierenden Worts eines sogenannten synchronisierenden Automaten vermutet, das sind Automaten, die initialisierende Wörter besitzen, in Abhängigkeit von der Anzahl der Zustände des Automaten. Die allgemeine Version dieser Vermutung ist nach wie vor offen und angesichts der offenbaren Schwierigkeit des Problems wurde in den letzten Jahren versucht, das Problem probabilistisch anzugehen. Zwei natürliche Fragen treten auf: 1. Synchronisiert ein zufälliger Automat mit großer Wahrscheinlichkeit? 2. Ist in der Klasse der synchronisierenden Automaten die Cerny-Vermutung mit hoher Wahrscheinlichkeit erfüllt? Das Hauptergebnis des Projekts gibt eine Teilantwort auf diese Fragen im Spezialfall der zirkulären Automaten, und zwar wurde bewiesen, daß zirkulärer Automaten mit großer Wahrscheinlichkeit synchronisieren. Genauere Abschätzungen der Synchronisationsgeschwindigkeit müssen noch weiter untersucht werden, aber das gewonnene Ergebnis unterstreicht die Möglichkeit, das Problem in ein Graphenfärbungsproblem zu übersetzen und öffnet den Weg zu neuen Entwicklungen. Neben diesem Hauptthema wurden Ergebnisse in verwandten Gebieten erzielt, und zwar in der Theorie der Schreier- und Orbitalgraphen von Automatengruppen und -semigruppen und den entsprechenden Entscheidungsproblemen, im Zusammenhang mit der Anwendung von Markovketten zur Modellierung kaputter Maschinen in der Industrieproduktion, in der Untersuchung zeitabhängiger Automaten und "gain graphs". Die Forschungsgruppe war zusammengesetzt aus Dr. D. D'Angeli, Dr. A. Rosenmann und Dr. A. Gutierrez-Sanchez und führenden internationalen Experten in den untersuchten Gebieten als externen Kollaborationspartnern. Die Forschungsthemen wurden im Rahmen eines Projektworkshops im Februar 2019 diskutiert, an dem auch andere wichtige Internationale Forscher teilnahmen. Die Ergebnisse wurden in zahlreichen internationalen Seminaren an verschiedenen Instituten präsentiert.