On the structure of Gröbner bases for graph coloring ideals

Vorschau

PDF
Michael Pernpeintner - Master's Thesis.pdf - Veröffentlichte Version
Download (1MB)

URL:	https://madoc.bib.uni-mannheim.de/49909
URN:	urn:nbn:de:bsz:180-madoc-499091
Dokumenttyp:	Abschlussarbeit , Master
Erscheinungsjahr:	2014
Ort der Veröffentlichung:	München
Hochschule:	Technische Universität München
Gutachter:	Hemmecke, Raymond
Datum der mündl. Prüfung:	28 September 2014
Sprache der Veröffentlichung:	Englisch
Einrichtung:	Außerfakultäre Einrichtungen > Institut für Enterprise Systems (InES)
Lizenz:	Creative Commons Namensnennung 4.0 International (CC BY 4.0)
Fachgebiet:	510 Mathematik
Freie Schlagwörter (Deutsch):	Gröbner Basis , Nullstellensatz
Freie Schlagwörter (Englisch):	Graph Coloring
Abstract:	In this thesis, we look at a well-known connection between the graph coloring problem and the solvability of certain systems of polynomial equations. In particular, we examine the connection between the structure of a graph and the structure of the Gröbner bases of the graph’s coloring ideal. From a theoretical viewpoint, we show some properties of such Gröbner bases, and we develop a polynomial-time algorithm to compute a Gröbner basis for chordal graphs. From the experimental side, we state results about specific Gröbner bases and about the Gröbner fan for a variety of graph families. Moreover, some heuristics and techniques are explored that reduce the computational complexity. The relevance of heuristic methods is justified by a section about expected intrinsic hardness of Gröbner basis computations.
Übersetzter Titel:	Über die Struktur von Gröbnerbasen für Graphenfärbungsideale (Deutsch)
Übersetzung des Abstracts:	In dieser Arbeit betrachten wir die Verbindung zwischen dem Graphenfärbungsproblem und der Lösbarkeit bestimmter polynomieller Gleichungssysteme. Im Speziellen untersuchen wir den Zusammenhang zwischen der Struktur eines Graphen und der Struktur der Gröbnerbasen des zugehörigen Färbungsideals. Wir zeigen einige Eigenschaften solcher Gröbnerbasen auf und konstruieren einen Algorithmus, der in polynomieller Zeit eine Gröbnerbasis für chordale Graphen erzeugt. Daneben zeigen wir spezifische Gröbnerbasen für einige Familien von Graphen, und treffen Aussagen über ihre Komplexität sowie Eigenschaften der zugehörigen Gröbnerfächer. Außerdem untersuchen wir einige Heuristiken, die dazu geeignet sind, den Rechenaufwand der verwendeten Algorithmen zu senken. In einem Kapitel über die intrinsische Komplexität der Berechnung von Gröbnerbasen rechtfertigen wir die Relevanz heuristischer Methoden und der Betrachtung von Spezialfällen. (Deutsch)

	Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.
	Dieser Datensatz wurde nicht während einer Tätigkeit an der Universität Mannheim veröffentlicht, dies ist eine Externe Publikation.