Discrete and Convex Geometry — DCG

  • Instructor: Gergely Ambrus
  • Contact: ambruge at gmail dot com
  • Prerequisites: basic notions of calculus, some classical Euclidean geometry
  • Text: Classnotes by the lecturer

Course description: This course will concentrate on the combinatorial aspects of geometric structures: discrete sets of points, lines, and convex sets. The connection of geometry and combinatorics has been extremely fruitful in the last century, and results obtained from this dual viewpoint have found applications in a broad range of subjects from number theory to analysis. Most prominently, they became the cornerstone of theoretical computer science as well. We are going to start from elementary notions of Euclidean geometry, therefore no special prerequisite is needed. Besides the classical theorems, we will also learn about recent developments of the last decade. A large part of discrete and combinatorial geometry has rooted in Budapest, making it a perfect location to study this beautiful subject!

Topics:

  • Linear, affine, convex combinations, convex sets
  • Combinatorial properties of convex sets: theorems of Helly, Radon and Carathedoroy
  • Lattice points, Minkowski's theorem, applications in number theory
  • Planar graphs, Euler's formula
  • Arrangements of points and lines on the plane, incidence problems
  • Szemeredi-Trotter theorem, distinct distances and unit distances
  • Density estimates for packing and covering
  • Estimates for circle and sphere packings
  • Random arrangements in higher dimensions
  • Transversals and epsilon nets
  • Applications in information theory