I am working through the following paper "Data Structures for Storing Small Sets in the Bitprobe Model" by Radhakrishnan et al. and am confused regarding one of their arguments about a lower bound.
In particular, they are trying to show that $s_A(2, m, 2) \in \Omega(m^{4/7})$. That is, the goal is to store a set $S$ of $2$ elements from a universe $U$ of size $m$ such that a query of the form "is $x \in S$" can be answered using only $2$ bit probes. The $s_A(2, m, 2)$ indicates the minimum number of bits required to answer such queries, and in particular, the scheme is allowed to be adaptive (the second probe can depend on the first one).
They begin by saying that such a scheme can be defined by three functions $a, b, c\colon [m] \to [s]$, where the query "is $x \in S$" is answered by first probing location $a(x)$ then probing locations $b(x)$ or $c(x)$ depending on the outcome of the first probe. They then go on to explain that this can be viewed as a bipartite multigraph where $G = (B = [s], C = [s], E = \{\langle b(x), c(x)\rangle : x \in [m]\})$. Lastly, they state that $E$ is naturally partitioned into sets $E_1, E_2, \ldots E_s$, where $$E_i = \{\langle b(x), c(x)\rangle : x \in [m], a(x) = i \}$$.
Now, my questions are as follows. First they make the assumption that "Each $E_i$ is a matching $\ldots$ Details Omitted". Why can this assumption be made? I can't for the life of me figure out why this needs to be the case.
My second (and more important question) is this. They provide the following example:
They state that edges with the same type of label (i.e $x$ and $x'$) belong to the same matching. In their caption, they state that if such a scheme were to exist, then there are some pairs that cannot be stored (such as $x$ and $y$ on the left). This is what I don't understand. They do not provide an explanation beyond the "If it were to exist in our graph, then the underlying scheme cannot store all sets of size two. In particular, it is easy to verify that if this configuration exists, there is no way to store the set $\{x, y\}$".
I am just getting myself familiar in this area, so some of the "obvious" things may not be so obvious to me right away.