Computer Science/Discrete Mathematics Seminar I

Topic: An isoperimetric inequality for the Hamming cube and some consequences

Speaker: Jinyoung Park

Affiliation: Rutgers University

Date & Time: Monday November 18th, 2019, 11:00am - 12:00pm

Location: Simonyi Hall 101

Video: https://video.ias.edu/csdm/2019/1118-JinyoungPark

I will introduce an isoperimetric inequality for the Hamming cube and some of its applications. The applications include a “stability” version of Harper’s edge-isoperimetric inequality, which was first proved by Friedgut, Kalai and Naor for half cubes, and later by Ellis for subsets of any size. Our inequality also plays a key role in a recent result on the asymptotic number of maximal independent sets in the cube.  This is joint work with Jeff Kahn.