Для цитирования:
Салий В. Н. Многоугольные графы как упорядоченные множества: критерий шпернеровости // Известия Саратовского университета. Новая серия. Серия : Математика. Механика. Информатика. 2016. Т. 16, вып. 2. С. 226-231. DOI: 10.18500/1816-9791-2016-16-2-226-231, EDN: WCNQMT
Многоугольные графы как упорядоченные множества: критерий шпернеровости
Конечное упорядоченное множество называется шпернеровым, если среди его максимальных по длине антицепей хотя бы одна составлена из элементов одинаковой высоты. Под многоугольным графом понимается бесконтурный граф, полученный из цикла путем некоторой ориентации его ребер. В многоугольном графе отношение достижимости вершин является отношением порядка. Таким образом, многоугольный граф можно рассматривать как упорядоченное множество. Найдены необходимые и достаточные условия шпернеровости таких упорядоченных множеств.
- Sperner E. Ein Satz uber Untermengen einer endlichen Menge // Math. Zeitschrift. 1928. Vol. 27, № 1. P. 544–548.
- Lubell D. A short proof of Sperner’s lemma // J. Comb. Theory. 1961. Vol. 1, № 2. P. 299.
- Мешалкин Л. Д. Обобщение теоремы Шпернера о числе подмножеств конечного множества // Теория вероятностей и ее применения. 1963. Т. 8, № 2. С. 219–220.
- Green C., Kleitman D. J. Strong versions of Sperner’s theorem // J. Comb. Theory Ser. A. 1976. Vol. 20, № 1. P. 80–88.
- Stanley R. P. Weyl groups, the hard Lefschetz theorem and the Sperner property // SIAM J. Alg. Discr. Math. 1980. Vol. 1, № 2. P. 168–184.
- Shahriari S. On the structure of maximum two-part Sperner families // Discr. Math. 1996. Vol. 162, № 2. P. 229–238.
- Кочкарев В. С. Структурные свойства одного класса максимальных шпернеровых семейств подмножеств // Изв. вузов. Математика. 2005. № 7. С. 37–42.
- Aydinian H., Erdoґ s P. L. On two-part Sperner systems for regular posets // Electronic Notes in Discr. Math. 2011. Vol. 38, № 1. P. 87–92.
- Lih K. W. Sperner families over a subset // J. Comb. Theory Ser. A. 1980. Vol. 29, № 1. P. 182–185.
- Griggs J. R. Collections of subsets with the Sperner property // Trans. Amer. Math. Soc. 1982. Vol. 269, № 2. P. 575–591.
- Wang J. Proof of a conjecture on the Sperner property of the subgroup lattice of an abelian p-group // Annals Comb. 1999. Vol. 2, № 1. P. 85–101.
- Jacobson M. S., Kezdy A. E., Seif S. The poset of connected induced subgraphs of a graph need not be Sperner // Order. 1995. Vol. 12, № 3. P. 315–318.
- Maeno T., Numata Y. Sperner property, matroids and finite-dimensional Gorenstein algebras // Contemp. Math. 2012. Vol. 280, № 1. P. 73–83.
- Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М. : Наука, 1997.
- Салий В. Н. Минимальные примитивные расширения ориентированных графов // Прикл. дискр. математика. 2008. Т. 1, № 1. С. 116–119.
- Салий В. Н. Упорядоченное множество связных частей многоугольного графа // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2013. Т. 13, вып. 2, ч. 2. С. 44–51.
- Салий В. Н. О шпернеровом свойстве для многоугольных графов // Компьютерные науки и информационные технологии : материалы междунар. науч. конф. Саратов : Издат. центр «Наука», 2014. С. 275–277.
- 885 просмотров