A Meshalkin theorem for projective geometries. (English) Zbl 1018.05100

Beck, Matthias; Zaslavsky, Thomas

J. Comb. Theory, Ser. A 102, No. 2, 433-441 (2003).

A projective geometry \(\mathbb{P}^{n-1}(q)\) of order \(q\) and rank \(n\) (i.e. dimension \(n-1\)) is viewed as a lattice of flats in which \(\widehat 0=\emptyset\) and \(\widehat 1\) is the set of all points. A Meshalkin sequence of length \(p\) in \(\mathbb{P}^{n-1}(q)\) is a sequence \(a=(a_1,a_2,\dots,a_p)\) of flats whose join is \(\widehat 1\), and whose ranks sum to \(n\). The authors prove upper bounds on the cardinality of a family, \({\mathcal M}\), of Meshalkin sequences, and (from the authors’ abstract) “corresponding LYM inequalities, assuming that (i) all joins are the whole geometry, and, for each \(k<p\), the set of all \(a_k\)’s of sequences in \({\mathcal M}\) contains no chain of length \(\ell\), and that (ii) the joins are arbitrary, and the chain condition holds for all \(k\). These results are \(q\)-analogs of generalizations of L. D. Meshalkin’s [Theor. Probab. Appl. 8, 203-204 (1963); translation from Teor. Veroyatn. Primen. 8, 219-220 (1963; Zbl 0123.36303)] and P. Erdős’s [Bull. Am. Math. Soc. 51, 898-902 (1945; Zbl 0063.01270)] generalizations of Sperner’s theorem and their LYM companions [M. Hochberg and W. M. Hirsch, Ann. N.Y. Acad. Sci. 175, 224-237 (1970; Zbl 0231.05007)], and they generalize G.-C. Rota and L. H. Harper’s \(q\)-analog [Matching theory, an introduction, Advances Probab. related Topics 1, 169-215 (1971; Zbl 0234.05001)] of Erdős’s generalization”.

Reviewer: William G.Brown (Montréal)

MSC:

05D05	Extremal set theory
06A07	Combinatorics of partially ordered sets
51E20	Combinatorial structures in finite projective spaces
11B65	Binomial coefficients; factorials; \(q\)-identities

Keywords:

Sperner’s theorem; Meshalkin’s theorem; LYM inequality; antichain; \(r\)-family; \(r\)-chain free

Citations:

Zbl 0123.36303; Zbl 0063.01270; Zbl 0231.05007; Zbl 0234.05001

References:

[1]	Anderson, I., Combinatorics of Finite Sets (1987), Clarendon Press: Clarendon Press Oxford, (Corr. repr., Dover, Mineola, NY, 2002) · Zbl 0604.05001
[2]	M. Beck, Xueqin Wang, T. Zaslavsky, A unifying generalization of Sperner’s theorem, submitted.; M. Beck, Xueqin Wang, T. Zaslavsky, A unifying generalization of Sperner’s theorem, submitted. · Zbl 1094.05055
[3]	Beck, M.; Zaslavsky, T., A shorter, simpler, stronger proof of the Meshalkin-Hochberg-Hirsch bounds on componentwise antichains, J. Combin. Theory Ser. A, 100, 196-199 (2002) · Zbl 1028.05111
[4]	Bollobás, B., On generalized graphs, Acta Math. Acad. Sci. Hung., 16, 447-452 (1965) · Zbl 0138.19404
[5]	K. Engel, Sperner Theory, Encyclopedia of Mathematics and Its Applications, Vol. 65, Cambridge University Press, Cambridge, 1997.; K. Engel, Sperner Theory, Encyclopedia of Mathematics and Its Applications, Vol. 65, Cambridge University Press, Cambridge, 1997. · Zbl 0868.05001
[6]	Erdős, P., On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc., 51, 898-902 (1945) · Zbl 0063.01270
[7]	Hochberg, M.; Hirsch, W. M., Sperner families, s-systems, and a theorem of Meshalkin, Ann. New York Acad. Sci., 175, 224-237 (1970) · Zbl 0231.05007
[8]	Klain, D. A.; Rota, G.-C., Introduction to Geometric Probability (1997), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0896.60004
[9]	Lubell, D., A short proof of Sperner’s theorem, J. Combin. Theory, 1, 209-214 (1966) · Zbl 0151.01503
[10]	Meshalkin, L. D., Generalization of Sperner’s theorem on the number of subsets of a finite set, Teor. Verojatnost. Primenen, 8, 219-220 (1963), (in Russian) (English trans., Theor. Probab. Appl. 8 (1963) 203-204) · Zbl 0123.36303
[11]	G.-C. Rota, L.H. Harper, Matching theory, an introduction, in: P. Ney (Ed.), Advances in Probability and Related Topics, Vol. 1, Marcel Dekker, New York, 1971, pp. 169-215.; G.-C. Rota, L.H. Harper, Matching theory, an introduction, in: P. Ney (Ed.), Advances in Probability and Related Topics, Vol. 1, Marcel Dekker, New York, 1971, pp. 169-215. · Zbl 0234.05001
[12]	Sperner, E., Ein Satz über Untermengen einer endlichen Menge, Math. Z., 27, 544-548 (1928) · JFM 54.0090.06
[13]	Yamamoto, K., Logarithmic order of free distributive lattices, J. Math. Soc. Japan, 6, 343-353 (1954) · Zbl 0056.26301