<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Maximum IPP Codes of Length 3
Wen Jiang1, Ye Li2, and Xingxing Yu1,3
1School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, USA
2School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA
3Center for Combinatorics, LPMC, Nankai University, Tianjin 300071, China
yu@math.gatech.edu
Annals of Combinatorics 13 (4) pp.491-510 December, 2009
AMS Subject Classification: 94B65, 05C75
Abstract:
Let Q be an alphabet with q elements. For any code C over Q of length n and for any two codewords a = (a1, … , an) and b = (b1, … , bn) in C, let D(a, b) = {(x1, … , xn) ∈ Qn : xi ∈ {ai, bi} for 1 ≤ i ≤ n}. Let C* = Ua,b∈C D(a,b). The code C is said to have the identifiable parent property (IPP) if, for any x∈C*, ∩x∈D(a,b){a, b}≠ Ø. Codes with the IPP were introduced by Hollmann et al [J. Combin. Theory Ser. A 82 (1998) 121–133]. Let F(n, q) = max{|C| : C is a q-ary code of length n with the IPP}. Tˆo and Safavi-Naini [SIAM J. Discrete Math. 17 (2004) 548–570] showed that 3q+6-6≤ F(3, q) ≤3q+6-, and determined F(3, q) precisely when q ≤ 48 or when q can be expressed as r2 +2r or r2 +3r +2 for r ≥ 2. In this paper, we establish a precise formula of F(3, q) for q ≥ 24. Moreover, we construct IPP codes of size F(3, q) for q ≥ 24 and show that, for any such code C and any x∈ C*, one can find, in constant time, a ∈C such that if x ∈ D(c, d) then a∈ {c, d}.
Keywords: IPP code, edge colored graph, component, complete graph
References:

1. Alon, N., Fischer, E., Szegedy, M.: Parent-identifying codes. J. Combin. Theory Ser. A 95(2), 349--–359 (2001)

2. Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. Macmillan Press Ltd, New York (1976)

3. Fernandz, M., Soriano, M.: Decoding Codes with the Identifiable Parent Property, In: Proceedings of the Seventh IEEE International Symposium on Computers and Communications.
IEEE Computer Society, Washington (2002)

4. Hollmann, H.D.L., Lint, J.H.V., Linnartz, J., Tolhuizen, L.M.G.M.: On codes with the identifiable parent property. J. Combin. Theory Ser. A 82(2), 121--–133 (1998)

5. Jiang, W.: Maximum Codes with the Identiable Parent Property, Ph.D Thesis. Georgia Institute of Technology, Atlanta (2006).

6. Kerner, J., Marton, K.: New bounds for perfect hashing via information theory. European J. Combin. 9(6), 523--530 (1988)

7. Tˆo, V., Safavi-Naini, R.: On the maximal codes of length 3 with the 2-identifiable parent property. SIAM J. Discrete Math. 17(4), 548--–570 (2004)