The Trifference Problem

Anurag Bishnoi wrote this beautiful post on a problem going back to a 1988 paper of Körner and Marton, and on a recent lovely paper by Anurag Bishnoi, Jozefien D’haeseleer, Dion Gijswijt, and Aditya Potukuchi, Blocking sets, minimal codes and trifferent codes.

Anurag's Math Blog

What is the largest possible size of a set $latex C$ of ternary strings of length $latex n$, with the property that for any three distinct strings in $latex C$, there is a position where they all differ?

Let $latex T(n)$ denote this largest size. Trivially, $latex T(1) = 3^1 = 3$, and after some playing around you can perhaps prove that $latex T(2) = 4$ (I encourage you to try it so that you understand the problem). With a bit more effort, and perhaps the help of a computer, you might also be able to show that $latex T(3) = 6$, and $latex T(4) = 9$. For example, here is a set of nine ternary strings showing that $latex T(4) geq 9$: $latex 0000, 0111, 2012, 2201, 2120, 0111, 1012, 1101, 1210$. You should check that for any three strings from these nine, there is at least one position…

View original post 872 more words

This entry was posted in Uncategorized. Bookmark the permalink.

2 Responses to The Trifference Problem

  1. Thanks a lot Gil! Here is the arXiv preprint:

    GK: Thanks, Anurag. I updated my post…

  2. tanner808 says:

    Thanks a lot! Fir sharing this post with us. Akira Leather Jacket

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s