6
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$ Commented Apr 29, 2014 at 17:29
  • 1
    $\begingroup$ @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. $\endgroup$
    – R B
    Commented Apr 29, 2014 at 17:33
  • $\begingroup$ Ah sorry. Was briefly confused. I'll delete my comment (and you can do the same :)) $\endgroup$ Commented Apr 29, 2014 at 17:45

3 Answers 3

5
$\begingroup$

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. $\{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>\}$.
$\endgroup$
3
  • 1
    $\begingroup$ Indeed -- but I am looking for a lower bound. Is this partition the smallest that can be achieved? $\endgroup$
    – user94741
    Commented Apr 29, 2014 at 13:32
  • $\begingroup$ Thank you for the update -- this dashes my hopes of a $\Omega(n)$ lower bound but is helpful information. $\endgroup$
    – user94741
    Commented Apr 29, 2014 at 13:50
  • $\begingroup$ @user94741 - Made a bit of mess, but I think I finally got it right. The optimal partition is of size $\Theta(logn)$. $\endgroup$
    – R B
    Commented Apr 29, 2014 at 14:18
8
$\begingroup$

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)$

$\endgroup$
2
  • $\begingroup$ I think this gives exactly my construction :). $\endgroup$
    – R B
    Commented Apr 29, 2014 at 18:51
  • $\begingroup$ Ah. that's entirely possible. I was trying to understand yours and decided that I wanted to think about it differently :) $\endgroup$ Commented Apr 29, 2014 at 19:01
5
$\begingroup$

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.