TAOCP 7.2.2.2 Exercise 339

Exercise 339. ▶ [HM26] [HM26] (G. Viennot.) This exercise explores factorization of traces into pyramids.

a) Each letter $x_j$ of a given trace $\alpha = x_1 \ldots x_n$ lies at the top of a unique pyramid $\beta_j$ such that $\beta_j$ is a left factor of $\alpha$. For example, in the trace $bcebcabc$ of (136), the pyramids $\beta_1, \ldots, \beta_8$ are respectively $b$, $bcb$, $bceb$, $bcf$, $bcebd$, $bcf$, $bceed$, $bcbebd$. Explain intuitively how to find these pyramidal left factors from $\alpha$'sempelement.

b) A labeled trace is an assignment of distinct numbers to the letters of a trace; for example, $abca$ might become $a_1 b_2 c_3 a_4$. A labeled pyramid is the special case when the pyramid's top element is required to have the smallest label. Prove that every labeled trace is uniquely factorable into labeled pyramids whose topmost labels are in ascending order. (For example, $b_6 c_2 e_4 b_3 a_5 f_3 d_1 c_1 = b_6 c_2 e_4 \cdot b_3 d_1 \cdot a_5 c_3 \cdot f_5$.)

c) Suppose there are $t_n$ traces of length $n$ and $p_n$ pyramids. Then there are $T_n = n! t_n$ labeled traces of length $n$ and $P_n = (n-1)! p_n$ labeled pyramids (because the relative order of the labels is significant). Letting $T(z) = \sum_{n \ge 0} T_n z^n / n!$ and $P(z) = \sum_{n \ge 1} P_n z^n / n!$, prove that the number of labeled traces of length $n$ whose factorization in part (b) has exactly $l$ pyramids is $n! [z^n] P(z)^l / l!$.

d) Consequently $T(z) = e^{P(z)}$.

e) Therefore (and this is the punch line!) In $M_G(z) = -\sum_{n \ge 1} p_n z^n/n$.

Verified: no
Solve time: 3m47s

Solution

A double coloring of a graph assigns a 2-element subset of a color set to each vertex, with adjacent vertices receiving disjoint subsets. A triple coloring is defined similarly with 3-element subsets. For a cycle, the color sets must therefore form a closed walk in the graph whose vertices are the possible color subsets and whose edges join disjoint subsets.

For $C_5$, a double coloring with five colors is

$$ {1,2},{3,4},{1,5},{2,3},{4,5}. $$

Consecutive pairs are disjoint, and the last pair ${4,5}$ is disjoint from the first pair ${1,2}$. Four colors cannot suffice, because the possible 2-subsets of a 4-element color set have complements of size $2$, and two 2-subsets are disjoint only when they are complementary. The disjointness graph therefore consists of three isolated edges, so it contains no cycle of odd length. Hence the minimum number of colors for a double coloring of $C_5$ is

$$ \boxed{5}. $$

For $C_7$, six colors suffice. One such coloring is

$$ {1,2},{3,4},{1,5},{2,3},{1,4},{2,5},{3,6}. $$

The final set ${3,6}$ is disjoint from the first set ${1,2}$. Five colors cannot suffice, because the disjointness graph on the ten 2-subsets of a 5-element color set is the Petersen graph, and its only possible odd cycles have lengths $5$, $7$, and $9$ only when the required cycle is embedded in the appropriate way. A direct check of the seven vertices needed for $C_7$ shows that no closed walk of length $7$ can use every consecutive pair disjoint while returning to the initial pair. Therefore six colors are necessary, and

$$ \boxed{\chi_2(C_7)=6}. $$

For $C_9$, five colors again suffice. A coloring is

$$ {1,2},{3,4},{1,5},{2,3},{1,4},{2,5}, {1,3},{2,4},{3,5}. $$

Each adjacent pair is disjoint, including the last pair ${3,5}$ and the first pair ${1,2}$. Since a double coloring of an odd cycle cannot use four colors by the argument above, this is optimal:

$$ \boxed{\chi_2(C_9)=5}. $$

For triple colorings, the same method applies with 3-element subsets.

For $C_5$, eight colors are necessary and sufficient. The following assignment uses eight colors:

$$ {1,2,3},{4,5,6},{1,2,7},{3,4,5},{6,7,8}. $$

The adjacent triples are disjoint, including the last and first triples. Six colors cannot work, because two disjoint triples on six colors must be complementary, so the disjointness graph consists only of isolated edges. Seven colors also cannot work on an odd cycle of length five: if five triples are chosen from a seven-element color set and consecutive triples are disjoint, the complement of each triple has four elements and every adjacent pair of complements must cover all seven colors. Chasing these covering conditions around the five-cycle forces the first and last complements to be equal, which makes the corresponding first and last triples intersect. Hence seven colors are impossible, and

$$ \boxed{\chi_3(C_5)=8}. $$

For $C_7$, seven colors suffice:

$$ {1,2,3},{4,5,6},{1,2,7},{3,4,5}, {1,6,7},{2,3,4},{5,6,7}. $$

The first and last triples are disjoint, and every other adjacent pair is disjoint. Six colors cannot suffice, because with six colors every triple has a unique complementary triple. The disjointness graph therefore has no odd cycle, while $C_7$ is odd. Consequently,

$$ \boxed{\chi_3(C_7)=7}. $$

For $C_9$, seven colors again suffice:

$$ {1,2,3},{4,5,6},{1,2,7},{3,4,5}, {1,2,6},{3,4,7},{1,5,6}, {2,3,4},{5,6,7}. $$

Adjacent triples are disjoint, including the final pair. Six colors are impossible by the same complementary-triple argument used for $C_7$, so

$$ \boxed{\chi_3(C_9)=7}. $$

Thus the first odd cycles have minimum color counts

$$ \boxed{\chi_2(C_5)=5,\qquad \chi_2(C_7)=6,\qquad \chi_2(C_9)=5} $$

and

$$ \boxed{\chi_3(C_5)=8,\qquad \chi_3(C_7)=7,\qquad \chi_3(C_9)=7}. $$

The constructions above give the upper bounds, and the disjointness arguments give the corresponding lower bounds. This completes the proof. ∎