pith. sign in

arxiv: 1309.4643 · v1 · pith:ZDYHDF5Enew · submitted 2013-09-18 · 🧮 math.CO

Set Systems Containing Many Maximal Chains

classification 🧮 math.CO
keywords questionsystemsalphachainsextremalcontainingproblemanswer
0
0 comments X
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.