Rechteckszerlegungen: Abzählende und strukturelle Aspekte

Eine Rechteckszerlegung ist eine Partition eines Rechtecks in endlich viele Rechtecke. Rechteckszerlegungen wurden in den vergangenen Jahren in der Literatur eingehend studiert. Beiträge zu diesem Forschungsgebiet kamen aus zahlreichen Teildisziplinen von Mathematik und Informatik. Kombinatorisch gesehen sind Rechteckszerlegungen eine sehr natürliche Struktur, denn sie stehen in enger Beziehung zu vielen anderen gut untersuchten kombinatorischen Objekten. Dazu zählen Bäume, (ebene) Karten, Klassen von Permutationen, Gitterpfade, u.v.a.m. Aus Sicht der algorithmischen Geometrie kommt das Interesse an Rechteckszerlegungen vor allem daher, dass sie als grundlegendes Modell für das Layout von integrierten Schaltkreisen verwendet werdenSchließlich sei noch erwähnt, dass Rechteckszerlegungen auch in den Grundlagen der architektonischen Gestaltung eine Rolle spielen. Die kombinatorische Analyse der Rechteckszerlegungen ist ausgesprochen anspruchsvoll. Viele naheliegende Fragestellungen konnten bisher nur für einige Spezialfälle beantwortet werden. Deshalb planen wir, in diesem Projekt einige strukturelle Aspekte von Rechteckszerlegungen sowie damit verwandte Anzahlprobleme zu untersuchen. Konkret sollen im Rahmen dieses Projekts die exakten und asymptotischen Anzahlen aller Rechteckszerlegungen bestimmt werden, die in bestimmte Klassen von Zerlegungen fallen. Dazu gehören u.a. die Klassen, die durch Klassen von Permutationen dargestellt werden können, welche ihrerseits über verbotene Muster definiert sind, zum Beispiel die sogenannten Baxter-Permutationen. Von letzteren weiß man, dass sie in Bijektion zu einer natürlichen Klasse von Rechteckszerlegungen stehen. Manche dieser Fragestellungen erschienen als offene Forschungsprobleme in der jüngeren Literatur zu diesem Thema. Methodisch greifen wir auf die strukturelle Analyse und auf moderne Methoden aus der analytischen und abzählenden Kombinatorik zurück. Dieses Projekt soll insbesondere das große Potenzial zeigen, das die analytische Kombinatorik hat, wenn es um das Lösen von Problemen aus der theoretischen Informatik geht. Diese Methoden wurden bis dato nur selten auf dem Gebiet der Rechteckszerlegungen eingesetzt, und wir glauben, dass ihr Einsatz zu vielversprechenden Fortschritten führen wird.

Das Projekt beschäftigte sich mit den abzählenden und strukturellen Aspekten von Rechteckzerlegungen. Eine Rechteckzerlegung ist eine Unterteilung eines Rechtecks in kleinere Rechtecke durch horizontale und vertikale Strecken. Solche Zerlegungen spielen eine wesentliche Rolle in der mathematischen Modellierung von VLSI-Chipdesign, in der Visualisierung wissenschaftlicher Daten, in geometrischen Algorithmen, in der Architekturgestaltung und weiteren Bereichen. Mathematisch betrachtet bilden Rechteckzerlegungen eine natürliche kombinatorische und geometrische Struktur, die sich leicht darstellen lässt, deren Analyse jedoch sehr anspruchsvoll ist. Die abzählenden Aspekte befassen sich damit, wie viele wesentlich unterschiedliche Möglichkeiten es gibt, ein Rechteck in eine vorgegebene Anzahl kleinerer Rechtecke zu zerlegen. Dabei werden die exakten Maße der Rechtecke nicht berücksichtigt; entscheidend sind die Nachbarschaften zwischen Strecken und/oder Rechtecken. Beispielsweise lässt sich leicht erkennen, dass ein Rechteck auf zwei Arten in 2 Rechtecke zerlegt werden kann (horizontal oder vertikal) und auf sechs Arten in 3 Rechtecke. Für Zerlegungen in eine größere Anzahl von Rechtecken ist die Antwort nicht unmittelbar ersichtlich und erfordert fortgeschrittene mathematische Methoden. Ab mindestens vier Rechtecken existieren zwei natürliche Abzählungsarten: die Schwachen Rechteckzerlegungen, bei denen Nachbarschaften zwischen Rechtecken und Strecken erhalten bleiben, und die Starken Rechteckzerlegungen, bei denen Nachbarschaften zwischen Rechtecken erhalten bleiben. Die strukturellen Aspekte betreffen insbesondere die Charakterisierung zulässiger Rechteckzerlegungen - etwa durch Darstellungen mittels anderer kombinatorischer Strukturen wie geometrische Graphen, Halbordnungen und Permutationen. Ein Schwerpunkt hierzu ist die Untersuchung von Mustervermeidungen, bei der Rechteckzerlegungen betrachtet werden, die bestimmte lokale "Muster" nicht enthalten. Die wichtigsten im Rahmen dieses Projekts erzielten Ergebnisse umfassen: 1. Eine einheitliche Darstellung schwacher und starker Rechteckzerlegungen durch Kongruenzverbände und Klassen von Permutationen. 2. Neue Algorithmen zur Abbildung von Rechteckzerlegungen auf Permutationen und umgekehrt. 3. Ein einheitlicher Rahmen, der zahlreiche frühere Ergebnisse zusammenfasst, vereinheitlicht und verallgemeinert. 4. Charakterisierung starker Guillotine-Rechteckzerlegungen durch Gitter-Muster (Mesh-Patterns). 5. Analytische Lösungen zur Abzählung aller Modelle schwacher Guillotine-Rechteckzerlegungen, die algorithmisch in einem Artikel von Merino und Mütze (2024) untersucht wurden. 6. Abzählung aller Klassen mustermeidender Rechteckzerlegungen, bei denen alle Muster T-Formen einer bestimmten Orientierung sind, in allen möglichen Kombinationen. 7. Neue Bijektionen zwischen Klassen von Rechteckzerlegungen und Inversionsfolgen, Permutationen und Gitterpfaden. 8. Beweis einer Vermutung von Yan und Lin (2020) zur Abzählung der Klasse I(011, 201). 9. Charakterisierung der Muster mit drei Strecken durch Gitter-Muster und Abzählung der entsprechenden Modelle. Diese Ergebnisse sind in Artikeln enthalten, die gemeinsam mit Jean Cardinal, Stefan Felsner und Éric Fusy (1-4), Cyril Banderier (5), Michaela Polley (6-8) sowie Torsten Mütze, Namrata und Michaela Polley (9) verfasst wurden.