panthema / 2016 / 0114-diploma-thesis
Sketch of a edge-split-attach operation, which breaks a unique exchange from e.

On the Structure of the Graph of Unique Symmetric Base Exchanges of Bispanning Graphs - Diploma Thesis in Mathematics

Posted on 2016-01-14 18:30 by Timo Bingmann at Permlink with 0 Comments. Tags: maths university

After a long exhausting period with many interruptions my diploma thesis in mathematics "On the Structure of the Graph of Unique Symmetric Base Exchanges of Bispanning Graphs" is finalized and submitted. The full abstract of the thesis is shown below, and an additional German abstract is available further down the page.

The final version of the thesis is available here: thesis pdf Bingmann-On-the-Structure-of-the-Graph-of-Unique-Symmetric-Base-Exchanges-of-Bispanning-Graphs.pdf, and was also uploaded to arXiv.org as 1601.03526.

The underlying problem discussed in the thesis is best explained using a game on a bispanning graph. You can play the game with this Java Applet or using the Java WebStart Launcher (if the Applet does not work). You play Alice's role and want to flip the colors of all edges in the graph. Bob will try to prevent this from happening.

In addition to the thesis itself, the source code of the accompanying computer program is also available. It was used while preparing the thesis to calculate exchanges graphs and to test many hypothesis about bispanning graphs. The program can enumerate all bispanning graphs and their exchange graphs for small numbers of vertices. See the program page for downloadable lists and PDFs of all bispanning graphs for small numbers of vertices.

Abstract

Bispanning graphs are undirected graphs with an edge set that can be decomposed into two disjoint spanning trees. The operation of symmetrically swapping two edges between the trees, such that the result is a different pair of disjoint spanning trees, is called an edge exchange or a symmetric base exchange. The graph of symmetric base exchanges of a bispanning graph contains a vertex for every valid pair of disjoint spanning trees, and edges between them to represent all possible edge exchanges. We are interested in a restriction of these graphs to only unique symmetric base exchanges, which are edge exchanges wherein selecting one edge leaves only one choice for selecting the other. In this thesis, we discuss the structure of the graph of unique symmetric edge exchanges, and the open question whether these are connected for all bispanning graphs.

This abstract problem can be nicely rephrased into a coloring game with two players: Alice and Bob are given a bispanning graph colored with two disjoint spanning trees, and Alice gets to flip the color of any edge. This creates a cycle in one color and a cut in the other, and Bob must then flip a different edge to repair the constraint that both colors represent disjoint spanning trees. Alice's objective is to invert the color of all edges in the graph, and Bob's to prevent this. We are interested in whether Alice can find a sequence of unique edge exchanges for any bispanning graph, since these leave Bob no choice in which edge to select, hence allowing Alice to win with certainty.

In this thesis, we first define and discuss the properties of bispanning graphs in depth. Intuitively, these are locally dense enough to allow the two disjoint spanning trees to reach all vertices, but sparse enough such that disjoint edge sets do not contain cycles. The whole class of bispanning graphs can be inductively constructed using only two operations, which makes the class tractable for inductive proofs.

We then describe in detail directed, undirected, and simplified versions of edge exchange graphs, first with unrestricted edge exchanges, and then with the restriction to unique symmetric base exchanges. These exchange graphs are related to a set of conjectures put forth by White in 1980 on base exchanges in matroids, and also to conjectures on cyclic base orderings of matroids. To date, these conjectures have not been proven in full generality, despite overwhelming computational evidence.

As steps towards showing the conjecture that the graph of unique symmetric base exchanges is connected for all bispanning graphs, we prove a composition method to construct the unique exchange graph of any bispanning graph from the exchange graphs of smaller bispanning graphs. Furthermore, using a computer program developed alongside this thesis, we are able to enumerate and make statements about all small bispanning graphs and their exchanges graphs.

Our composition method classifies bispanning graphs by whether they contain a non-trivial bispanning subgraph, and by vertex and edge connectivity. For bispanning graphs containing a non-trivial bispanning subgraph, we prove that the unique exchange graph is the Cartesian graph product of two smaller exchange graphs. For 2-vertex-connected bispanning graphs, we show that the bispanning graph is the 2-clique sum of two smaller bispanning graphs, and that the unique exchange graph can be built by joining their exchange graphs and forwarding edges at the join seam. And for all remaining bispanning graphs, we prove a composition method at a vertex of degree three, wherein the unique exchange graph is constructed from the exchange graphs of three reduced bispanning graphs.

We conclude this thesis with ideas and evidence for future approaches to proving the connectivity of the unique exchange graphs and show the most difficult bispanning graphs instances.

Zusammenfassung

