Maximum Distance Separable codes are known to play an important and influential role in the area of coding theory. An MDS code over an alphabet F is defined via an encoding function C : F k → F n that allows to retrieve a message m ∈ F k from the codeword C(m) even after erasing any nk of its symbols. Equivalently, the Hamming distance between any two distinct codewords is at least nk + 1. The wellknown Singleton bound implies that MDS codes are optimal with respect to the number of erasures that they can handle. However, the minimum possible alphabet size of such codes for given parameters n and k is unknown and forms a central open question in coding theory (see Conjectures 1 and 2).
The present paper initiates the study of the alphabet size of codes in a generalized setting where the coding scheme is required to handle a pre-specified subset of all possible erasure patterns. Such scenarios arise naturally in the distributed storage settings in which there is a need to rebuild the entire data set by contacting one of the pre-specified sets of storage nodes, referred to as a recovery group. The desired set of recovery groups is determined based on the network configuration, the reliability of storage nodes, as well as the network access patterns. Similar constraints appear in availability codes [1], which have recently attracted interest Mira Gonen is with the Department of Computer Science, Ariel University, Ariel 40700, Israel (e-mail: mirag@ariel.ac.il).
Ishay Haviv is with the School of Computer Science, The Academic College of Tel Aviv-Yaffo, Tel Aviv 61083, Israel.
Michael Langberg is with the Department of Electrical Engineering, State University of New-York at Buffalo, Buffalo, NY 14260, USA (e-mail: mikel@buffalo.edu). Work supported in part by NSF grant 1909451.
Alex Sprintson is with the Department of Electrical and Computer Engineering, Texas A&M University, College Station, TX 77843-3128, USA (e-mail: spalex@tamu.edu). Work supported in part by NSF grants 1642983 and 1718658. from the research community. However, in availability codes each recovery group is used for retrieving a single symbol, whereas we are focusing on retrieving the entire set of k symbols.
The set of erasure patterns is naturally represented by an n-vertex k-uniform hypergraph in which the vertices represent the n coordinates of the codewords and the (hyper)edgesfoot_0 correspond to the possible sets of locations of unerased symbols (i.e., decoding sets). For a given uniform hypergraph G we are interested in minimizing the size of an alphabet over which there exists a coding scheme with respect to the erasure patterns defined by G.
Definition 1 (The q parameter) Let G = ([n], E) be a kuniform hypergraph on the vertex set [n] = {1, . . . , n}. Let q(G) denote the smallest size q of an alphabet F for which there exist an encoding function Similarly, let q lin (G) denote the smallest prime power q for which there exist linear encoding and decoding functions as above when F is a field of size q.
Observe that for the complete n-vertex k-uniform hypergraph, denoted by κ n,k , the values of q(κ n,k ) and q lin (κ n,k ) are equal, respectively, to the minimum alphabet sizes of general and linear MDS codes of length n and dimension k. We state below the MDS conjectures for general and for linear codes (see, e.g., [2]- [5]).
Conjecture 1 (MDS Conjecture for general codes) For given integers k < q = 6, let n(q, k) be the largest integer n such that q(κ n,k ) ≤ q. Then,
Conjecture 2 (MDS Conjecture for linear codes) For given integers k < q where q is a prime power, let n(q, k) be the largest integer n such that q lin (κ n,k ) ≤ q. Then, n(q, k) ≤ q + 2 if q is even and k ∈ {3, q -1} q + 1 otherwise.
(2)
Note that in Conjecture 2 the right-hand side is known to form a lower bound on the left-hand side, and that the special case of the above conjectures for k = 2 is known to hold (see, e.g., [5]). The MDS Conjecture for linear codes over prime fields has been proven by S. Ball in his seminal paper [6].
In this work we aim to study the behavior of the q parameter for general sub-hypergraphs of κ n,k . Our results imply strong relations between the q parameter of uniform hypergraphs and their chromatic number. A valid coloring of a hypergraph G is an assignment of colors to its vertices so that the vertices of each edge are assigned to distinct colors. This is at times referred to as a strong coloring and is consistent with the notion of graph coloring (i.e., the coloring of hypergraphs with edges of size two). The chromatic number χ(G) of G is the minimum number of colors that allows a valid coloring of G.
In what follows we give an overview of our results. Some of the proofs can be found in Section III. All proofs appear in the full version of this work [7].
We start with the following upper bounds.
Theorem 1 For every k-uniform hypergraph G, q(G) ≤ q(κ χ(G),k ) and q lin (G) ≤ q lin (κ χ(G),k ). In particular,
Here, for an integer x, [x] pp represents the smallest prime power that is greater or equal to x.
Theorem 1 formalizes the natural intuition that for simple collections of erasure patterns G, i.e., the setting in which χ(G) is small, a small alphabet size q suffices for a suitable erasure code. The question we next consider is whether the upper bound provided by Theorem 1 is tight.
The following result shows that Theorem 1 is not tight in general.
Proposition 1 There exists a 3-uniform hypergraph G with q lin (G) = q(G) = 2 and yet q(κ χ(G),3 ) ≥ 5.
We further show that for every k ≥ 3 the chromatic number of k-uniform hypergraphs can be significantly larger than their q parameter (even while restricted to the linear setting). This implies a large gap between the q parameter and its upper bound provided by Theorem 1.
Proposition 2 For every k ≥ 3 and every prime power q, there exists a k-uniform hypergraph G with q lin (G) ≤ q and yet χ(G) ≥ q k -1 q-1 .
For k = 2, the question at hand seems to be more challenging. Here we ask whether there exists a graph G for which q(G) is significantly smaller than q lin (G) which in turn is known to be at most [χ(G) -1] pp . We thus study the relationship between q(G) and χ(G). Our results for this case are outlined below.
To study the relationship between q and χ for the case k = 2, we define the following graph family.
Definition 2 (The graph family G q ) For an integer q, let G q be the graph whose vertex set consists of all the balanced vectors of length q 2 over [q], that is, the vectors
The graph family G q is extremal with respect to the q parameter in the sense given by the following lemma.
Lemma 1 For every integer q, 1) q(G q ) ≤ q and 2) χ(G) ≤ χ(G q ) for every graph G with q(G) = q.
By Lemma 1, the challenge of obtaining graphs with chromatic number much larger than the q parameter reduces to the study of the chromatic number χ(G q ) of G q . We first show that if we require the coding scheme of G q to be linear then the size of the used alphabet cannot be smaller than [χ(G q ) -1] pp (implying that Theorem 1 is tight in this case). Recall that this is in contrast to the situation of k ≥ 3 (see Proposition 2). Proposition 3 For every integer q,
And what about non-linear codes? Is q(G q ) significantly smaller than χ(G q )? For q = 2, it is not difficult to see that χ(G q ) = 3 = q(G q ) + 1. However, an exhaustive analysis due to [8] shows that for q = 3 it holds that χ(G q ) = 6 > q(G q ) + 1. For general values of q, we provide the bounds stated below. We use here the notation n(q, 2) which stands for the largest integer n for which there exists an MDS code of length n and dimension 2 over an alphabet of size q. Note that if q is a prime power then n(q, 2) = q + 1.
Proposition 4 For every integer q, n(q, 2) ≤ χ(G q ) ≤ q + 1 2 .
In particular, if q is a prime power then
It is interesting to understand the asymptotic behavior of χ(G q ) as a function of q. In an attempt to shed some light on this question, we provide a couple of related results, described next.
Firstly, we consider a natural family of independent sets of G q which we refer to as canonical independent sets. The canonical independent set A i,j associated with two distinct indices i, j ∈ [q 2 ] is the set of all vertices u ∈ [q] q 2 of G q that satisfy u i = u j . For a prime power q, it can be seen that A i,j is an independent set of maximum size in G q . In fact, this type of independent set is used to obtain the upper bound in Proposition 4. However, we show that if we restrict ourselves to colorings of G q whose color classes are all contained in canonical independent sets then the number of used colors has to be quadratic in q (see Proposition 5) and is thus close to the upper bound of Proposition 4.
Secondly, we focus on the subgraph of G q induced by the vertices whose vectors in [q] q 2 form concatenations of q permutations of [q]. It is shown that the chromatic number of this subgraph is only linear in q, corresponding now to the lower bound of Proposition 4. Intuitively speaking, this might hint that the difficulty in coloring the graph G q using few colors comes from the 'less-structured areas' of the graph (see Proposition 6).
We conclude our work with a further extension of the q parameter to an error-tolerant model.
In this last study, for a given uniform hypergraph G and an error parameter ε > 0, we are interested in minimizing the size of the alphabet over which there exists a coding scheme with respect to the erasure patterns defined by G that guarantees success probability at least 1ε. We first study the setting in which the success probability is taken over the uniform distribution on the messages. This is given formally in the following definition.
Definition 3 (The q ε parameter) Let G = ([n], E) be a kuniform hypergraph on the vertex set [n] and let ε > 0. Let q ε (G) denote the smallest size q of an alphabet F for which there exist an encoding function C : F k → F n and a decoding function D : (F ∪ {⊥}) n → F k such that for every edge e ∈ E it holds that
where m is uniformly chosen from F k .
Notice that the q parameter given in Definition 1 coincides with Definition 3 when ε = 0. Similar to Theorem 1, the following holds.
Theorem 2 For every ε ≥ 0 and a k-uniform hypergraph G,
We focus our study on the case k = 2. To demonstrate Definition 3, we consider the complete graph κ n,2 . For ε = 0, this takes us to 2-dimensional MDS codes. However, if the probability of success is slightly relaxed it turns out that the required alphabet size can be reduced. For example, in Proposition 7 of Section IV we show that
• for ε = 1 3 , q ε (κ 20,2 ) ≤ 3 whereas q(κ 20,2 ) = 19, • for ε = 1 4 , q ε (κ 7,2 ) ≤ 4 whereas q(κ 7,2 ) = 6, and • for ε = 1 6 , q ε (κ 6,2 ) ≤ 6 whereas q(κ 6,2 ) = 7. Notice that, for k = 2, ε > 0 implies ε ≥ 1 q 2 (as our error is measured over a sample space of size q 2 ). Thus, as a first step in understanding q ε , in the analysis above and those that follow, we study ε for the intermediate value of 1 q . A full study addressing q ε for general ε is left for future work.
In Section IV, we study the q ε parameter for general graphs G (with k = 2 and ε = 1/q). As in our study of the q parameter, we employ the tool of universal graphs (i.e., an analog to the graph family of Definition 2) and apply it for the error-tolerant setting. See Propositions 8, 9, and 10 in Section IV.
Finally, in Section IV-C, we further extend the notion of error to allow an average error ε over both the messages and the edges in E. Here, the decoding error is computed assuming a uniform set of k messages and a uniform decoding edge in E (see Definition 6 in Section IV-C). Roughly speaking, we show in Theorem 3 that this last notion of error allows significant flexibility in the sense that for a given ε the relaxed q ε parameter is bounded by approximately 1/ε on complete graphs.
Let G be a k-uniform hypergraph on the vertex set [n] and let χ = χ(G). Denoting q = q(κ χ,k ), it follows that for an alphabet F of size q there exist an encoding function C : F k → F χ and a decoding function D : (F ∪ {⊥}) χ → F k such that for every k-subset e of [χ] and every message m ∈ F k it holds that D(C e (m)) = m.
To prove that q(G) ≤ q we define a coding scheme over the alphabet F as follows. Fix a valid coloring g : which corresponds to the color of the ith vertex. Here, and throughout, we use the notation C i (m) to denote the ith entry in the codeword C(m). It remains to show that given a word C e (m) ∈ (F ∪ {⊥}) n for an edge e of G and a message m ∈ F k , it is possible to retrieve m. Indeed, consider the word C e (m) restricted to the entries corresponding to an edge e (recall that the value of these entries is not the erasure symbol ⊥). As the vertices of e are colored by g using distinct colors, the values of the corresponding entries in C e (m) equal to k distinct entries in C(m). As C(m) is decodable from any set of k distinct entries via D, we conclude that given C e (m) we can retrieve m as well. An identical proof shows that q lin (G) ≤ q lin (κ χ(G),k ) ≤ [χ(G) -1] pp (where the rightmost inequality follows from the known upper bounds on q lin as discussed after Conjecture 2).
The proof is based on the Fano plane illustrated in Figure 1. Recall that the Fano plane is defined over a set of 7 points, denoted here by the integers in [7], and consists of 7 lines with 3 points on every line and 3 lines on every point. Let G be the 3-uniform hypergraph on the vertex set [7] whose edges are all the 3-subsets of [7] that do not form lines in the Fano plane. We claim that G satisfies the assertion of the proposition. To this end, we turn to show that 1) χ(G) = 7, 2) q lin (G) = q(G) = 2, and 3) q(κ 7,3 ) ≥ 5. For Item 1, observe that every two vertices of G are included in some edge of G, hence every valid coloring of G assigns every vertex to a distinct color, implying that χ(G) = 7. For Item 2, consider the three vectors v 1 = (0, 0, 0, 1, 1, 1, 1), v 2 = (0, 1, 1, 1, 0, 0, 1), and v 3 = (1, 1, 0, 1, 1, 0, 0) over the binary field F 2 , and let C : F 3 2 → F 7 2 be a linear encoding function whose image is the linear span of {v 1 , v 2 , v 3 }.
It is straightforward to verify that if we restrict the images of the function C to the coordinates of any edge of G we get an invertible function from F 3 2 to F 3 2 . For example, restricting C to coordinates {1, 2, 4} gives a function whose image is spanned by the restrictions of {v 1 , v 2 , v 3 } to these coordinates, i.e., a function with image spanned by {(0, 0, 1), (0, 1, 1), (1, 1, 1)}. As the latter vectors are linearly independent over F 2 it follows that the restriction of C at hand is invertible. We conclude that for every edge e of G and for every message m ∈ F 3 2 , one can decode m from the codeword C(m) even if the symbols in the locations of [7] \ e are erased, hence q lin (G) ≤ 2. Since it clearly holds that q lin (G) ≥ q(G) ≥ 2, Item 2 follows. Finally, Item 3 follows from the fact that q(κ n,k ) ≥ nk + 1 for every n ≥ k ≥ 2 (see [9]).
Let F be a field of size q. Consider a k-uniform hypergraph G whose vertices correspond to normalized vectors in F k . Here, a normalized vector (x 1 , . . . , x k ) ∈ F k is one in which the leading nonzero entry equals 1. The number of vertices n in G is thus ∑ k i=1 q k-i = (q k -1)/(q -1). The edge set of G consists of all k-collections of vertices in G that correspond to linearly independent vectors. As any two vertices in G have corresponding vectors that can be completed to a linearly independent set of size k, any two vertices in G are included in at least one edge in G. Thus χ(G) = n = (q k -1)/(q -1).
In what follows, we use a natural relation between vertices in G and linear functions F k → F. Specifically, if vertex i in G is defined by the vector (x 1 , . . . , x k ), then the function
be a linear code which maps messages m = (m 1 , . . . , m k ) to the codeword C(m) using the relation above. Namely, the ith entry C i (m) of C(m) is defined to be f i (m). As edges in G consist of vertices that correspond to linearly independent vectors, it follows that for every edge in G, the message m can be recovered from C e (m). This implies that q lin (G) ≤ q.
For an integer q, let n q denote the number of vertices in the graph G q . Recall that the vertices of G q are the balanced vectors of [q] q 2 , and note that each of them can be realized as a function from F 2 to F, where F is an alphabet of size q. Namely, with each vertex v in G q we associate a function f v (m) that takes m ∈ F 2 and returns an element in F. We turn to show a coding scheme over the alphabet F with respect to the erasure patterns defined by the graph G q . To this end, consider the encoding function C : F 2 → F n q for which for any m, C v (m) = f v (m). Here, for any vertex v in G q , C v (m) denotes the entry of C corresponding to v. For the decoding, consider a word C(m) and assume that all of its symbols but the two that correspond to some adjacent vertices u and v are erased. We claim that given C u (m) and C v (m) it is possible to retrieve m. Indeed, by the definition of G q , the possible pairs (C u (m), C v (m)) over all messages m ∈ F 2 are all the distinct pairs in F 2 , hence the pair (C u (m), C v (m)) fully determines the message m. This implies that q(G q ) ≤ q.
For the second item, let G = (V, E) be a graph with q(G) = q. Then there exists a coding scheme over an alphabet F of size q with respect to the erasure patterns defined by G. Let C : F 2 → F |V| be the encoding function of such a coding scheme. Observe that the existence of a corresponding decoding function implies that for every adjacent vertices u and v in G it holds that the possible pairs (C u (m), C v (m)) over all messages m ∈ F 2 are all the pairs in F 2 . We assign to every non-isolated vertex v ∈ V the vertex of G q that represents the function that assigns every m ∈ F 2 to C v (m). We further assign isolated vertices of G to arbitrary vertices of G q . This mapping forms a homomorphism from G to G q , so in particular, it holds that χ(G) ≤ χ(G q ).
For an integer q, let n q denote the number of vertices in the graph G q . Assume in contradiction that for some prime power q , q lin (G q ) = q < [χ(G q ) -1] pp , and let C be a linear encoding function for the graph G q over a field F of size q . Note that for every message m ∈ F 2 , C(m) = (C 1 (m), . . . , C n q (m)), where each C i (m) is a linear function of m. One may represent each such function C i by a vector (x 1 , x 2 ) ∈ F 2 such that C i (m) = x 1 m 1 + x 2 m 2 for every m = (m 1 , m 2 ). By the decodability of C, it follows that the vectors associated with the endpoints of any edge in G q are linearly independent (in particular, there are no entries in C which correspond to the zero linear function). Thus, similar to the proof of Proposition 2, we may assume that the vectors corresponding to entries of C are normalized, i.e., their leading nonzero coefficient is 1, since such a normalized C is still an erasure code for G q . A simple counting argument shows that the number of distinct normalized vectors in F 2 is precisely q + 1. This implies that χ(G q ) ≤ q + 1, since using the distinct normalized vectors of C to represent color classes one could color G q . This in turn implies that [χ(G q ) -1] qq ≤ q , in contradiction to our assumption.
For an integer q consider the graph G q given in Definition 2. For two distinct indices i, j ∈ [q 2 ] let A i,j be the set of all vertices u ∈ [q] q 2 of G q that satisfy u i = u j . Every set A i,j forms an independent set in G q since for every two distinct vertices u, v ∈ A i,j we have u i = u j and v i = v j , and thus (u i , v i ) = (u j , v j ), which implies that the collection of pairs {(u i , v i )} i∈[q 2 ] is not equal to [q] × [q]. We refer to such independent sets of G q as canonical. The canonical independent sets of G q are used in the proof of Proposition 4.
Proposition 5 For every sufficiently large integer q, the number of canonical independent sets required to cover the vertex set of G q is Ω(q 2 ).
Definition 4 (The graphs H q and H cyclic q ) Let q be an integer. Let the vector representation of a permutation σ ∈ S q be (σ(1), . . . , σ(q)). A vector (v 1 , . . . , v q 2 ) of [q] q 2 is said to be a concatenation of q permutations if for every i ∈ [q] the vector (v q(i-1)+1 , . . . , v qi ) is a permutation of [q]. Let H q be the subgraph of G q induced by the vectors in [q] q 2 that are concatenations of q permutations. Let H cyclic q be the subgraph of G q induced by the vectors in [q] q 2 that are concatenations of q cyclic permutations. Proposition 6 For every integer q, χ(H cyclic q ) ≤ χ(H q ) ≤ q.
IV. THE q ε PARAMETER A. The study of κ.
• For ε = 1 3 , q ε (κ 20,2 ) ≤ 3 whereas q(κ 20,2 ) = 19, and • For ε = 1 4 , q ε (κ 7,2 ) ≤ 4 whereas q(κ 7,2 ) = 6, and • For ε = 1 6 , q ε (κ 6,2 ) ≤ 6 whereas q(κ 6,2 ) = 7.
B. The study of general graphs G (k = 2).
Definition 5 (The graphs G q,ε , H q,ε , and H cyclic q,ε ) For an integer q and an error parameter ε, let G q,ε be the graph whose vertex set consists of all the vectors of length q 2 over [q], that is, the vectors u ∈ [q] q 2 , where two vertices u = (u 1 , . . . , u q 2 ) and v = (v 1 , . . . , v q 2 ) are adjacent if the collection of pairs {(u i , v i )} i∈[q 2 ] is at least of size (1ε)q 2 . H q,ε and H cyclic q,ε are subgraphs of G q,ε induced on the vertices of H q and H cyclic q respectively.
The graph family G q,ε is extremal with respect to the q ε parameter in the sense given by the following lemma.
Lemma 2 For every integer q, 1) q ε (G q,ε ) ≤ q and 2) χ(G) ≤ χ(G q,ε ) for every graph G with q ε (G) = q.
As with the graphs G q , by Lemma 2, the challenge of obtaining graphs with chromatic number much larger than the q ε parameter reduces to the study of the chromatic number χ of G q,ε and its subgraphs.
Proposition 8 For any q and ε = 1 q , χ(G q,ε ) ≤ O 5 q q 2q . Proposition 9 For any q and ε = 1 q , χ(H cyclic q,ε ) ≤ q 2 .
Proposition 10 For any q and ε = 1 q , χ(H q,ε ) ≤ q! • q.
In this subsection we allow average error over both the messages and the edges in E. Here, the decoding error is computed assuming a uniform set of k messages and a uniform decoding edge in E.
Definition 6 (The q ε parameter) Let G = ([n], E) be a kuniform hypergraph on the vertex set [n] and let ε > 0. Let q ε(G) denote the smallest size q of an alphabet F for which there exist an encoding function C : where m is uniformly chosen from F k , and e is uniformly chosen from E.
Theorem 3 Let n be any integer. For any prime power p, q ε(κ n,2 ) ≤ p for ε = 1 p+1 .
For clarity, in the rest of the paper we refer to the hyperedges of a hypergraph as edges.
Authorized licensed use limited to: University at Buffalo Libraries. Downloaded on September 16,2020 at 18:24:19 UTC from IEEE Xplore. Restrictions apply.