A finite-delay code for lexicographic graph products

Introduction

Background and the source problem

In zero-error communication, a message must be decoded correctly for every output that the channel can produce. Shannon’s graph formulation records which input symbols can be confused [1]. The vertices of a finite simple graph $F$ are the input symbols, and two distinct vertices are adjacent when some channel output could have arisen from either symbol. A set of messages can be transmitted in one use precisely when its symbols form an independent set, that is, a set of pairwise nonadjacent vertices. Thus the maximum number of messages in one use is the independence number $\alpha(F)$.

Longer words can use the alphabet more efficiently. For $n$ independent uses, two words can be confused if their symbols are equal or adjacent in every coordinate. The corresponding graph is the strong power $F^{\boxtimes n}$. A zero-error code is therefore an independent set in this graph: every pair of codewords must have a coordinate with distinct, nonadjacent symbols. The Shannon capacity measures the exponential growth of the largest such codes,

Concatenation of codes proves the equality between the limit and the supremum; the argument is recalled in Lemma 2.1. For a graph with at least one vertex, $\log_2\Theta(F)$ is the achievable zero-error rate in bits per use. The survey of Körner and Orlitsky [4] gives the broader information-theoretic background.

The question considered here concerns two ways of combining the same symbol alphabets $V(G)$ and $V(H)$. In the strong product, the two components are transmitted in parallel: the receiver can distinguish two pairs as soon as either component distinguishes them. In the lexicographic product, the first component selects a class and the second selects a symbol within that class. Confusable classes are joined completely, so an outer confusion hides every inner distinction. This is the hierarchical communication model discussed by Sason [3 Section 1].

and they are adjacent in the lexicographic product $G \circ H$ if

The strong power $F^{\boxtimes n}$ is the $n$-fold strong product of $F$.

These are the conventions of [3 Definitions 1, 2 and 5]. For example, suppose $g$ and $g'$ are adjacent, whereas $h$ and $h'$ are distinct and nonadjacent. The symbols $(g,h)$ and $(g',h')$ are distinguishable in $G \boxtimes H$, but confusable in $G \circ H$. Every strong-product edge is also a lexicographic-product edge, and adding confusions cannot improve a code. Hence

This can be a genuine loss for a single use. The pentagon satisfies $\alpha(C_5 \circ C_5) = 4$ and $\alpha(C_5 \boxtimes C_5) = 5$; § 3.1 recalls the elementary example. The issue is whether this loss persists in the exponential growth rate of long codes.

Sason [3, Theorem 6, equations (71)–(72)] proves

The two product capacities consequently agree whenever the right-hand side equals $\Theta(G)\Theta(H)$. The unresolved case is joint coding that outperforms separate codes for the two factors. Since reversing the factors changes the lexicographic confusability rule, Sason asks whether both ordered products can lose capacity.

Contribution

The loss of distinguishability in one use can always be recovered by rearranging the components of a longer code. The result has the following two forms.

1. For every pair of finite simple graphs,

(Theorem 3.2).

Thus Question 1.2 has a negative answer, including for the graph–complement families proposed in [3 equation (160)]. The identity concerns the two product operations; their common capacity may still exceed $\Theta(G)\Theta(H)$.

2. The same comparison holds after adjoining any strong-product factor $K$, and for any expression formed by mixing strong and lexicographic products (Theorem 4.2). For instance,

More generally, the capacity of a parenthesized product depends only on its list of graph factors, not on which of the two operations is used at each step or on the order of the factors.

The mechanism is a one-block delay. Start with any length-$n$ code $C$ for $G \boxtimes H$; its codewords are pairs of words $(\mathbf{g},\mathbf{h})$. To transmit a list of $k$ codewords, shift the outer words one block to the right:

output block	1	2	3	$\cdots$	$k+1$
outer word	$\mathbf{g}^{(0)}$	$\mathbf{g}^{(1)}$	$\mathbf{g}^{(2)}$	$\cdots$	$\mathbf{g}^{(k)}$
inner word	$\mathbf{h}^{(1)}$	$\mathbf{h}^{(2)}$	$\mathbf{h}^{(3)}$	$\cdots$	$\mathbf{h}^{(k+1)}$

