# Given a set of sets, what is the largest common intersection between them?

Given a set of sets: $$S = \{~\{1, 2, 3\}, \{2, 3, 4\}, \{1, 3, 4\}~\}$$, I would like to find the largest common subset of $$S$$. If $$S$$ does not have a subset across all elements of $$S$$, I would like to find the largest common subset across the largest subset of $$S$$.

For example:

$$S = \{~\{1, 5, 4\}, \{2, 3, 4\}, \{1, 3, 4\}~\}$$ has $$\{4\}$$ in common across all subsets.

$$T = \{~\{1, 2, 6\}, \{2, 3, 4\}, \{1, 3, 4\}~\}$$ has $$\{3, 4\}$$ in common across the subset $$\{T_1, T_2\}$$

Given sets $$A_1,\dots,A_n$$, find the largest $$k$$ such that there exist $$k$$ distinct indices $$i_1,\dots,i_k$$ that make $$A_{i_1} \cap \cdots \cap A_{i_k}$$ have a non-empty intersection.
This can be solved in $$O(nm)$$ time, where $$m$$ denotes the maximum size of any of the $$A_i$$. It suffices to find $$x$$ in $$A_1 \cup \cdots \cup A_n$$ that maximizes $$|\{i : x \in A_i\}|$$ (i.e., the number of sets $$A_1,\dots,A_n$$ that contain $$x$$). When you've found this $$x$$, you can output the corresponding set $$\{i : x \in A_i\}$$ of indices. You can output the intersection $$\cap_{i : x \in A_i} A_i$$ too if you want.
Naively, this might appear to take $$O(n^2m)$$ time. However, the algorithm can be implemented in $$O(nm)$$ time, by scanning through the elements of the sets, maintaining a hashtable with a counter for each element $$x$$ that counts the number of sets it is contained in, and incrementing the right counter as you encounter each element.
The correctness follows from the fact that if $$A_{i_1} \cap \cdots \cap A_{i_k}$$ has a non-empty intersection, there must be some $$x \in A_1 \cup \cdots \cup A_n$$ that is contained in $$A_{i_1} \cap \cdots \cap A_{i_k}$$, and thus the algorithm above will find that combination of indices.