Binary codes from subset inclusion matrices

Abstract

In this paper, we study the minimum distances of binary linear codes with parity check matrices formed from subset inclusion matrices $W_{t,n,k}$, representing $t$-element subsets versus $k$-element subsets of an $n$-element set. We provide both lower and upper bounds on the minimum distances of these codes and determine the exact values for any $t\le 3$ and sufficiently large $n$. Our study combines design and integer linear programming techniques. The codes we consider are connected to locally recoverable codes, LDPC codes and combinatorial designs.