Спернер отбасы - Sperner family

Жылы комбинаторика, а Спернер отбасы (немесе Sperner жүйесі; құрметіне аталған Эмануэль Спернер ), немесе тәртіпсіздік, Бұл отбасы F ішкі жиындар ақырлы жиынтықтың E онда жиындардың ешқайсысы басқасын қамтымайды. Соған сәйкес, спернер отбасы - бұл античайн қосу тор үстінен қуат орнатылды туралы E. Спернер тұқымдасын кейде ан деп те атайды тәуелсіз жүйе немесе қажет емес жиынтық.

Спернер отбасыларын санайды Нөмірлер, және олардың мөлшері шектелген Спернер теоремасы және Любелл-Ямамото-Мешалкин теңсіздігі. Тілінде сипатталуы мүмкін гиперографтар олар атаған отбасылардан гөрі тәртіпсіздіктер.

Нөмірлер

Жиынтықтағы әртүрлі спернерлік отбасылардың саны n элементтері санайды Нөмірлер, олардың біріншісі

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (кезек A000372 ішінде OEIS ).

Дәл болғанымен асимптотикалық бағалау үлкен мәндерімен белгілі n, бұл сандарды тиімді есептеу үшін қолдануға болатын нақты формула бар-жоғы белгісіз.

Барлық спернерліктердің жиынтығы n элементтері ретінде ұйымдастырылуы мүмкін ақысыз тарату торы, онда екі спернер отбасының қосылуы одақтағы басқа жиынтықтың суперсеті болып табылатын жиынтықтарды алып тастау арқылы екі отбасының бірігуінен алынады.

Спернер отбасының санымен шектеледі

Спернер теоремасы

The к- элементтің ішкі жиындары n-элементтер жиынтығы Спернер тұқымдасын құрайды, олардың мөлшері қашан көбейтіледі к = n/ 2 (немесе оған жақын бүтін сан).Спернер теоремасы бұл отбасылар Спернердің ең үлкен отбасылары екенін айтады n- элементтер жиынтығы Формальды түрде теоремада әрбір спернер отбасы үшін деп айтылады S астам n- элементтер жиынтығы,

{ displaystyle | S | leq { binom {n} { lfloor n / 2 rfloor}}.}

LYM теңсіздігі

The Любелл-Ямамото-Мешалкин теңсіздігі Спернердің жанұясының мөлшерін тағы бір байланыстырады және оны Спернер теоремасын дәлелдеуге болады. а_к өлшем жиынтығының санын білдіреді к Спернер отбасында n элементтер, содан кейін

