## DIMACS TR: 2000-20

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

### Authors: A. Barg, G. Cohen, S. Encheva, G. Kabatiansky, G. Zemor

**
ABSTRACT
**

Let $C$ be a code of length $n$ over an alphabet of
$q$ letters. A codeword $y$ is called a descendant of a set
of $t$ codewords $ x^1,\dots,x^t$ if $y_i\in\{x^1_i,\dots,x^t_i\}$
for all $i=1,\dots,n.$ A code is said to have the identifiable 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.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-20.ps.gz

DIMACS Home Page