И.А. Дерендяев. О решетках максимальных антицепей конечных частично упорядоченных множеств ... С. 95-104.

УДК 512.567

MSC: 06B15, 06A05, 06A11

DOI: 10.21538/0134-4889-2017-23-3-95-104

Полная версия статьи

Настоящая статья посвящена решеткам максимальных антицепей конечных частично упорядоченных (ч.у.) множеств произвольной высоты. Решетки максимальных антицепей конечных ч.у. множеств высоты 1 хорошо изучены и применяются, например, в анализе формальных понятий. Однако существует множество общих свойств, присущих конечным ч.у. множествам любой высоты. Для произвольного элемента $x$ некоторого ч.у. множества мы вводим понятие наименьшей (наибольшей) максимальной антицепи, содержащей $x$, обозначаемой как $m_{x}$ ($M_{x}$). Мы доказываем, что для любой максимальной антицепи $A$ справедливо равенство $A = \bigvee_{x\in A}m_{x} = \bigwedge_{x\in A}M_{x}$. Это соотношение позволяет описать все неразложимые элементы решеток максимальных антицепей. Основным результатом статьи является описание всех конечных ч.у. множеств, решетка максимальных антицепей которых изоморфна некоторой заранее заданной решетке. Неразложимые элементы в этом описании играют ключевую роль.

Ключевые слова: частично упорядоченное множество, максимальная антицепь, решетка максимальных антицепей.

Список литературы

1. Birkhoff G. Rings of sets // Duke Math. J. 1937. Vol. 3, no. 3. P. 443-454.

2. Behrendt G. Maximal antichains in partially ordered sets // Ars Combin. 1988. No. 25C. P. 149-157.

3. Reuter K. The jump number and the lattice of maximal antichains // Discrete Math. 1991. Vol. 88, iss. 2-3. P. 289-307.

4. Morvan M., Nourine L. Simplicial elimination schemes, extremal lattices and maximal antichain lattices // Order. 1996. Vol. 13, iss. 2. P. 159-173. doi: http://dx.doi.org/10.1007/BF00389839.

5. Ganter B., Wille R. Formal concept analysis: Mathematical foundations. Berlin; Heidelberg: Springer-Verlag, 1999. 284 p. doi: http://dx.doi.org/10.1007/978-3-642-59830-2.

6. Garg V. Maximal antichain lattice algorithms for distributed computations // Internat. Conf. on Distributed Computing and Networking. 2013. P.240--254. (Lecture Notes Comp. Sci., vol. 7730.) doi: http://dx.doi.org/10.1007/978-3-642-35668-1_17.

Поступила 19.05.2017

Дерендяев Илья Александрович
магистрант
Уральский федеральный университет, г. Екатеринбург
e-mail: ilia.derendiaev@yandex.ru

English

I.A. Derendiaev. On maximal antichain lattices of finite posets.

This paper is devoted to maximal antichain lattices of posets of arbitrary length. Maximal antichain lattices of finite posets of length1 have been well studied and are applied, for example, in formal concept analysis. However, there are many general properties inherent in finite posets of any length. For an arbitrary element$x$ of some poset, we introduce the notions of smallest and largest maximal antichains containing$x$, which are denoted by $m_{x}$ and $M_{x}$, respectively. We prove that the equality $A=\bigvee_{x\in A}m_{x}=\bigwedge_{x\in A}M_{x}$ holds for any maximal antichain$A$. This equality allows us to describe all irreducible elements of maximal antichain lattices. The main result of this paper is a description of all finite posets whose maximal antichain lattice is isomorphic to a given lattice. Irreducible elements play a key role in this description.

Keywords: poset, maximal antichain, maximal antichain lattice.

The paper was received by the Editorial Office on May 19, 2017

Ilia Aleksandrovich Derendiaev, graduate student, Ural Federal University, Yekaterinburg, 620002 Russia,
 e-mail: ilia.derendiaev@yandex.ru .