<p>A partial answer is that for even $k$ such a labeling does not exist.</p>

<p>For a set of $t$ disjoint subsets $S_1, \ldots, S_{t}$ (of size $n/k$, let $f(S_1, \ldots, S_t)$ denote the sum of their values).</p>

<p>Claim: if $t &lt; k$ and $S_1 \cup \ldots \cup S_t \ne S'_1 \cup \ldots \cup S'_t$ then $f(S_1, \ldots, S_t) \ne f(S'_1, \ldots, S'_t)$.</p>

<p>To see why the claim is true, choose a set $S_{t+1}, \ldots, S_{k}$ such that $\bigcup_{i=1}^{k} S_i = [n]$ but then one of these new sets intersects one of the $S'_i$'s so $f(S_1, \ldots, S_k)$ is not allowed to be the same as $f(S'_1, \ldots, S'_t, S_{t+1}, \ldots, S_k)$.</p>

<p>Corollary: $T &gt; {n \choose tn/k}/t$.</p>

<p>Setting $t = k/2$ gives a lower bound of $T \ge 2{n \choose n/2}/k = \Omega(2^n/\sqrt{n})$.</p>

<p>Note that for odd $k$ one gets a lower bound of order ${n \choose n(1-1/k)/2} \approx 2^{H((1-1/k)/2)n} = 2^{n(1-O(1/k^2))}$.  Already for $k = 5$ we have $H((1-1/k)/2) = H(0.4) \approx 0.97$ so the exponent tends to $1$ pretty quickly.</p>

<p>I would guess that no solution exists for odd $k$ either but I'm not sure how to prove it.</p>

CC BY-SA 3.0
2012-07-25T18:32:51.373Z
Thank you, very beautiful solution! But I'm not sure if we can generalize it to odd $k$.
Alex Golovnev
CC BY-SA 3.0
2012-07-25T15:43:16.153Z
2012-07-25T19:25:51.700Z
2012-07-25T19:25:51.700Z
Per Austrin
<p>This is not an answer, just an explanation why for k=2 no such labeling can exist (I am sure this was already known to Alex, so this is just a write-up for other readers like myself...)</p>

<p>For k=2 we have $T\ge {n \choose n/2}\ge 1.99^n$. This is because there are ${n \choose n/2}$ subsets of size n/2. If any two get the same label, e.g. A and B, then either the sum of the label of A and its complement is not in S, or the sum of the label of B and the complement of A is in S. This implies $T\ge {n \choose n/2}$ (for large n).</p>

<p>For larger k a similar argument shows that all the labels must be different, but this only gives a weaker exponential lower bound. So already k=3 seems to be unknown.</p>

CC BY-SA 3.0
2012-07-25T09:59:07.263Z
Yes, thank you! It will be great if somebody can give any intuition why there is no such labelling for larger $k$, or why it's hard to find such a labelling.
Alex Golovnev
CC BY-SA 3.0
2012-07-25T08:23:25.920Z
2012-07-25T08:23:25.920Z
domotorp
<p>Fix $k\ge5$.
For any big enough $n$, we would like to label all subsets of $\{1..n\}$ of size exactly $n/k$ by positive integers from $\{1...T\}$.
We would like this labelling to satisfy the following property: there is a set $S$ of integers, s.t.</p>

<ol>
<li>If $k$ subsets of size $n/k$ don't intersect (i.e. the union of these sets form all the set $\{1..n\}$), then the sum of their labels is in $S$.</li>
<li>Otherwise, the sum of their labels isn't in $S$.</li>
</ol>

<p>Does there exist a $k\ge5$ and a labelling, s.t. $T\cdot|S|=O(1.99^n)$?</p>

<p>For example, for any $k$ we can label subsets in the following way.
$T=2^n$, each subset has $n$ bits in their number: first bit is equal $1$ iff the subset contains $1$, the second bit is equal $1$ iff the subset contains $2$ e.t.c.
It's easy to see, that $S$ contains only one element $2^n-1$.
But here $T\cdot|S|=\Theta(2^n)$. Can we do it better?</p>

CC BY-SA 3.0
2012-07-24T15:44:34.477Z
Why 5 and not 3?
domotorp
CC BY-SA 3.0
2012-07-24T17:16:55.047Z
@domotorp: Do you know how to do it for smaller $k$?
Alex Golovnev
CC BY-SA 3.0
2012-07-24T18:34:43.813Z
That would give a constructive proof for the million dollar question! Not so fast! :)
Tayfun Pay
CC BY-SA 3.0
2012-07-24T19:32:17.797Z
@Geekster: Could you please explain?
Alex Golovnev
CC BY-SA 3.0
2012-07-24T21:37:25.880Z
Is it possible to make T=O(1.99^n)?  The question seems to suggest that it is possible, but it is unclear to me how to do that.
Tsuyoshi Ito
CC BY-SA 3.0
2012-07-25T16:42:10.317Z
@TsuyoshiIto, thank you, I understood that I don't know how to do it even for T=O(1.99^n).
Alex Golovnev
<ds.algorithms><graph-algorithms><it.information-theory><nt.number-theory><exp-time-algorithms>
Subset Numbering
Alex Golovnev
# Subset Numbering

