The \(G\) -MVC lower bound graph family \(G_{x,y}\)  from [1]}:  See fig:censor-hillel-mvc-lb-graph for an illustration of \(G_{x,y}\) . At a high level, the lower bound graph of [1]} has four cliques \(A_1, A_2, B_1, B_2\)  of size \(k\)  which are called the row vertices and \(2 \log _2 k\)  4-cycles which are called bit-gadgets. There are \(\log _{2} k\)  4-cycles for the row vertices \(A_{1}, B_{1}\)  and the other \(\log _{2} k\)  4-cycles are for the row vertices \(A_{2}, B_{2}\) 
The \(i^{th}\)  bit gadget for \(A_{1}, B_{1}\)  is a 4-cycle with vertices \(t_{A_{1}}^{i}, f_{A_{1}}^{i}, t_{B_{1}}^{i}, f_{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 \(t_{A_{1}}^{j}\)  if the \(j^{th}\)  bit of the binary representation of \(i-1\)  is 1 and it is connected to \(f_{A_{1}}^{j}\)  otherwise.
For example, the vertex \(a_{1}^{1}\)  is connected to all the \(f_{A_{1}}\)  vertices. The connections for other row vertices in \(A_{2}, B_{1}, B_{2}\)  to the corresponding bit gadget vertices are similar.
