Combinatorial Geometry (M.Tech CS 2024-25)
Combinatorial Geometry (M.Tech CS 2024-25)
Instructor Arijit Ghosh
Status Completed
Teaching assistants Jatin Das and Uddalok Sarkar
Description To study the basics of Combinatorial Geometry
Prerequisites Mathematical maturity of a finishing undergraduate student in mathematical sciences
Class timings 11:15 AM - 1:05 PM on Wednesdays and Fridays at ACMU Seminar Room
Syllabus
Basics of combinatorial convex geometry
Geometric transversal theory
Separation theorems for convex sets
Fundamentals of linear programming
Structure theory of polyhedra and polytopes
Polarity and polyhedra
Incidence geometry and its applications
Introduction to lattices (if time permits)
Borsuk–Ulam theorem, and its applications (if time permits)
VC theory and its applications (if time permits)
Volumes in high dimension (if time permits)
References
[AS16] Noga Alon and Joel Spencer, The Probabilistic Method, 4th Edition, Wiley, 2016
[AZ14] Martin Aigner and Günter M. Ziegler, Proofs from THE BOOK, Springer, 2014
[B21] Imre Bárány, Combinatorial Convexity, American Mathematical Society, 2021
[B20] Kim C. Border, Convex Analysis and Economic Theory, Lecture notes, Caltech, 2020
[B10] Alexander Barvinok, Combinatorics of Polytopes, Lecture Notes, Univ. Michigan, 2010
[B11] Alexander Barvinok, Combinatorics, geometry and complexity of integer points, Lecture Notes, Univ. Michigan, 2010
[BT97] Dimitris Bertsimas and John N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997
[BO97] Imre Barany and Shmuel Onn, Caratheodory's Theorem: Colourful and Applicable, Bolyai Society Mathematical Studies, 6:11 - 21, 1997
[BV04] Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004
[D12] Zeev Dvir, Incidence Theorems and Their Applications, Foundations and Trends in Theoretical Computer Science, 2012
[H11] Sariel Har-Peled, Geometric Approximation Algorithms, American Mathematical Society, 2011
[K06] Vladlen Koltun, Advanced Geometric Algorithms, Lecture Notes, Stanford University, 2006
[LGM19] Jesus de Loera, Xavier Goaoc, Frederic Meunier and Nabil H. Mustafa, The Discrete Yet Ubiquitous Theorems of Caratheodory, Helly, Sperner, Tucker, and Tverberg, Bulletin of the American Mathematical Society, 56: 415-511, 2019
[LY08] David G. Luenberger and Yinyu Ye, Linear and Nonlinear Programming, Third Edition, Springer, 2008
[M99] Jiri Matousek, Geometric Discrepancy, Springer, 1999
[M02] Jiří Matoušek, Lectures on Discrete Geometry, Springer, 2002
[MG07] Jiří Matoušek and Bernd Gärtner, Understanding and Using Linear Programming, Springer, 2007
[N22] Nabil H. Mustafa, Sampling in Combinatorial and Geometric Set Systems, American Mathematical Society, 2022
[PA95] Janos Pach and Pankaj K Agarwal, Combinatorial Geometry, Wiley-Interscience, 1995
[R21] Thomas Rothvoss, Asymptotic Convex Geometry, Lecture Notes, UW Seattle, 2023
[R23a] Thomas Rothvoss, Lattices, Lecture Notes, UW Seattle, 2023
[R23b] Thomas Rothvoss, Networks and Combinatorial Optimization, Lecture Notes, UW Seattle, 2023
[U15] Torsten Ueckerdt, Combinatorics in the Plane, Lecture Notes, KIT, 2015
[W14] David P. Williamson, Mathematical Programming I, Lecture Notes, Cornell University, 2014
Lecture details
Topics covered in Lecture 1
Topics covered in Lecture 2
Definitions
Convex combination and convex hull
Affine independence, affine combination, and affine hull
Equivalence between affine independence and linear independence
Radon's theorem
Helly's theorem
Carathéodory's theorem about convex hulls
Discussion on the infinite version of Helly's theorem
Reading materials:
Topics covered in Lecture 3
Klee’s theorem on covering by translates and its different variants
Rey-Pastor-Santalo theorem on a common transversal of segments
Helly’s theorem on approximation of functions by affine functions
Center point of a point set
Rado's center point theorem
Reading materials:
Topics covered in Lecture 4
Definitions from convex geometry: interior, boundary, and closure of convex sets
Statements of hyperplane separation theorem
Proof of hyperplane separation theorem (strict case)
Supporting hyperplane theorem, and its proof using hyperplane separation theorem (strict case)
Reading materials:
Topics covered in Lecture 5
Recall the results discussed in the previous class
Proof of hyperplane separation theorem (non-strict case)
Supporting hyperplane theorem 2 (other direction)
Reading materials:
Topics covered in Lecture 6
Introduction to linear programming (LP)
Types of LP: standard and equational forms
LP duality
Statement of the strong duality theorem
Weak duality theorem and its proof
Basic feasible solutions (BFS) for LP in standard and equational forms
Statement of the fundamental theorem for LP (for both standard and equational forms)
Reading materials:
Topics covered in Lecture 7
Proof of fundamental theorem for LP (equational form)
Cone, conic hull, and their properties
Proof of finitely generated cones are closed sets
Strong alternatives
Strong alternatives and system of linear equations
Farkas Lemma (Type 1) and its proof
Reading materials:
Topics covered in Lecture 8
Discussions on the materials covered in the previous lecture
Equivalence between LP strong duality, Farkas lemma, and hyperplane separation of finitely generated cones and points
Farkas lemma (type 2) and its proof
Consequence of LP strong duality: relation between feasibility question and finding an optimal solution of a LP
Reading materials:
Topics covered in Lecture 9
Proof of strong duality of LP
Complementary slackness for LP
Statement of Clark's theorem for LP
Definitions of polyhedra and polytopes
A brief discussion on the Minkowski-Weyl theorem: equivalence between bounded polyhedra and polytopes
Reading materials:
Topics covered in Lecture 10
Farkas lemma (type 3)
Clark's theorem for LP via Farkas lemma (type 3)
Fourier-Motzkin's elimination technique for solving LP
Polyhedra and linear transformations (via Fourier-Motzkin's technique)
Polytopes are bounded polyhedra (using ``polyhedron under a linear map is a polyhedron")
Minkowski sum of sets
Minkowski sum of two polyhedra is also a polyhedron (using ``polyhedron under a linear map is a polyhedron")
Reading materials:
Additional reading material:
Chapters 2 and 4 from [BT97]
Topics covered in Lecture 11
Definition of
Extreme points
Vertices
Faces of a polyhedron
Basic feasible solution (BFS) of a polyhedron
Extreme points of a face, interior of a polyhedron etc.
Equivalence between BFS solutions and extreme points of a polyhedron
Reading materials:
Chapter 9 from [B10]
Topics covered in Lecture 12
Properties of polyhedra
Unbounded polyhedra
Bounded polyhedra are polytopes (Weyl-Minkowski Theorem)
Pointed polyhedra and lines
Recession cone and polyhedral cones
Reading materials:
Chapter 9 from [B10]
Topics covered in Lecture 13
Polyhedral cones without lines are conic hulls of polytopes
Pointed polyhedron is a Minkowski sum of the convex hull of its extreme points and its recession cones
Any polyhedron can be expressed as Minkowski sum of vector subspace, polytope and polyhedral cone
Reading materials:
Chapter 9 from [B10]
Topics covered in Lecture 14
Faces of a polyhedra
Polar of a set
Polar of a polar of a convex set containing the origin
Reading materials:
Chapters 9 and 16 from [B10]
Topics covered in Lecture 15
Introduction to incidence geometry
Point-line incidence problem
Point-line incidence bound using Kővári–Sós–Turán theorem
Alternative proof (outline) using Cauchy–Schwarz inequality
Statement of Szemerédi–Trotter (ST) theorem
Bounding the number of heavy lines using ST theorem
Basics of planar graphs
Crossing lemma, and its probabilistic proof
Reading materials:
Topics covered in Lecture 16
Proof of Szemerédi–Trotter (ST) theorem using Crossing lemma
ST theorem for points and curves
Beck's Ramsey-type result for points and lines
Erdos unit distance problem and connection to ST theorem for points and circles
Bounding number of unit area triangles using ST theorem
Reading materials: