RUS  ENG
Full version
JOURNALS // Izvestiya of Saratov University. Mathematics. Mechanics. Informatics // Archive

Izv. Saratov Univ. Math. Mech. Inform., 2016 Volume 16, Issue 2, Pages 226–231 (Mi isu640)

Computer Sciences

The Sperner property for polygonal graphs considered as partially ordered sets

V. N. Salii

Saratov State University, 83, Astrakhanskaya st., 410012, Saratov, Russia

Abstract: A finite poset is said to have the Sperner property if at least one of its maximum antichains is formed from elements of the same height. 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.

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

UDC: 519.17

DOI: 10.18500/1816-9791-2016-16-2-226-231



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024