Extremal regular graphs and hypergraphs related to fractional repetition codes

Fractional repetition codes (FRCs) are a special family of storage codes with the repair-by-transfer property in distributed storage systems. Constructions of FRCs are naturally related to combinatorial designs, graphs, and hypergraphs. In this paper, we consider an extremal problem on regular graphs related to FRCs where each packet is stored on \(\rho =2\) $\rho =2$ nodes. The problem asks for the minimum number of vertices in an \(\alpha \) $\alpha$ -regular graph such that any k vertices induce at most \(\delta \) $\delta$ edges, where \(\alpha \) $\alpha$ , k, and \(\delta \) $\delta$ are given. Such a problem is closely related to (and can be seen as a generalization of) the classical cage problem, and its solution indicates the minimum number of nodes in an FRC-based distributed storage system. In addition, we further consider FRCs with \(\rho \ge 3\) $\rho \ge 3$ and generalize the extremal problem to a linear hypergraph version.