The two boundary words are fixed in advance. To compare two messages, look at their first different input block, say $j$. If its inner words distinguish the messages, that distinction appears in output block $j$, where the preceding outer words still agree. If its outer words distinguish them, that distinction appears in block $j+1$ and survives regardless of the inner words. One of these cases always holds because $C$ is an independent code.

All $|C|^k$ input lists can therefore be transmitted in $k+1$ blocks over $G \circ H$. The output rate is $k/(k+1)$ times the input rate, and this factor tends to one. This works for every input code, so no finite code attaining capacity is needed. With $m$ graph factors, successive delays $m-1$, $m-2$, $\ldots$, $0$ protect each component in the same way and cost $m-1$ extra blocks. All words are chosen before transmission; the construction uses no feedback.

Related work

The distinction between one-use and asymptotic coding is central to Shannon’s original pentagon example [1]. Two independent one-use codes provide four words in $C_5^{\boxtimes2}$, while a joint code has five; Lovász proved the exact capacity $\Theta(C_5)=\sqrt{5}$ [2 Theorems 1–2]. More generally, Alon and Lubetzky [8 Theorems 1–2] show that even a long initial segment of the sequence $\alpha(F^{\boxtimes n})^{1/n}$ can be far below its limiting value. Our comparison therefore works with an arbitrary input code, rather than trying to estimate capacity from bounded block lengths. The one-use identity $\alpha(G \circ H)=\alpha(G)\alpha(H)$ belongs to the classical theory of lexicographic products [7]; its contrast with strong-product coding is illustrated in § 3.1.

There is also an earlier route to the same capacity identity through upper bounds. Zuiddam’s spectral duality theorem writes Shannon capacity as the minimum of a family of graph parameters [9 Theorem 1.1]. Each parameter in this family is normalized on the one-vertex graph, monotone under homomorphisms of complementary graphs, additive under disjoint union, and multiplicative under strong product. Vrana [10 Section 4.4, Proposition 4.4 and the following paragraph] observes that $\Theta(G \circ H)=\Theta(G \boxtimes H)$ would follow if every such parameter were also multiplicative under lexicographic product. Fritz proves this additional property for a broad construction of fractional invariants, crediting Cox for the argument [11 Proposition 4.13], and records the general assertion as Roberson’s Problem 6.10. The code conversion here establishes the capacity identity directly; it does not require or establish that assertion for every spectral parameter.

Equality between the two product capacities is compatible with a gain from joint coding. Haemers [5] already gives graphs for which $\Theta(G \boxtimes H)>\Theta(G)\Theta(H)$. Alon proved that capacity can also be strictly superadditive under disjoint union [6]; Schrijver [12 Theorem 2] proves that these two strict inequalities are equivalent for a fixed pair of graphs. Sason’s Theorem 7 supplies explicit graph–complement families where even the lexicographic-product capacity exceeds this product [3]. The result proved here identifies the full joint capacity for the lexicographic product, including in precisely this regime.

Codes, powers, and elementary comparisons

An independent code in $F^{\boxtimes n}$ is equivalently a set of words such that each two distinct words have a coordinate containing distinct, nonadjacent vertices of $F$. Such a coordinate will be called a distinguishing coordinate. Definition 1.1 gives two ways to distinguish lexicographic symbols:

In the first case the inner symbols are unrestricted. For two distinct product symbols, failure of equality or adjacency in the strong product is equivalent to a distinction in at least one factor. Thus a distinguishing coordinate in a strong-product code may come from either factor, even if the other factor is adjacent there. This freedom is what the delay construction preserves.

Proof. Put $a_n=\alpha(F^{\boxtimes n})$. Concatenating independent codes of lengths $u$ and $v$ gives an independent code of length $u+v$, so $a_{u+v}\ge a_u a_v$. Fix $u\ge1$ and write $n=qu+r$, with $0\le r<u$. Concatenate $q$ length-$u$ codes and fill the remaining $r$ positions with a common fixed vertex. The resulting code has size $a_u^q$, giving $a_n\ge a_u^q$. Hence

Taking the supremum over $u$ proves that this lower limit equals the supremum; the reverse inequality for the upper limit follows from its definition. Finiteness follows from $a_n\le|V(F)|^n$.

If $F'\subseteq F$ is a spanning inclusion, equality or adjacency in $F'$ implies equality or adjacency in $F$. Thus $F'^{\boxtimes n}$ is a spanning subgraph of $(F)^{\boxtimes n}$ for every $n$. Each independent set in the latter is independent in the former. Taking roots and suprema proves the second assertion.

