Instructor: Prof. Shakhar Smorodinsky
 Office: Math building (58), room 208
 Tel.: (08) 6461604
 Email: "My first name" at math and you know whats next"

Time and place of lectures:
 Tuesday 1214 building 58 (math) room 201
 Wednesday 1416 building 58 (math) room 201

Lecture Notes from previous years (Taken by Yelena Yuditsky)
Homework exercises
About the course:
The course is intended for
3rd year undergraduate (with my permisiion) as well as M.Sc. and Ph.D. students both in computer science
and/or mathematics.
We will touch main topics in the area of 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 nonrelated areas such as additive number theory or hard Erdos problems.
The course does not require any special background except for basic linear algebra, probability and combinatorics.
Prerequisites
Probability.
Gradinghomework
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 LiptonTarjan 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 ksets in R2 and R3. An application of incidences to additive number theory.
Coloring and hiting problems for geometric hypergraphs : VCdimension, Transversals and Epsilonnets. Weak epsnets for convex sets. Conflictfree colorings .
" Arrangements and Davenport Schinzel sequences.
Geometric permutations.
" Geometric Ramsey and Turan type theorems: Application of Dilworth theorem, ErdosSzekeres theorem for convex sets, quasiplanar graphs.
RECOMMENDED BOOKS:
 J. Matousek, Lectures on Discrete Geometry, GTM 212, Springer 2002.
 J. Pach and P.K. Agarwal, Combinatorial Geometry, John Wiley & Sons, NewYork, NY, 1995.

