Partition of $\{(i, j)\ |\ i \neq j \leq n\}$ Consider the set of  $n^2 - n$ pairs $\{(i, j)\ |\ i \neq j \leq n\}$. 

Call a partition $(P_1,\ldots,P_r)$ of this set valid if for each $P_t$, the sets $\{i\ |\ \exists k: (i,k) \in P_t\}$ and $\{j\ |\ \exists k: (k,j) \in P_t\}$ are disjoint.

I would like a lower bound on the size (i.e. number of sets) of any valid partition. This feels like a natural problem but I was unable to find a reference.

Note that there are valid partitions containing sets of size $n^2/4$, e.g. those containing $\{(i, j)\ |\ i \leq n/2 \mbox{ and } j &gt; n/2\}$.
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)$