The leading constant in the Erdős–Kleitman asymptotic for families of subsets containing no 4-member Boolean algebra

Erdős and Kleitman proved in 1971 that a family $Q$ of subsets of an $n$-element set containing no 4-member Boolean algebra — no four distinct members $A, B, C, D$ with $A \cup B = C$ and $A \cap B = D$ — has size at most a constant times $2^n / n^{1/4}$, and constructed such families of size at least another constant times $2^n / n^{1/4}$. They then asked whether an absolute constant $c$ exists with $\max|Q| = c \cdot 2^n / n^{1/4} + o(2^n / n^{1/4})$, writing that they could not prove this and had no guess at the value of $c$. The known follow-up work (Gunderson–Rödl–Sidorenko 1999, Johnston–Lu–Milans 2015, and later) improves only the constants and $d$-dependence of the general-$d$ upper bound $b(n,d) \le c_d \cdot n^{-1/2^d} \cdot 2^n$, never sharpening either side of the $d = 2$ problem to a matching leading constant, so both the existence and the value of $c$ remain open. The problem is to prove or disprove the existence of the limit $c = \lim_{n \to \infty} b(n,2) \cdot n^{1/4} / 2^n$ and, if it exists, determine it.

Background

Fix an $n$-element set $[n] = \{1, \dots, n\}$ and let $2^{[n]}$ be the collection of all $2^n$ subsets of $[n]$, the Boolean lattice, ordered by inclusion; any subcollection $Q \subseteq 2^{[n]}$ is called a family of sets. Sperner's theorem, the founding result of extremal set theory, determines the largest family containing no two sets one of which contains the other. The next level of algebraic structure is a $d$-dimensional Boolean algebra of sets: a collection of $2^d$ distinct sets built from pairwise disjoint nonempty sets $X_1, \dots, X_d$ and a possibly empty set $X_0$ by taking, for every subset $I$ of $\{1, \dots, d\}$, the union of $X_0$ with all $X_i$ whose index $i$ lies in $I$. For $d = 2$ this is a 4-member Boolean algebra: four distinct sets $A, B, A \cup B, A \cap B$ with $A$ and $B$ incomparable, the configuration the 1971 source characterizes by the equations $A \cup B = C$ and $A \cap B = D$. Write $b(n,d)$ for the maximum size of a family in $2^{[n]}$ containing no $d$-dimensional Boolean algebra. Forbidding 1-dimensional Boolean algebras is exactly Sperner's condition, with maximum $C(n, \lfloor n/2 \rfloor)$, which is about $2^n / n^{1/2}$; Erdős and Kleitman showed that forbidding the 4-member algebra costs far less: $b(n,2)$ is of order $2^n / n^{1/4}$. Their upper bound comes from a Zarankiewicz-type argument — a bound on 0-1 matrices with no $2 \times 2$ all-ones submatrix, applied to the incidence structure between two layers (the families of $k$-element and $(k+1)$-element subsets) — combined with the Lubell function, the standard weighted measure of how a family spreads across layers, which assigns each set $A$ the weight $1/C(n, |A|)$ and sums over the family; a single set of size near $n/2$ carries Lubell weight about $n^{1/2}/2^n$, so an entire middle layer contributes weight $1$. Their lower bound takes all sets whose sizes lie in a Sidon set of integers — a set whose pairwise sums are all distinct — of about $n^{1/4}$ layer sizes near the middle of the lattice, since Sidon-ness blocks the layer arithmetic $|A| + |B| = |A \cup B| + |A \cap B|$ that a 4-member Boolean algebra would force. The same circle of ideas connects the problem to sets of integers containing no affine $d$-cube, that is, no $2^d$ distinct numbers of the form $x_0$ or $x_0$ plus the sum of $x_i$'s over a nonempty subset of $\{1, \dots, d\}$, studied by Gunderson and Rödl; for $d = 2$ the integer problem is the classical Sidon-set problem with extremal size $\Theta(n^{1/2})$. Later literature sharpened the order picture for general $d$: Gunderson, Rödl and Sidorenko proved $b(n,d) \le c_d \cdot n^{-1/2^d} \cdot 2^n$ with a constant $c_d$ depending badly on $d$, via a reduction to hypergraph Turán-type bounds for complete $d$-partite hypergraphs with parts of size 2; Johnston, Lu and Milans improved this to $b(n,d) \le C \cdot n^{-1/2^d} \cdot 2^n$ with an absolute constant $C$, and proved that, for sufficiently large $n$, the Lubell function of any Boolean-algebra-free family is at most $2(n+1)^{1-2^{1-d}}$. None of these methods tracks the leading constant at $d = 2$: Lubell and random-restriction arguments are order-level by design, and the hypergraph reductions lose large multiplicative factors, which is exactly why the Erdős–Kleitman question about the constant $c$ survives.

