Abstract
We study the structure of the partially ordered set of minors of an arbitrary function of several variables. We give an abstract characterization of such “minor posets” in terms of colorings of partition lattices, and we also present infinite families of examples as well as some constructions that can be used to build new minor posets.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Beran, L., Ježek, J.: On embedding of lattices in simple lattices. Acta Univ. Carolinae—Math. et Phys. 13, 87–89 (1972)
Birkhoff, G.: Lattice Theory. American Mathematical Society Colloquium Publications, vol. 25. American Mathematical Society, Providence RI (1967)
Brinkmann, G., McKay, B.D.: Posets on up to 16 points. Order 19, 147–179 (2002)
Couceiro, M., Lehtonen, E., Waldhauser, T.: Parametrized arity gap. Order 30, 557–572 (2013)
Couceiro, M., Pouzet, M.: On a quasi-ordering on Boolean functions. Theoret. Comput. Sci. 396, 71–87 (2008)
Lehtonen, E., Szendrei, Á.: Partial orders induced by quasilinear clones. In: Proceedings of the Salzburg Conference 2011 (AAA81), Contributions to General Algebra, vol. 20, pp. 51–84. Verlag Johannes Heyn, Klagenfurt (2012)
Lehtonen, E., Waldhauser, T.: Posets of minors of functions in multiple-valued logic. In: Proceedings of the 47th IEEE International Symposium on Multiple-Valued Logic (ISMVL 2017), pp. 43–48. IEEE Computer Society (2017)
Ore, O.: Theory of equivalence relations. Duke Math. J. 9, 573–627 (1942)
Post, E.L.: The Two-Valued Iterative Systems of Mathematical Logic. Annals of Mathematics Studies, vol. 5. Princeton University Press, Princeton (1941)
Willard, R.: Essential arities of term operations in finite algebras. Discrete Math. 149, 239–259 (1996)
Acknowledgements
Research supported by the Hungarian National Research, Development and Innovation Office (NKFIH grants no. K104251 and K115518) and by the János Bolyai Research Scholarship. This work was developed during the authors’ mutual visits to the Technische Universität Dresden and the University of Szeged. The authors would like to thank the anonymous reviewers for their valuable comments and suggestions for improving the paper.
Author information
Authors and Affiliations
Corresponding author
Electronic supplementary material
Rights and permissions
About this article
Cite this article
Lehtonen, E., Waldhauser, T. Minor Posets of Functions as Quotients of Partition Lattices. Order 36, 23–41 (2019). https://doi.org/10.1007/s11083-018-9453-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11083-018-9453-8