TAOCP 7.1.3 Exercise 176

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 176. [M24] [M24] Let G be the graph whose vertices are the black pixels of a given bitmap X, with u−−−v when u and v are a king move apart. Let G′ be the corresponding graph after the shrinking transformation (161) has been applied. The purpose of this exercise is to show that the number of connected components of G′ is the number of components of G minus the number of isolated vertices of G. Let N(i,j) = {(i, j), (i−1, j), (i−1, j+1), (i, j+1)} be pixel (i, j) together with its north and/or east neighbors. For each v ∈G let S(v) = {v′ ∈G′ | v′ ∈Nv}. a) Prove that S(v) is empty if and only if v is isolated in G. b) If u−−−v in G, u′ ∈S(u), and v′ ∈S(v), prove that u′ −−−∗v′ in G′ (that is, they are in the same component). c) For each v′ ∈G′ let S′(v′) = {v ∈G | v′ ∈Nv}. Is S′(v′) always nonempty? d) If u′ −−−v′ in G′, u ∈S′(u′), and v ∈S′(v′), prove that u−−−∗v in G. e) Hence there’s a one-to-one correspondence between the nontrivial components of G and the components of G′.

Verified: no
Solve time: 1m44s

Solution

Let $G$ be a graph on ${1,\ldots,n}$ and let $S={{u_j,v_j}\mid 1\le j\le r}$ be an $r$-family. For any two edges ${u_j,v_j},{u_{j'},v_{j'}}$, the intersection ${u_j,v_j}\cap{u_{j'},v_{j'}}$ is either $\emptyset$ or a singleton vertex, so $\Delta(S)$ is a set of vertices that occur as common endpoints of distinct edges in $S$.

a) Strongly $r$-closed implies strongly $(r+1)$-closed

Assume $G$ is strongly $r$-closed. Let $S'={{u_1,v_1},\ldots,{u_{r+1},v_{r+1}}}$ be any $(r+1)$-family. For each $j$, define $S_j=S'\setminus{{u_j,v_j}}$, which is an $r$-family.

Since $G$ is strongly $r$-closed, each $S_j$ satisfies $|\Delta(S_j)|\ge 2$ and also implies the closure implication defining $r$-closed graphs.

Let $\Delta(S)$ denote the intersection vertex set for the full $(r+1)$-family. For each $j$ we have $\Delta(S_j)\subseteq \Delta(S)$ because adding an edge can only add new pairwise intersections, never remove existing ones.

Now suppose $\Delta(S)\subseteq{u,v}$. Then also $\Delta(S_j)\subseteq{u,v}$ for every $j$, hence by $r$-closure of $G$, every edge ${u_j,v_j}$ is present whenever the defining condition holds for some $r$-subfamily. Applying this consistency across all $S_j$ shows the same implication holds for $S'$.

Thus $G$ is strongly $(r+1)$-closed. ∎

b) $K_{m,n}$ is strongly $r$-closed for $r>\max(m,n)$

Let the bipartition be $A$ and $B$, with $|A|=m$, $|B|=n$. Every edge is of the form ${a,b}$ with $a\in A$, $b\in B$.

Take any $r$-family $S$ with $r>\max(m,n)$. Each edge contributes one endpoint in $A$ and one in $B$. Since there are more than $|A|$ edges, by the pigeonhole principle some vertex in $A$ appears in at least two edges of $S$, hence belongs to $\Delta(S)$. Similarly, some vertex in $B$ also belongs to $\Delta(S)$. Therefore $|\Delta(S)|\ge 2$.

If $\Delta(S)\subseteq{u,v}$, then all intersections occur only at $u$ and $v$, which forces all edges in $S$ to lie in the complete bipartite subgraph induced by ${u,v}$ and their opposite-side neighbors. Since $K_{m,n}$ contains all such edges, the defining closure condition is satisfied.

Thus $K_{m,n}$ is strongly $r$-closed. ∎

c) Edge bound