(Asked by: username_0 on 2012-07-24)

Fix $k\ge5$.
For any big enough $n$, we would like to label all subsets of $\{1..n\}$ of size exactly $n/k$ by positive integers from $\{1...T\}$.
We would like this labelling to satisfy the following property: there is a set $S$ of integers, s.t.

1. If $k$ subsets of size $n/k$ don't intersect (i.e. the union of these sets form all the set $\{1..n\}$), then the sum of their labels is in $S$.
2. Otherwise, the sum of their labels isn't in $S$.

Does there exist a $k\ge5$ and a labelling, s.t. $T\cdot|S|=O(1.99^n)$?

For example, for any $k$ we can label subsets in the following way.
$T=2^n$, each subset has $n$ bits in their number: first bit is equal $1$ iff the subset contains $1$, the second bit is equal $1$ iff the subset contains $2$ e.t.c.
It's easy to see, that $S$ contains only one element $2^n-1$.
But here $T\cdot|S|=\Theta(2^n)$. Can we do it better?

**Tags:** ds.algorithms, graph-algorithms, it.information-theory, nt.number-theory, exp-time-algorithms
> **Comments:**
> **username_1**: Why 5 and not 3?  
> **username_0**: @domotorp: Do you know how to do it for smaller $k$?  
> **username_2**: That would give a constructive proof for the million dollar question! Not so fast! :)  
> **username_0**: @Geekster: Could you please explain?  
> **username_3**: Is it possible to make T=O(1.99^n)?  The question seems to suggest that it is possible, but it is unclear to me how to do that.  
> **username_0**: @TsuyoshiIto, thank you, I understood that I don't know how to do it even for T=O(1.99^n).  

---

## 2 answers

### Answer by username_4 on 2012-07-25. Score: 7

A partial answer is that for even $k$ such a labeling does not exist.

For a set of $t$ disjoint subsets $S\_1, \ldots, S\_{t}$ (of size $n/k$, let $f(S\_1, \ldots, S\_t)$ denote the sum of their values).

Claim: if $t < k$ and $S\_1 \cup \ldots \cup S\_t \ne S'\_1 \cup \ldots \cup S'\_t$ then $f(S\_1, \ldots, S\_t) \ne f(S'\_1, \ldots, S'\_t)$.

To see why the claim is true, choose a set $S\_{t+1}, \ldots, S\_{k}$ such that $\bigcup\_{i=1}^{k} S\_i = [n]$ but then one of these new sets intersects one of the $S'\_i$'s so $f(S\_1, \ldots, S\_k)$ is not allowed to be the same as $f(S'\_1, \ldots, S'\_t, S\_{t+1}, \ldots, S\_k)$.

Corollary: $T > {n \choose tn/k}/t$.

Setting $t = k/2$ gives a lower bound of $T \ge 2{n \choose n/2}/k = \Omega(2^n/\sqrt{n})$.

Note that for odd $k$ one gets a lower bound of order ${n \choose n(1-1/k)/2} \approx 2^{H((1-1/k)/2)n} = 2^{n(1-O(1/k^2))}$. Already for $k = 5$ we have $H((1-1/k)/2) = H(0.4) \approx 0.97$ so the exponent tends to $1$ pretty quickly.

I would guess that no solution exists for odd $k$ either but I'm not sure how to prove it.

> **Comments:**
> **username_0**: Thank you, very beautiful solution! But I'm not sure if we can generalize it to odd $k$.  

---

### Answer by username_1 on 2012-07-25. Score: 4

This is not an answer, just an explanation why for k=2 no such labeling can exist (I am sure this was already known to Alex, so this is just a write-up for other readers like myself...)

For k=2 we have $T\ge {n \choose n/2}\ge 1.99^n$. This is because there are ${n \choose n/2}$ subsets of size n/2. If any two get the same label, e.g. A and B, then either the sum of the label of A and its complement is not in S, or the sum of the label of B and the complement of A is in S. This implies $T\ge {n \choose n/2}$ (for large n).

For larger k a similar argument shows that all the labels must be different, but this only gives a weaker exponential lower bound. So already k=3 seems to be unknown.

> **Comments:**
> **username_0**: Yes, thank you! It will be great if somebody can give any intuition why there is no such labelling for larger $k$, or why it's hard to find such a labelling.  

---

