K-Plex 2-Erasure Codes and Blackburn Partial Latin Squares.

A k-plex of order n is an ${n} \times {n}$ matrix on n symbols, where every row contains k distinct symbols, every column contains k distinct symbols, and every symbol occurs exactly k times. Yi et al. (2019) introduced 3-plex codes which are 2-erasure codes (2-erasure tolerant array codes) derived from 3-plexes. In this paper, we generalize 3-plex codes to k-plex codes. We introduce the notion of a “strong” k-plex which implies the derived k-plex code is 2-erasure tolerant. Moreover, k-plex codes derived from strong $k$ -plexes have a straightforward algorithm for reconstruction. These general k-plex codes offer greater flexibility when choosing a suitable code for a storage system, enabling the operator to better optimize the unavoidable trade-offs involved. Blackburn asked for the maximum number of entries in an ${n} \times {n}$ partial Latin square on n symbols in which if distinct cells $({i},{j})$ and $({i}',{j}')$ contain the same symbol, then the cells $({i}',{j})$ and $({i},{j}')$ are empty. A “strong” k-plex satisfies the Blackburn property (along with two other properties related to erasure coding). We investigate the necessary conditions for the existence of Blackburn k-plexes (and hence necessary conditions for the existence of strong k-plexes). We show that any Blackburn k-plex has order ${n} \geq \lceil (\sqrt {2}+1){k}-2 \rceil $. We describe how to construct strong k-plexes of order n when $k \in \{2,3,4,5\}$ for all possible orders n, and we give a simple construction of strong k-plexes of order ${k}^{2}$ for $k \geq 2$. [ABSTRACT FROM AUTHOR]