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

Prikl. Diskr. Mat. Suppl., 2014 Issue 7, Pages 135–137 (Mi pdma176)

This article is cited in 2 papers

Applied graph theory

The Sperner property for polygonal graphs

V. N. Salii

Saratov State University, Saratov

Abstract: A finite partially ordered set (poset) is said to have the Sperner property if at least one of its maximum antichains is formed from elements of the same hight. A polygonal graph is a directed acyclic graph derived from a circuit by some orientation of its edges. The reachability relation of a polygonal graph is a partial order. A criterion is presented for posets associated with polygonal graphs to have the Sperner property.

Keywords: partially ordered set, Sperner property, polygonal graph, path, zigzag.

UDC: 519.17



© Steklov Math. Inst. of RAS, 2024