Polynomially Improved Lower Bounds for Trifferent Codes via Locally Sparse $3$-Uniform Hypergraphs

Abstract

A ternary code is \emph{trifferent} if every three distinct codewords have a coordinate in which their symbols are pairwise distinct. Let $T(n)$ be the maximum size of a trifferent code of length $n$. The classical Körner--Marton construction gives $T(n)\ge c_0(9/5{)}^{n/4}$ for an absolute constant $c_0>0$. We prove the polynomial strengthening $T(n)\ge c\sqrt{n}(9/5{)}^{n/4}$ for an absolute constant $c>0$. Our proof refines the outer-code step in the Körner--Marton concatenation. We encode non separating triples as edges of a $3$-uniform hypergraph, randomly thin its vertex set, and remove high-degree vertices together with all remaining Berge cycles of lengths two and three. The resulting locally sparse hypergraph admits a large independent set by a theorem of Verstraete and Wilson, producing the additional factor $\sqrt{n}$. Concatenation with the length-four Tetra code then yields the stated lower bound.

Added a brief discussion outlining a viable extension of the framework to generalized m-trifferent codes

Topics & keywords