Wymiar VC kulek w 3 wymiarach

9

Szukam wymiaru VC następującego zestawu układów.

Wszechświat U={p1,p2,,pm} takie, że UR3. W ustawionym systemieR każdy zestaw SR odpowiada kuli w R3 tak, że zestaw S zawiera element w U tylko wtedy, gdy zawiera odpowiednią kulę R3.

Szczegóły, które już znam.

  1. Wymiar VC jest co najmniej 4. Jest tak, ponieważ if p1,p2,p3,p4 są 4 rogi czworościanu, po czym można je rozbić R

  2. Wymiar VC to atmost 5. Dzieje się tak, ponieważ można ustawić system zestawu R4 z kulkami w R3 odpowiadające hiperpłaszczyznom w R4. Wiadomo, że hiperplany wRd mieć wymiar VC d+1.

Ashwinkumar BV
źródło

Odpowiedzi:

8

Oto prosty argument:

Załóżmy, że istnieje zestaw Uz 5 punktów, które mogą zostać rozbite przez kule. Tak dla każdego zestawuSU, istnieje piłka B św BU=S i piłka B św BU=US. W związku z tym,BB nie zawiera punktów U. GdybyBB=, B i Bmożna oddzielić samolotem. W przeciwnym razie przecięcie powierzchniB i Bjest kołem. Płaszczyzna, w której leży koło, oddziela sięS od US. W związku z tym,U może zostać rozbita przez półprzestrzenie, sprzeczność.

Ten sam argument w wyższym wymiarze pokazuje, że wymiar VC kulek jest równy wymiarowi VC półprzestrzeni.

Sasho Nikolov
źródło
Tak. Uświadomiłem sobie to rozwiązanie, ale za późno;).
Sariel Har-Peled
8

Moje rozwiązanie jest nieprawidłowe. Zobacz inną odpowiedź ...

Sariel Har-Peled
źródło
Nie, podaję to jako przykład w rozmowie. Zamiast wspominać o <= 5, pomyślałem, że lepiej zanotować dokładną liczbę. W każdym razie dzięki.
Ashwinkumar BV
Zakładałem, że nie jest to problem związany z pracą domową ...
Sariel Har-Peled,
@ Sariel: Znalazłem łatwy dowód. Czy powinienem napisać, czy chcesz się zastanowić?
Sasho Nikolov
1
Prześlij jako inną odpowiedź, a następnie usunę moje ...
Sariel Har-Peled,