Given $n$ points numbered $1, 2, \cdots, n$, provide some edges, such that for each partition of the $n$ points, we can choose some edges from the provided ones, so that any two points in $1, 2, \cdots, n$ are connected iff they are in the same set. It's fine if you use some more points, and we don't care what they're connected to.
E.g. Let $n=3$, and we can provide $(1,4), (2,4), (3,4)$. If any two, taking example 1 and 2, are in a same set, while the other is not, choose $(1,4)$ and $(2,4)$. Choose nothing if the three are separated, or all if they're in same set. Of course, $(1,2), (2,3), (3,1)$ is also valid.
As I know, when $n=5$, we can provide only 9 edges, $(1,6), (2,6), (3,6), (4,6), (5,6), (2,7), (3,7), (4,7), (5,7)$, one less than connecting every pair of points.
Now for large $n$, how many edges at least should be provided? I know it can be done in $\mathcal O(n \log^2 n)$, but not whether it's best result, neither what the constant is.