Binary codes and partial permutation decoding sets from biadjacency matrices of Bipartite graphs ┍ (2k; k; k + 1; 1)

Abstract

For a set Ω = f1; 2; : : : ; ng where n = 2k 6; let Ω fkg denote the set of all subsets of Ω of size k: We examine the binary codes from the row span of biadjacency matrices of bipartite graphs with bipartition (Ω fkg ;Ω fk+1g ) and two vertices as k-subsets and (k+1)-subsets of Ω being adjacent if they  have one element in common. We show that S2k is contained in the automorphism group of the graphs and the codes, respectively. In addition, we determine the duals of the codes, and by identifying suitable information sets, we construct 2-PD sets for the dual codes.

Key words: Biadjacency matrix, binary code, bipartite graphs, permutation decoding.