{ displaystyle sum _ {k = 0} ^ {n} { frac {a_ {k}} {n k}} leq 1. таңдаңыз

Мазасыздық

A тәртіпсіздік ешқайсысында басқалары болмайтындай шектеулі жиынтықтың ішкі жиындарының отбасы; яғни бұл Спернер отбасы. Айырмашылық әдетте қойылған сұрақтарда. Тәртіпсіздіктер комбинаторлық оңтайландыруды зерттеудің маңызды құрылымы болып табылады.

(Неғұрлым күрделі тілде, тәртіпсіздік а гиперграф ${ displaystyle (V, E)}$ қосылған қасиетімен ${ displaystyle A not subseteq B}$ қашан болса да ${ displaystyle A, B in E}$ және ${ displaystyle A neq B}$ (яғни, бірде-бір шетте басқасы болмайды. Тәртіпке қарама-қарсы ұғым - бұл абстрактілі қарапайым, мұнда жиектің әр ішкі жиыны гиперграфта болады; бұл тапсырыс тамаша ішкі жиындарының позициясында V.)

Егер ${ displaystyle H = (V, E)}$ беспорядок болса, онда блокатор туралы H, деп белгіленеді ${ displaystyle b (H)}$ , бұл шыңдар жиынтығы V және барлық минималды жиындардан тұратын жиек жиынтығы ${ displaystyle B subseteq V}$ сондай-ақ ${ displaystyle B cap A neq varnothing}$ әрқайсысы үшін ${ displaystyle A in E}$ . Мұны көрсетуге болады ${ displaystyle b (b (H)) = H}$ (Эдмондс және Фулкерсон 1970 ), сондықтан блокаторлар бізге екіліктің түрін береді. Біз анықтаймыз ${ displaystyle nu (H)}$ ішіндегі ірі жиектер жиынтығының өлшемі болуы керек H және ${ displaystyle tau (H)}$ ішіндегі ең кішкентай жиектің өлшемі болуы керек ${ displaystyle b (H)}$ . Мұны байқау қиын емес ${ displaystyle nu (H) leq tau (H)}$ .

Мысалдар

Егер G қарапайым циклсыз граф ${ displaystyle H = (V (G), E (G))}$ бұл тәртіпсіздік (егер шеттер реттелмеген шыңдар жұбы ретінде қарастырылса) және ${ displaystyle b (H)}$ бұл барлық минималды жиынтық төбелік қақпақтар. Мұнда ${ displaystyle nu (H)}$ - бұл ең үлкен сәйкестіктің өлшемі және ${ displaystyle tau (H)}$ - бұл ең кішкентай шыңның қақпағының өлшемі. Кёниг теоремасы үшін екенін айтады екі жақты графиктер, ${ displaystyle nu (H) = tau (H)}$ . Басқа графиктер үшін бұл екі шама әр түрлі болуы мүмкін.
Келіңіздер G граф болып, рұқсат етіңіз ${ displaystyle s, t in V (G)}$ . Жинақ H барлық жиектер жиынтығы с-т жолдар ретсіздік болып табылады ${ displaystyle b (H)}$ бұл бөлінетін барлық минималды жиектер жиынтығы с және т. Бұл жағдайда ${ displaystyle nu (H)}$ - шеттік-бөлшектеудің максималды саны с-т жолдар, және ${ displaystyle tau (H)}$ бұл ең кіші жиекті бөлгіштің өлшемі с және т, сондықтан Менгер теоремасы (шекті-қосылым нұсқасы) бұл туралы айтады ${ displaystyle nu (H) = tau (H)}$ .
Келіңіздер G байланысты граф болып, рұқсат етіңіз H тәртіпсіздіктер болыңыз ${ displaystyle E (G)}$ ағаштарының барлық жиектер жиынтығынан тұрады G. Содан кейін ${ displaystyle b (H)}$ бұл барлық минималды жиектер жиынтығы G.

Кәмелетке толмағандар

Бұған ұқсас шамалы қатынас бар кіші қатынас графиктер бойынша. Егер ${ displaystyle H = (V, E)}$ бұл былық және ${ displaystyle v in V}$ , содан кейін мүмкін жою v ретсіздікті алу ${ displaystyle H setminus v}$ шыңымен орнатылған ${ displaystyle V setminus {v }}$ және барлығынан тұратын жиек жиынтығы ${ displaystyle A in E}$ құрамында жоқ v. Біз келісім-шарт v ретсіздікті алу үшін ${ displaystyle H / v = b (b (H) setminus v)}$ . Бұл екі операция ауысады және егер Дж тағы бір ретсіздік, біз мұны айтамыз Дж Бұл кәмелетке толмаған туралы H егер тәртіпсіздік изоморфты болса Дж -дан алуға болады H өшіру және қысылу реті бойынша.

Әдебиеттер тізімі

Андерсон, Ян (1987), «Спернер теоремасы», Соңғы жиынтықтардың комбинаторикасы, Оксфорд университетінің баспасы, 2-4 бет.
Эдмондс, Дж.; Фулкерсон, Д.Р. (1970), «Бөтелке экстремасы», Комбинаторлық теория журналы, 8 (3): 299–306, дои:10.1016 / S0021-9800 (70) 80083-7.
Кнут, Дональд Э. (2005), «7.2.1.6 бөлімінің жобасы: барлық ағаштарды құру», Компьютерлік бағдарламалау өнері, IV, 17-19 бет.
Спернер, Эмануэль (1928), «Ein Satz über Untermengen einer endlichen Menge» (PDF), Mathematische Zeitschrift (неміс тілінде), 27 (1): 544–548, дои:10.1007 / BF01171114, JFM 54.0090.06.