SPC product codes, graphs with cycles and Kostka numbers

The SPC product code is a very popular error correction code with four as its minimum distance. Over the erasure channel, it is supposed to correct up to three erasures. However, this code can correct a higher number of erasures under certain conditions. A codeword of the SPC product code can be represented either by an erasure pattern or by a bipartite graph, where the erasures are represented by an edge. When the erasure contains erasures that cannot be corrected, the corresponding graph contains cycles. In this work we determine the number of strict uncorrectable erasure patterns (bipartite graphs with cycles) for a given size with a fixed number of erasures (edges). Since a bipartite graph can be unequivocally represented by its biadjacency matrix, it is enough to determine the number of non-zero binary matrices whose row and column sum vectors are different from one. At the same time, the number of matrices with prescribed row and column sum vectors can be evaluated in terms of the Kostka numbers associated with Young tableaux.The first author was supported by CAPES (Brazil) and FAPESP by Grant 2013/25977-7. The second author was partially supported by Spanish Grants AICO/2017/128 of the Generalitat Valenciana and VIGROB-287 of the Universitat d’Alacant. The third author would also like to thank the Max-Planck Institut für Mathematik in Bonn for the wonderful working conditions and stimulating environment over the duration of his visit when this work was developed. The third author was supported by CAPES-Brazil