## Abstract

Let C be a code of length n over an alphabet of q letters. The descendant code (C^{0}) of C^{0} ={c_{1},c_{2},..c_{t}}⊆C is defined to be the set of words x =(x^{1},x^{2},..,x^{n}) such that x^{i}∈{c^{i} _{1},c^{i} _{2},..,c^{i} _{t}} for all i = 1,..,n. C is a t¯-separable code if for any two distinct C^{1} ,C^{2} ⊆C such that |C^{1}|≤t, |C^{2}|≤t, we always have desc(C^{1})≠desc(C^{2}). The study of separable codes is motivated by questions about multimedia fingerprinting for protecting copyrighted multimedia data. Let M(t¯,n,q) be the maximal possible size of such a separable code. In this paper, we provide an improved upper bound for M(2¯,2,q) by a graph theoretical approach, and a new lower bound for M(2¯,2,q) by deleting suitable points and lines from a projective plane, which coincides with the improved upper bound in some places. This corresponds to the bounds of maximum size of bipartite graphs with girth 6 and a construction of such maximal bipartite graphs.

Original language | English |
---|---|

Pages (from-to) | 31-40 |

Number of pages | 10 |

Journal | Designs, Codes, and Cryptography |

Volume | 74 |

Issue number | 1 |

DOIs | |

State | Published - 1 Jan 2013 |

## Keywords

- 4-Cycle free bipartite graph
- Multimedia fingerprinting
- Projective plane
- Separable code
- Zarankiewicz number