Subset-Nummerierung

Fix . Für jedes ausreichend große n möchten wir alle Teilmengen von { 1 .. n } der Größe genau n / k durch positive ganze Zahlen von { 1 ... T } kennzeichnen . Wir möchten, dass diese Kennzeichnung die folgende Eigenschaft erfüllt: Es gibt eine Menge S von ganzen Zahlen, st$k\ge5$$n$$\{1..n\}$$n/k$$\{1...T\}$$S$

1. Wenn Teilmengen der Größe n / k nicht schneiden (dh die Vereinigung dieser Sätze bilden alle die Menge { 1 .. n } ), dann ist die Summe ihrer Etiketten ist in S .$k$$n/k$$\{1..n\}$$S$
2. Ansonsten ist die Summe ihrer Etiketten nicht in .$S$

Gibt es ein und eine Kennzeichnung, st T ⋅ | S | = O ( 1,99 n ) ?$k\ge5$$T\cdot|S|=O(1.99^n)$

Zum Beispiel können wir für jedes Teilmengen wie folgt beschriften. T = 2 n , jede Teilmenge hat n Bits in ihrer Anzahl: Das erste Bit ist gleich 1, wenn die Teilmenge 1 enthält , das zweite Bit ist gleich 1, wenn die Teilmenge 2 usw. enthält. Es ist leicht zu erkennen, dass S nur ein Element 2 n enthält - 1 . Aber hier T ⋅ | S | = Θ ( 2 n ) . Können wir es besser machen?$k$$T=2^n$$n$$1$$1$$1$$2$$S$$2^n-1$$T\cdot|S|=\Theta(2^n)$

Eine teilweise Antwort ist, dass selbst für solche Kennzeichnung nicht existiert.$k$

Für eine Menge von disjunkten Teilmengen S 1 , … , S t (mit der Größe n / k sei f ( S 1 , … , S t ) die Summe ihrer Werte).$t$$S_1, \ldots, S_{t}$$n/k$$f(S_1, \ldots, S_t)$

Behauptung: Wenn und S 1 ∪ … ∪ S t ≠ S ′ 1 ∪ … ∪ S ′ t, dann ist f ( S 1 , … , S t ) ≠ f ( S ′ 1 , … , S ′ t ) .$t < k$$S_1 \cup \ldots \cup S_t \ne S'_1 \cup \ldots \cup S'_t$$f(S_1, \ldots, S_t) \ne f(S'_1, \ldots, S'_t)$

$S_{t+1}, \ldots, S_{k}$$\bigcup_{i=1}^{k} S_i = [n]$$S'_i$$f(S_1, \ldots, S_k)$$f(S'_1, \ldots, S'_t, S_{t+1}, \ldots, S_k)$

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

Das Setzen von ergibt eine Untergrenze von .$t = k/2$$T \ge 2{n \choose n/2}/k = \Omega(2^n/\sqrt{n})$

Man beachte, dass man für ungerades eine Untergrenze der Ordnung erhält . Bereits für wir so dass der Exponent ziemlich schnell zu tendiert .$k$k=5H((1-1/k)/2)=H(0,4)${n \choose n(1-1/k)/2} \approx 2^{H((1-1/k)/2)n} = 2^{n(1-O(1/k^2))}$$k = 5$$H((1-1/k)/2) = H(0.4) \approx 0.97$$1$

Ich würde vermuten, dass es auch für ungerade keine Lösung gibt, aber ich bin mir nicht sicher, wie ich das beweisen soll.$k$

Dies ist keine Antwort, sondern nur eine Erklärung, warum für k = 2 keine solche Kennzeichnung existieren kann (ich bin sicher, dass dies Alex bereits bekannt war, daher ist dies nur eine Zusammenfassung für andere Leser wie mich ...)

$T\ge {n \choose n/2}\ge 1.99^n$${n \choose n/2}$$T\ge {n \choose n/2}$

Für größere ka zeigt ein ähnliches Argument, dass alle Bezeichnungen unterschiedlich sein müssen, dies ergibt jedoch nur eine schwächere exponentielle Untergrenze. Also scheint schon k = 3 unbekannt zu sein.