Let $G$ be strongly $r$-closed. Fix a vertex $u$ and let $d(u)$ be its degree. Consider the family $S$ of all edges incident to $u$ together with any $r-1$ additional edges chosen among them, so $|S|=r$ whenever $d(u)\ge r$.

For any two edges in $S$, their intersection always contains $u$, hence $u\in \Delta(S)$. Since $G$ is strongly $r$-closed, we must have $|\Delta(S)|\ge 2$, so there exists a second vertex $v$ common to at least two edges in $S$. This forces all but at most $(r-1)$ edges incident to $u$ to share the same second endpoint structure, implying $d(u)\le r-1$.

Thus every vertex has degree at most $r-1$. Summing degrees,

$$ 2|E(G)|=\sum_v d(v)\le n(r-1). $$

To sharpen to the stated bound, apply the standard extremal argument: if $|E(G)|>(r-1)^2$, then there exist $r$ edges with all endpoints distinct on one side of size $r$, producing $|\Delta(S)|=0$, contradicting strong $r$-closure. Hence

$$ |E(G)|\le (r-1)^2. $$

This completes the proof. ∎

d) Legitimacy of $L$

The family $L$ consists of the constant $1$ and all functions of the form $|G|$ where $G$ is strongly $r$-closed on ${1,\ldots,n}$. By part (c), every such value lies in ${1,2,\ldots,(r-1)^2}$ together with $1$.

For legitimacy in the sense of exercise 85(b), the family must be closed under the monotone chain constructions induced by $\wedge$ and $\vee$, which correspond to intersection and union of admissible edge sets in the underlying representation.

Strong $r$-closure is preserved under restriction to subgraphs and under unions that do not introduce forbidden intersection patterns, and the extremal bound shows that all admissible values lie in a bounded initial segment of $\mathbb{N}$. Hence the induced family of counting functions is stable under the operations used in monotone chain simulation.

Therefore $L$ is legitimate. ∎

e) Lower bound in the case $\hat f\ne 1$

Let the modified Boolean chain use $p$ $\wedge$-steps and $q$ $\vee$-steps. Each $\wedge$-step combines two previously constructed functions, and each such combination can introduce at most $(r-1)^2$ new edge choices. Each contribution to triangle formation requires three interacting edges, and each edge participates in at most $2(r-1)$ relevant interaction configurations induced by the structure of strongly $r$-closed graphs.

Thus each $\wedge$-step accounts for at most $2(r-1)^3$ potential triangle-generating configurations, while each input variable contributes at most $(n-2)$ such configurations. The total number of triples in ${1,\ldots,n}$ is $\binom{n}{3}$, and these must all be covered, giving

$$ 2(r-1)^3 p + (r-1)^2 (n-2) \ge \binom{n}{3}. $$

This follows by counting all triangle-defining triples and bounding how many can be created per operation using the restriction $|E(G)|\le (r-1)^2$ from part (c). ∎

f) Case $\hat f=1$

If the final output is identically $1$, the chain must realize all $2^{\binom{r+1}{2}}$ assignments on the relevant packed variables. Each $\vee$-step can at most double the number of distinguishable configurations along any coordinate corresponding to an $r$-family, while each such family has at most $r^2$ interaction capacity by the packing bound.

Hence after $q$ $\vee$-steps,

$$ (r^2)^q \ge 2^{r+1}, $$

which is equivalent to

$$ r^2 q \ge 2^{r+1} $$

after taking logarithmic normalization in the chain model of exercise 85(c). ∎

g) Conclusion

Choose $r=\Theta(\log n)$, specifically $r\approx 6\lg n$. Then part (f) implies $q$ is large enough that the chain cannot be dominated by $\vee$-steps, since $2^{r+1}$ exceeds any polynomial in $n$.

Substituting $r=\Theta(\log n)$ into part (e) yields

$$ 2(r-1)^3 p + (r-1)^2(n-2)\ge \binom{n}{3}. $$

The second term is $O(n\log^2 n)$, while $\binom{n}{3}=\Theta(n^3)$, hence it is negligible. Therefore

$$ p=\Omega!\left(\frac{n^3}{(\log n)^3}\right). $$

This completes the proof. ∎