Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 14486))
Included in the following conference series:
275Accesses
Abstract
This paper dates back to the asymptotic solutions of Rota’s problem on the size of maximum antichain in the set partition lattice by Canfield and Harper and others. The knowledge of asymptotic coefficients could pave the way to the asymptotic solutions of such problems as (maximal) antichain counting in partition lattices. In addition to our attempt to reduce uncertainty in the values of these coefficients, we provide some inequalities for the discrepancy between the number of antichains and maximal antichains in partition lattices and give alternative proof for the number of maximal antichains obtained by us recently and recorded in the Online Encyclopaedia of Integer Sequences (https://oeis.org/A358041).
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 8579
- Price includes VAT (Japan)
- Softcover Book
- JPY 10724
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
See also [4] for\(n<20\).
- 2.
- 3.
- 4.
join- and meet-irreducible elements are also called supremum- and infimum-irreducible elements, respectively.
- 5.
https://github.com/LarimUQO/lattice-miner.
References
Rota, G.: A generalization of Sperner’s theorem. J. Combin. Theory2, 104 (1967)
Engel, K.: Encyclopedia of Mathematics and its Applications Sperner Theory. Cambridge University Press, Cambridge (1997)
Graham, R.L.: Maximum antichains in the partition lattice. Math. Intell.1(2), 84–86 (1978)
Harper, L.H.: The morphology of partially ordered sets. J. Comb. Theory Ser. A17(1), 44–58 (1974)
Jichang, S., Kleitman, D.J.: Superantichains in the lattice of partitions of a set. Stud. Appl. Math.71(3), 207–241 (1984)
Canfield, E.R., Harper, L.H.: Large antichains in the partition lattice. Random Struct. Algorithms6(1), 89–104 (1995)
Canfield, E.R.: The size of the largest antichain in the partition lattice. J. Comb. Theory, Ser. A83(2), 188–201 (1998)
Farley, J.D.: Was Gelfand right? The many loves of lattice theory. Notices of the American Mathematical Society69(2) (2022)
Korshunov, A.D., Shmulevich, I.: The number of special monotone Boolean functions and statistical properties of stack filters. Diskretn. Anal. Issled. Oper., Ser. 17(3), 17–44 (2000)
Ganter, B.: Algorithmen zur formalen begriffsanalyse. In: Ganter, B., Wille, R., Wolff, K.E. (eds.) Beiträge zur Begriffsanalyse, pp. 241–254. B.I.-Wissenschaftsverlag, Mannheim (1987)
Ganter, B., Reuter, K.: Finding all closed sets: a general approach. Order8(3), 283–290 (1991)
Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations, 1st edn. Springer-Verlag, New York Inc, Secaucus, NJ, USA (1999)
Aigner, M.: Combinatorial Theory. Springer, Berlin, Heidelberg (2012)
Ignatov, D.I.: Introduction to formal concept analysis and its applications in information retrieval and related fields. In: Braslavski, P., Karpov, N., Worring, M., Volkovich, Y., Ignatov, D.I. (eds.) RuSSIR 2014. CCIS, vol. 505, pp. 42–141. Springer, Cham (2015).https://doi.org/10.1007/978-3-319-25485-2_3
Bocharov, A., Gnatyshak, D., Ignatov, D.I., Mirkin, B.G., Shestakov, A.: A lattice-based consensus clustering algorithm. In: Huchard, M., Kuznetsov, S.O., (eds.) Proceedings of the Thirteenth International Conference on Concept Lattices and Their Applications, Moscow, Russia, 18–22 July 2016. Volume 1624 of CEUR Workshop Proceedings, pp. 45–56. CEUR-WS.org (2016)
Knuth, D.: The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Pearson Education (2014)
Canfield, E., Harper, L.: A Simplified Guide to Large Antichains in the Partition (2000)
Reuter, K.: The jump number and the lattice of maximal antichains. Discret. Math.88(2), 289–307 (1991)
Markowsky, G., Markowsky, L.: Lattice data analytics: the poset of irreducibles and the macneille completion. In: 10th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications, IDAACS 2019, Metz, France, 18–21 September 2019, pp. 263–268. IEEE (2019)
Lahcen, B., Kwuida, L.: Lattice miner: a tool for concept lattice construction and exploration. In: Supplementary Proceeding of International Conference on Formal concept analysis (ICFCA 2010) (2010)
Roth, C., Obiedkov, S., Kourie, D.: Towards concise representation for taxonomies of epistemic communities. In: Yahia, S.B., Nguifo, E.M., Belohlavek, R. (eds.) CLA 2006. LNCS (LNAI), vol. 4923, pp. 240–255. Springer, Heidelberg (2008).https://doi.org/10.1007/978-3-540-78921-5_17
Babin, M.A., Kuznetsov, S.O.: Approximating concept stability. In: Domenach, F., Ignatov, D.I., Poelmans, J. (eds.) ICFCA 2012. LNCS (LNAI), vol. 7278, pp. 7–15. Springer, Heidelberg (2012).https://doi.org/10.1007/978-3-642-29892-9_7
Acknowledgements
This study was implemented in the Basic Research Program’s framework at HSE University. This research was also supported in part through computational resources of HPC facilities at HSE University.
I would like to thank all the OEIS editors, especially Joerg Arndt, Michel Marcus, and N. J. A. Sloane. I also would like to thank anonymous reviewers and Jaume Baixeries for relevant suggestions, and Lev P. Shibasov and Valentina A. Goloubeva for the lasting flame of inspiration. Last but not least I would like to thank Zamira Ignatova for her care and patience.
Author information
Authors and Affiliations
National Research University Higher School of Economics, Moscow, Russia
Dmitry I. Ignatov
- Dmitry I. Ignatov
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toDmitry I. Ignatov.
Editor information
Editors and Affiliations
National Research University Higher School of Economics, Moscow, Russia
Dmitry I. Ignatov
Krasovskii Institute of Mathematics and Mechanics of Russian Academy of Sciences, Yekaterinburg, Russia
Michael Khachay
University of Oslo, Oslo, Norway
Andrey Kutuzov
American University of Armenia, Yerevan, Armenia
Habet Madoyan
Artificial Intelligence Research Institute, Moscow, Russia
Ilya Makarov
University of Hamburg, Hamburg, Germany
Irina Nikishina
Skolkovo Institute of Science and Technology, Moscow, Russia
Alexander Panchenko
Mohamed bin Zayed University of Artificial Intelligence, Abu Dhabi, United Arab Emirates
Maxim Panov
University of Florida, Gainesville, FL, USA
Panos M. Pardalos
National Research University Higher School of Economics, Nizhny Novgorod, Russia
Andrey V. Savchenko
Apptek, Aachen, Germany
Evgenii Tsymbalov
Kazan Federal University, Kazan, Russia
Elena Tutubalina
MTS AI, Moscow, Russia
Sergey Zagoruyko
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Ignatov, D.I. (2024). Is Canfield Right? On the Asymptotic Coefficients for the Maximum Antichain of Partitions and Related Counting Inequalities. In: Ignatov, D.I.,et al. Analysis of Images, Social Networks and Texts. AIST 2023. Lecture Notes in Computer Science, vol 14486. Springer, Cham. https://doi.org/10.1007/978-3-031-54534-4_25
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-031-54533-7
Online ISBN:978-3-031-54534-4
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative