Find 2 sets with an empty intersection I have the following problem. The problem can be formulated in three different ways

Given sets $B_{-n},\ldots,B_n \subset \{1,\ldots,m\}$. 

Find $i,j \in \{-n,\ldots,n\}$ with $|i| \neq |j|$ and $i,j \neq 0$ that satisfy $B_i \cap B_j = \emptyset$ 

"Invert" the sets $B_i$

Define $A_k=\{i: k\in B_i \}$. $A_1, \ldots, A_m \subset \{-n,\ldots,n\}$. 

Find $i,j \in \{-n,\ldots,n\}$ with $|i| \neq |j|$ and $i,j \neq 0$ that satisfy the property $\{i,j\} \not\subset A_k$ for all $k=1,\ldots,m$

Relation instead of set of sets

Define relation $R\subset\{1,\ldots,m\}\times\{-n,\ldots,n\}$ with $kRi \equiv k \in B_i$.

Find $i,j \in \{-n,\ldots,n\}$ with $|i| \neq |j|$ and $i,j \neq 0$ that satisfy the property for no $k=1,\ldots,m: kRi \land kRj$

Naive Algorithm

As far as I can tell, the 3 problems are the same thing viewed from slightly different perspectives. One possible algorithm would be to iterate through all pairs $(i,j)$ and check if the condition is satisfied. This algorithm has runtime of $\mathcal{O}(n^2\cdot f(m,n))$ with the runtime $f$ of the check if the pair satisfies the property. 

Specifically for the first case: 
Assuming the sets are implemented sorted lists the intersection can be checked to be empty in $\mathcal{O}(m)$ time via a simple mergesort-like scan.

Question

Is there an algorithm for this problem that solves it in $\mathcal{o}(n^2)$ time? (maybe with some tradeoff in the $m$ component)
Here is one example for an algorithm, which can run at $O(4^m \cdot m+ n\cdot m)$ time, which is $o(n^2)$ if $m\ll c\log n$ for every $c&lt;0.5$.

We convert a subset $B_i$ into an ordinal number $1\leq j\leq 2^m$, a number of $m$-bits, in $O(m)$ time, where the $k^{\text{th}}$ bit of $j$ euqals one iff $k\in B_i$. Now, for every ordinal number $j$ we save a link list $L_j$ which contains pointers to all subsets $B_i$ that are associated with ordinal number $j$. This can be done in $O(n\cdot m)$ time.

Second, since all subsets with the same ordinal number are containing the same elements, using $O(m)$ time we can determine for every ordinal numbers $j_1,j_2$ if the corresponding subsets of $L_{j_1},L_{j_2}$ have a common element (i.e., there exists $1\leq k\leq m$ s.t., the $k^{\text{th}}$ bit  of both $j_1$ and $j_2$ is one) or not. In case the corresponding subsets have empty intersection, and in case that $L_{j_1}$ and $L_{j_2}$ are non empty, and it is NOT the case where $L_{j_1},L_{j_2}$ containing a single subset, pointing respectively to to $B_{n}$ and $B_{-n}$, then we can find $B_{i}$ and $B_{j}$ satisfying the above condition in $O(1)$.

In the worst case, we run over all ordinal numbers $1\leq j_1,j_2\leq m$ in $O((2^m)^2)=O(4^m)$ time, and checking an empty intersection takes $O(m)$ time. Since the first step takes $O(n\cdot m)$ time, the complexity of the algorithm is  $O(4^m \cdot m+ n\cdot m)$.