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

Preview

PDF
Michael Pernpeintner - Master's Thesis.pdf - Published
Download (1MB)

URL:	https://madoc.bib.uni-mannheim.de/49909
URN:	urn:nbn:de:bsz:180-madoc-499091
Document Type:	Final Thesis , Master's
Year of publication:	2014
Place of publication:	München
University:	Technische Universität München
Evaluator:	Hemmecke, Raymond
Date of oral examination:	28 September 2014
Publication language:	English
Institution:	Außerfakultäre Einrichtungen > Institut für Enterprise Systems (InES)
License:
Subject:	510 Mathematics
Individual keywords (German):	Gröbner Basis , Nullstellensatz
Keywords (English):	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.
Translation of the title:	Über die Struktur von Gröbnerbasen für Graphenfärbungsideale (German)
Translation of the abstract:	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. (German)

	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.