Print Email Facebook Twitter The Trifference Problem Title The Trifference Problem Author van Donkelaar, Mirko (TU Delft Electrical Engineering, Mathematics and Computer Science) Contributor Gijswijt, D.C. (mentor) Bishnoi, A. (mentor) Komjáthy, J. (graduation committee) Degree granting institution Delft University of Technology Programme Applied Mathematics Date 2022-07-14 Abstract A code C is defined to be a set of S words, where a word is a sequence of n entries. We call S the size and n the length of the code. The entries of the code can have k different values, {0, .., (k − 1)}. Define a perfect k-hash code (PHC) as a code with the property that any collection of v words in the code is different at at least one index. PHC’s are useful mathematical objects within different fields of theoretical computer science and coding theory. This thesis will focus on one typical kind of PHC, a trifferent code. Such a trifferent code is defined as a PHC where k = v = 3. This means that any collection of three words in the code has to differ at some index. We now define T (n) to be the largest possible size of a trifferent code given that it has length n. The question that arises is, what is the value of T (n)? It turns out that determining the exact value is complicated, unless n is really small. Therefore, we try to understand the asymptotic nature of the function T (n). This is what we call the trifference problem. This paper will cover and prove the best known asymptotic upper and lower bound on T (n). Moreover, it will explain and include a Python code that can be used to show and prove all values of T (n) for n ∈ {1, .., 6}. Lastly, two different ways to explicitly construct trifferent codes for any value of n will be given and compared. Subject TrifferencePerfect-k HashingCoding Theory To reference this document use: http://resolver.tudelft.nl/uuid:d59e2578-cae3-4625-badd-72f72e4e7a7d Part of collection Student theses Document type bachelor thesis Rights © 2022 Mirko van Donkelaar Files PDF The_Trifference_Problem_F ... port_2.pdf 501.92 KB Close viewer /islandora/object/uuid:d59e2578-cae3-4625-badd-72f72e4e7a7d/datastream/OBJ/view