M2 Informatique fondamentale 2016-2017
Discrete mathematics course
Focus: isoperimetries
Instructors. Matthieu Fradelizi (matthieu.fradelizi@u-pem.fr), Xavier Goaoc (goaoc@univ-mlv.fr) and Alfredo Hubard (Alfredo.Hubard@u-pem.fr)
Topic. This course will explore various aspects of isoperimetry in discrete mathematics and several of its applications, in particular in algorithms.
Schedule.
- Week 1 (introduction)
- Wed, jan 18th, 14:00-16:00 room 3B082 (Fradelizi) Convexity and continuous isoperimetry
- Thu, jan 19th, 10:00-12:00 room 4B09R (Hubard) Combinatorial convexity and applications
- Fri, jan 20th, 14:00-16:00 room 3B082 (Goaoc) Graphs, sampling, crossing lemma and applications
- Week 2 (isoperimetry on the discrete cube)
- Wed, jan 25th, 14:00-16:00 room 4B09R (Fradelizi) Harper's theorems
- Fri, jan 27th, 14:00-16:00 room 3B075 (Fradelizi) Applications of Harper's theorems to influence and votes
- Week 3 (Proofs by compression in hypergraphs)
- Wed, feb 1st, 14:00-16:00 room 4B09R (Goaoc) Geometric hypergraphs, VC dimension, compressive proof of Sauer's lemma
- Fri, feb 3rd, 14:00-16:00 room 4B09R (Goaoc) The Kruskal-Katona theorem and its compressive proof
- Articles proposed for the final presentations
- Testing surface area with arbitrary accuracy, by Neeman
- A simple proof of the Boros-Furedi-Barany-Pach-Gromov theorem, by Karasev
- An isoperimetric inequality on the discrete cube, and an elementary proof of the isoperimetric inequality in Gauss space, by Bobkov
- An isoperimetric inequality for antipodal subsets of the discrete cube, by Ellis and Leader
- Excluded permutation matrices and the Stanley-Wilff conjecture, by Marcus and Tardos
- Elections Can be Manipulated Often, by Friedgut, Kalai and Nisan
- Homological connectivity of random 2-complexes, by Linial and Meshulam
- Twice Ramanujan sparsifiers, by Batson, Spielman and Srivatsava
- Shallow excluded minors and improved graph decompositions, by Plotkin, Rao and Smith
- Two-weeks break
- Week 4 (Threshold in random graphs)
- Wed, feb 22nd, 14:00-16:00 room 3B082 (Hubard) Threshold phenomena in random graphs
- Fri, feb 24th, 14:00-16:00 room 4B09R (Fradelizi) Threshold for monotone property (from Harper's theorem or the Kruskal-Katona theorem)
- Week 5 (planarity and embedding)
- Wed, mar 1st, 14:00-16:00 room 4B09R (Hubard) Separator theorem for planar graphs via circle packing
- Fri, mar 3rd, 14:00-16:00 room 4B09R (Hubard) Embeddings: distorsion, cuts, bi-lipschitz, sparsest-cut
- Week 6 (expander graphs)
- Wed, mar 8th, 14:00-16:00 room 4B09R (Fradelizi) Cheeger's inequality, spectral view on isoperimetry
- Fri, mar 10th, 14:00-16:00 room 4B09R (Hubard) Construction of expander graphs
- Week 7 (expander graphs)
- Wed, mar 15th, 14:00-16:00 room 4B09R (Goaoc) Some algorithmic applications of expander graphs
- Fri, mar 17th, 14:00-16:00 room 4B09R (Goaoc) Ramanujan graphs and interleaving of polynomials