# Kruskal–Katona theorem

Kruskal–Katona theorem 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.

Contents 1 Statement 1.1 Statement for simplicial complexes 1.2 Statement for uniform hypergraphs 1.3 Lovász' simplified formulation 2 Ingredients of the proof 3 History 4 See also 5 References 6 External links Statement Given two positive integers N and i, there is a unique way to expand N as a sum of binomial coefficients as follows: {displaystyle 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 jgeq 1.} This expansion can be constructed by applying the greedy algorithm: set ni to be the maximal n such that {displaystyle Ngeq {binom {n}{i}},} replace N with the difference, i with i − 1, and repeat until the difference becomes zero. Define {displaystyle N^{(i-1)}={binom {n_{i}}{i-1}}+{binom {n_{i-1}}{i-2}}+ldots +{binom {n_{j}}{j-1}}.} Statement for simplicial complexes An integral vector {displaystyle (f_{0},f_{1},...,f_{d-1})} is the f-vector of some {displaystyle (d-1)} -dimensional simplicial complex if and only if {displaystyle 0leq f_{i}^{(i-1)}leq f_{i-1},quad 1leq ileq d-1.} Statement for uniform hypergraphs Let A be a set consisting of N distinct i-element subsets of a fixed set U ("the universe") and B be the set of all {displaystyle (i-r)} -element subsets of the sets in A. Expand N as above. Then the cardinality of B is bounded below as follows: {displaystyle |B|geq {binom {n_{i}}{i-r}}+{binom {n_{i-1}}{i-r-1}}+ldots +{binom {n_{j}}{j-r}}.} Lovász' simplified formulation The following weaker but useful form is due to László Lovász (1993) Let A be a set of i-element subsets of a fixed set U ("the universe") and B be the set of all {displaystyle (i-r)} -element subsets of the sets in A. If {displaystyle |A|={binom {x}{i}}} then {displaystyle |B|geq {binom {x}{i-r}}} .

In this formulation, x need not be an integer. The value of the binomial expression is {displaystyle {binom {x}{i}}={frac {x(x-1)dots (x-i+1)}{i!}}} .

Ingredients of the proof For every positive i, list all i-element subsets a1 < a2 < … ai of the set N of natural numbers in the colexicographical order. For example, for i = 3, the list begins {displaystyle 123,124,134,234,125,135,235,145,245,345,ldots .} Given a vector {displaystyle f=(f_{0},f_{1},...,f_{d-1})} with positive integer components, let Δf be the subset of the power set 2N consisting of the empty set together with the first {displaystyle f_{i-1}} i-element subsets of N in the list for i = 1, …, d. Then the following conditions are equivalent: Vector f is the f-vector of a simplicial complex Δ. Δf is a simplicial complex. {displaystyle f_{i}^{(i-1)}leq f_{i-1},quad 1leq ileq d-1.} The difficult implication is 1 ⇒ 2. History The theorem is named after Joseph Kruskal and Gyula O. H. Katona, who published it in 1963 and 1968 respectively. According to Le & Römer (2019), it was discovered independently by Kruskal (1963), Katona (1968), Marcel-Paul Schützenberger (1959), Harper (1966), and Clements & Lindström (1969). Donald Knuth (2011) writes that the earliest of these references, by Schützenberger, has an incomplete proof. See also Sperner's theorem References Clements, G. F.; 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 0246781. Reprinted in Gessel, Ira; Rota, Gian-Carlo, eds. (1987), Classic Papers in Combinatorics, Boston, Massachusetts: Birkhäuser Boston, Inc., pp. 416–424, doi:10.1007/978-0-8176-4842-8, ISBN 0-8176-3364-2, MR 0904286 Harper, L. H. (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 O. H. (1968), "A theorem of finite sets", in Erdős, Paul; Katona, Gyula O. H. (eds.), Theory of Graphs, Akadémiai Kiadó and Academic Press. Reprinted in Gessel & Rota (1987, pp. 381–401). Knuth, Donald (2011), "7.2.1.3", The Art of Computer Programming, volume 4A: Combinatorial algorithms, part 1, p. 373. Kruskal, Joseph B. (1963), "The number of simplices in a complex", in Bellman, Richard E. (ed.), Mathematical Optimization Techniques, University of California Press. Lovász, László (1993), Combinatorial problems and exercises, Amsterdam: North-Holland. Le, Dinh Van; Römer, Tim (2019), A Kruskal–Katona type result and applications, 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, M.P. (1959), "A Characteristic Property of Certain Polynomials of E. F. Moore and C. E. Shannon", RLE Quarterly Progress Report, 55 (Processing and Transmission of Information): 117–118, retrieved 19 March 2019. External links Kruskal-Katona theorem on the polymath1 wiki Categories: Algebraic combinatoricsHypergraphsSet familiesTheorems in combinatorics

Si quieres conocer otros artículos parecidos a Kruskal–Katona theorem puedes visitar la categoría Algebraic combinatorics.

Subir

Utilizamos cookies propias y de terceros para mejorar la experiencia de usuario Más información