The generalized trifference problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908360639512576 |
|---|---|
| author | Bishnoi, Anurag Kielak, Bartłomiej Kovács, Benedek Nagy, Zoltán Lóránt Somlai, Gábor Vizer, Máté Zheng, Zeyu |
| author_facet | Bishnoi, Anurag Kielak, Bartłomiej Kovács, Benedek Nagy, Zoltán Lóránt Somlai, Gábor Vizer, Máté Zheng, Zeyu |
| contents | We study the problem of finding the largest number $T(n, m)$ of ternary vectors of length $n$ such that for any three distinct vectors there are at least $m$ coordinates where they pairwise differ.
For $m = 1$, this is the classical trifference problem which is wide open.
We prove upper and lower bounds on $T(n, m)$ for various ranges of the parameter $m$ and determine the phase transition threshold on $m=m(n)$ where $T(n, m)$ jumps from constant to exponential in $n$.
By relating the linear version of this problem to a problem on blocking sets in finite geometry, we give explicit constructions and probabilistic lower bounds.
We also compute the exact values of this function and its linear variation for small parameters. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_07706 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The generalized trifference problem Bishnoi, Anurag Kielak, Bartłomiej Kovács, Benedek Nagy, Zoltán Lóránt Somlai, Gábor Vizer, Máté Zheng, Zeyu Combinatorics Information Theory We study the problem of finding the largest number $T(n, m)$ of ternary vectors of length $n$ such that for any three distinct vectors there are at least $m$ coordinates where they pairwise differ. For $m = 1$, this is the classical trifference problem which is wide open. We prove upper and lower bounds on $T(n, m)$ for various ranges of the parameter $m$ and determine the phase transition threshold on $m=m(n)$ where $T(n, m)$ jumps from constant to exponential in $n$. By relating the linear version of this problem to a problem on blocking sets in finite geometry, we give explicit constructions and probabilistic lower bounds. We also compute the exact values of this function and its linear variation for small parameters. |
| title | The generalized trifference problem |
| topic | Combinatorics Information Theory |
| url | https://arxiv.org/abs/2505.07706 |