Twierdzenie Spernera – twierdzenie kombinatoryczne w ekstremalnej teorii zbiorów, określające maksymalną liczność rodziny zbiorów, w której żaden zbiór nie jest podzbiorem innego. Twierdzenie to zostało sformułowane przez niemieckiego matematyka Emanuela Spernera w 1928 roku.
Twierdzenie Rodzinę zbiorów skończonych, w której żaden zbiór nie jest zawarty w innym nazywa się rodziną Spernera. Rodzina Spernera stanowi antyłańcuch w uporządkowanym przez zawieranie zbiorze potęgowym pewnego skończonego zbioru Przykładem rodziny Spernera jest rodzina wszystkich -elementowych podzbiorów zbioru dla pewnego której liczność wynosi .
Zgodnie z twierdzeniem Spernera jeśli jest rodziną Spernera podzbiorów zbioru -elementowego toRównoważnie rodzina jest antyłańcuchem w o maksymalnej liczbie elementów.
Dowód Niech będzie rodziną Spernera podzbiorów zbioru -elementowego i niech Wówczas nierówność Lubella-Yamamoto-Meshalkina daje
Ponieważ współczynniki dwumianowe spełniają nierówność
zachodzi
co jest równoważne tezie lematu.
Uogólnienia
Wszystkie antyłańcuchy o maksymalnej mocy W 1979 roku Lovász wskazał wszystkie rodziny Spernera podzbiorów zbioru -elementowego o maksymalnej liczności. Dla parzystych taka rodzina jest unikalna i jest nią Z kolei dla nieparzystych są dwie takie rodziny – oraz .
Uogólnienie Bollobása (1965) Niech podzbiory oraz zbioru -elementowego spełniają warunek wtedy i tylko wtedy, gdy Wówczas liczby oraz spełniają nierówność
Twierdzenie Spernera otrzymamy, przyjmując .
Uogólnienie Erdősa (1945) Niech będzie rodziną podzbiorów zbioru -elementowego Jeśli nie istnieją różne zbiory dla których to moc rodziny jest nie większa od sumy największych współczynników dwumianowych . Twierdzenie Spernera stanowi tu przypadek
Zobacz też
nierówność Lubella-Yamamoto-Meshalkina twierdzenie Dilwortha twierdzenie Erdősa-Ko-Rado
Przypisy
Spernera Kategoria:Rodziny zbiorów Kategoria:Nierówności