BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20180101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190603T163000
DTEND;TZID=Asia/Seoul:20190603T173000
DTSTAMP:20260423T090713
CREATED:20190411T160640Z
LAST-MODIFIED:20240707T090357Z
UID:770-1559579400-1559583000@dimag.ibs.re.kr
SUMMARY:Jinyoung Park (박진영)\, The number of maximal independent sets in the Hamming cube
DESCRIPTION: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.
URL:https://dimag.ibs.re.kr/event/2019-06-03/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR