RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2015 Issue 8, Pages 124–127 (Mi pdma243)

This article is cited in 2 papers

Applied Theory of Coding, Automata and Graphs

The Sperner property for trees

V. N. Salii

Saratov State University, Saratov

Abstract: 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.

Keywords: partially ordered set, Sperner property, tree, acyclic digraph, out-tree, in-tree, functional digraph, contrafunctional digraph.

UDC: 519.17

DOI: 10.17223/2226308X/8/47



© Steklov Math. Inst. of RAS, 2024