Kruskal–Katonas teorem

Inom algebraisk kombinatorik ger Kruskal –Katona-satsen en fullständig karaktärisering av f -vektorerna för abstrakta enkla komplex . Det inkluderar som ett specialfall Erdős–Ko–Rado-satsen och kan omformuleras i form av enhetliga hypergrafer . Den är uppkallad efter Joseph Kruskal och Gyula OH Katona , men har självständigt upptäckts av flera andra.

Påstående

Givet två positiva heltal N och i finns det ett unikt sätt att expandera N som summan av binomialkoefficienter enligt följande:

N={\ binom {n_{i}}{i}}+{\binom {n_{i-1}}{i-1}}+\ldots +{\binom {n_{j}}{j}},\quad n_ {i}>n_{i-1}>\ldots >n_{j}\geq j\geq 1.

Denna expansion kan konstrueras genom att tillämpa den giriga algoritmen : ställ n _i till maximal n så att $N\geq {\binom {n}{i}},$ ersätt N med skillnad, i med i − 1, och upprepa tills skillnaden blir noll. Definiera

N^{(i-1)}={\binom {n_{i}}{i-1}}+{\binom {n_{i-1}}{i-2}}+\ldots + {\binom {n_{j}}{j-1}}.

Uttalande för enkla komplex

En integralvektor $(f_{0},f_{1},...,f_{d-1})$ är f -vektorn för något $(d-1)$ -dimensionellt förenklat komplex om och endast om

0\leq f_{i}^{(i)}\leq f_{i-1},\quad 1\leq i\leq d-1.

Utlåtande för enhetliga hypergrafer

Låt A vara en mängd som består av N distinkta i -elementdelmängder av en fixerad mängd U ("universum") och B vara mängden av alla $(ir)$ -elementundermängder av mängderna i A . Expandera N enligt ovan. Då är kardinaliteten av B avgränsad nedan enligt följande:

|B|\geq {\binom {n_{i}}{ir}}+{\binom {n_{i-1}}{ir-1}}+\ldots +{\binom {n_{j }}{jr}}.

Lovász förenklade formulering

Följande svagare men användbara form beror på László Lovász ( 1993 ) Låt A vara en uppsättning av i -elementdelmängder av en fast mängd U ("universum") och B vara mängden av alla $(ir)$ -elementdelmängder av mängderna i A . Om $|A|={\binom {x}{i}}$ sedan $|B|\geq {\binom {x}{ir}}$ .

I denna formulering behöver x inte vara ett heltal. Värdet på binomialuttrycket är ${\binom {x}{i}}={\frac {x(x-1)\dots (x-i+1)}{i!}}$ .

Bevisets ingredienser

För varje positivt i , lista alla i -elementdelmängder a ₁ < a ₂ < … a _i av mängden N av naturliga tal i den kolexikografiska ordningen . Till exempel, för i = 3, börjar listan

123,124,134,234,125,135,235,145,245,345,\ldots .

Givet en vektor $f=(f_{0},f_{1},...,f_{d-1})$ med positiv heltalskomponenter, låt Δ _f vara delmängden av effektmängden 2 ^N bestående av den tomma mängden tillsammans med den första $f_{i-1}$ i -elementdelmängder av N i listan för i = 1, …, d . Då är följande villkor likvärdiga:

Vektor f är f -vektorn för ett förenklat komplex Δ .
Δ _f är ett enkelt komplex.
$f_{i}^{(i)}\leq f_{i-1},\quad 1\leq i\leq d -1.$

Den svåra innebörden är 1 ⇒ 2.

Historia

Teoremet är uppkallat efter Joseph Kruskal och Gyula OH Katona , som publicerade det 1963 respektive 1968. Enligt Le & Römer (2019) upptäcktes den oberoende av Kruskal (1963) , Katona (1968) , Marcel-Paul Schützenberger ( 1959 ), Harper (1966) och Clements & Lindström (1969) . Donald Knuth ( 2011 ) skriver att den tidigaste av dessa referenser, av Schützenberger, har ett ofullständigt bevis.

Se även

Sperners teorem

Clements, GF; Lindström, B. (1969), "A generalization of a combinatorial theorem of Macaulay", Journal of Combinatorial Theory , 7 : 230–238, doi : 10.1016/S0021-9800(69)80016-5 , MR 024678 . Återtryckt i Gessel, Ira ; Rota, Gian-Carlo , red. (1987), Classic Papers in Combinatorics , Boston, Massachusetts: Birkhäuser Boston, Inc., s. 416–424, doi : 10.1007/978-0-8176-4842-8 , ISBN 0-8176-3364-2 , MR 2609
Harper, LH (1966), "Optimal numberings and isoperimetric problems on graphs", Journal of Combinatorial Theory , 1 : 385–393, doi : 10.1016/S0021-9800(66)80059-5 , MR 0200192
Katona, Gyula OH (1968), "A theorem of finite sets", i Erdős, Paul ; Katona, Gyula OH (red.), Theory of Graphs , Akadémiai Kiadó och Academic Press . Omtryckt i Gessel & Rota (1987 , s. 381–401).
Knuth, Donald (2011), "7.2.1.3", The Art of Computer Programming, volym 4A: Combinatorial algorithms, del 1, sid. 373 .
Kruskal, Joseph B. (1963), "The number of simplices in a complex", i Bellman, Richard E. (red.), Mathematical Optimization Techniques , University of California Press .
Lovász, László (1993), Kombinatoriska problem och övningar , Amsterdam: North-Holland .
Le, Dinh Van; Römer, Tim (2019), Resultat och tillämpningar av typen Kruskal–Katona , arXiv : 1903.02998
Stanley, Richard (1996), Combinatorics and commutative algebra , Progress in Mathematics, vol. 41 (2nd ed.), Boston, MA: Birkhäuser Boston, Inc., ISBN 0-8176-3836-9 .
Schützenberger, MP (1959), "A Characteristic Property of Certain Polynomials of EF Moore and CE Shannon" , RLE Quarterly Progress Report , 55 (Bearbetning och överföring av information): 117–118 , hämtad 19 mars 2019 .

externa länkar

Kruskal-Katonas teorem på polymath1-wikin