M2 Informatique fondamentale 2015-2016
Discrete mathematics course
Focus: combinatorial geometry
Instructors. Xavier Goaoc (goaoc@univ-mlv.fr) and Nabil Mustafa (nabilhassan.mustafa@esiee.fr)
Material. Several lectures will be based on Matousek's Lectures in discrete geometry, referenced as [LDM] below. Additional ressources can be found below (and will be added as the lectures progress).
Schedule. The hours and rooms are indicative. The up-to-date version is available from the ENT.
- Week 1 (geometric graph theory)
- Tue, jan 19th, 15:30 (Mustafa): planarity, embeddability, Hanani-Tutte theorem. Notes
- Wed, jan 20th, 10:45 (Goaoc): crossing lemma, Szemeredi-Trotter theorem, application to sum-product. Slides
- Week 2
- Wed, jan 27th, 10:45 (Goaoc): Simplicial complexes and inclusion-exclusion.
- Fri, jan 29th, 9:00 (Goaoc): Delaunay triangulations, Voronoi diagrams, application to simplified inclusion-exclusion
- Week 3 (set systems)
- Tue, feb 2nd, 15:30 (Mustafa): shatter function, VC dimension, Sauer's lemma (proofs by induction, compression, linear algebra). Notes
- Wed, feb 3rd, 10:45 (Goaoc): shifting and Kruskal-Katona theorem Frankl's paper
- Week 4 (set systems)
- Tue, feb 9th, 15:30 (Mustafa): discrepancy of set systems, Spencer's theorem. Notes
- Thu, feb 11th, 15:30 (Mustafa): epsilon nets. Notes
- Week 5
- Distribution of articles for final presentations.
Recommandations are:
- Sublinear geometric algorithms, Chazelle, Lui, Magen. paper
- Improved deterministic algorithms for linear programming in low dimensions, Chan. paper
- A Simple Aggregative Algorithm for Counting Triangulations of Planar Point Sets and Related Problems, Alvarez, Seidel. paper
- Simplifying inclusion-exclusion formulas, Goaoc, Matousek, Patak, Safernova, Tancer. paper
- Helly theorems and generalized linear programming, Amenta. paper
Other possible choices are
- A counterexample to Beck's conjecture on the discrepancy of three
permutations, Newman, Nikolov. paper
- Canonical Ordering for Triangulations on the Cylinder, with Applications to Periodic Straight-line Drawings, Castelli Aleardi, Devillers, Fusy. paper
- On characterizing terrain visibility graphs, Evans, Saeedi. paper
- Morris's pigeonhole principle and the Helly theorem for unions of convex sets Eckhoff, Nischke.
- Wed, feb 17th, 10:45 (Goaoc): Helly and fractional Helly theorems, centerpoint theorem, selection lemma, weak epsilon-nets.
- Fri, feb 19th, 14:00 (Goaoc): Tucker lemma, Borsuk-Ulam theorem, Kneser colorings, ham-sandwich theorems
- 2 weeks break
- Week 6 (polynomial methods)
- Wed, mar 9th, 10:45 (Goaoc): Kakeya-Besicovitch sets, finite version, Dvir's theorem, joints
- Thu, mar 10th, 14:00 (Goaoc): polynomial ham sandwich and polynomial partitioning theorems
- Week 7 (embeddings) [LDM Chapter 15]
- Mon, mar 14th, 10:45 (Goaoc): embeddings, Johnson-Lindenstrauss Lemma
- Fri, mar 18th, 14:00 (Goaoc): embedding into \l_2 (Bourgain's theorem) and \l_{\infty} (Matousek's theorem)
- Week 8: final presentations
- Tue, mar 22nd: Dubov (15:30), Csikos (16:30)
- Thu, mar 24th: Jartoux (9:30), Antunes (10:30), Malalanirainy (14:00)