Set Systems Containing Many Maximal Chains

Abstract

The purpose of this short problem paper is to raise an extremal question on set systems which seems to be natural and appealing. Our question is: which set systems of a given size maximise the number of $(n+1)$-element chains in the power set $\mathcal{P}(\{1,2,\dots ,n\})$? We will show that for each fixed $\alpha >0$ there is a family of $\alpha 2^n$ sets containing $(\alpha +o(1))n!$ such chains, and that this is asymptotically best possible. For smaller set systems we are unable to answer the question. We conjecture that a `tower of cubes' construction is extremal. We finish by mentioning briefly a connection to an extremal problem on posets and a variant of our question for the grid graph.

5 pages

References in corpus (2)

• Supersaturation in the Boolean lattice
• Sperner's Theorem and a Problem of Erdos-Katona-Kleitman