Numeracja podzbiorów

Napraw . Dla każdego wystarczająco dużego chcielibyśmy oznaczyć wszystkie podzbiory wielkości dokładnie dodatnimi liczbami całkowitymi z . Chcielibyśmy, aby to etykietowanie spełniało następującą właściwość: istnieje zestaw liczb całkowitych , uln { 1 .. n } n / k { 1 ... T } $k\ge5$$n$$\{1..n\}$$n/k$$\{1...T\}$$S$

1. Jeśli podzbiory rozmiaru nie przecinają (czyli suma tych zbiorów tworzą cały zbiór ), to suma ich etykietach jest w .n / k { 1 .. n } $k$$n/k$$\{1..n\}$$S$
2. W przeciwnym wypadku, suma ich etykietach nie jest w .$S$

Czy istnieje i oznakowanie, st ?T ⋅ | S | = O ( 1,99 n$k\ge5$$T\cdot|S|=O(1.99^n)$

Na przykład dla dowolnego możemy oznaczyć podzbiory w następujący sposób. , każdy podzbiór ma bitów w swojej liczbie: pierwszy bit jest równy jeśli podzbiór zawiera , drugi bit jest równy jeśli podzbiór zawiera itd. Łatwo zauważyć, że zawiera tylko jeden element . Ale tutaj . Czy możemy to zrobić lepiej?T = 2 n n 1 1 1 2 S 2 n - 1 T ⋅ | S | = Θ ( 2 n$k$$T=2^n$$n$$1$$1$$1$$2$$S$$2^n-1$$T\cdot|S|=\Theta(2^n)$

Częściowa odpowiedź brzmi, że nawet takie oznakowanie nie istnieje.$k$

Dla zestawu rozłącznych podzbiorów S 1 , … , S t (o rozmiarze n / k , niech f ( S 1 , … , S t ) oznacza sumę ich wartości).$t$$S_1, \ldots, S_{t}$$n/k$$f(S_1, \ldots, S_t)$

Twierdzenie: jeśli i S 1 ∪ ... ∪ S T ≠ S ' 1 ∪ ... ∪ S " T , a następnie 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)$

Zrozumieć, dlaczego żądanie wprawdzie wybrać zestaw tak, że ⋃ k i = 1 S I = [ n ] , ale następnie jedną na jedno z tych nowych zestawów przecina się z S " i jest tak F. ( S 1 , ... , S K ) nie mogą być takie same jak f ( S ' 1 , ... , 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)$

Następstwo: .$T > {n \choose tn/k}/t$

Ustawienie daje dolną granicę T ≥ 2 ($t = k/2$.$T \ge 2{n \choose n/2}/k = \Omega(2^n/\sqrt{n})$

Zauważ, że dla nieparzystego dostaje się dolną granicę rzędu ($k$. Już dlak=5mamyH((1-1/k)/2)=${n \choose n(1-1/k)/2} \approx 2^{H((1-1/k)/2)n} = 2^{n(1-O(1/k^2))}$$k = 5$ więc wykładnikdość szybkodąży do 1 .$H((1-1/k)/2) = H(0.4) \approx 0.97$$1$

Domyślam się, że nie istnieje również rozwiązanie dla nieparzystego , ale nie jestem pewien, jak to udowodnić.$k$

To nie jest odpowiedź, tylko wyjaśnienie, dlaczego dla k = 2 nie może istnieć takie oznakowanie (jestem pewien, że było to już znane Alexowi, więc jest to tylko napis dla innych czytelników takich jak ja ...)

Dla k = 2 mamy . Jest tak, ponieważ istnieją($T\ge {n \choose n/2}\ge 1.99^n$podzbiory wielkości n / 2. Jeśli jakieś dwa otrzymają tę samą etykietę, np. A i B, wówczas albo suma znacznika A i jego dopełniacza nie jest w S, albo suma znacznika B i dopełniacza A jest w S. To implikujeT≥(${n \choose n/2}$(dla dużych n).$T\ge {n \choose n/2}$

Dla większego ka podobny argument pokazuje, że wszystkie etykiety muszą być różne, ale daje to tylko słabszą wykładniczą dolną granicę. Więc już k = 3 wydaje się być nieznane.