New bounds on (2)over-bar-separable codes of length 2

Abstract

Let be a code of length over an alphabet of letters. The descendant code of is defined to be the set of words such that for all . is a -separable code if for any two distinct such that , , we always have . The study of separable codes is motivated by questions about multimedia fingerprinting for protecting copyrighted multimedia data. Let be the maximal possible size of such a separable code. In this paper, we provide an improved upper bound for by a graph theoretical approach, and a new lower bound for 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 and a construction of such maximal bipartite graphs.