The sperner property for trees | Applied Discrete Mathematics. Supplement. 2015. № 8.

The sperner property for trees

The reachability relation of a directed acyclic graph is a partial order on the set of its vertices. One of the interesting properties of a partially ordered set is its Sperner property that means that at least one of maximum antichains is formed from elements of the same height. In graphs with the reachability relation, this property is discussed for out-trees and in-trees, it is modified and studied for functional and contrafunctional digraphs closely related to these trees, and for unoriented trees also.

Download file

Counter downloads: 234

Keywords

упорядоченное множество, бесконтурный орграф, шпернеро-во свойство, дерево, входящее дерево, выходящее дерево, функциональный орграф, контрафункциональный орграф, partially ordered set, Sperner property, tree, acyclic digraph, out-tree, in-tree, functional digraph, contrafunctional digraph

Authors

Name	Organization	E-mail
Salii V. N.	Saratov State University

Всего: 1

References

Харари Ф. Теория графов. М.: Мир, 1973.

Atkinson M. D. and Ng D. T. N. On the width of an orientation of a tree // Order. 1988. V. 5. No. 1. P. 33-43.

Новокшонова Е. Н. Шпернерово свойство для линейных графов // Компьютерные науки и информационные технологии: Материалы Междунар. науч. конф. Саратов: Издат. Центр «Наука», 2014. С. 230-231.

Салий В. Н. Шпернерово свойство для многоугольных графов // Прикладная дискретная математика. Приложение. 2014. №7. С. 135-137.

Богомолов А. Д., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997.

Sperner E. Ein Satz uber Untermengen einer endlichen Menge // Math. Zeitschrift. 1928. B. 27. No. 1. S. 544-548.