Simons Collaboration on Algorithms and Geometry Monthly Meeting, October 2020

Date & Time


Location

Online

Invitation Only

Participation is by invitation only. All participants must register.

10:15 AM – 12:30 PM

  • Agendaplus--large
    10:15-11:15Jeff Kahn, Counting maximal independent sets in the cube, Part I
    11:15 - 11:30 AMBreak
    11:30 AM -12:30 PMJeff Kahn, Counting maximal independent sets in the cube, Part II
  • Abstractplus--large

    Counting maximal independent sets in the cube

    [The \(d\)-dimensional Hamming cube is \(\{0, 1\}^d\) with the natural graph structure, and an independent set in a graph is a set of vertices spanning no edges.]

    The center of this discussion is a recent result of Jinyoung Park and myself stating that the number of maximal independent sets in the cube is asymptotically \(2d2^{N/4}\), where \(N = 2^d\). We’ll spend some time putting this in context (combinatorial and statistical mechanical), and try to give some idea of what goes into its proof. One ingredient there is a new isoperimetric inequality for the cube that raises some interesting questions.

  • Contactsplus--large

    General Meeting Assistance
    Emily Klein
    MPS Event Coordinator, Simons Foundation
    eklein@simonsfoundation.org
    (646) 751-1262

Subscribe to MPS announcements and other foundation updates