Groupe de travail: Graphes, Algorithmes, Probabilités

Date Titre Orateur Heure Salle
13/09/10 "Counting independent stets up to the tree threshold" d'après Dror Weitz Marc 14h Verte
20/09/10 "Matroides" d'après James Oxley Anne !!10h!! LINC
27/09/10 "Polynomials with the half-plane property and matroid theory" d'après Petter Brändén Justin !!10h!! verte 2
04/10/10 "Biased Random Walks on Galton-Watson Trees" d'après Lyons, Pemantle, Peres Omid 14h rose
11/10/10 "Bootstrap percolation" Hamed 14h LINC
25/10/10 "Poisson approximations" Yogesh 14h LINC
22/11/10 "The push algorithm for broadcasting and the geometry of graphs" Nikolaos Fountoulakis (MPI) 14h Rose
29/11/10 "Poisson Hypothesis for Infinite Generalized Jackson Networks" Alexander Rybko (IPIT) 14h Rose
13-14/12/10 "Spectra of diluted random graphs" Justin et Marc IHP
20/12/10 "Loss networks and Markov random fields" Marc 14h LINC
10/2/11 "Boolean functions" Yogesh 14h LINC
17/2/11 "Discrete Fourier analysis" Marc 14h LINC
3/3/11 "Hypercontractivity and Applications to Noise Sensitivity" Yogesh 14h Orange 1
10/3/11 "Application to percolation" Yogesh 14h LINC
8/4/11 "Phase transitions and computational complexity" Amin Coja-Oghlan (University of Warwick) 11h Rose

Pour cet été, c'est Stéphane qui reprend la main. Suivez le lien!

Voici un début de liste de livres/articles. L'ordre est assez aléatoire!

Merci de m'envoyer vos suggestions!


  • Janson, Luczak and Rucinski, "Random Graphs".
  • Alon and Spencer, "The Probabilistic Method".
  • Mézard and Montanari, "Information, Physics and Computation".
  • Grimmett, "Probability on graphs".
  • Presutti, "Scaling limits in Statistical Mechanics and Microstructures in Continuum Mechanics".
  • Aldous and Fill, "Reversible Markov Chains and Random Walks on Graphs".
  • Levin, Peres, Wilmer, "Markov Chains and Mixing Times".
  • Welsh, "Complexity: Knots, Colourings and Counting".


  • Jordan and Wainwright, "Graphical models, exponential families, and variational inference".
  • van der Hofstad, "Random Graphs and Complex Networks".
  • Wormald, "Models of random regular graphs".
  • Saloff-Coste, "Lectures on finite Markov chains".
  • Jerrum, "Counting, sampling and integrating: algorithms and complexity".
  • Garban and Steiff, "Noise sensitivity and percolation".
  • Kalai and Safra,"Threshold Phenomena and Influence".
  • Hoory, Linial, and Wigderson, "Expander graphs and their applications".
  • Mossel, "Survey: Information flow on trees".


  • Jordan and Sejnowski (ed.), "Graphical Models".
  • Johnstone, "On the distribution of the largest eigenvalue in principal components analysis".
  • Amini and Wainwright, "High-dimensional analysis of semidefinite relaxations for sparse principal components".
  • Candes and Tao, "The Dantzig selector: Statistical estimation when p is much larger than n".
  • Drineas et al., "Clustering in large graphs and matrices".


  • Arora and Barak, "Computational Complexity: A Modern Approach".
  • Papadimitriou and Steiglitz, "Combinatorial optimization".
  • Schrijver, "Combinatorial optimization : polyhedra and efficiency".
  • Boyd and Vandenberghe, "Convex Optimization".
  • Trevisan, "Inapproximability of Combinatorial Optimization Problems".
  • Vazirani, "Approximation Algorithms".


  • Godsil and Royle, "Algebraic Graph Theory".
  • Colin de Verdière, "Spectres de graphes".

    Return home