Set Systems Containing Many Maximal Chains. (9th October 2014) - JOHNSON, J. ROBERT; LEADER, IMRE; RUSSELL, PAUL A.
Abstract : The purpose of this short problem paper is to raise the following extremal question on set systems: Which set systems of a given size maximise the number of ( n + 1)-element chains in the power set P (1, 2, . . ., n )? We will show that for each fixed α > 0 there is a family of α2 n sets containing (α + o (1)) n ! such chains, and that this is asymptotically best possible. For smaller set systems 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.