TAOCP 7.2.2 Exercise 36
A commafree code means that no concatenation of codewords admits a valid parsing into codewords starting at a non-boundary position.
Exercise 36. [**] [M22] A two-letter block code on an $m$-letter alphabet can be represented as a digraph $D$ on $m$ vertices, with $a \to b$ if and only if $ab$ is a codeword.
a) Prove that the code is commafree $\iff$ $D$ has no oriented paths of length 3.
b) How many arcs can be in an $m$-vertex digraph with no oriented paths of length $r$?
Verified: no
Solve time: 3m56s
(a)
A commafree code means that no concatenation of codewords admits a valid parsing into codewords starting at a non-boundary position.
A directed path of length $3$ in $D$ is a sequence of vertices
$$ a \to b \to c \to d. $$
By definition of the code, this means $ab$, $bc$, and $cd$ are all codewords.
Now consider the concatenation $abcd$. Its length-2 substrings are $ab$, $bc$, and $cd$. The substring $bc$ is a codeword that begins at position 2, not at a codeword boundary. Hence the concatenation admits an alternative parsing:
$$ (ab)(cd) \quad \text{and also contains the internal codeword } bc, $$
so decoding is ambiguous. Therefore the code is not commafree.
Conversely, suppose the code is not commafree. Then there exist codewords $ab$ and $cd$ such that the concatenation $abcd$ contains a codeword $bc$ starting at position 2. This implies
$$ a \to b,\quad b \to c,\quad c \to d, $$
so $a \to b \to c \to d$ is a directed path of length $3$ in $D$.
Thus, the code is commafree if and only if $D$ has no directed path of length $3$.
(b)
Let $D$ be an $m$-vertex digraph with no directed path of length $r$.
Step 1: height function (correct formulation)
For each vertex $v$, define
$$ h(v) = \max{\text{length of a directed path starting at } v}, $$
where length is measured in edges.
Because no directed path has $r$ edges, every such path has length at most $r-1$, so
$$ 0 \le h(v) \le r-1. $$
Step 2: key inequality and orientation
If $u \to v$ is an arc, then any longest path starting at $v$ can be extended by one step through $u \to v$ when viewed from $u$. Hence
$$ h(u) \ge 1 + h(v), $$
so
$$ h(u) > h(v). $$
Therefore every directed edge goes strictly from a vertex of larger $h$-value to a vertex of smaller $h$-value.
Define layers
$$ V_i = {v : h(v) = i}, \quad 0 \le i \le r-1. $$
Then every arc goes from $V_i$ to $V_j$ only when $i > j$.
Step 3: completeness between layers
We show that in an extremal digraph maximizing the number of arcs, every possible arc between different layers with correct orientation is present.
Take $u \in V_i$, $v \in V_j$ with $i > j$. If the arc $u \to v$ is missing, we may add it.
After adding $u \to v$, any directed path starting at $v$ has length at most $h(v)=j$. Thus any path starting at $u$ that uses the new edge has length at most
$$ 1 + h(v) = 1 + j \le i, $$
and since $i \le r-1$, no path of length $r$ is created. Hence the added edge preserves the constraint.
Therefore an extremal digraph must contain all possible arcs from $V_i$ to $V_j$ for every $i>j$.
So the extremal structure is a complete $(r-1)$-partite oriented digraph with all edges directed from higher layers to lower layers.
Step 4: counting arcs
Let $a_i = |V_i|$, with
$$ \sum_{i=0}^{r-1} a_i = m. $$
Every pair of vertices with different layers contributes exactly one arc, from higher to lower layer. Hence the number of arcs is
$$ E = \sum_{0 \le j < i \le r-1} a_i a_j. $$
Rewrite:
$$ E = \frac{1}{2}\left(m^2 - \sum_{i=0}^{r-1} a_i^2\right). $$
Step 5: optimization
For fixed $m$, maximizing $E$ is equivalent to minimizing $\sum a_i^2$. This is minimized when the $a_i$ are as equal as possible.
Write
$$ m = q(r-1) + s, \quad 0 \le s < r-1. $$
Then the minimum occurs when:
- $s$ layers have size $q+1$,
- $r-1-s$ layers have size $q$.
Thus
$$ \sum a_i^2 = s(q+1)^2 + (r-1-s)q^2. $$
Substituting into the expression for $E$,
$$ E_{\max} = \frac{1}{2}\left(m^2 - s(q+1)^2 - (r-1-s)q^2\right). $$
Final result
A digraph on $m$ vertices with no directed path of length $r$ has at most
$$ \frac{1}{2}\left(m^2 - s(q+1)^2 - (r-1-s)q^2\right), \quad m = q(r-1) + s,\ 0 \le s < r-1, $$
arcs, achieved by a complete $(r-1)$-partite orientation with all edges directed from higher layers to lower layers.