<p><strong>The optimal partition is of size <span class="math-container">$\Theta(logn)$</span>.</strong></p>
<hr />
<p><strong>Lower bound:</strong></p>
<p>A proof of the lower bound can be done inductively by using the claim &quot;a partition of <span class="math-container">$k$</span> numbers require <span class="math-container">$\geq log_2 k$</span> sets&quot;.</p>
<p>The base, for <span class="math-container">$k=2$</span> is trivial.
For general <span class="math-container">$k$</span>, it's enough to observe that every partition you make still leaves a set <span class="math-container">$\{&lt;i,j&gt;|i,j\in I, i\neq j\}$</span> uncovered where <span class="math-container">$I \geq \frac{k}{2}$</span>, use the induction hypothesis and you're done.</p>
<hr />
<p><strong>Upper bound:</strong></p>
<p>You can build a simple <span class="math-container">$O(logn)$</span> sized partition in the following way:</p>
<blockquote>
<p><strong>Partition</strong>(min,max)</p>
<p><span class="math-container">$setA$</span> = <span class="math-container">$\{(i,j) | i\leq min+\frac{min+max}{2}, j&gt;min+\frac{min+max}{2}\}$</span></p>
<p><span class="math-container">$setB$</span> = <span class="math-container">$\{(i,j) | i&gt; min+\frac{min+max}{2}, j\leq min+\frac{min+max}{2}\}$</span></p>
<p>return <span class="math-container">$\{setA,setB\}\cup Partition(min,min+\frac{min+max}{2}) \# Partition(min+\frac{min+max}{2},max)$</span></p>
</blockquote>
<p>( where initially you run Partition(1,<span class="math-container">$n$</span>) ).</p>
<p>The idea is greedily selecting the largest possible sets A,B and reducing the problem in size.</p>
<p>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.</p>
<p>i.e. if <span class="math-container">$n=4$</span>, then the initial sets are <span class="math-container">$setA=\{&lt;1,3&gt;,&lt;1,4&gt;,&lt;2,3&gt;,&lt;2,4&gt;\}$</span>, <span class="math-container">$setB=\{&lt;3,1&gt;,&lt;3,2&gt;,&lt;4,1&gt;,&lt;4,2&gt;\}$</span>, when you join the inner sets you get in addition the sets <span class="math-container">$\{&lt;1,2&gt;,&lt;3,4&gt;\}$</span>  and <span class="math-container">$\{&lt;2,1&gt;,&lt;4,3&gt;\}$</span> (which is the union of the inner).</p>
<p>The number of sets in the partition is given by:
<span class="math-container">$$S(n) = 2 + S(\lceil n/2\rceil) = 2\lceil log_2n\rceil = O(logn)$$</span></p>
<p>Another example, for <span class="math-container">$n=8$</span>:</p>
<ol>
<li><span class="math-container">$\{1,2,3,4\}\times \{5,6,7,8\}$</span>.</li>
<li><span class="math-container">$\{5,6,7,8\}\times \{1,2,3,4\}$</span>.</li>
<li><span class="math-container">$\{1,2\}\times \{3,4\} \cup \{5,6\}\times \{7,8\}$</span></li>
<li><span class="math-container">$\{3,4\}\times \{1,2\} \cup \{7,8\}\times \{5,6\}$</span></li>
<li><span class="math-container">$\{&lt;1,2&gt;,&lt;3,4&gt;,&lt;5,6&gt;,&lt;7,8&gt;\}$</span>.</li>
<li><span class="math-container">$\{&lt;2,1&gt;,&lt;4,3&gt;,&lt;6,5&gt;,&lt;8,7&gt;\}$</span>.</li>
</ol>

CC BY-SA 3.0
2014-04-29T13:32:03.630Z
Indeed -- but I am looking for a lower bound. Is this partition the smallest that can be achieved?
user94741
CC BY-SA 3.0
2014-04-29T13:50:40.273Z
Thank you for the update -- this dashes my hopes of a $\Omega(n)$ lower bound but is helpful information.
user94741
CC BY-SA 3.0
2014-04-29T14:18:50.350Z
@user94741 - Made a bit of mess, but I think I finally got it right. The optimal partition is of size $\Theta(logn)$.
R B
CC BY-SA 3.0
2014-04-29T13:31:02.037Z
2014-04-29T14:17:32.247Z
2020-06-17T09:38:08.363Z
R B
<p>A slightly different way of arguing for the upper bound of $\log n$ is as follows:</p>

<ol>
<li><p>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). </p></li>
<li><p>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. </p></li>
<li><p>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. </p></li>
</ol>

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

CC BY-SA 3.0
2014-04-29T18:51:41.823Z
I think this gives exactly my construction :).
R B
CC BY-SA 3.0
2014-04-29T19:01:19.250Z
Ah. that's entirely possible. I was trying to understand yours and decided that I wanted to think about it differently :)
Suresh Venkat
CC BY-SA 3.0
2014-04-29T17:57:43.710Z
2014-04-29T17:57:43.710Z
Suresh Venkat
<p>The same partition that R B and Suresh Venkat gave can be described as follows even more explicitly. Consider the binary encoding of each number from $1$ to $n$. Let $x_i$ be the $i$-th digit in the encoding of $x$ (say, $x_1$ is the least significant digit of $x$). Note that if $x\neq y$ then $x_i\neq y_i$ for some $i\in\{1,\dots,\lceil \log_2 n\rceil\}$. Below, we will consider the first digit $i$ such that $x_i\neq y_i$. For $i\in\{1,\dots,\lceil \log_2 n\rceil\}$, we define
$$P_i = \{(x,y): \text{the first binary digit where } x \text{ and } y \text{ differ is } i, \ x_i=0, y_i=1\},$$
$$Q_i = \{(x,y): \text{the first binary digit where } x \text{ and } y \text{ differ is } i, \ x_i=1, y_i=0\}.$$</p>

