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 > n/2\}$.
Partition of $\{(i, j)\ |\ i \neq j \leq n\}$
co.combinatorics
The optimal partition is of size $\Theta(logn)$.Lower bound:A proof of the lower bound can be done inductively by using the claim a partition of $k$ numbers require $\geq log_2 k$ sets.The base, for $k=2$ is trivial.For general $k$, it's enough to observe that every partition you make still leaves a set $\{<i,j>|i,j\in I, i\neq j\}$ uncovered where $I \geq \frac{k}{2}$, use the induction hypothesis and you're done.Upper bound:You can build a simple $O(logn)$ sized partition in the following way:Partition(min,max)$setA$ = $\{(i,j) | i\leq min+\frac{min+max}{2}, j>min+\frac{min+max}{2}\}$$setB$ = $\{(i,j) | i> min+\frac{min+max}{2}, j\leq min+\frac{min+max}{2}\}$return $\{setA,setB\}\cup Partition(min,min+\frac{min+max}{2}) \# Partition(min+\frac{min+max}{2},max)$( where initially you run Partition(1,$n$) ).The idea is greedily selecting the largest possible sets A,B and reducing the problem in size.When you recursively approach the smaller fragments of the set, you can join these together (two sets per each recursion level - join all the setA's together and all of the setB's), as their elements are disjoint.i.e. if $n=4$, then the initial sets are $setA=\{<1,3>,<1,4>,<2,3>,<2,4>\}$, $setB=\{<3,1>,<3,2>,<4,1>,<4,2>\}$, when you join the inner sets you get in addition the sets $\{<1,2>,<3,4>\}$  and $\{<2,1>,<4,3>\}$ (which is the union of the inner).The number of sets in the partition is given by:$$S(n) = 2 + S(\lceil n/2\rceil) = 2\lceil log_2n\rceil = O(logn)$$Another example, for $n=8$:$\{1,2,3,4\}\times \{5,6,7,8\}$.$\{5,6,7,8\}\times \{1,2,3,4\}$.$\{1,2\}\times \{3,4\} \cup \{5,6\}\times \{7,8\}$$\{3,4\}\times \{1,2\} \cup \{7,8\}\times \{5,6\}$$\{<1,2>,<3,4>,<5,6>,<7,8>\}$.$\{<2,1>,<4,3>,<6,5>,<8,7>\}$.