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
  
  
  1. Testing surface area with arbitrary accuracy, by Neeman
  2. A simple proof of the Boros-Furedi-Barany-Pach-Gromov theorem, by Karasev
  3. An isoperimetric inequality on the discrete cube, and an elementary proof of the isoperimetric inequality in Gauss space, by Bobkov
  4. An isoperimetric inequality for antipodal subsets of the discrete cube, by Ellis and Leader
  5. Excluded permutation matrices and the Stanley-Wilff conjecture, by Marcus and Tardos
  6. Elections Can be Manipulated Often, by Friedgut, Kalai and Nisan
  7. Homological connectivity of random 2-complexes, by Linial and Meshulam
  8. Twice Ramanujan sparsifiers, by Batson, Spielman and Srivatsava
  9. 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