The finite-delay construction

Proof. Choose any independent code $C$ in $(G\boxtimes H)^{\boxtimes n}$ and put $M=|C|$. The construction will have $M^k$ outputs; choosing a maximum code gives the displayed bound. Write a codeword as $(\mathbf{g},\mathbf{h})$, where each bold symbol is a length-$n$ word in the corresponding factor graph. Choose common boundary words $\mathbf{g}^{(0)}\in V(G)^n$ and $\mathbf{h}^{(k+1)}\in V(H)^n$.

A message is a list of $k$ members of $C$,

Encode it as the following $k+1$ blocks, each of length $n$ over $V(G\circ H)$:

Pairing bold words means pairing their coordinates in order. All input inner words are recoverable from the first $k$ blocks, and all input outer words from the last $k$ blocks. The map is injective and has $M^k$ outputs.

Consider two distinct messages and use primes for the second message. Let $j$ be their first differing information block. Then

For $j=1$ this is the common boundary word. For $j>1$ it follows from equality of the preceding information blocks.

The two $j$th codewords are distinct members of $C$. Some coordinate $i$ therefore satisfies

If the first condition holds, coordinate $i$ of output block $j+1$ distinguishes the two outputs by its outer symbols. The last block in (5) ensures that this remains valid for $j=k$. If the first condition does not hold, the second does. Coordinate $i$ of output block $j$ then has equal outer symbols by (6) and distinguishing inner symbols. Both cases satisfy (3). Thus every two different outputs are nonadjacent in the required strong power of $G\circ H$. Its independence number is at least $M^k$.

Proof. For nonempty graphs, fix $n \ge1$ and put $M_n=\alpha((G\boxtimes H)^{\boxtimes n})$. By (1) and Lemma 3.1,

Letting $k$ tend to infinity while $n$ is fixed gives $\Theta(G\circ H)\ge M_n^{1/n}$. Taking the supremum over $n$ gives $\Theta(G\circ H)\ge\Theta(G\boxtimes H)$.

To prove the reverse inequality, consider an edge between distinct pairs in $G\boxtimes H$. If its outer vertices differ, they are adjacent in $G$, which is enough for lexicographic adjacency. If they agree, the inner vertices must be distinct and adjacent in $H$, again giving lexicographic adjacency. Thus $G\boxtimes H$ is a spanning subgraph of $G\circ H$, and Lemma 2.1 proves the reverse inequality.

Apply the established equality to $(H,G)$. The coordinate swap is an isomorphism $H\boxtimes G\cong G\boxtimes H$, and isomorphisms preserve independent codes in every strong power. This proves all of (7).

If either factor has empty vertex set, all three product graphs are empty. Defining their independence numbers and capacities to be zero gives the same identity.

The pentagon as an example

The classical five-cycle makes the difference between one use and capacity concrete. Label $C_5$ by $\mathbb{Z}/5\mathbb{Z}$, with differences $\pm1$ defining edges. Its independence number is two: an independent set $A$ is disjoint from its translate $A+1$, so $2|A|\le5$, and $\{0,2\}$ attains the bound. An independent set in $C_5\circ C_5$ occupies at most two outer fibers, each containing at most two vertices. The set $\{0,2\}\times\{0,2\}$ attains this bound, so $\alpha(C_5\circ C_5)=4$.

By contrast, Shannon’s code [1]

is independent in $C_5\boxtimes C_5$. A difference $\pm2$ between indices distinguishes the outer symbols, and a difference $\pm1$ distinguishes the inner symbols. This code is optimal. Indeed, for any independent set $S$ in the strong product put $A_i=\{h:(i,h)\in S\}$. Consecutive fibers $A_i,A_{i+1}$ are disjoint and have no edges between them, and each fiber is independent. Thus their union is independent in $C_5$, giving $|A_i|+|A_{i+1}|\le2$. Summing these five inequalities proves $2|S|\le10$. Consequently,

Set $i_0=i_{k+1}=0$. Applying the delay construction to $C$ gives the explicit code

