Set Systems Containing Many Maximal Chains. (9th October 2014)

• Record Type: Journal Article
• Authors: JOHNSON, J. ROBERT; LEADER, IMRE; RUSSELL, PAUL A.
• Is Part Of: Combinatorics, probability and computing. Volume 24:Number 3(2015:May)
• Page Start: 480
• Page End: 485
• Publication Date: 2014-10-09
• Subjects: Primary 05D05; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548314000510
• Languages: English
• ISSNs: 0963-5483

Abstract

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 $\mathcal{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.