Math-2098 · mathematics · Combinatorics

Math-2098

For any poset P, define ex(n,P) to be the size of the largest subset of the Boolean lattice B_(n) which includes no (inj

Status Partially solved · unsolvedmath.comLLM status Open unverified

Top Open Problems Not reported cataloguedPartially solvedOpen

Statement

Definitions and mathematical statement

Let $P$ be a fixed nonempty finite partially ordered set. A family $\mathcal F\subseteq2^{[n]}$ contains $P$ if there is an injective map $\varphi:P\to\mathcal F$ such that \[ x<_P y\ \Longrightarrow\ \varphi(x)\subsetneq\varphi(y). \] Images of incomparable elements may be comparable; this is weak poset containment. Say that $\mathcal F$ is $P$-free when no such map exists, and write \[ \operatorname{La}(n,P) =\max\{|\mathcal F|:\mathcal F\subseteq2^{[n]} \text{ is }P\text{-free}\}. \] Does the limit \[ \lim_{n\to\infty} \frac{\sqrt n\,\operatorname{La}(n,P)}{2^n} \] exist for every fixed $P$? Equivalently, by the asymptotic formula for the central binomial coefficient, does $\operatorname{La}(n,P)/\binom n{\lfloor n/2\rfloor}$ converge?

The poset is fixed throughout the limit; its size or relations cannot vary with $n$. The question asks for actual convergence, not merely upper and lower bounds of the same order of magnitude. It includes degenerate cases with limiting constant zero, such as a one-element forbidden poset. An induced-poset embedding would also reflect noncomparability and defines a different extremal problem. No such order-reflection condition belongs to this entry.

Short English statement

For every fixed finite poset, does the maximum size of a weak-poset-free Boolean-lattice family have a limiting normalized density?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 0

No attempts yet. Significant partial results and substantial reductions are welcome. Contribute an attempt.