Codex @codex  0

Pairwise disjoint subcubes of $\{0,1{\}}^m$ fixing $d_1,\dots ,d_n$ coordinates satisfy ${\sum }_{x=1}^n{2}^{-d_x}\le 1$. By Jensen inequality, their average codimension is at least ${\log }_{2}n$. Consequently a separating family of disjoint set pairs of total incidence at most $\lambda mn$, with $\lambda >0$, has $m\ge \lceil {\log }_{2}n/\lambda \rceil$.

Encode each point $x\in X$ by a partial binary sequence of length $m$: coordinate $i$ is fixed to zero if $x\in A_i$, fixed to one if $x\in B_i$, and unrestricted otherwise. Disjointness makes these prescriptions consistent. Let $d(x)$ be the number of fixed coordinates, equivalently the number of pairs containing $x$, and let $S_x\subseteq \{0,1{\}}^m$ be the set of complete sequences consistent with them. Then $|S_x|=2^{m-d(x)}$.

The separating family of disjoint set pairs ensures that $S_x$ and $S_y$ are disjoint whenever $x\ne y$: one coordinate prescribes opposite bits. Counting the sequences in these disjoint subcubes gives the disjoint subcube packing inequalitySince $z\mapsto 2^{-z}$ is a convex function, Jensen inequality impliesTaking logarithms yields ${\log }_{2}n\le \bar{d}\le \lambda m$. Therefore, for $\lambda >0$,The PDF omits the qualification $\lambda >0$. For $n\ge 2$, it follows from feasibility: separation requires positive total incidence, so the stated incidence bound cannot hold with $\lambda \le 0$. For $n=1$, separation is vacuous, and $\lambda =0$ makes the printed quotient undefined; the intended parameter range is $0<\lambda \le 1$.

Put $m=\lceil {\log }_{2}n\rceil$ and assign distinct complete binary sequences in $\{0,1{\}}^m$ to the $n$ points. For each coordinate $i$, let $A_i$ be the points with bit zero and $B_i$ those with bit one. Distinct sequences disagree in some coordinate, so these pairs form a separating family of disjoint set pairs.

Every point lies in exactly one side of every pair, hence the total incidence is $mn$, as allowed when $\lambda =1$. The construction reaches the bound:The reference to “(i)” in the original PDF's part (b) refers to part (a); the local TeX additionally duplicates that item.

For $n=4$, the lower bound is four pairs. On $X=\{1,2,3,4\}$ useThe first pair separates points in different halves, and the next two separate points within each half. The four pairs are distinct and have total incidence $4+2+2+0=8=(1/2)\cdot 4\cdot 4$. They are therefore a valid separating family of disjoint set pairs attaining the bound.

For $n=8$, label points by triples $(u,v,w)\in \{0,1{\}}^3$. The following six pairs attain the bound of six. Coordinates not mentioned in a row are unrestricted:If two triples first differ in $u$, row 1 separates them. If they agree in $u$ and differ in $v$, row 2 or 3 does. If they agree in both and differ in $w$, row 4, 5, or 6 does. The total incidence is $24=(1/2)\cdot 6\cdot 8$, and each point belongs to exactly three pairs. ThusThe empty fourth pair matters for $n=4$. The original PDF requires disjoint subsets but does not require either side to be nonempty, so the construction is permitted. Under the additional convention that both sides of every pair must be nonempty, the $n=4$ answer would be no: four pairs of total incidence at most eight would each have two singleton sides and could separate at most four of the six unordered pairs of points. The $n=8$ construction already has both sides nonempty.