Subset-Nummerierung

10

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, stk5n{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 .kn/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 ) ?k5T|S|=O(1.99n)

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?kT=2nn1112S2n1T|S|=Θ(2n)

Alex Golovnev
quelle
3
Warum 5 und nicht 3?
Domotorp
@domotorp: Weißt du, wie es für kleinere ? k
Alex Golovnev
Das wäre ein konstruktiver Beweis für die Millionen-Dollar-Frage! Nicht so schnell! :)
Tayfun Pay
@ Geekster: Könnten Sie bitte erklären?
Alex Golovnev
3
Ist es möglich, T = O (1,99 ^ n) zu machen? Die Frage scheint darauf hinzudeuten, dass dies möglich ist, aber mir ist unklar, wie das geht.
Tsuyoshi Ito

Antworten:

7

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).tS1,,Stn/kf(S1,,St)

Behauptung: Wenn und S 1S tS 1S t, dann ist f ( S 1 , , S t ) f ( S 1 , , S t ) .t<kS1StS1Stf(S1,,St)f(S1,,St)

St+1,,Ski=1kSi=[n]Sif(S1,,Sk)f(S1,,St,St+1,,Sk)

T>(ntn/k)/t

Das Setzen von ergibt eine Untergrenze von .t=k/2T2(nn/2)/k=Ω(2n/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 .kk=5H((1-1/k)/2)=H(0,4)(nn(11/k)/2)2H((11/k)/2)n=2n(1O(1/k2))k=51H((11/k)/2)=H(0.4)0.971

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

Per Austrin
quelle
k
4

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(nn/2)1.99n(nn/2)T(nn/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.

domotorp
quelle
k