Forbidden graded posets in middle levels: supersaturation, enumeration and randomness
Abstract
Let P be a fixed finite poset whose maximal chains all have h elements, and let 𝒲n,h be the union of h consecutive middle levels of 2[n]. We prove that the maximum size of a P-free subfamily of 𝒲n,h is (π(P)+o(1))Mn for a constant π(P), where Mn=binom n⌊ n/2⌋, and that the number of P-free subfamilies is 2(π(P)+o(1))Mn. For connected P we prove supersaturation above (π(P)+ε)Mn and determine, in terms of the coordinate patterns of the copies of P in the window, a range of p in which the largest P-free subfamily of the random family 𝒲n,h(p) has size (π(P)+o(1))pMn and a range in which it has size (h+o(1))pMn; the two ranges meet whenever all copies have the same pattern. For the Boolean poset Qd, which has height d+1, the threshold order in the corresponding window 𝒲n,d+1 is n−d/(2d−1), and πd=π(Qd) satisfies (d+1)λd≤πd≤ d+1−binom d⌊ d/2⌋−1, where λd is the vertex Turán density of d-dimensional subcubes in the hypercube. Together with a construction of Ellis, Ivan and Leader this gives d+1−πd=exp(−Θ(d)). For the diamond, known bounds give 2.1479≤π2≤2.15121.
Related
- Meet obstructions and saturation for the constant window convolution on graded posets
- Supersaturation: Cliques and Positive Square Energy
- Strict spectral supersaturation for cliques: extremal graphs and sharp thresholds
- Complete counterexamples to Mubayi's supersaturation conjecture for graphs
- Strong counterexamples to Mubayi's supersaturation conjecture in every uniformity
BibTeX
@misc{ai2026forbidden,
title = {{Forbidden graded posets in middle levels: supersaturation, enumeration and randomness}},
author = {Jiangdong Ai and Mingyu Liu and Zhiyu Song},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.28413},
eprint = {2610.28413},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.28413},
}
RIS
TY - UNPB
TI - Forbidden graded posets in middle levels: supersaturation, enumeration and randomness
AU - Jiangdong Ai
AU - Mingyu Liu
AU - Zhiyu Song
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.28413
UR - https://arxiv.org/abs/2610.28413
AB - Let P be a fixed finite poset whose maximal chains all have h elements, and let 𝒲_n,h be the union of h consecutive middle levels of 2^[n]. We prove that the maximum size of a P-free subfamily of 𝒲_n,h is (π(P)+o(1))M_n for a constant π(P), where M_n=binom n⌊ n/2⌋, and that the number of P-free subfamilies is 2^(π(P)+o(1))M_n. For connected P we prove supersaturation above (π(P)+ε)M_n and determine, in terms of the coordinate patterns of the copies of P in the window, a range of p in which the largest P-free subfamily of the random family 𝒲_n,h(p) has size (π(P)+o(1))pM_n and a range in which it has size (h+o(1))pM_n; the two ranges meet whenever all copies have the same pattern. For the Boolean poset Q_d, which has height d+1, the threshold order in the corresponding window 𝒲_n,d+1 is n^−d/(2^d−1), and π_d=π(Q_d) satisfies (d+1)λ_d≤π_d≤ d+1−binom d⌊ d/2⌋^−1, where λ_d is the vertex Turán density of d-dimensional subcubes in the hypercube. Together with a construction of Ellis, Ivan and Leader this gives d+1−π_d=exp(−Θ(d)). For the diamond, known bounds give 2.1479≤π_2≤2.15121.
ER -