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"orner–Marton construction gives $T(n)\ge c_0(9\mathrm{/}5{)}^{n\mathrm{/}4}$ for an absolute constant $c_0>0$. We prove the polynomial strengthening $T(n)\ge c\sqrt{n}(9\mathrm{/}5{)}^{n\mathrm{/}4}$ for an absolute constant $c>0$. Our proof refines the outer-code step in the K"orner–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.