Graphs and Geometry

Graphs are purely combinatorial objects. While it is natural
for us to use geometry to visualize them in order to better grasp their structure, it is perhaps a bit
surprising that representing a graph geometrically can significantly help to study its properties that
have apparently nothing to do with geometry and also to devise algorithms for various graph
problems.
The purpose of the course is to present three topics where graphs and geometry couple in a nice
way yielding arguably unexpected applications. The topics are chosen to display a broad spectrum
of mathematical tools used in the development, study and use of various geometric
representations of graphs while keeping the prerequisites reasonably low. The tools are ranging
from elementary geometry, linear algebra and (elements of) differential geometry to probabilistic
constructions, metric embeddings and optimization.
The topics covered will be:
1) Coin representations of planar graphs—Koebe’s theorem, the Cage theorem.
Applications: the planar separator theorem and a bound on the expansion of planar
graphs.
2) Colin de Verdière’s graph parameter—its minor monotonicity, geometric characterizations
it provides (outerplanarity, planarity, linkless embeddability), discussion of open problems
Application: Steinitz’s representation of a planar graph.
3) Low distortion metric embeddings—distortion, the Johnson–Lindenstraus lemma, a
random subset embedding, Bourgain’s theorem.
Application: Algorithm to approximate the sparsest cut in a given graph.

Target group: Students with solid background in mathematics or theoretical computer science

Prerequisites: Familiarity with linear algebra, elementary probability theory and basic calculus are assumed. More advanced tools will be used only sparingly and will be covered in the lectures. The presentation will be adjusted to the background of the audience. The main prerequisite is an interest in mathematics and its interfaces with algorithm design.

Evaluation: participation + graded homeworks + exam

Teaching format: lecture + recitation

ECTS: 3 Year: 2022

Track segment(s):
Elective

Teacher(s):
Vojtech Kaluza

Teaching assistant(s):
Elizaveta Streltsova

If you want to enroll to this course, please click: REGISTER