Ural Mathematical Journal
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Ural Math. J.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Ural Mathematical Journal, 2024, Volume 10, Issue 1, Pages 44–60
DOI: https://doi.org/10.15826/umj.2024.1.004
(Mi umj219)
 

Sperner theorems for unrelated copies of posets and generating distributive lattices

Gábor Czédli

University of Szeged
References:
Abstract: 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.
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
Funding agency Grant number
Development and Innovation Fund of Hungary K 138892
This research was supported by the National Research, Development and Innovation Fund of Hungary, under funding scheme K 138892.
Bibliographic databases:
Document Type: Article
Language: English
Citation: Gábor Czédli, “Sperner theorems for unrelated copies of posets and generating distributive lattices”, Ural Math. J., 10:1 (2024), 44–60
Citation in format AMSBIB
\Bibitem{Cze24}
\by G\'abor~Cz\'edli
\paper Sperner theorems for unrelated copies of posets and generating distributive lattices
\jour Ural Math. J.
\yr 2024
\vol 10
\issue 1
\pages 44--60
\mathnet{http://mi.mathnet.ru/umj219}
\crossref{https://doi.org/10.15826/umj.2024.1.004}
\elib{https://elibrary.ru/item.asp?id=68586403}
\edn{https://elibrary.ru/EVFPQW}
Linking options:
  • https://www.mathnet.ru/eng/umj219
  • https://www.mathnet.ru/eng/umj/v10/i1/p44
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Ural Mathematical Journal
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024