Fix a coordinate of the Boolean hypercube, delete it in each of the two sections, and replace each section by a binary initial segment of the same size. This preserves the total size. Mathematical induction on dimension proves that it does not decrease contained edge counts; the crossing contribution is the size of the section intersection, maximized by nested initial segments.
If both sections for every coordinate are binary initial segments, then the family itself is a binary initial segment, apart from the possible family . Any missing vertex earlier than a present vertex must disagree with it in every coordinate; the two are therefore complementary and consecutive in binary order on the discrete cube, forcing this sole exceptional shape.

Articles by others on the same topic (0)

There are currently no matching articles.