Seminars in December 2016

• Jaehoon Kim (김재훈), Tree packing conjecture for bounded degree trees

  Tree packing conjecture for bounded degree trees

  Jaehoon Kim (김재훈)
  School of Mathematics, Birmingham University, UK

  2016/12/28 Wed 4PM-5PM

  We prove that if T₁,…, T_n is a sequence of bounded degree trees so that T_i has i vertices, then K_n has a decomposition into T₁,…, T_n. This shows that the tree packing conjecture of Gyárfás and Lehel from 1976 holds for all bounded degree trees.
  We deduce this result from a more general theorem, which yields decompositions of dense quasi-random graphs into suitable families of bounded degree graphs.
  In this talk, we discuss the ideas used in the proof.
  This is joint work with Felix Joos, Daniela Kühn and Deryk Osthus.

  Tags:

  • 김재훈

• Eric Vigoda, Analyzing Markov Chains using Belief Propagation

  Analyzing Markov Chains using Belief Propagation

  Eric Vigoda
  School of Computer Science, Georgia Institute of Technology, Atlanta, Georgia, USA

  2016/12/16 Friday 3PM-4PM

  For counting weighted independent sets weighted by a parameter λ (known as the hard-core model) there is a beautiful connection between statistical physics phase transitions on infinite, regular trees and the computational complexity of approximate counting on graphs of maximum degree D. For λ below the critical point there is an elegant algorithm devised by Weitz (2006). The drawback of his algorithm is that the running time is exponential in log D. In this talk we’ll describe recent work which shows O(n log n) mixing time of the single-site Markov chain when the girth>6 and D is at least a sufficiently large constant. Our proof utilizes BP (belief propagation) to design a distance function in our coupling analysis. This is joint work with C. Efthymiou, T. Hayes, D. Stefankovic, and Y. Yin which appeared in FOCS ’16.

  Tags:

  • EricVigoda