Let it be two independent sets $A=\{a_1,a_2,…,a_n\}$ and $B=\{b_1,b_2,…,b_n\}$ such that (i) $a_i\neq b_i$, (ii) if $a_i=a_j$ then $b_i\neq b_j$, and (iii) if $b_i= b_j$ then $a_i\neq a_j$. I am trying to find the minimum number of distinct elements between both sets $\min(\mid A\mid+\mid B\mid)$.
My first guess was that the restriction implies $\min(\mid A\mid+\mid B\mid)=n+1$; for instance, if $a_1=a_2=\dots =a_n$, then $b_1\neq b_2\neq \dots \neq b_n$, yielding this result. However, empirical results seem to point to $\min(\mid A\mid+\mid B\mid)<n+1$ in some cases. For instance, if we consider the elements of set $A$ as all distinct pairwise sums from a set of certain positive integers, and the elements of set $B$ as all distinct pairwise products from that same set of certain positive integers, the sum product problem literature points to $\min(\mid A\mid+\mid B\mid)<n+1$ in many cases. I would like to understand how the restrictions described allows that empirical result, if possible with an example.
Thanks in advance!
Best Answer
Roughly, $\min(|A|+|B|)=2\sqrt n$.
Given two lists $A$ and $B$ satisfying your constraints, it must be true that $$ |A|\cdot |B|\ge n $$ because the given restrictions imply that the ordered pairs $$ (a_1,b_1),(a_2,b_2),\dots,(a_n,b_n) $$ are all distinct. Indeed, if $(a_i,b_i)=(a_j,b_j)$, that would contradict the condition $a_i=a_j\implies b_i\neq b_j$. Since there are at most $|A|\cdot |B|$ distinct ordered pairs, the size of the above list is at most $|A|\cdot |B|$.
The fact that $|A|\cdot |B|\ge n$ readily implies that $|A|+|B|\ge 2\sqrt n$: $$ |A|+|B|\ge |A|+\frac{n}{|A|}=2\sqrt n+\left(\sqrt{A}-\sqrt{n\over |A|}\right)^2\ge 2\sqrt n $$ To see that this bound is achievable, given $n$, let $m=\lceil \sqrt n\rceil$, and define $$ a_i=\lfloor i/m\rfloor ,\\ b_i= i\;\text{ rem }\;m $$ for each $i\in \{1,\dots,n\}$. Here, $i\;\text{ rem }\;m$ means the remainder when $i$ is divided by $m$, and is the unique element of $\{0,1,\dots,m-1\}$ which is congruent to $i$ modulo $m$. (This is the
%operator in many programming languages).Since the ordered pairs $(a_i,b_i)$ are all distinct (which is a consequence of how integer division works), this satisfies your constraints. Furthermore, there are only $n/m\le m$ distinct values for $A$ and $m$ distinct values for $B$, so $|A|+|B|\le 2m\approx 2\sqrt n$.