Set systems containing many maximal chains

DOI10.1017/S0963548314000510zbMATH Open1371.05299arXiv1309.4643OpenAlexW2154182959MaRDI QIDQ5364237FDOQ5364237

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)

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Most probably intersecting families of subsets
• Compressions and probably intersecting families
• Sperner's theorem and a problem of Erdős, Katona and Kleitman
• Title not available (Why is that?)
• The maximum number of disjoint pairs in a family of subsets
• Supersaturation in the Boolean lattice

Cited In (2)

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

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)