Partition of $\{(i, j)\ |\ i \neq j \leq n\}$
A slightly different way of arguing for the upper bound of $\log n$ is as follows:


Observe that by mirroring across the line $x = y$, we can ignore all points in the upper triangle of the grid (at the cost of increasing the partition size by a factor of 2). 
Now consider the lower triangle. If we draw the vertical line $x = n/2$, and "reflect it" off the diagonal $x = y$, we get a square with endpoints $(n/2, 0)$ and $(n, n/2-1)$. all of these points can be placed in a single set. 
This leaves two similar  copies of the lower triangle with half its size. Any construction for these two triangles can be "paired up" since sets in these partitions don't conflict. 


This yields the recurrence 
$$ S(n) = 1 + S(n/2) $$
and hence $S(n) = \Theta(\log n)$