A Hypergraph Approach to the Identifying Parent Property: The Case of Multiple Parents

Abstract

Let C be a code of length n over an alphabet of q letters. An n-word y is called a descendant of a set of t codewords x1 , . . . ,xt if $y_i\in\{x^1_i,\dots,x^t_i\}$ for all i=1, . . . ,n. A code is said to have the t-identifying parent property if for any n-word that is a descendant of at most t parents it is possible to identify at least one of them. We prove that for any $t\le q-1$ there exist sequences of such codes with asymptotically nonvanishing rate.