×

Another generalization of Lindström’s theorem on subcubes of a cube. (English) Zbl 1011.06002

A Kruskal-Katona-type theorem for posets of the form \(P(N; A_1, \ldots, A_m) = \{ A \subseteq N: \bigwedge_i A_i \not\subseteq A\}\). If \(x \in P = P(N; A_1, \ldots, A_m)\), let \(\Delta (x)\) be the shadow of \(x\), i.e., those subsets of \(x\) of \(|x|- 1\) elements. Given a suitable linear ordering \(\prec\) of \(P\), and given \(X \subseteq P\), let \(C(X)\) be a compression of \(X\), formed by pushing the elements of \(X\) to \(\prec\)-minimal sets of the same cardinality. Then for any appropriate \(i\) and \(F \subseteq \{x \in P: |x|= i\}\), \(\Delta(C(F)) \subseteq C(\Delta(F))\).

MSC:

06A07 Combinatorics of partially ordered sets
05D05 Extremal set theory
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Bezrukov, S. L., Shadow minimization in the partial mappings semilattice (in Russian), Diskret. Analiz, 46, 3-16 (1988) · Zbl 0746.05003
[2] Bezrukov, S. L., Isoperimetric problems in discrete spaces, (Frankl, P.; Füredi, Z.; Katona, G.; Miklós, D., Extremal Problems for Finite Sets, 3 (1994), Bolyai Society Mathematical Studies), 59-91 · Zbl 0818.05061
[3] Bezrukov, S. L.; Elsässer, R., The spider poset is Macaulay, J. Combin. Theory Ser. A, 90, 1-26 (2000) · Zbl 0951.06006
[4] Engel, K., Sperner Theory (1997), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0868.05001
[5] Frankl, P.; Füredi, Z.; Kalai, G., Shadows of colored complexes, Math. Scand., 63, 169-178 (1988) · Zbl 0651.05003
[6] L. H. Harper, and, J. D. Chavez, Discrete Isoperimetric Problems and Pathmophisms, forthcoming monograph.; L. H. Harper, and, J. D. Chavez, Discrete Isoperimetric Problems and Pathmophisms, forthcoming monograph.
[7] Katona, G. O.H., A theorem of finite sets, (Erdős, P.; Katona, G., Theory of Graphs (1968), Akadémiai Kiadó and Academic Press: Akadémiai Kiadó and Academic Press Budapest and New York), 187-207 · Zbl 0878.05079
[8] Kruskal, J. B., The number of simplices in a complex, (Bellman, R., Mathematical Optimization Techniques (1963), Univ. of California Press: Univ. of California Press Berkeley), 251-278
[9] Leck, U., Extremalprobleme für den Schatten in Posets (in German) (1995), Freie Univ. BerlinShaker-Verlag: Freie Univ. BerlinShaker-Verlag Aachen
[10] Leck, U., Optimal shadows and ideals in submatrix orders, Discrete Math., 235, 173-187 (2001) · Zbl 0986.06002
[11] Leeb, K., Salami-Taktik beim Quader-Packen (in German), Arbeitsber. Inst. Math. Masch. Datenverarb. (Inform.), 11, 1-15 (1978)
[12] Lindström, B., The optimal number of faces in cubical complexes, Ark. Mat., 8, 245-257 (1971) · Zbl 0221.05021
[13] Moghadam, H. S., Compression operators and a solution to the bandwidth problem of the product of \(n\) paths (1983), Univ. of California at Riverside
[14] Sali, A., Extremal theorems for submatrices of a matrix, Combinatorics, 52 (1987), Eger: Eger Hungary, p. 439-446
[15] Vasta, J. C., The maximum rank ideal problem on the orthogonal product of simplices (1998), Univ. of California at Riverside
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.