10
$\begingroup$

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?

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

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.

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Alex Golovnev Jul 25 '12 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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