# Subset Numbering

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?

• Why 5 and not 3? – domotorp Jul 24 '12 at 15:44
• @domotorp: Do you know how to do it for smaller $k$? – Alex Golovnev Jul 24 '12 at 17:16
• That would give a constructive proof for the million dollar question! Not so fast! :) – Tayfun Pay Jul 24 '12 at 18:34
• @Geekster: Could you please explain? – Alex Golovnev Jul 24 '12 at 19:32
• 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 Jul 24 '12 at 21:37

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.

• Thank you, very beautiful solution! But I'm not sure if we can generalize it to odd $k$. – Alex Golovnev Jul 25 '12 at 18:32

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.

• 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 Jul 25 '12 at 9:59