Loading Events

« All Events

:

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

June 3 Monday @ 4:30 PM - 5:30 PM

Room B232, IBS (기초과학연구원)

Speaker

Jinyoung Park (박진영)
Department of Mathematics, Rutgers University, USA
https://sites.google.com/view/jinyoungpark

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.

Details

Date:
June 3 Monday
Time:
4:30 PM - 5:30 PM
Event Category:
Event Tags:
,

Venue

Room B232
IBS (기초과학연구원)

Organizer

Sang-il Oum
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
Discrete Mathematics Group (DIMAG)
Center for Mathematical and Computational Sciences
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr
Copyright (c) IBS 2018. All rights reserved.