Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


Для цитирования:

Салий В. Н. Многоугольные графы как упорядоченные множества: критерий шпернеровости // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2016. Т. 16, вып. 2. С. 226-231. DOI: 10.18500/1816-9791-2016-16-2-226-231

Опубликована онлайн: 
14.06.2016
Полный текст в формате PDF(Ru):
(downloads: 31)
Язык публикации: 
русский
Рубрика: 
УДК: 
519.17
DOI: 
10.18500/1816-9791-2016-16-2-226-231

Многоугольные графы как упорядоченные множества: критерий шпернеровости

Авторы: 
Салий Вячеслав Николаевич, Саратовский национальный исследовательский государственный университет им. Н. Г. Чернышевского
Аннотация: 

Конечное упорядоченное множество называется шпернеровым, если среди его максимальных по длине антицепей хотя бы одна составлена из элементов одинаковой высоты. Под многоугольным графом понимается бесконтурный граф, полученный из цикла путем некоторой ориентации его ребер. В многоугольном графе отношение достижимости вершин является отношением порядка. Таким образом, многоугольный граф можно рассматривать как упорядоченное множество. Найдены необходимые и достаточные условия шпернеровости таких упорядоченных множеств.

Список источников: 
  1. Sperner E. Ein Satz uber Untermengen einer endlichen Menge // Math. Zeitschrift. 1928. Vol. 27, № 1. P. 544–548.
  2. Lubell D. A short proof of Sperner’s lemma // J. Comb. Theory. 1961. Vol. 1, № 2. P. 299.
  3. Мешалкин Л. Д. Обобщение теоремы Шпернера о числе подмножеств конечного множества // Теория вероятностей и ее применения. 1963. Т. 8, № 2. С. 219–220.
  4. Green C., Kleitman D. J. Strong versions of Sperner’s theorem // J. Comb. Theory Ser. A. 1976. Vol. 20, № 1. P. 80–88.
  5. 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.
  6. Shahriari S. On the structure of maximum two-part Sperner families // Discr. Math. 1996. Vol. 162, № 2. P. 229–238.
  7. Кочкарев В. С. Структурные свойства одного класса максимальных шпернеровых семейств подмножеств // Изв. вузов. Математика. 2005. № 7. С. 37–42.
  8. 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.
  9. Lih K. W. Sperner families over a subset // J. Comb. Theory Ser. A. 1980. Vol. 29, № 1. P. 182–185.
  10. Griggs J. R. Collections of subsets with the Sperner property // Trans. Amer. Math. Soc. 1982. Vol. 269, № 2. P. 575–591.
  11. 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.
  12. 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.
  13. Maeno T., Numata Y. Sperner property, matroids and finite-dimensional Gorenstein algebras // Contemp. Math. 2012. Vol. 280, № 1. P. 73–83.
  14. Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М. : Наука, 1997.
  15. Салий В. Н. Минимальные примитивные расширения ориентированных графов // Прикл. дискр. математика. 2008. Т. 1, № 1. С. 116–119.
  16. Салий В. Н. Упорядоченное множество связных частей многоугольного графа // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2013. Т. 13, вып. 2, ч. 2. С. 44–51.
  17. Салий В. Н. О шпернеровом свойстве для многоугольных графов // Компьютерные науки и информационные технологии : материалы междунар. науч. конф. Саратов : Издат. центр «Наука», 2014. С. 275–277.