×

New bounds on \(\bar{2}\)-separable codes of length 2. (English) Zbl 1351.94091

Summary: Let \(\mathbb{C}\) be a code of length \(n\) over an alphabet of \(q\) letters. The descendant code \(\mathsf{desc}(\mathbb C_0)\) of \(\mathbb C_0 = \{\mathbf{c}^1, \mathbf{c}^2, ... , \mathbf{c}^t\} \subseteq \mathbb{C}\) is defined to be the set of words \(\mathbf{x} = (x_1, x_2, ... ,x_n)\) such that \(x_i \in \{c^1_i, c^2_i, ... , c^t_i\}\) for all \(i=1, ... , n\). \(\mathbb{C}\) is a \(\overline{t}\)-separable code if for any two distinct \(\mathbb{C}_1, \mathbb{C}_2 \subseteq \mathbb{C}\) such that \(|\mathbb{C}_1| \leq t\), \(|\mathbb{C}_2| \leq t\), we always have \(\mathsf{desc}(\mathbb{C}_1) \neq \mathsf{desc}(\mathbb{C }_2)\). The study of separable codes is motivated by questions about multimedia fingerprinting for protecting copyrighted multimedia data. Let \(M(\overline{t},n,q)\) be the maximal possible size of such a separable code. In this paper, we provide an improved upper bound for \(M(\overline{2},2,q)\) by a graph theoretical approach, and a new lower bound for \(M(\overline{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.

MSC:

94B25 Combinatorial codes
94A62 Authentication, digital signatures and secret sharing
05B40 Combinatorial aspects of packing and covering
05C51 Graph designs and isomorphic decomposition
05B25 Combinatorial aspects of finite geometries
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Benson C.T.: Minimal regular graphs of girths eight and twelve. Can. J. Math. 18, 1091-1094 (1966). · Zbl 0146.45701
[2] Blackburn S.R.: Frameproof codes. SIAM J. Discret. Math. 16, 499-510 (2003). · Zbl 1041.68063
[3] Bollobás B.: Extremal Graph Theory. Academic Press, New York (1978). · Zbl 0419.05031
[4] Boneh D., Shaw J.: Collusion-secure fingerprinting for digital data. IEEE Trans. Inf. Theory 44, 1897-1905 (1998). · Zbl 0931.94051
[5] Bryant D.E., Fu H.L.: \[C_4\] C4-saturated bipartite graphs. Discret. Math. 259, 263-268 (2002). · Zbl 1015.05036
[6] Cheng M., Miao Y.: On anti-collusion codes and detection algorithms for multimedia fingerprinting. IEEE Trans. Inf. Theory 57, 4843-4851 (2011). · Zbl 1365.94092
[7] Cheng M., Ji L., Miao Y.: Separable codes. IEEE Trans. Inf. Theory 58, 1791-1803 (2012). · Zbl 1365.94569
[8] Damásdi G., Héger H., Szönyi T.: Cages, geometries and Zarankiewicz’ problem. Ann. Univ. Eőtvős Loránd (2013). · Zbl 1289.05227
[9] de Caen D., Székely L.A.: On dense bipartite graphs of girth eight and upper bounds for certain configurations in planar point-line systems. J. Comb. Theory Ser. A 77, 268-278 (1997). · Zbl 0878.05051
[10] Erdős P., Sárkőzy A., Sós V.T.: On product representations of powers. I. Eur. J. Comb. 16, 567-588 (1995). · Zbl 0840.11010
[11] García-Vázquez P., Balbuena C., Marcote X., Valenzuela J.C.: On extremal bipartite graphs with high girth. Electron. Notes Discret. Math. 26, 67-73 (2006). · Zbl 1225.05141
[12] Goddard W., Henning M.A., Oellermann O.R.: Bipartite Ramsey numbers and Zarankiewicz numbers. Discret. Math. 219, 85-95 (2000). · Zbl 0953.05051
[13] Györi E.: \[C_6\] C6-free bipartite graphs and product representations of squares. Discret. Math. 165(166), 371-375 (1997). · Zbl 0873.05058
[14] Hirschfeld J.W.P.: Projective Geometries over Finite Fields, 2nd edn. Oxford Science, Oxford (1998). · Zbl 0899.51002
[15] Hollmann H.D.L., van Lint J.H., Linnartz J.-P., Tolhuizen L.M.G.M.: On codes with the identifiable parent property. J. Comb. Theory Ser. A 82, 121-133 (1998). · Zbl 0910.05070
[16] Hoory S.: The size of bipartite graphs with a given girth. J. Comb. Theory Ser. B 86, 215-220 (2002). · Zbl 1027.05050
[17] Lam T.: Graphs without cycles of even length. Bull. Australas. Math. Soc. 63, 435-440 (2001). · Zbl 0979.05069
[18] Lam T.: A result on \[2k2\] k-cycle-free bipartite graphs. Australas. J. Comb. 32, 163-170 (2005). · Zbl 1066.05080
[19] Liu K.J.R., Trappe W., Wang Z.J., Wu M., Zhao H.: Multimedia Fingerprinting Forensics for Traitor Tracing. Hindawi Publishing Corporation, New York (2005).
[20] Mehlhorn K.: Data Structures and Algorithms 1. Springer, Berlin (1984). · Zbl 0556.68001
[21] Naor A., Verstraëthe J.: A note on bipartite graphs without \[2k2\] k-cycles. Comb. Probab. Comput. 14, 845-849 (2005). · Zbl 1079.05047
[22] Neuwirth S.: The size of bipartite graphs with girth eight, arXiv:math/0102210 (2001).
[23] Singer J.: A theorem in finite projective geometry and some applications to number theory. Trans. Am. Math. Soc. 43, 377-385 (1938). · Zbl 0019.00502
[24] Staddon J.N., Stinson D.R., Wei R.: Combinatorial properties of frameproof and traceability codes. IEEE Trans. Inf. Theory 47, 1042-1049 (2001). · Zbl 1001.94032
[25] Stinson D.R., van Trung, T., Wei R.: Secure frameproof codes, key distribution pattern, group testing algorithms and related structures. J. Stat. Plan. Inference 86, 595-617 (2000). · Zbl 1054.94013
[26] Wenger R.: Extremal graphs with no \[C^4\] C4’s, \[C^6\] C6’s, or \[C^{10}\] C10’s. J. Comb. Theory Ser. B 52, 113-116 (1991). · Zbl 0755.05060
[27] Zarankiewicz K.: Problem P101. Colloquium Math. 2, 301 (1951).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.