Suppose we have two sets $A = \{a_1, a_2, \ldots, a_n\}$ and $B = \{b_1, b_2, \ldots, b_m\}$, together with some binary relations between them $R \subseteq A \times B$. We want to have two embedding functions $f: A \to \mathbb{R}^d$ and $g: B \to \mathbb{R}^d$, such that for each $b \in B$, $f(a)^\top g(b) > f(a')^\top g(b)$, for each pair of $(a, a')$ with $(a, b) \in R$ and $(a', b) \notin R$. We call such embedding functions good functions (w.r.t $d$, $A$ and $B$).
The intuition is that two elements having a binary relation should have more similar embeddings than two not having such a relation. We want to know how to estimate the minimum necessary dimension $d$.
Problem Given two sets $A$ and $B$, what is the minimum $d = d(A, B)$ such that good embedding functions exist w.r.t $d$, $A$, and $B$?
We can easily see that such embedding functions always exist when $d \geq n$, and we can utilize techniques in row-rank approximation.