Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26350
Titel: Riemann-Roch theory for sublattices of the root lattice An, graph automorphisms and counting cycles in graphs
Alternativtitel: Riemann-Roch-Theorie für Untergitter des Wurzelgitter, Graphen-Automorphie und Zählen von Zyklen in Graphen
VerfasserIn: Manjunath, Madhusudan
Sprache: Englisch
Erscheinungsjahr: 2011
Kontrollierte Schlagwörter: Riemann-Roch-Satz
Gitter <Mathematik>
Graph
Automorphismus
Freie Schlagwörter: Untergitter
Wurzelgitter
Graphenautomorphismus
Riemann-Roch
sublattices of An
graph automorphisms
DDC-Sachgruppe: 510 Mathematik
Dokumenttyp: Dissertation
Abstract: This thesis consists of two independent parts. In the rst part of the thesis, we develop a Riemann-Roch theory for sublattices of the root lattice An extending the work of Baker and Norine (Advances in Mathematics, 215(2): 766-788, 2007) and study questions that arise from this theory. Our theory is based on the study of critical points of a certain simplicial distance function on a lattice and establishes connections between the Riemann-Roch theory and the Voronoi diagrams of lattices under certain simplicial distance functions. In particular, we provide a new geometric approach for the study of the Laplacian of graphs. As a consequence, we obtain a geometric proof of the Riemann-Roch theorem for graphs and generalise the result to other sub-lattices of An. Furthermore, we use the geometric approach to study the problem of computing the rank of a divisor on a nite multigraph G to obtain an algorithm that runs in polynomial time for a xed number of vertices, in particular with running time 2O(n log n)poly(size(G)) where n is the number of vertices of G. Motivated by this theory, we study a dimensionality reduction approach to the graph automorphism problem and we also obtain an algorithm for the related problem of counting automorphisms of graphs that is based on exponential sums. In the second part of the thesis, we develop an approach, based on complex-valued hash functions, to count cycles in graphs in the data streaming model. Our algorithm is based on the idea of computing instances of complex-valued random variables over the given stream and improves drastically upon the naive sampling algorithm.
Diese Dissertation besteht aus zwei unabhaengigen Teilen. Im ersten Teil entwickeln wir auf der Arbeit von Baker und Norine (Advances in Mathematics, 215(2): 766-788, 2007) aufbauend eine Riemann-Roch Theorie fuer Untergitter (sublattices) des Wurzelgitter (root lattice) An und untersuchen die Fragestellungen, die sich daraus ergeben. Unsere Theorie basiert auf der Untersuchung kritischer Punkte einer bestimmten simplizialen (simplicial) Metrik (distance function) auf Gitter und zeigt Verbindungen zwischen der Riemann-Roch Theorie und Voronoi-Diagrammen von Gittern unter einer gewissen simplizialen Metrik. Insbesondere liefern wir einen neuen geometrischen Beweis des Riemann-Roch Theorems fuer Graphen und generalisieren das Resultat fuer andere Untergitter von An. Des Weiteren verwenden wir den geometrischen Ansatz um das Problem der Berechnung des Rang (rank) eines Teilers (divisor) auf einem endlichen Multigraphen G und erhalten einen Algorithmus, der fuer eine xe Anzahl von Knoten in Polynomialzeit, genauer in Zeit 2O(n log n)poly(size(G)) mit n ist die Anzahl der Knoten in G, laeuft. Von dieser Theorie ausgehend untersuchen wir einen Anzatz fuer das Graphautomorphismusproblem ueber eine Dimensionalitaetsreduktion und erhalten ebenfalls einen Algorithmus fuer das verwandte Problem des Zaehlens von Automorphismen eines Graphen, der auf exponentiellen Summen basiert. Im zweiten Teil der Dissertation entwickeln wir einen auf komplexwertigen Hashfunktionen basierenden Ansatz um in einem Streaming-Modell die Zyklen eines Graphen zu zaehlen. Unser Algorithmus basiert auf der Idee Instanzen von komplexwertigen Zufallsvariablen ueber dem gegebenen Stream zu berechnen und stellt eine drastische Verbesserung ueber den naiven Sampling-Algorithmus dar. Im zweiten Teil der Dissertation entwickeln wir einen auf komplexwertigen Hashfunktionen basierenden Ansatz um in einem Streaming-Modell die Zyklen eines Graphen zu zaehlen. Unser Algorithmus basiert auf der Idee Instanzen von komplexwertigen Zufallsvariablen ueber dem gegebenen Stream zu berechnen und stellt eine drastische Verbesserung ueber den naiven Sampling-Algorithmus dar.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-47818
hdl:20.500.11880/26406
http://dx.doi.org/10.22028/D291-26350
Erstgutachter: Mehlhorn, Kurt
Tag der mündlichen Prüfung: 20-Dez-2011
Datum des Eintrags: 13-Mär-2012
Fakultät: MI - Fakultät für Mathematik und Informatik
Fachrichtung: MI - Mathematik
Sammlung:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Dateien zu diesem Datensatz:
Datei Beschreibung GrößeFormat 
thesis_manjun_final.pdf909,5 kBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.