Set Systems Containing Many Maximal Chains
classification
🧮 math.CO
keywords
questionsystemsalphachainsextremalcontainingproblemanswer
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.