ГлавнаяАрхивШпернерово свойство для многоугольных графов

Шпернерово свойство для многоугольных графов | Прикладная дискретная математика. 2014. № 7 (Приложение).

Конечное упорядоченное множество называется шпернеровым, если среди его максимальных по длине антицепей хотя бы одна составлена из элементов одинаковой высоты. Под многоугольным графом понимается бесконтурный граф, полученный из цикла путём некоторой ориентации его рёбер. В многоугольном графе отношение достижимости вершин является отношением порядка. Таким образом, многоугольный граф можно рассматривать как упорядоченное множество. Найдено необходимое и достаточное условие шпернеровости таких упорядоченных множеств.
  • Title Шпернерово свойство для многоугольных графов
  • Headline Шпернерово свойство для многоугольных графов
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 7 (Приложение)
  • Date:
  • DOI
Ключевые слова
упорядоченное множество, шпернерово свойство, многоугольный граф, цепь, зигзаг, partially ordered set, Sperner property, polygonal graph, path, zigzag
Авторы
Ссылки
Салий В. Н. Упорядоченное множество связных частей многоугольного графа // Изв. Сарат. ун-та. Нов. cер. Сер. Математика. Механика. Информатика. 2013. Т. 13. №2(ч. 2). С.44-51.
Maeno T. and Numata Y. Sperner property, matroids and finite-dimensional Gorenstein algebras // Contemp. Math. 2012. V.280. No. 1. P. 73-83.
Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997.
Jacobson M. S., Kezdy A. E., and Seif S. The poset of connected induced subgraphs of a graph need not be Sperner // Order. 1995. V. 12. No3. P.315-318.
Stanley E. P. Weyl groups, the hard Lefschetz theorem and the Sperner property // SIAM J. Alg. Discr. Math. 1980. V. 1. No. 2. P. 168-184.
Wang J. Proof of a conjecture on the Sperner property of the subgroup lattice of an abelian p-group // Annals Comb. 1999. V.2. No. 1. P. 85-101.
Sperner E. Ein Satz uber Untermengen einer endlichen Menge // Math. Zeitschrift. 1928. V. 27. No. 1. S. 544-548.
Мешалкин Л. Д. Обобщение теоремы Шпернера о числе подмножеств конечного множества // Теория вероятностей и её применения. 1963. Т. 8. №2. С. 219-220.
Шпернерово свойство для многоугольных графов | Прикладная дискретная математика. 2014. № 7 (Приложение).
Шпернерово свойство для многоугольных графов | Прикладная дискретная математика. 2014. № 7 (Приложение).