Set systems containing many maximal chains

DOI10.1017/S0963548314000510MaRDI QIDQ5364237zbMATH OpenOpenAlexFDO

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

Publication date 4 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.4643

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Extremal set theory (05D05)

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 $mathcalP(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.

Recommendations

• Maximum-size antichains in random set-systems
• On an extremal problem of set system
• Subsets of posets minimising the number of chains
• Multicoloured extremal problems
• Colouring set families without monochromatic \(k\)-chains

Cites work

• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 3256524 (Why is no real title available?)
• Compressions and probably intersecting families
• Most probably intersecting families of subsets
• Sperner's theorem and a problem of Erdős, Katona and Kleitman
• Supersaturation in the Boolean lattice
• The maximum number of disjoint pairs in a family of subsets

Cited in

(2)

• Improved bounds for cross-Sperner systems
• Chain-dependent conditions in extremal set theory

This page was built for publication: Set systems containing many maximal chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5364237)