Riemann-Roch theory for sublattices of the root lattice An, graph automorphisms and counting cycles in graphs

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.