\(G\) -MDS lower bound graph family \(G_{x,y}\)  from [1]}: 
For any \(k\)  that is a power of 2 and for each pair of bit vectors \(x, y \in \lbrace 0, 1\rbrace ^{k^2}\) , there is a graph, denoted \(G_{x, y}\) , in this family.
See fig:Bachrach-MDS-lb-graph for an illustration of \(G_{x,y}\) .
This lower bound graph has four sets of row vertices \(A_{1}, B_{1}, A_{2}, B_{2}\)  each of which contain \(k\)  vertices.
Moreover there are two sets of bit gadgets, each set containing \(\log _{2} k\)  bit gadgets, one set for \(A_{1}, B_{1}\)  and the other set for \(A_{2}, B_{2}\) .
The \(i^{th}\)  bit gadget for \(A_{1}, B_{1}\)  is a 6-cycle with vertices \(f_{A_{1}}^{i}, t_{A_{1}}^{i}, u_{A_{1}}^{i}, f_{B_{1}}^{i}, t_{B_{1}}^{i}, u_{B_{1}}^{i}\) .
The vertices in \(a_{1}^{i} \in A_{1}\)  are connected to the bit gadget vertices \(f_{A_{1}}^j, t_{A_{1}}^j\)  depending on the binary representation of \(i-1\) .
Specifically, \(a_1^i\)  is connected to the complement of the binary representation of \(i-1\) .
For example, the vertex \(a_{1}^{1}\)  is connected to all the \(t_{A_{1}}\)  vertices. The connections for other row vertices are similar.
All of these edges are fixed, i.e., independent of \(x\)  and \(y\) . Additionally, \(x\)  determines edges between \(A_1\)  and \(A_2\) , whereas \(y\)  determines edges between
\(B_1\)  and \(B_2\) . Specifically, index the \(k^2\)  bits in \(x\)  as \(x_{i, j}\) , \(1 \le i, j \le k\) . Connect vertex \(i \in A_1\)  and vertex \(j \in A_2\)  iff \(x_{i,j} = 1\) .
The edges between \(B_1\)  and \(B_2\)  are similarly determined by the bit vector \(y\) .
One can check that \(G_{x, y}\)  has \(4k + 12\log _2 k\)  vertices, \(4k\cdot \log _2 k\)  fixed edges, and \(O(k^2)\)  variable edges (i.e., edges determined
by \(x\)  and \(y\) ).
