A Kruskal-Katona theorem for cubical complexes

TR Number
Date
1996-06-06
Journal Title
Journal ISSN
Volume Title
Publisher
Virginia Tech
Abstract

The optimal number of faces in cubical complexes which lie in cubes refers to the maximum number of faces that can be constructed from a certain number of faces of lower dimension, or the minimum number of faces necessary to construct a certain number of faces of higher dimension. If m is the number of faces of r in a cubical complex, and if s > r(s < r), then the maximum(minimum) number of faces of dimension s that the complex can have is

m(s/r) +. (m-m(r/r))(s/r), in terms of upper and lower semipowers. The corresponding formula for simplicial complexes, proved independently by J. B. Kruskal and G. A. Katona, is m(s/r). A proof of the formula for cubical complexes is given in this paper, of which a flawed version appears in a paper by Bernt Lindstrijm. The n-tuples which satisfy the optimaiity conditions for cubical complexes which lie in cubes correspond bijectively with f-vectors of cubical complexes.

Description
Keywords
cubical, simplicial, comples, Lindstrom, Kruskal
Citation
Collections