A note on balanced independent sets in the cube

Ben Barber

Research output: Contribution to journalArticle (Academic Journal)peer-review

74 Downloads (Pure)

Abstract

Ramras conjectured that the maximum size of an independent set in the discrete cube Qn containing equal numbers of sets of even and odd size is 2n−1 − \binom {n−1} {(n−1)/2} when n is odd. We prove this conjecture, and find the analogous bound when n is even. The result follows from an isoperimetric inequality in the cube.
Original languageEnglish
Pages (from-to)205-207
Number of pages3
JournalAustralasian Journal of Combinatorics
Volume52
Publication statusPublished - Feb 2012

Fingerprint Dive into the research topics of 'A note on balanced independent sets in the cube'. Together they form a unique fingerprint.

Cite this