1
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ I don't understand what you are asking. Do you want to solve the problem which is stated at the beginning (how to find a formula for the minimum...) or do you simply want to prove that $\min |A|+|B| \le n$? For $n=9$ I built a very simple example which has nothing to deal with sums or whatever: $$A=(x,x,x,y,y,y,z,z,z)$$ $$B=(x,y,z,x,y,z,x,y,z)$$ here $|A|+|B|=6$ $\endgroup$
    – Crostul
    Commented Mar 2, 2022 at 12:07
  • $\begingroup$ Thanks for your comment @Crostul; it has pointed out that I forgot to add the restriction $a_i\neq b_i$, which I had in mind but not wrote. Also, I edit the question to make it more concrete $\endgroup$ Commented Mar 2, 2022 at 15:25
  • 1
    $\begingroup$ @JuanMoreno The restriction $a_i\neq b_i$ does not matter at all, since you can just replace everything in $B$ with a new symbol different from anything in $A$. To make the example in the previous comment work with your new restriction, just do $$A=(x,x,x,y,y,y,z,z,z)\\\\B = (p,q,r,p,q,r,p,q,r)$$ $\endgroup$ Commented Mar 2, 2022 at 16:13

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$
1
  • 1
    $\begingroup$ Good answer to a poorly written question. I am not sure what the question is asking to. +1 $\endgroup$
    – Crostul
    Commented Mar 2, 2022 at 19:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .