I have a bipartite graph $G=(U,V,E)$ with the following two conditions:
- Every node $u\in U$ has a degree of at most a constant $c$, i.e., $1\leq \text{deg}(u)\leq c$;
- Every node $v\in V$ has a degree of at most $d$;
- No two nodes in $U$ are connected to the same set of nodes in $V$, i.e., for any two distinct $u_1,u_2\in U$, $\text{neighbor}(u_1)\neq\text{neighbor}(u_2)$.
Is it possible to show that the $|V|=\Theta(|U|)$? Note that here $|U|,d\rightarrow\infty$, $d=o(|U|)$, and every $u$ is connected to at least one $v\in V$. Otherwise, is there a way to derive the minimum size of $|V|$ in terms of $|U|$ and $d$?
For the case of $c=1$, it is clear that we have $|V|=|U|$, but things are not so clear to me when $c>1$. The best I could do for a general $c=\Theta(1)$ is $|V|=O(|U|/d)$: the $u$'s contribute at least 1 edge each giving us $|E|\geq|U|$. Dividing $|E|$ by $d$ gives us the bound.
In your situation, there is to every node $u \in U$ a set of nodes $S_u \subseteq V$. Your first condition implies that the cardinality of each $S_u$ is somewhere in between $1$ and $c$. A priori, this means that there are $$ \binom{n}{1} + \binom{n}{2} + \cdots + \binom{n}{c} $$ possible sets $S_u$, where $n = |V|$. When $d \to \infty$, this number can also be attained. From this we infer $|V| = \Omega(|U|^{1/c})$, and this is the best one can do.