("Diamond-Free Posets Problem") What is the size of the largest subset of the Boolean lattice B_(n) which includes no B_
Status Partially solved · unsolvedmath.comLLM status Open unverified
Top Open Problems Not reported cataloguedPartially solvedOpenStatement
Definitions and mathematical statement
Let $[n]=\{1,\ldots,n\}$ and order its power set $2^{[n]}$ by inclusion. A family $\mathcal F\subseteq2^{[n]}$ is diamond-free in the weak-poset sense if it contains no four distinct sets $A,B,C,D$ with \[ A\subsetneq B\subsetneq D, \qquad A\subsetneq C\subsetneq D. \] No extra incomparability condition on $B$ and $C$ is imposed. Define \[ \operatorname{La}(n,B_2) =\max\{|\mathcal F|:\mathcal F\subseteq2^{[n]} \text{ is diamond-free}\}. \] Determine this maximum, especially its sharp asymptotic value relative to the central binomial coefficient. The familiar asymptotic conjecture is \[ \operatorname{La}(n,B_2) =(2+o(1))\binom n{\lfloor n/2\rfloor}. \] Two middle levels of the Boolean lattice supply the corresponding asymptotic lower bound, since a required configuration needs three distinct ranks along each displayed chain.Families need not be downward closed, symmetric, or concentrated in a bounded number of levels. Distinctness of all four sets is essential. This is ordinary forbidden-poset containment, where required order relations must be preserved but additional relations are allowed. Requiring $B$ and $C$ to be incomparable would instead give the induced-diamond variant, with a different admissible class of set families.
Short English statement
Determine the largest weak-diamond-free family of subsets of an n-element set, in particular whether its asymptotic size is twice the middle level.Sources
- S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3100043 (AMR-030-0043), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
- S2 Cooper - Combinatorial Problems I Like (2020 snapshot), Matroids, Lattices, and Posets, source-order bullet 43. Original source indexed by AMR-030-0043. https://people.math.sc.edu/cooper/combprob.html.
Statement licence: CC-BY-4.0 · Source file
Contributions 0
No attempts yet. Significant partial results and substantial reductions are welcome. Contribute an attempt.