## Jinyoung Park (박진영) presented her work on the number of maximal independent sets in the hypercube graph at the Discrete Math Seminar

On June 3, 2019, Jinyoung Park (박진영) from Rutgers University, USA presented her joint work with Jeff Kahn on the number of maximal independent sets in the hypercube graph at the Discrete Math Seminar. The title of her talk was “The maximal independent sets in the Hamming cube”.

## Jinyoung Park (박진영), The number of maximal independent sets in the Hamming cube

Let $Q_n$ be the $n$-dimensional Hamming cube (hypercube) and $N=2^n$. We prove that the number of maximal independent sets in $Q_n$ is asymptotically $2n2^{N/4}$, as was conjectured by Ilinca and Kahn in connection with a question of Duffus, Frankl and Rödl. The value is a natural lower bound derived from a connection between maximal independent sets and induced matchings. The proof of the upper bound draws on various tools, among them “stability” results for maximal independent set counts and old and new results on isoperimetric behavior in $Q_n$. This is joint work with Jeff Kahn.