Sperner theorems for unrelated copies of posets and generating distributive lattices

Gábor Czédli

Ural mathematical journal, Tome 10 (2024) no. 1, pp. 44-60

Résumé

For a finite poset (partially ordered set) $U$ and a natural number $n$, let $S(U,n)$ denote the largest number of pairwise unrelated copies of $U$ in the powerset lattice (AKA subset lattice) of an $n$-element set. If $U$ is the singleton poset, then $S(U,n)$ was determined by E. Sperner in 1928; this result is well known in extremal combinatorics. Later, exactly or asymptotically, Sperner's theorem was extended to other posets by A. P. Dove, J. R. Griggs, G. O. H. Katona, D. J. Stahl, and W. T. Jr. Trotter. We determine $S(U,n)$ for all finite posets with 0 and 1, and we give reasonable estimates for the "$V$-shaped" $3$-element poset and, mainly, for the $4$-element poset with $0$ and three maximal elements. For a lattice $L$, let $G_{\min} (L)$ denote the minimum size of generating sets of $L$. We prove that if $U$ is the poset of the join-irreducible elements of a finite distributive lattice $D$, then the function $k \mapsto G_{\min} (D^k)$ is the left adjoint of the function $n \mapsto S(U,n)$. This allows us to determine $G_{\min} (D^k)$ in many cases. E.g., for a 5-element distributive lattice $D$, $G_{\min}(D^{2023})=18$ if $D$ is a chain and $G_{\min}(D^{2023})=15$ otherwise. The present paper, another recent paper, and a 2021 one indicate that large direct powers of small distributive lattices could be of interest in cryptography.

Détail

Keywords: Sperner theorem for partially ordered sets, Antichain of posets, Unrelated copies of a poset, Incomparable copies of a poset, Distributive lattice, Smallest generating set, Minimum-sized Generating set, Cryptography with lattices

Bibliographie

[1] Czédli G., “Four-generated direct powers of partition lattices and authentication”, Publ. Math. Debrecen, 99 (2021), 447–472 | DOI | MR | Zbl

[2] Czédli G., “Generating some large filters of quasiorder lattices”, Acta Sci. Math. (Szeged), 2024 | DOI

[3] Czédli G., Generating Boolean lattices by few elements and exchanging session keys, 2023 14 p., arXiv: [math.RA] 2303.10790v3

[4] Czédli G., “Generating the powers of a Boolean lattice with an extra 0”, Algebra and Model Theory 14: Proc. Internat. Conf., Novosibirsk—Erlagol, Novosibirsk State Technical University, Novosibirsk, 2023, 25–40

[5] Czédli G., “Minimum-sized generating sets of the direct powers of free distributive lattices”, Cubo, 26:2 (2024), 217–237 | DOI

[6] Dove A. P., Griggs J. R., “Packing posets in the Boolean lattice”, Order, 32 (2015), 429–438 | DOI | MR | Zbl

[7] Gelfand I. M., Ponomarev V. A., “Problems of linear algebra and classification of quadruples of subspaces in a finite dimensional vector space”, Hilbert Space Operators and Operator Algebras: Proc. Internat. Conf., Tihany, 1970, v. 5, Colloq. Math. Soc. János Bolyai, North-Holland Publishing, Amsterdam–London, 1972, 163–237 | MR

[8] Grätzer G., Lattice Theory: Foundation, Birkhäuser, Basel, 2011, XXX+614 pp. | DOI | MR | Zbl

[9] Griggs J. R., Stahl J., Trotter W. T. Jr., “A Sperner theorem on unrelated chains of subsets”, J. Combinatorial Theory Ser. A, 36:1 (1984), 124–127 | DOI | MR | Zbl

[10] Katona G. O. H., Nagy D. T., “Incomparable copies of a poset in the Boolean lattice”, Order, 32 (2015), 419–427 | DOI | MR | Zbl

[11] Lubell D., “A short proof of Sperner's lemma.”, J. Combinatorial Theory, 1:2 (1966), 299 | DOI | MR | Zbl

[12] McKenzie. R. N., McNulty G. F., Taylor W. F., Algebras, Lattices, Varieties. I., Wadsworth $\$ Brooks/Cole, Monterey, California, 1987, XII+361 pp. | DOI | MR | Zbl

[13] Sperner E., “Ein Satz über Untermengen einer endlichen Menge”, Math. Z., 27 (1928), 544–548 (in German) | DOI | MR

[14] Zádori L., “Subspace lattices of finite vector spaces are 5-generated”, Acta Sci. Math. (Szeged), 74:3 (2008), 493–499 | MR | Zbl