Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

For citation:

Salii V. N. The Sperner Property for Polygonal Graphs Considered as Partially Ordered Sets. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2016, vol. 16, iss. 2, pp. 226-231. DOI: 10.18500/1816-9791-2016-16-2-226-231, EDN: WCNQMT

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
14.06.2016
Full text:
download
(downloads: 140)
Language: 
Russian
Heading: 
Computer Sciences
UDC: 
519.17
DOI: 
10.18500/1816-9791-2016-16-2-226-231
EDN: 
WCNQMT

The Sperner Property for Polygonal Graphs Considered as Partially Ordered Sets

Autors: 
Salii Viacheslav Nikolaevich, Saratov State University
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
References: 
  1. Sperner E. Ein Satz uber Untermengen einer endlichen Menge // Math. Zeitschrift. 1928. Vol. 27, № 1. P. 544–548.
  2. Lubell D. A short proof of Sperner’s lemma // J. Comb. Theory. 1961. Vol. 1, № 2. P. 299.
  3. Meshalkin L. D. Generalization of Sperner’s theorem on the number of subsets of a finite set. Teoria veroiatnostei i ee primeneniia [Theory of probability and I’ts applications], 1963, vol. 8, no. 2, pp. 219–220 (in Russian).
  4. Green C., Kleitman D. J. Strong versions of Sperner’s theorem // J. Comb. Theory Ser. A. 1976. Vol. 20, № 1. P. 80–88.
  5. Stanley R. P. Weyl groups, the hard Lefschetz theorem and the Sperner property // SIAM J. Alg. Discr. Math. 1980. Vol. 1, № 2. P. 168–184.
  6. Shahriari S. On the structure of maximum two-part Sperner families // Discr. Math. 1996. Vol. 162, № 2. P. 229–238.
  7. Kochkarev V. S. Structural properties of a class of maximal Sperner families of subsets. Russian Math., 2005, vol. 49, no. 7, pp. 35–40.
  8. Aydinian H., Erdoґ s P. L. On two-part Sperner systems for regular posets // Electronic Notes in Discr. Math. 2011. Vol. 38, № 1. P. 87–92.
  9. Lih K. W. Sperner families over a subset // J. Comb. Theory Ser. A. 1980. Vol. 29, № 1. P. 182–185.
  10. Griggs J. R. Collections of subsets with the Sperner property // Trans. Amer. Math. Soc. 1982. Vol. 269, № 2. P. 575–591.
  11. Wang J. Proof of a conjecture on the Sperner property of the subgroup lattice of an abelian p-group // Annals Comb. 1999. Vol. 2, № 1. P. 85–101.
  12. Jacobson M. S., Kezdy A. E., Seif S. The poset of connected induced subgraphs of a graph need not be Sperner // Order. 1995. Vol. 12, № 3. P. 315–318.
  13. Maeno T., Numata Y. Sperner property, matroids and finite-dimensional Gorenstein algebras // Contemp. Math. 2012. Vol. 280, № 1. P. 73–83.
  14. Bogomolov A. M., Salii V. N. Algebraic Foundations of the Theory of Discrete Systems. Moscow, Nauka, 1997 (in Russian).
  15. Salii V. N. Minimal primitive extensions of oriented graphs. Prikl. diskr. matematika [Appl. Discr. Matematics], 2008, vol. 1, no. 1, pp. 116–119 (in Russian).
  16. Salii V. N. Ordered set of connected parts of polygonal graph. Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform., 2013, vol. 13, iss. 2, pt. 2, pp. 44–51 (in Russian).
  17. Salii V. N. O shpernerovom svoistve dlia mnogougol’nykh grafov [On Sperner property for polygonal graphs]. Komp’iuternye nauki i informatsionnye tekhnologii. Materialy mezhdunar. nauch. konf. [Computer science and information technology. Proc. Intern. Sci. Conf.], Saratov, Publ. center “Nauka”, 2014, pp. 275–277 (in Russian).
Received: 
16.01.2016
Accepted: 
24.05.2016
Published: 
30.06.2016
  • 888 reads