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

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.