\documentclass[11pt]{article} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage{amsmath,amssymb,amsthm} \usepackage[a4paper,hmargin=23mm,vmargin=25mm]{geometry} \usepackage{lmodern,microtype,xcolor} \usepackage{needspace} \let\BolzanoSection\section \renewcommand{\section}{\Needspace{9\baselineskip}\BolzanoSection} \usepackage{hyperref} \hypersetup{pdftitle={A finite-delay code for lexicographic graph products},pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník},colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue} \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{question}[theorem]{Question} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \DeclareMathOperator{\capsh}{\Theta} \newcommand{\spow}[2]{{#1}^{\boxtimes #2}} \newcommand{\near}{\simeq} \title{A finite-delay code for lexicographic graph products\thanks{This work was produced within the Bolzano project (\url{https://bolzano.app}), using AI systems for mathematical research and manuscript preparation. The listed authors contributed to the project and the preparation of this release. The manuscript received only limited human checking.}} \author{Mat\v{e}j Kripner \qquad V\'{a}clav Rozho\v{n} \qquad Robert \v{S}\'{a}mal\\[0.4em] Martin \v{S}indel\'{a}\v{r} \qquad Adri\'{a}n Z\'{a}me\v{c}n\'{i}k} \date{} % Collection typography. \definecolor{BolzanoInk}{HTML}{24445C} \hypersetup{colorlinks=true,linkcolor=BolzanoInk,citecolor=BolzanoInk, urlcolor=BolzanoInk,pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník},pdflang={en-US}} \urlstyle{same} \setlength{\emergencystretch}{1em} \let\BolzanoBibliography\thebibliography \renewcommand{\thebibliography}[1]{\BolzanoBibliography{#1}\raggedright} \begin{document} \maketitle \begin{abstract} For all finite simple graphs, the strong product and both ordered lexicographic products have the same Shannon capacity, answering a question of Sason. An explicit code conversion delays one component by a single block, with rate loss tending to zero. The equality extends to arbitrary mixtures of the two products and survives adjoining an additional strong-product factor. \end{abstract} \section{Introduction} \subsection{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~\cite{Shannon}. 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, \begin{equation}\label{eq:capacity} \capsh(F)=\lim_{n\to\infty}\alpha(F^{\boxtimes n})^{1/n} =\sup_{n\ge1}\alpha(F^{\boxtimes n})^{1/n}. \end{equation} Concatenation of codes proves the equality between the limit and the supremum; the argument is recalled in Lemma~\ref{lem:elementary}. For a graph with at least one vertex, $\log_2\capsh(F)$ is the achievable zero-error rate in bits per use. The survey of K\"orner and Orlitsky~\cite{KO} 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 \emph{strong product}, the two components are transmitted in parallel: the receiver can distinguish two pairs as soon as either component distinguishes them. In the \emph{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~\cite[Section~1]{Sason}. \begin{definition}[Strong and lexicographic products]\label{def:products} Write $x\near_F y$ when $x=y$ or $xy\in E(F)$. Both products have vertex set $V(G)\times V(H)$. Distinct pairs $(g,h)$ and $(g',h')$ are adjacent in the strong product $G\boxtimes H$ if \[ g\near_G g' \quad\hbox{and}\quad h\near_H h', \] and they are adjacent in the lexicographic product $G\circ H$ if \[ gg'\in E(G) \quad\hbox{or}\quad (g=g'\ \hbox{and}\ hh'\in E(H)). \] The strong power $F^{\boxtimes n}$ is the $n$-fold strong product of $F$. \end{definition} These are the conventions of \cite[Definitions~1, 2 and~5]{Sason}. 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 \begin{equation}\label{eq:easy} \capsh(G\circ H)\le\capsh(G\boxtimes H). \end{equation} 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$; Section~\ref{sec:pentagon} recalls the elementary example. The issue is whether this loss persists in the exponential growth rate of long codes. Sason~\cite[Theorem~6, equations~(71)--(72)]{Sason} proves \[ \capsh(G)\capsh(H)\le\capsh(G\circ H) \le\capsh(G\boxtimes H). \] The two product capacities consequently agree whenever the right-hand side equals $\capsh(G)\capsh(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 \emph{both} ordered products can lose capacity. \begin{question}[{\cite[Section~6, equation~(145)]{Sason}}]\label{q:source} Do there exist finite simple graphs $G,H$ such that \[ \max\{\capsh(G\circ H),\capsh(H\circ G)\} <\capsh(G\boxtimes H)? \] \end{question} \subsection{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. \begin{enumerate} \item For every pair of finite simple graphs, \[ \capsh(G\circ H)=\capsh(H\circ G)=\capsh(G\boxtimes H) \qquad\text{(Theorem~\ref{thm:identity}).} \] Thus Question~\ref{q:source} has a negative answer, including for the graph--complement families proposed in \cite[equation~(160)]{Sason}. The identity concerns the two product operations; their common capacity may still exceed $\capsh(G)\capsh(H)$. \item The same comparison holds after adjoining any strong-product factor $K$, and for any expression formed by mixing strong and lexicographic products (Theorem~\ref{thm:contexts}). For instance, \[ \capsh((G\circ H)\boxtimes K) =\capsh(G\boxtimes H\boxtimes K). \] 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. \end{enumerate} The mechanism is a one-block delay. Start with any length-$n$ code $\mathcal 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: \[ \begin{array}{c|ccccc} \text{output block}&1&2&3&\cdots&k+1\\ \hline \text{outer word}&\mathbf g^{(0)}&\mathbf g^{(1)}&\mathbf g^{(2)} &\cdots&\mathbf g^{(k)}\\ \text{inner word}&\mathbf h^{(1)}&\mathbf h^{(2)}&\mathbf h^{(3)} &\cdots&\mathbf h^{(k+1)} \end{array} \] 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 $\mathcal C$ is an independent code. All $|\mathcal 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. \subsection{Related work} The distinction between one-use and asymptotic coding is central to Shannon's original pentagon example~\cite{Shannon}. Two independent one-use codes provide four words in $C_5^{\boxtimes2}$, while a joint code has five; Lov\'asz proved the exact capacity $\capsh(C_5)=\sqrt5$~\cite[Theorems~1--2]{Lovasz}. More generally, Alon and Lubetzky~\cite[Theorems~1--2]{AL} 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~\cite{GS}; its contrast with strong-product coding is illustrated in Section~\ref{sec:pentagon}. 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 \cite[Theorem~1.1]{Zuiddam}. 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~\cite[Section~4.4, Proposition~4.4 and the following paragraph]{Vrana} observes that $\capsh(G\circ H)=\capsh(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 \cite[Proposition~4.13]{Fritz}, 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~\cite{Haemers} already gives graphs for which $\capsh(G\boxtimes H)>\capsh(G)\capsh(H)$. Alon proved that capacity can also be strictly superadditive under disjoint union~\cite{AlonUnion}; Schrijver~\cite[Theorem~2]{Schrijver} 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~\cite{Sason}. The result proved here identifies the full joint capacity for the lexicographic product, including in precisely this regime. \section{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~\ref{def:products} gives two ways to distinguish lexicographic symbols: \begin{equation}\label{eq:distinguish} g\not\near_G g',\qquad\hbox{or}\qquad g=g'\ \hbox{and}\ h\not\near_H h'. \end{equation} 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. \begin{lemma}\label{lem:elementary} For every nonempty finite graph $F$, the supremum in \eqref{eq:capacity} is a limit. If $F$ is a spanning subgraph of $F'$, then $\capsh(F)\ge\capsh(F')$. \end{lemma} \begin{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 r1$ it follows from equality of the preceding information blocks. The two $j$th codewords are distinct members of $\mathcal C$. Some coordinate $i$ therefore satisfies \[ g_i^{(j)}\not\near_G g_i'^{(j)} \quad\hbox{or}\quad h_i^{(j)}\not\near_H h_i'^{(j)}. \] If the first condition holds, coordinate $i$ of output block $j+1$ distinguishes the two outputs by its outer symbols. The last block in \eqref{eq:encoding} 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 \eqref{eq:previous} and distinguishing inner symbols. Both cases satisfy \eqref{eq:distinguish}. Thus every two different outputs are nonadjacent in the required strong power of $G\circ H$. Its independence number is at least $M^k$. \end{proof} \begin{theorem}\label{thm:identity} For all finite simple graphs $G,H$, \begin{equation}\label{eq:identity} \capsh(G\circ H)=\capsh(H\circ G)=\capsh(G\boxtimes H). \end{equation} \end{theorem} \begin{proof} For nonempty graphs, fix $n\ge1$ and put $M_n=\alpha((G\boxtimes H)^{\boxtimes n})$. By \eqref{eq:capacity} and Lemma~\ref{lem:delay}, \[ \capsh(G\circ H)\ge M_n^{k/[n(k+1)]} \qquad(k\ge1). \] Letting $k$ tend to infinity while $n$ is fixed gives $\capsh(G\circ H)\ge M_n^{1/n}$. Taking the supremum over $n$ gives $\capsh(G\circ H)\ge\capsh(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~\ref{lem:elementary} 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 \eqref{eq:identity}. 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. \end{proof} \subsection{The pentagon as an example}\label{sec:pentagon} 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~\cite{Shannon} \[ \mathcal C=\{(i,2i):i\in\mathbb Z/5\mathbb Z\} \] 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, \[ \alpha(C_5\circ C_5)=4<5=\alpha(C_5\boxtimes C_5). \] Set $i_0=i_{k+1}=0$. Applying the delay construction to $\mathcal C$ gives the explicit code \[ \bigl\{\bigl((i_{j-1},2i_j)\bigr)_{j=1}^{k+1}: i_1,\ldots,i_k\in\mathbb Z/5\mathbb Z\bigr\} \] 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\'asz's evaluation $\capsh(C_5)=\sqrt5$~\cite{Lovasz} and the limit in~\eqref{eq:capacity} give $\capsh(C_5\boxtimes C_5)=\capsh(C_5)^2=5$, because the $n$th strong power of $C_5\boxtimes C_5$ is $C_5^{\boxtimes 2n}$. Theorem~\ref{thm:identity} therefore gives $\capsh(C_5\circ C_5)=5$. The extra confusions reduce the largest one-use code from five to four, but do not reduce capacity. \section{Mixed products}\label{sec:contexts} 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. \begin{proposition}[A code for mixed products] \label{prop:context-code} Let $E$ be an expression in nonempty finite simple graphs $G_1,\ldots,G_m$, using $\boxtimes$ and $\circ$ as above. For every nonempty finite simple graph $K$ and integers $n,k\ge1$, \begin{equation}\label{eq:mixed-code} \alpha((E\boxtimes K)^{\boxtimes n(k+m-1)}) \ge\alpha((G_1\boxtimes\cdots\boxtimes G_m \boxtimes K)^{\boxtimes n})^k. \end{equation} \end{proposition} \begin{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 \[ \bigl((\mathbf g_1^{(t-m+1)},\ldots, \mathbf g_m^{(t)}),\mathbf z^{(t)}\bigr). \] 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