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
{w1,…,wr}
⊆Γ if for all i=1,…,v , we have
wi∈{wi1, …,
wir} . We call a code r
-secure frameproof of size t if |Γ|=t
and for any v -word that is produced by two sets
C1 and C2 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
bcd(KG(t,r))≥bcm(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