scientific article; zbMATH DE number 1168010

Thema dieser Arbeit sind binäre Matroide. Matroide als abstrakte Verallgemeinerung des Basisbegriffes in Vektorräumen haben einen wesentlichen Anwendungsbereich in der Graphentheorie gefunden. Die hierbei betrachteten graphischen Zyklenmatroide stellen einen Spezialfall allgemeiner Matroide dar. Binäre Matroide liegen als Klasse zwischen den Extremen `graphische Matroide' \(\subseteq\) `allgemeine Matroide'. Wenn man einen einfachen Graphen als \((V,E)\) definiert, wobei die Kanten \(e\in E\) je zweielementige Teilmengen der Eckenmenge \(V\) sind, so besteht der Übergang zu binären Matroiden im wesentlichen darin, auf die Beschränkung \(\#e=2\) zu verzichten. Gleichzeitig erlaubt eine derartige `Darstellung' eines allgemeinen Matroids, wenn sie denn existiert (das Matroid also binär ist), explizites Rechnen und Strukturaussagen, die in diesem Ausmaß für beliebige Matroide nicht möglich sind. Die grundsätzliche Fragestellung, die hinter dieser Arbeit steht, ist das Isomorphieproblem: Wann sind zwei binäre Matroide isomorph? Der konkrete Ansatz bestand darin, eine Liste aller Isomorphieklassen einfacher binärer Matroide mit Rang \(\leq 5\) zu erstellen. Die 46 Isomorphieklassen einfacher binärer Matroide mit Rang \(\leq 4\) kann man noch ohne wesentlichen Einsatz theoretischer Untersuchungen berechnen, für Rang \(\leq 6\) übersteigt die Zahl der Isomorphieklassen mit der Größenordnung \(10^7\) das Maß des explizit Behandelbaren. Diese Aufzählung war nicht primär Selbstzweck (obwohl z.T. auch interessant), sondern vor allem ein Kriterium für die Relevanz von Definitionen und Sätzen. Techniken, die den Arbeitsaufwand bei der Erstellung dieser Liste reduzierten und sinnvoll für größere Matroide verallgemeinert werden konnten, wurden genauer untersucht. Kapitel 1 gibt eine kurze Einführung in Matroidtheorie mit Schwerpunkt bei Zyklenmatroiden. Kapitel 2 stellt (bekannte) Grundlagen über binäre Matroide zusammen. Kapitel 3 untersucht `unzerlegbare' Matroide, die während der hier angestellten Untersuchungen in verschiedenen Zusammenhängen eine Rolle spielten. Das wesentliche Ergebnis dieses (vom Rest der Arbeit weitgehend unabhängigen) Kapitels ist eine matroidtheoretische Verschärfung des Vierfarbensatzes. (Um nochmals auf den Anfang zurückzukommen: Auch das ist ein Beispiel graphentheoretisch motivierter Beschäftigung mit Matroiden.) In den Kapiteln 4 bis 6 werden verschiedene Konzepte untersucht, die explizit für die Erstellung der Liste (Kapitel 7) genutzt wurden. Nach Kapitel 4 kann man die Elementzahl der behandelten Matroide auf die Hälfte des theoretisch Möglichen reduzieren. Kapitel 5 erlaubt es, die Betrachtungen weiter auf `gerade' Matroide zu beschränken. Kapitel 6 schließlich behandelt eine Invariante, die vor allem dazu genutzt wird, für eine Menge von Matroiden zu entscheiden, welche überhaupt isomorph sein können. Insgesamt muß man bei Anwendung dieser Techniken nicht alle 1372 Isomorphieklassen einfacher binärer Matroide mit Rang \(\leq 5\) einzeln auseinandersortieren, sondern nur 88 Isomorphieklassen gerader Matroide (nach Kapitel 5) mit maximal 15 Elementen (nach Kapitel 4), was durch die Aufteilung in Gruppen mit je gleichem Index (Kapitel 6) deutlich erleichtert wird. Für binäre Matroide größeren Ranges ist das bei weitem nicht ausreichend. Bis wir ein binäres Matroid durch ein System handhabbarer Invarianten vollständig charakterisieren können, bleibt noch viel zu tun.

Recommendations

Cited in

(18)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4396972)