Quantitative embeddings with applications

Abstract

In this thesis, we discuss quantitative embeddings that generalize a theorem of Kolmogorov and Barzdin. The theorem says that any bounded degree graph with V vertices can be mapped into a 3-dimensional ball of radius sqrt(V), so that at most a constant number of edges intersect any unit ball. In one generalization we describe how much freedom we have in placing the vertices of the graph, and in the other we prove a similar result for simplicial complexes of any dimension. We also discuss applications of these quantitative embeddings to a problem in metric geometry related to the isoperimetric inequality and a problem about constructing local quantum error-correcting codes.