Bispannende Graphen sind ungerichtete Graphen, deren Kantenmenge sich in zwei disjunkte aufspannende Bäume zerlegen lässt. Man nennt einen symmetrischen Tausch von zwei Kanten zwischen den beiden Bäumen einen zulässigen Kantentausch oder einen symmetrischen Basenwechsel, wenn das Ergebnis ein anderes Paar disjunkter aufspannender Bäume ist. Der Graph der symmetrischen Basenwechsel eines bispannenden Graphen enthält einen Knoten für jedes gültige Paar disjunkter aufspannender Bäume und eine Kante für jeden zulässigen Kantentausch. Wir interessieren uns für die Einschränkung dieses Graphen auf zwingende symmetrische Basenwechsel, bei denen durch die Wahl eines der Tauschkanten die andere eindeutig bestimmt wird. Die vorliegende Arbeit befasst sich mit der Struktur des Graphen der zwingenden symmetrischen Basenwechsel und mit der offenen Frage, ob dieser für alle bispannenden Graphen verbunden ist.

Dieses abstrakte Problem lässt sich anschaulich als Färbungsspiel auf einem Graphen mit zwei Spielern darstellen: Alice und Bob ist ein bispannender Graph gegeben, in dem zwei aufspannende Bäume durch zwei verschiedene Kantenfarben gekennzeichnet sind. Alice darf die Farbe einer Kante tauschen. Hierdurch entsteht ein Kreis in einer Farbe und ein Schnitt in der anderen. Bob muss nun durch Umfärben einer anderen Kanten die Bedingungen wiederherstellen, dass beide Farben zwei disjunkte aufspannende Bäume darstellen. Alices Ziel ist die Farben aller Kanten im Graphen zu tauschen, Bobs dies zu verhindern. Wir interessieren uns dafür, ob Alice eine Folge von zwingenden symmetrischen Basenwechseln finden kann, denn diese zwingen Bob eine bestimmte Kante zu wählen und erlauben es somit Alice mit Sicherheit zu gewinnen.

In dieser Arbeit definieren und diskutieren wir zuerst die Eigenschaften von bispannenden Graphen. Intuitiv sind diese lokal dicht genug, um zwei disjunkte aufspannende Bäume zu zulassen, aber licht genug, dass disjunkte Kantenmengen keine Kreise enthalten. Die Klasse der bispannenden Graphen lässt sich mit nur zwei Operationen induktiv konstruieren, was sie für induktive Beweise greifbar macht.

Dann beschreiben wir im Detail gerichtete, ungerichtete und einfache Varianten von Basenwechselgraphen, zuerst ohne Einschränkung und dann auf zwingende symmetrische Basenwechsel beschränkt. Diese Basenwechselgraphen stehen in Beziehung zu Vermutungen von White aus dem Jahre 1980 und zu weiteren Vermutungen zur zyklischen Basenanordnung von Matroiden. Diese Vermutungen wurden bis heute noch nicht in voller Allgemeinheit bewiesen, trotz einer überwältigenden Anzahl mit Computer verifizierten Beispielen.

Als Schritte um die Vermutung zu zeigen, dass alle Basenwechselgraphen trotz Einschränkung auf zwingende Basenwechsel verbunden sind, beweisen wir eine Methode, um den zwingenden Basenwechselgraphen jedes bispannenden Graphen aus den Basenwechselgraphen kleinerer bispannender Graphen zusammenzusetzen. Für bispannende Graphen, die einen nicht-trivialen bispannenden Teilgraphen enthalten, zeigen wir, dass der zwingende Basenwechselgraph das Kartesische Graphprodukt von zwei kleineren Basenwechselgraphen ist. Für 2-knotenzusammenhängende bispannende Graphen können wir beweisen, dass dieser sich als die 2-Clique-Summe von zwei kleineren bispannenden Graphen darstellen lässt, und dass der zwingende Basenwechselgraph sich durch Zusammenfügen der Basenwechselgraphen dieser beiden konstruieren lässt. Für die übrigen bispannenden Graphen zeigen wir eine Reduktion an einem Knoten mit Grad drei und eine Methode, den zwingende Basenwechselgraphen aus den Basenwechselgraphen von drei reduzierten bispannenden Graphen zu erzeugen.

Als Abschluss der Arbeit diskutieren wir Ideen und Hinweise für zukünftige Ansätze die Verbundenheit des zwingenden Basenwechselgraphen zu beweisen, und verweisen auf die schwierigsten Instanzen bispannender Graphen.


Post Comment
Name:
E-Mail or Homepage:
 

URLs (http://...) are displayed, e-mails are hidden and used for Gravatar.

Many common HTML elements are allowed in the text, but no CSS style.
RSS 2.0 Weblog Feed Atom 1.0 Weblog Feed Valid XHTML 1.1 Valid CSS (2.1)
Copyright 2005-2016 Timo Bingmann - Impressum