Can I read Set Systems Containing Many Maximal Chains on EtoBox?

Set Systems Containing Many Maximal Chains by Johnson, J. Robert; Leader, Imre; Russell, Paul A. is a scholarly article available to read on EtoBox.

What is Set Systems Containing Many Maximal Chains about?

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.

Author

Johnson, J. Robert; Leader, Imre; Russell, Paul A.

Published

2013

Language

EN