<p>It is clear that every pair $(x,y)$ (where $x\neq y$) belongs to some $P_i$ or $Q_i$, and that the projections of each set on the first and second coordinates are disjoint. The total number of sets is $2\lceil \log_2 n\rceil$ by construction. </p>

CC BY-SA 3.0
2014-04-30T14:11:50.573Z
2014-04-30T14:11:50.573Z
Yury
<p>Consider the set of  $n^2 - n$ pairs $\{(i, j)\ |\ i \neq j \leq n\}$. </p>

<p>Call a partition $(P_1,\ldots,P_r)$ of this set <em>valid</em> 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.</p>

<p>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.</p>

<p>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\}$.</p>

CC BY-SA 3.0
2014-04-29T17:29:50.197Z
I'm confused about something. Your example gives a valid partition of size $2$. Isn't that a lower bound ? Conversely, you can always put each point in a different set and you'd have a partition of size $n^2 - n$.
Suresh Venkat
CC BY-SA 3.0
2014-04-29T17:33:44.530Z
@SureshVenkat - I'm not following, by 2 sets he didn't cover all of the $n^2-n$ pairs but roughly half of them. i.e. the pairs in $\{(i,j)|i,j\leq n/2, j\neq i\}$ are not covered by the $n^2/4$ sized set he gave as an example.
R B
CC BY-SA 3.0
2014-04-29T17:45:40.377Z
Ah sorry. Was briefly confused. I'll delete my comment (and you can do the same :))
Suresh Venkat
<co.combinatorics>
Partition of $\{(i, j)\ |\ i \neq j \leq n\}$
user94741
# Partition of $\{(i, j)\ |\ i \neq j \leq n\}$

(Asked by: username_0 on 2014-04-29)

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\}$.

**Tags:** co.combinatorics

> **Comments:**
> **username_1**: I'm confused about something. Your example gives a valid partition of size $2$. Isn't that a lower bound ? Conversely, you can always put each point in a different set and you'd have a partition of size $n^2 - n$.  
> **username_2**: @SureshVenkat - I'm not following, by 2 sets he didn't cover all of the $n^2-n$ pairs but roughly half of them. i.e. the pairs in $\{(i,j)|i,j\leq n/2, j\neq i\}$ are not covered by the $n^2/4$ sized set he gave as an example.  
> **username_1**: Ah sorry. Was briefly confused. I'll delete my comment (and you can do the same :))  

---

## 3 answers

### Answer by username_2 on 2014-04-29. Score: 5 | Accepted answer

**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\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. $\{1,2,3,4\}\times \{5,6,7,8\}$.
2. $\{5,6,7,8\}\times \{1,2,3,4\}$.
3. $\{1,2\}\times \{3,4\} \cup \{5,6\}\times \{7,8\}$
4. $\{3,4\}\times \{1,2\} \cup \{7,8\}\times \{5,6\}$
5. $\{<1,2>,<3,4>,<5,6>,<7,8>\}$.
6. $\{<2,1>,<4,3>,<6,5>,<8,7>\}$.

> **Comments:**
> **username_0**: Indeed -- but I am looking for a lower bound. Is this partition the smallest that can be achieved?  
> **username_0**: Thank you for the update -- this dashes my hopes of a $\Omega(n)$ lower bound but is helpful information.  
> **username_2**: @username_0 - Made a bit of mess, but I think I finally got it right. The optimal partition is of size $\Theta(logn)$.  

---

### Answer by username_1 on 2014-04-29. Score: 8

A slightly different way of arguing for the upper bound of $\log n$ is as follows:

1. 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).
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.
3. 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)$

> **Comments:**
> **username_2**: I think this gives exactly my construction :).  
> **username_1**: Ah. that's entirely possible. I was trying to understand yours and decided that I wanted to think about it differently :)  

---

### Answer by username_3 on 2014-04-30. Score: 5

The same partition that username_2 and username_1 gave can be described as follows even more explicitly. Consider the binary encoding of each number from $1$ to $n$. Let $x\_i$ be the $i$-th digit in the encoding of $x$ (say, $x\_1$ is the least significant digit of $x$). Note that if $x\neq y$ then $x\_i\neq y\_i$ for some $i\in\{1,\dots,\lceil \log\_2 n\rceil\}$. Below, we will consider the first digit $i$ such that $x\_i\neq y\_i$. For $i\in\{1,\dots,\lceil \log\_2 n\rceil\}$, we define
$$P\_i = \{(x,y): \text{the first binary digit where } x \text{ and } y \text{ differ is } i, \ x\_i=0, y\_i=1\},$$
$$Q\_i = \{(x,y): \text{the first binary digit where } x \text{ and } y \text{ differ is } i, \ x\_i=1, y\_i=0\}.$$

It is clear that every pair $(x,y)$ (where $x\neq y$) belongs to some $P\_i$ or $Q\_i$, and that the projections of each set on the first and second coordinates are disjoint. The total number of sets is $2\lceil \log\_2 n\rceil$ by construction.


---

