2026/07/29 by Xuejiao Han, Yubo Sun, Gennian Ge
Computer Science · Mathematics · #cs.IT #math.IT
10 pages
arxiv created 2026/07/29 · arxiv updated 2026/07/30
A ternary code is 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)≥ c0(9/5)n/4 for an absolute constant c0>0. We prove the polynomial strengthening T(n)≥ c√(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 √ n. Concatenation with the length-four Tetra code then yields the stated lower bound.