Discrete Geometry (201-2-0191 ). Fall 2008/9

Ben Gurion University of the Negev, Department of Mathematics

Instructor: Dr. Shakhar Smorodinsky
  • Office: Math building (58), room 208
  • Tel.: (08) 6461604
  • E-mail: "My first name" at math and you know whats next"
Time and place of lectures:
  • Sundays 16:00-18:00 bldg 32 room 113
  • Tuesdays16:00-18:00 bldg 34 room 209

Lecture Notes (by Yelena Yuditsky)

Lecture 2 , Lecture 3 , Lecture 4 , Lecture 5 , Lecture 6 , Lecture 7 , Lecture 8 , Lectures 9-10 , Lecture 11 , Lecture 12 , Lecture 13 , Lecture 14 , Lecture 15 , Lecture 16 , Lecture 17 , Lectures 18-19 , Lecture 20 , Lecture 21 , Lecture 22 , Lecture 23 , Lecture 24

Homework exercises

Exercise 1 (PDF). (due 14.12.2008)

Exercise 2 (PDF). (due 11.01.2009)

Exercise 3 (PDF). (due 15.02.2009)

Exercise4 (PDF). (due 1.03.2009)

About the course:

  The course is intended for M.Sc. students as well as 3rd year undergraduate students both in computer science and/or mathematics. We will touch main topics in the area discrete geometry. Some of the topics are motivated by the analysis of algorithms in computational geometry, wireless and sensor networks. Some other beautiful and elegant tools are proved to be powerful in seemingly non-related areas such as additive number theory or hard Erdos problems. The course does not require any special background except for basic linear algebra, and a little of probability and combinatorics.

Prerequisites

  • 201-18001 Probability.

    Grading

    TBA

    Syllabus

  • " Fundamental theorems and basic definitions: Convex sets, convex combinations, Separation Helly's theorem, fractional Helly, Radon's theorem, Caratheodory's theorem, centerpoint theorem. Tverberg's theorem. Planar graphs. Koebe's Theorem. A geometric proof of Lipton-Tarjan separator theorem for planar graphs.
  • " Geometric graphs: the crossing lemma. Application of crossing lemma to Erdos problems: Incidences between points and lines and points and unit circles. Repeated distance problem, distinct distances problem. Selection lemmas: points and discs, points and simplexes. upper bounds on k-sets in R2 and R3. An application of incidences to additive number theory. Coloring and hiting problems for geometric hypergraphs : VC-dimension, Transversals and Epsilon-nets. Weak eps-nets for convex sets. Conflict-free colorings .
  • " Arrangements and Davenport Schinzel sequences. Geometric permutations.
  • " Geometric Ramsey and Turan type theorems: Application of Dilworth theorem, Erdos-Szekeres theorem for convex sets, qusi-planar graphs.

    RECOMMENDED BOOKS:

    • J. Matousek, Lectures on Discrete Geometry, GTM 212, Springer 2002.
    • J. Pach and P.K. Agarwal, Combinatorial Geometry, John Wiley & Sons, New-York, NY, 1995.