Construction of Optimal (r, δ)-Locally Recoverable Codes and Connection With Graph Theory

A block code is called a locally recoverable code (LRC for short) with
$(r,\delta)$
-locality, if subject to any
$\delta -1$
erasure failures, every symbol in the encoding can still be recovered by accessing at most
$r$
other symbols. Recently, it was discovered by several authors that a
$q$
-ary optimal
$(r,\delta)$
-LRC, i.e., an LRC achieving the generalized Singleton-type bound, can have length much bigger than
$q+1$
. This is quite different from the classical
$q$
-ary MDS codes where it is conjectured that the code length is upper bounded by
$q+1$
(or
$q+2$
for some special cases). In this paper, we further investigate constructions of optimal
$(r,\delta)$
-LRCs along the line of using parity-check matrices. Inspired by classical Reed-Solomon codes and the work in Jin (2019), we equip parity-check matrices with the Vandermonde structure. It turns out that a parity-check matrix with the Vandermonde structure that produces an optimal LRC must obey certain disjoint property for subsets of
$\mathbb {F}_{q}$
. We manage to show the existence of these disjoint subsets. Thus, this yields an optimal
$(r,\delta)$
-LRC with code length
$\Omega \left({q^{\frac {\delta }{2}\left({1+\frac {1}{\lfloor \frac {d-1}{\delta }\rfloor -1}}\right)}}\right)\vphantom {\bigg)_{j}}$
, where
$d$
is the minimum distance. In particular, to our surprise, for
$\delta =2$
this disjoint condition is equivalent to a well-studied problem in extremal graph theory. With the help of extremal graph theory, we succeed to improve all of the best known results in Guruswami
et al.
(2018) for
$d\geq 7$
. In addition, for
$d=6$
, we are able to remove the constraint required in Jin (2019) that
$q$
is even.