The Sperner property for polygonal graphs considered as partially ordered sets

V. N. Salii

Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 16 (2016) no. 2, pp. 226-231.

Résumé

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.

Bibliographie

[1] Sperner E., “Ein Satz uber Untermengen einer endlichen Menge”, Math. Zeitschrift, 27:1 (1928), 544–548 | DOI | MR | Zbl

[2] Lubell D., “A short proof of Sperner's lemma”, J. Comb. Theory, 1:2 (1961), 299 | DOI | MR

[3] Meshalkin L. D., “Generalization of Sperner's theorem on the number of subsets of a finite set”, Theory of probability and i ts applications, 8:2 (1963), 219–220 (in Russian) | Zbl

[4] Green C., Kleitman D. J., “Strong versions of Sperner's theorem”, J. Comb. Theory Ser. A, 20:1 (1976), 80–88 | DOI | MR | Zbl

[5] Stanley R. P., “Weyl groups, the hard Lefschetz theorem and the Sperner property”, SIAM J. Alg. Discr. Math., 1:2 (1980), 168–184 | DOI | MR | Zbl

[6] Shahriari S., “On the structure of maximum two-part Sperner families”, Discr. Math., 162:2 (1996), 229–238 | DOI | MR | Zbl

[7] Kochkarev V. S., “Structural properties of a class of maximal Sperner families of subsets”, Russian Math., 49:7 (2005), 35–40 | MR | Zbl

[8] Aydinian H., Erdós P. L., “On two-part Sperner systems for regular posets”, Electronic Notes in Discr. Math., 38:1 (2011), 87–92 | DOI | Zbl

[9] Lih K. W., “Sperner families over a subset”, J. Comb. Theory Ser. A, 29:1 (1980), 182–185 | DOI | MR | Zbl

[10] Griggs J. R., “Collections of subsets with the Sperner property”, Trans. Amer. Math. Soc., 269:2 (1982), 575–591 | DOI | MR | Zbl

[11] Wang J., “Proof of a conjecture on the Sperner property of the subgroup lattice of an abelian $p$-group”, Annals Comb., 2:1 (1999), 85–101 | DOI | MR

[12] Jacobson M. S., Kezdy A. E., Seif S., “The poset of connected induced subgraphs of a graph need not be Sperner”, Order, 12:3 (1995), 315–318 | DOI | MR | Zbl

[13] Maeno T., Numata Y., “Sperner property, matroids and finite-dimensional Gorenstein algebras”, Contemp. Math., 280:1 (2012), 73–83 | DOI | MR

[14] Bogomolov A. M., Salii V. N., Algebraic foundations of the theory of discrete systems, Nauka, M., 1997 (in Russian) | MR

[15] Salii V. N., “Minimal primitive extensions of oriented graphs”, Appl. Discr. Matematics, 1:1 (2008), 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., 13:2/2 (2013), 44–51 (in Russian) | Zbl

[17] Salii V. N., “On Sperner property for polygonal graphs”, Computer science and information trchnology, Proc. Intern. Sci. Conf., Publ. center “Nauka”, Saratov, 2014, 275–277 (in Russian)