Suppose $𝐿_1,…,𝐿_𝑘$ are lists with $n$ elements each. We use a fully independent hash function ℎ to compute a value for each element of each list. (We suppose the hash function returns a value uniformly at random from $[𝑛^c]$ for some large constant $c$. Note also that two elements $x$, and $y$ where $x = y$ has $ℎ(𝑥)=ℎ(𝑦)$). Let $𝑀_1,\ldots,𝑀_𝑘$ be sublists with the smallest $𝑋$ elements by computed hash value in each list and let $𝐶_1 = L_1$. Define more $𝐶$s by: $$ 𝐶_{𝑖+1}= \begin{cases} 𝐶_𝑖\cup𝐿_𝑖 & \text{if }|𝐶_𝑖\cap 𝑀_𝑖|<𝑋/𝑟,\\ 𝐶_𝑖 & \text{otherwise}. \end{cases} $$
What size of $𝑋$ will ensure in expectation that $c_1\left(\frac{|C_i \cap M_i|}{|M_i|}\right) \leq \frac{|𝐶_𝑖\cap𝐿_𝑖|}{|L_i|} \leq c_2\left(\frac{|C_i \cap M_i|}{|M_i|}\right)$ for some constants $c_1$ and $c_2$; I am happy if this works for any constants (e.g. $c_1 = 0.5$ and $c_2 = 2$).
I am looking to minimize the size of $X$.
