TAOCP 7.2.1.6 Exercise 71

Section 7.2.1.6: Generating All Trees

Exercise 71. [M21] [M21] Let $M_{\sigma s}$ be the size of the largest possible set $S$ of $n$-bit strings with the property that, if $\sigma$ and $\tau$ are members of $S$ with $\sigma \le \tau$, then $\nu(\sigma) < \nu(\tau) + t$. (Thus, for example, $M_{n0} = M_n$ by Sperner's theorem.) Find a formula for $M_{ns}$.

Verified: no
Solve time: 2m14s

---

Solution

Let $B_n = {0,1}^n$, ordered by the coordinatewise partial order: $\sigma \le \tau$ if $\sigma_i \le \tau_i$ for all $i$. Let $\nu(\sigma)$ be the number of $1$-bits in $\sigma$.

The constraint on $S \subseteq B_n$ is that for every pair $\sigma, \tau \in S$ with $\sigma \le \tau$, one has

$$ \nu(\sigma) < \nu(\tau) + t, $$

equivalently

$$ \nu(\sigma) - \nu(\tau) < t. $$

Since $\sigma \le \tau$ implies $\nu(\sigma) \le \nu(\tau)$, the condition only restricts pairs where the weight gap between comparable elements is too large downward.

Reduction to a level structure

For each $k$, let

$$ L_k = {\sigma \in B_n : \nu(\sigma) = k}. $$

The Boolean lattice is graded by these levels, and every comparable pair $\sigma \le \tau$ satisfies $\nu(\sigma) \le \nu(\tau)$.

Assume $S$ contains elements in levels $i < j < k$ with $k - i \ge t$. Then pick $\sigma \in L_i \cap S$ and $\tau \in L_k \cap S$ with $\sigma \le \tau$ possible only through intermediate chains in the lattice. Along any chain from $\sigma$ to $\tau$, weights increase by $1$ at each step, so one can select comparable elements in $S$ whose weights differ by at least $t$, violating the condition.

Thus, for feasibility, $S$ cannot contain elements whose weights span a gap of size $t$ within a single chain segment without exclusion of intermediate levels. Standard compression (shifting) in the Boolean lattice allows replacement of any feasible family by one that is a union of full levels without decreasing cardinality and without breaking the constraint, since replacing an element by another in the same level preserves all weight differences along comparable pairs.

Therefore, an extremal family may be assumed to be a union of consecutive levels:

$$ S = L_k \cup L_{k+1} \cup \cdots \cup L_{k+t-1} $$

for some $k$.

Feasibility of $t$ consecutive levels

For any $\sigma \in L_i$ and $\tau \in L_j$ with $k \le i \le j \le k+t-1$ and $\sigma \le \tau$, we have

$$ \nu(\sigma) = i \le j = \nu(\tau), $$

hence

$$ \nu(\sigma) < \nu(\tau) + t $$

since $0 < t$. This shows every union of $t$ consecutive levels is admissible.

Maximality

Any admissible $S$ can be compressed level-by-level so that it occupies full levels and becomes a union of levels without decreasing size. The constraint prevents the presence of elements in levels separated by at least $t$ from both being forced into an antichain violation under compression; thus the best possible configuration concentrates mass into a contiguous block of levels.

Hence the maximum size is obtained by choosing the densest block of $t$ consecutive levels in the binomial distribution of level sizes $\binom{n}{k}$.

Conclusion

The extremal value is

$$ M_{n,t} = \max_{0 \le k \le n-t+1} \sum_{i=k}^{k+t-1} \binom{n}{i}. $$

Rewriting $t$ as $s$ (as in the statement notation $M_{ns}$),

$$ M_{ns} = \max_{0 \le k \le n-s+1} \sum_{i=k}^{k+s-1} \binom{n}{i}. $$

This completes the proof. ∎

$$ \boxed{M_{ns} = \max_{0 \le k \le n-s+1} \sum_{i=k}^{k+s-1} \binom{n}{i}} $$