Кіріспе
Абстрактіл қарапайым кешендегі әр түрлі өлшемді жақтардың саны туралы. Алгебралық комбинаторикада Крускал–Катона теоремасы абстрактіл қарапайым кешендердің f-векторларының толық сипаттамасын береді. Ол Эрдёс–Ко–Радо теоремасын ерекше жағдай ретінде қамтиды және бірыңғай гиперграфтар арқылы қайта формулировкалауға болады. Бұл теорема Джозеф Крускал мен Гюла О. Х. Катонаның есімімен аталады, бірақ оны бірнеше ғалымдар тәуелсіз түрде ашқан.
In algebraic combinatorics, the Kruskal–Katona theorem gives a complete characterization of the f vectors of abstract simplicial complexes. It includes as a special case the Erdős–Ko–Rado theorem and can be restated in terms of uniform hypergraphs. It is named after Joseph Kruskal and Gyula O. H. Katona, but has been independently discovered by several others.
Бірыңғай гиперграфтар үшін мәлімдеме
A - белгілі бір U ("әмбебап жиын") жиынының N түрлі i элементтен тұратын кіші жиындықтарынан құралған жиын, ал B - A жиынындағы жиындардың барлық элементтік кіші жиындықтарының жиыны. N-ді жоғарыда көрсетілгендей кеңейтіңіз. Онда B жиынының кардиналдығы төменнен былай шектеледі:
Ловасттың қарапайымдастырылған пішімі
Келесі әлсіз, бірақ пайдалы формасы мынаған байланысты: А – белгілі бір жиынның (U) i элементті кіші жиындықтарының жиыны ("әмбебап жиын") және В – А жиынындағы жиындардың барлық элементті кіші жиындықтарының жиыны. Егер онда .
In this formulation, x need not be an integer. The value of the binomial expression is .
Осы формула бойынша x-тің бүтін сан болуы міндетті емес. Биномдық өрнектің мәні: .
In this formulation, x need not be an integer. The value of the binomial expression is .
Дәлелдің құрамдас бөліктері
Әрбір оң i үшін, табиғи сандар жиыны N-нің a1 < a2 < ai барлық i элементтен тұратын жиынтықтарын лексикографиялық ретпен тізімдеңіз. Мысалы, i = 3 үшін тізім былай басталады.
Оң бүтін компоненттері бар вектор f берілген болсын, Δf – бос жиынтықты және i = 1, ..., d үшін тізімдегі N-нің алғашқы i элементтен тұратын жиынтықтарды қамтитын 2^N жиынының қуатынан тұратын жиынның ішкі жиыны болсын. Онда келесі шарттар эквивалентті:
1. f векторы – жай кешен Δ-ның f векторы.
2. Δf – жай кешен. Қиын жағдай 1 ⇒ 2.
Δf is a simplicial complex. The difficult implication is 1 ⇒ 2.
Тарих
Теорема 1963 және 1968 жылдары Джозеф Крускаль мен Гюла О. Х. Катона жариялаған есімдерімен аталады. Авторлардың мәліметінше, бұл теореманы тәуелсіз түрде , , , және де ашқан. ал ең алғашқы сілтеме, Шютценбергердің жұмысы, толық емес дәлелге ие екенін жазады.