The generalized trifference problem

Anurag Bishnoi, Bartłomiej Kielak, Benedek Kovács, Zoltán Lóránt Nagy, Gábor Somlai, Máté Vizer, Zeyu Zheng · 2025

Read The generalized trifference problem by Anurag Bishnoi, Bartłomiej Kielak, Benedek Kovács, Zoltán Lóránt Nagy, Gábor Somlai, Máté Vizer, Zeyu Zheng (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-07706.txt.

Description

Codes made of three-symbol strings can be judged by how much any three of them clash. Anurag Bishnoi and co-authors study the largest such codes in a 2025 paper. For any three distinct strings, at least a set number of spots must show all three symbols at once.

The team proves upper and lower bounds for that largest size across ranges of the clash demand. They find the exact point where the size jumps from flat to fast-growing as the demand rises. A straight-line version of the task links to blocking sets in finite geometry, which yields builds by hand. Small cases are worked out in full, for both the plain and the straight-line task.

Catalog record

CREATORAnurag Bishnoi, Bartłomiej Kielak, Benedek Kovács, Zoltán Lóránt Nagy, Gábor Somlai, Máté Vizer, Zeyu Zheng
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-07706

Browse the full library · About the Tower of Babel