### Secure Frameproof Code Through Biclique Cover

*Hossein Hajiabolhassan, Farokhlagha Moazami*

#### Abstract

For a binary code Γ of length v , a
v -word w produces by a set of codewords
{w

^{1},…,w^{r}} ⊆Γ if for all i=1,…,v , we have w_{i}∈{w_{i}^{1}, …, w_{i}^{r}} . We call a code r -secure frameproof of size t if |Γ|=t and for any v -word that is produced by two sets C_{1}and C_{2}of size at most r , then the intersection of these sets is non-empty. A d -biclique cover of size v of a graph G is a collection of v complete bipartite subgraphs of G such that each edge of G belongs to at least d of these complete bipartite subgraphs. In this paper, we show that for t≥2r, an r-secure frameproof code of size t and length v exists if and only if there exists a 1-biclique cover of size v for the Kneser graph KG(t,r) whose vertices are all r-subsets of a t-element set and two r-subsets are adjacent if their intersection is empty. Then we investigate some connection between the minimum size of d-biclique covers of Kneser graphs and cover-free families, where an (r,w; d) cover-free family is a family of subsets of a finite set X such that the intersection of any r members of the family contains at least d elements that are not in the union of any other w members. The minimum size of a set X for which there exists an (r,w;d) cover-free family with t blocks is denoted by N((r,w;d),t). We prove that for t > 2r and r>s, we have bc_{d}(KG(t,r))≥bc_{m}(KG(t,s)), where m=N((r-s,r-s;d),t-2s). Finally, we show that for any 1≤i < r, 1≤j < w, and t≥r+w we have N((r,w;d),t)≥N((r-i,w-j;m),t), where m=N((i,j;d),t-r-w+i+j).Full Text: PDF PostScript