TAOCP 7.2.2 Exercise 34

Exercise 34. [15] [15] What's the largest commafree subset of the following words?

aced babe bade bead beef cafe cede dada dead dear face fade feed

Verified: no
Solve time: 5m56s

Each word has length 4. A set $S$ is commafree if for any $x,y \in S$, no word of $S$ appears as a nonaligned overlap across the boundary of $xy$. Equivalently, for $k=1,2,3$, the word

$$ z = \text{suffix}k(x) + \text{prefix}{4-k}(y) $$

must not lie in $S$ unless it forces a forbidden triple ${x,y,z}$.

Thus the problem is an independent set problem in a 3-uniform hypergraph whose hyperedges are all triples ${x,y,z}$ arising from valid overlaps.

1. Systematic derivation of all overlap constraints

We compute all overlaps for $k=1,2,3$ over all ordered pairs. Only overlaps that produce listed words matter.

Words

$$ \begin{aligned} &\text{aced, babe, bade, bead, beef, cafe, cede, dada, dead, dear, face, fade, feed} \end{aligned} $$

2. Overlaps of length 3 + 1 (k = 3)

This produces $z = x_2x_3x_4y_1$.

The only matching case is:

$x = \text{aced}$ (suffix $ced$)
$y$ begins with $e$

This yields:

$$ {\text{aced}, \text{cede}, y} \quad \text{for } y \in {\text{bead, beef, cede, dead, dear, feed}} $$

So we obtain:

$$ {aced, cede, bead},; {aced, cede, beef},; {aced, cede, dead},; {aced, cede, dear},; {aced, cede, feed} $$

3. Overlaps of length 2 + 2 (k = 2)

Here $z = x_3x_4y_1y_2$. The nontrivial valid overlaps are:

Centered at cede

$$ \begin{aligned} &{aced, bade, cede}, {aced, dead, cede}, {aced, dear, cede}, {aced, fade, cede}\ &{face, bade, cede}, {face, dead, cede}, {face, dear, cede}, {face, fade, cede} \end{aligned} $$

Other valid overlaps

$$ {bade, bead, dead}, {cede, bead, dead} $$

$$ {cafe, cede, face}, {fade, cede, face} $$

$$ {cafe, bade, fade}, {cafe, dead, fade} $$

$$ {bead, dead, dear}, {feed, dead, dear} $$

4. Overlaps of length 1 + 3 (k = 1)

Here $z = x_4y_1y_2y_3$. The only nontrivial cases are:

$$ {aced, dada, cede} $$

$$ {bead, dead, dear}, {feed, dead, dear} $$

5. Structural simplification

A key observation is that almost every constraint involves the word $\text{cede}$ or $\text{dead}$.

We separate the structure.

Step 1: Remove $\text{cede}$

If $\text{cede} \notin S$, then every constraint involving cede disappears. This eliminates all dense clusters involving:

aced
face
bade/fade/cafe interactions through cede

After removing cede, the remaining active constraints are:

$$ {bade, bead, dead},\quad {bead, dead, dear},\quad {feed, dead, dear},\quad {cafe, bade, fade},\quad {cafe, dead, fade} $$

Now we solve the residual system on 12 words.

6. Minimum deletion (hitting set formulation)

We want a smallest set $R$ intersecting every remaining forbidden triple.

The constraints are:

${bade, bead, dead}$
${bead, dead, dear}$
${feed, dead, dear}$
${cafe, bade, fade}$
${cafe, dead, fade}$

7. Finding the optimal hitting set

Key observation

“dead” appears in 4 of 5 constraints
“cafe” appears in 2 constraints that are otherwise independent of dead

Try:

$$ R = {\text{dead}, \text{cafe}} $$

Check coverage:

${bade, bead, dead}$ hit by dead
${bead, dead, dear}$ hit by dead
${feed, dead, dear}$ hit by dead
${cafe, bade, fade}$ hit by cafe
${cafe, dead, fade}$ hit by cafe or dead

So $R$ is valid.

No single vertex can hit all constraints:

dead misses ${cafe, bade, fade}$
cafe misses ${bade, bead, dead}$, etc.

Thus $|R| = 2$ is optimal.

8. Constructing the maximum commafree set

We remove:

$$ {\text{cede}, \text{dead}, \text{cafe}} $$

All remaining 10 words form a valid commafree set.

$$ S = {\text{aced, babe, bade, bead, beef, dada, dear, face, fade, feed}} $$

9. Final answer

$$ |S| = 10 $$

$$ \boxed{10} $$