“Kruskal–Katona theorem”的意思、由来-开放百科全书

词条

Kruskal–Katona theorem

释义

Statement
Statement for simplicial complexes Statement for uniform hypergraphs Lovász' simplified formulation
Ingredients of the proof
History
See also
References
External links

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.

Statement

Given two positive integers N and i, there is a unique way to expand N as a sum of binomial coefficients as follows:

This expansion can be constructed by applying the greedy algorithm: set n_i to be the maximal n such that replace N with the difference, i with i − 1, and repeat until the difference becomes zero. Define

Statement for simplicial complexes

An integral vector is the f-vector of some -dimensional simplicial complex if and only if

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 -element subsets of the sets in A. Expand N as above. Then the cardinality of B is bounded below as follows:

Lovász' simplified formulation

The following weaker but useful form is due to {{harvs|first=László|last=Lovász|authorlink=László Lovász|year=1993|txt}} Let A be a set of i-element subsets of a fixed set U ("the universe") and B be the set of all -element subsets of the sets in A. If then .

In this formulation, x need not be an integer. The value of the binomial expression is .

Ingredients of the proof

For every positive i, list all i-element subsets a₁ < a₂ < … a_i of the set N of natural numbers in the colexicographical order. For example, for i = 3, the list begins

Given a vector with positive integer components, let Δ_f be the subset of the power set 2^N consisting of the empty set together with the first 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.

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 {{harvtxt|Le|Römer|2019}}, it was discovered independently by {{harvtxt|Kruskal|1963}}, {{harvtxt|Katona|1968}}, {{harvs|first=Marcel-Paul|last=Schützenberger|authorlink=Marcel-Paul Schützenberger|year=1959|txt}}, {{harvtxt|Harper|1966}}, and {{harvtxt|Clements|Lindström|1969}}.

{{harvs|first=Donald|last=Knuth|authorlink=Donald Knuth|year=2011|txt}} writes that the earliest of these references, by Schützenberger, has an incomplete proof.

References

{{citation

| last1 = Clements | first1 = G. F.
| last2 = Lindström | first2 = B.
| doi = 10.1016/S0021-9800(69)80016-5
| journal = Journal of Combinatorial Theory
| mr = 0246781
| pages = 230–238
| title = A generalization of a combinatorial theorem of Macaulay
| volume = 7
| year = 1969}}. Reprinted in {{citation
| editor1-last = Gessel | editor1-first = Ira | editor1-link = Ira Gessel
| editor2-last = Rota | editor2-first = Gian-Carlo | editor2-link = Gian-Carlo Rota
| doi = 10.1007/978-0-8176-4842-8
| isbn = 0-8176-3364-2
| location = Boston, Massachusetts
| mr = 904286
| pages = 416–424
| publisher = Birkhäuser Boston, Inc.
| title = Classic Papers in Combinatorics
| year = 1987}}

{{citation

| last = Harper | first = L. H.
| doi = 10.1016/S0021-9800(66)80059-5
| journal = Journal of Combinatorial Theory
| mr = 0200192
| pages = 385–393
| title = Optimal numberings and isoperimetric problems on graphs
| volume = 1
| year = 1966}}

{{citation

| last = Katona | first = Gyula O. H. | author-link = Gyula O. H. Katona
| contribution = A theorem of finite sets
| editor1-last = Erdős | editor1-first = Paul | editor1-link = Paul Erdős
| editor2-last = Katona | editor2-first = Gyula O. H. | editor2-link = Gyula O. H. Katona
| publisher = Akadémiai Kiadó and Academic Press
| title = Theory of Graphs
| year = 1968}}. Reprinted in {{harvtxt|Gessel|Rota|1987|pages=381–401}}.

{{citation|last=Knuth|first=Donald|date=2011| author-link = Donald Knuth

| title =The Art of Computer Programming, volume 4A: Combinatorial algorithms, part 1|section=7.2.1.3|page=373}}.

{{citation

| last = Kruskal | first = Joseph B. | author-link = Joseph Kruskal
| contribution = The number of simplices in a complex
| editor-last = Bellman | editor-first = Richard E. | editor-link = Richard E. Bellman
| publisher = University of California Press
| title = Mathematical Optimization Techniques
| year = 1963}}.

{{citation|last=Lovász|first=László|date=1993|title=Combinatorial problems and exercises|location=Amsterdam|publisher=North-Holland}}.
{{citation|title=A Kruskal–Katona type result and applications|first1=Dinh Van|last1=Le|first2=Tim|last2=Römer|year=2019|arxiv=1903.02998}}
{{citation

| last = Stanley | first = Richard | author-link = Richard P. Stanley
| edition = 2nd
| isbn = 0-8176-3836-9
| location = Boston, MA
| publisher = Birkhäuser Boston, Inc.
| series = Progress in Mathematics
| title = Combinatorics and commutative algebra
| volume = 41
| year = 1996}}.

{{citation|last=Schützenberger|first=M.P.|date=1959|title=A Characteristic Property of Certain Polynomials of E. F. Moore and C. E. Shannon|url=https://dspace.mit.edu/handle/1721.1/53341#files-area|journal=RLE Quarterly Progress Report|volume=55|issue=Processing and Transmission of Information|pages=117-118|doi= |access-date=19 March 2019}}.

External links

Kruskal-Katona theorem on the polymath1 wiki

4 : Algebraic combinatorics|Hypergraphs|Set families|Theorems in combinatorics

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。