in $(C_5\circ C_5)^{\boxtimes(k+1)}$. It has $5^k$ words of length $k+1$, and $5^k/(k+1)\to5$. This reaches the capacity: Lovász’s evaluation $\Theta(C_5)=\sqrt{5}$ [2] and the limit in (1) give $\Theta(C_5\boxtimes C_5)=\Theta(C_5)^2=5$, because the $n$th strong power of $C_5\boxtimes C_5$ is $C_5^{\boxtimes2n}$. Theorem 3.2 therefore gives $\Theta(C_5\circ C_5)=5$. The extra confusions reduce the largest one-use code from five to four, but do not reduce capacity.

Mixed products

For more than two factors, an inner distinction must survive every lexicographic product above it. It suffices to arrange that all components to its left agree when that distinction is transmitted. Successive delays achieve this simultaneously for every factor.

An expression $E$ below is any parenthesized formula built from graphs using $\boxtimes$ and $\circ$, for example $(G_1\circ G_2)\boxtimes(G_3\circ G_4)$. Its vertices are naturally tuples with one coordinate for each graph occurrence. List these occurrences from left to right as $G_1,\ldots,G_m$; the same graph may occur more than once. We also allow a separate graph $K$ joined by a strong product.

Proof. First note a consequence of the product definitions: if two tuples agree in their first $i-1$ coordinates and their $i$th coordinates are distinct and nonadjacent in $G_i$, the resulting vertices of $E$ are nonadjacent. To prove this, induct on the number of graph factors. The one-factor case is the hypothesis itself. Otherwise write $E=A\star B$, where $\star$ is either product and $A$ uses the first $r$ factors. If $i\le r$, induction gives distinct nonadjacent $A$-vertices, which distinguish the two vertices of $E$ for either choice of $\star$. If $i>r$, the $A$-vertices agree, and induction gives distinct nonadjacent $B$-vertices. Equality in the first component and a distinction in the second again distinguish the vertices of either product. This proves the assertion.

Take an independent input code of length $n$ and size $M$ with words $(\mathbf{g}_1,\ldots,\mathbf{g}_m,\mathbf{z})$. A message is a list of $k$ such words, with superscripts $1,\ldots,k$. For $1\le t\le k+m-1$, the $t$th output block is

The tuples are interpreted coordinate by coordinate as a length-$n$ word over $V(E\boxtimes K)$: component $i$ is delayed by $m-i$ blocks, whereas the $K$-component has no delay. Every component with an index outside $\{1,\ldots,k\}$ is a fixed boundary word, independent of the message. Each $\mathbf{g}_i^{(j)}$ is recovered from block $j+m-i$, and $\mathbf{z}^{(j)}$ from block $j$, so the encoding is injective.

For distinct messages let $j$ be their first differing information index. The two $j$th words belong to an independent code, so at some coordinate they are distinct and nonadjacent in a factor. If that factor is $K$, output block $j$ preserves the distinction. If it is $G_i$, use output block $t=j+m-i$. For every $\ell<i$, the $G_\ell$ component there comes from information index $j+\ell-i<j$, or from a common boundary word. These preceding components agree. The observation in the first paragraph therefore preserves the $G_i$ distinction in the evaluated graph $E$. It remains a distinction after taking the strong product with $K$. Thus every pair of outputs is distinguished in some coordinate. There are $M^k$ outputs, proving (8). □

Proof. Assume all graphs are nonempty, and put $M_n=\alpha((G_1\boxtimes\cdots\boxtimes G_m\boxtimes K)^{\boxtimes n})$. Proposition 4.1 gives

For fixed $n$, let $k\to\infty$ to obtain the lower bound $M_n^{1/n}$, and then take the supremum over $n$.

For the reverse bound, the strong product of all factors is a spanning subgraph of $E$. Induct again on the number of factors. For $E=A\star B$, the inductive inclusions in $A$ and $B$ imply that the strong product of all factors is a spanning subgraph of $A\boxtimes B$. This is $E$ when $\star=\boxtimes$, and is a spanning subgraph of $E$ when $\star=\circ$, by the edge inclusion proved for Theorem 3.2. The one-factor case is equality. Taking a strong product with $K$ preserves this inclusion. Lemma 2.1 gives the upper bound in (9). The first identity is the case $E=G\circ H$. Taking $K$ to be the one-vertex graph and using coordinate permutations of the pure strong product proves the last assertion. If a factor has empty vertex set, both sides are zero, completing the proof. □