Problem Statement

Let $b(n,2)$ be the maximum cardinality of a family $Q$ of subsets of an $n$-element set such that no four distinct members $A, B, C, D$ of $Q$ satisfy $A \cup B = C$ and $A \cap B = D$ (equivalently, $Q$ contains no 4-member Boolean algebra, that is, no 2-dimensional Boolean algebra of sets). Prove or disprove that the limit $c = \lim_{n \to \infty} b(n,2) \cdot n^{1/4} / 2^n$ exists, that is, that $b(n,2) = (c + o(1)) \cdot 2^n / n^{1/4}$ for an absolute constant $c$; and if it exists, determine the exact value of $c$. A positive resolution consists of a construction of $B_2$-free families of size $(c - o(1)) \cdot 2^n / n^{1/4}$ together with a proof that every $B_2$-free family has size at most $(c + o(1)) \cdot 2^n / n^{1/4}$ with the same constant $c$. A disproof consists of proving the limit does not exist, for example by exhibiting $\epsilon > 0$ and two sequences $n_k, m_k \to \infty$ such that $b(n_k,2) \cdot n_k^{1/4}/2^{n_k}$ and $b(m_k,2) \cdot m_k^{1/4}/2^{m_k}$ stay separated by more than $\epsilon$ for all large $k$.

References

1. P. Erdős and D. J. Kleitman, On collections of subsets containing no 4-member Boolean algebra, Proceedings of the American Mathematical Society 28 (1971), no. 1, 87–90. DOI: 10.1090/S0002-9939-1971-0270924-9. https://doi.org/10.1090/S0002-9939-1971-0270924-9
2. D. S. Gunderson and V. Rödl, Extremal problems for affine cubes of integers, Combinatorics, Probability and Computing 7 (1998), no. 1, 65–79. DOI: 10.1017/S0963548397003283. https://doi.org/10.1017/S0963548397003283
3. D. S. Gunderson, V. Rödl and A. Sidorenko, Extremal problems for sets forming Boolean algebras and complete partite hypergraphs, Journal of Combinatorial Theory, Series A 88 (1999), no. 2, 342–367. DOI: 10.1006/jcta.1999.2973. https://doi.org/10.1006/jcta.1999.2973
4. T. Johnston, L. Lu and K. G. Milans, Boolean algebras and Lubell functions, Journal of Combinatorial Theory, Series A 136 (2015), 174–183; preprint arXiv:1307.3312. DOI: 10.1016/j.jcta.2015.06.004. https://arxiv.org/abs/1307.3312
5. J. Barát, Z. Füredi, I. Kantor, Y. Kim and B. Patkós, Large B_d-free and union-free subfamilies, Electronic Notes in Discrete Mathematics 38 (2011), 101–104; preprint arXiv:1012.3918. DOI: 10.1016/j.endm.2011.09.017. https://arxiv.org/abs/1012.3918
6. I. Tomon, Forbidden induced subposets of given height, Journal of Combinatorial Theory, Series A 161 (2019), 537–562; preprint arXiv:1708.07711. DOI: 10.1016/j.jcta.2018.09.008. https://arxiv.org/abs/1708.07711
7. J. Liu and G. Yu, A relationship for LYM inequalities between Boolean lattices and linear lattices with applications, Advances in Applied Mathematics 171 (2025), article 102935; preprint arXiv:2403.04817. DOI: 10.1016/j.aam.2025.102935. https://arxiv.org/abs/2403.04817
8. G. O. H. Katona and Y. Mao, Multiplicity for partially ordered sets, preprint arXiv:2607.00456 (2026). https://arxiv.org/abs/2607.00456
9. G. O. H. Katona and Y. Mao, Ramsey-Turán theory for partially-ordered sets, preprint arXiv:2605.31546 (2026). https://arxiv.org/abs/2605.31546