×

Level Eulerian posets. (English) Zbl 1317.06004

Summary: The notion of level posets is introduced. This class of infinite posets has the property that between every two adjacent ranks the same bipartite graph occurs. When the adjacency matrix is indecomposable, we determine the length of the longest interval one needs to check to verify Eulerianness. Furthermore, we show that every level Eulerian poset associated to an indecomposable matrix has even order. A condition for verifying shellability is introduced and is automated using the algebra of walks. Applying the Skolem-Mahler-Lech theorem, the \(\mathbf{ab}\)-series of a level poset is shown to be a rational generating function in the non-commutative variables \(\mathbf a\) and \(\mathbf b\). In the case the poset is also Eulerian, the analogous result holds for the \(\mathbf{cd}\)-series. Using coalgebraic techniques a method is developed to recognize the \(\mathbf{cd}\)-series matrix of a level Eulerian poset.

MSC:

06A07 Combinatorics of partially ordered sets
05A15 Exact enumeration problems, generating functions
05C45 Eulerian and Hamiltonian graphs
52B22 Shellability for polytopes and polyhedra
57M15 Relations of low-dimensional topology with graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Babson E., Hersh P.: Discrete Morse functions from lexicographic orders. Trans. Am. Math. Soc. 357, 509-534 (2005) · Zbl 1050.05117 · doi:10.1090/S0002-9947-04-03495-6
[2] Bayer M., Billera L.J.: Generalized Dehn-Sommerville relations for polytopes, spheres and Eulerian partially ordered sets. Invent. Math. 79, 143-157 (1985) · Zbl 0543.52007 · doi:10.1007/BF01388660
[3] Bayer M., Klapper A.: A new index for polytopes. Discret. Comput. Geom. 6, 33-47 (1991) · Zbl 0761.52009 · doi:10.1007/BF02574672
[4] Bayer M., Hetyei G.: Flag vectors of Eulerian partially ordered sets. Eur. J. Combin. 22, 5-26 (2001) · Zbl 0971.06004 · doi:10.1006/eujc.2000.0414
[5] Bayer M., Hetyei G.: Generalizations of Eulerian partially ordered sets, flag numbers, and the Möbius function. Discret. Math. 256, 577-593 (2002) · Zbl 1020.06001 · doi:10.1016/S0012-365X(02)00336-9
[6] Billera L.J., Hetyei G.: Linear inequalities for flags in graded partially ordered sets. J. Combin. Theory Ser. A 89, 77-104 (2000) · Zbl 0959.52010 · doi:10.1006/jcta.1999.3008
[7] Billera L.J., Hetyei G.: Decompositions of partially ordered sets. Order 17, 141-166 (2000) · Zbl 0982.06002 · doi:10.1023/A:1006420120193
[8] Björner A.: Topological methods in Handbook of combinatorics, vols. 1, 2., pp. 1819. Elsevier, Amsterdam (1995) · Zbl 0851.52016
[9] Björner A., Wachs M.: Bruhat order of Coxeter groups and shellability. Adv. Math. 43, 87-100 (1982) · Zbl 0481.06002 · doi:10.1016/0001-8708(82)90029-9
[10] Björner A., Wachs M.: On lexicographically shellable posets. Trans. Am. Math. Soc. 277, 323-341 (1983) · Zbl 0514.05009 · doi:10.2307/1999359
[11] Ehrenborg R.: k-Eulerian posets. Order 18, 227-236 (2001) · Zbl 1010.06005 · doi:10.1023/A:1012296719116
[12] Ehrenborg R., Readdy M.: Coproducts and the cd-index J. Algebr. Combin. 8, 273-299 (1998) · Zbl 0917.06001 · doi:10.1023/A:1008614816374
[13] Ehrenborg R., Readdy M.: Homology of Newtonian coalgebras. Eur. J. Combin. 23, 919-927 (2002) · Zbl 1034.52010 · doi:10.1006/eujc.2002.0620
[14] Ehrenborg R., Readdy M.: Classification of the factorial functions of Eulerian binomial and Sheffer posets. J. Combin. Theory Ser. A 114, 339-359 (2007) · Zbl 1109.06003 · doi:10.1016/j.jcta.2006.06.003
[15] Forman R.: Morse theory for cell complexes. Adv. Math. 134, 90-145 (1998) · Zbl 0896.57023 · doi:10.1006/aima.1997.1650
[16] Gross J., Tucker T.W. (2001) Topological graph theory. Reprint of the 1987 original (Wiley, New York) with a new preface and supplementary bibliography. Dover Publications, Inc., Mineola · Zbl 0481.06002
[17] Heap B.R., Lynn M.S.: The structure of powers of nonnegative matrices. I. The index of convergence. SIAM J. Appl. Math. 14, 610-639 (1966) · Zbl 0166.03705 · doi:10.1137/0114052
[18] Holladay J.C., Varga R.S.: On powers of non-negative matrices. Proc. Am. Math. Soc. 9, 631-634 (1958) · Zbl 0096.00805 · doi:10.1090/S0002-9939-1958-0097416-8
[19] Kozlov D.: General lexicographic shellability and orbit arrangements. Ann. Combin. 1, 67-90 (1997) · Zbl 0943.52004 · doi:10.1007/BF02558464
[20] Lech C.: A note on recurring series. Ark. Mat. 2, 417-421 (1953) · Zbl 0051.27801 · doi:10.1007/BF02590997
[21] Mahler K.: On the Taylor coefficients of rational functions. Proc. Camb. Philos. Soc. 52, 39-48 (1956) · Zbl 0070.04004 · doi:10.1017/S0305004100030966
[22] Perrin, D., Schützenberger, M-P.: Synchronizing prefix codes and automata and the road coloring problem, In: Symbolic dynamics and its applications (New Haven, CT, 1991). Contemp. Math., 135, 295-318. Am. Math. Soc., Providence (1992) · Zbl 0787.68073
[23] Pták V.: On a combinatorial theorem and its application to nonnegative matrices. Czechoslov. Math. J. 8(83), 487-495 (1958) · Zbl 0082.24402
[24] Pták V., Sedlaček I.: On the index of imprimitivity of nonnegative matrices. Czechoslov. Math. J. 8(83), 496-501 (1958) · Zbl 0082.24403
[25] Rosenblatt D.: On the graphs and asymptotic forms of finite Boolean relation matrices and stochastic matrices. Naval. Res. Logist. Quart. 4, 151-167 (1957) · doi:10.1002/nav.3800040206
[26] Sachkov, V.N., Tarakanov, V.E.: Combinatorics of nonnegative matrices. Translations of Mathematical Monographs, vol. 213. The American Mathematical Society, Providence (2002) · Zbl 1006.05001
[27] Skolem T.: Einige Sätze über gewisse Reihenentwicklungen und exponentiale Beziehungen mit Anwendung auf diophantische Gleichungen. Oslo Vid. Akad. Skrifter I 6, 1-61 (1933) · JFM 59.0935.04
[28] Stanley R.P.: Flag f-vectors and the cd-index. Math. Z. 216, 483-499 (1994) · Zbl 0805.06003 · doi:10.1007/BF02572336
[29] Stanley R.P.: Enumerative Combinatorics, vol. I. Cambridge University Press, Cambridge (1997) · Zbl 0889.05001 · doi:10.1017/CBO9780511805967
[30] Stanley R.P.: Enumerative Combinatorics, vol. II. . Cambridge University Press, Cambridge (1999) · Zbl 0928.05001 · doi:10.1017/CBO9780511609589
[31] Wachs, M.: Poset topology: tools and applications. In: Miller, E., Reiner, V., Sturmfels, B. (eds.) Geometric combinatorics. IAS/Park City Math. Series, 13, pp. 497-615. Am. Math. Soc., Providence (2007) · Zbl 1135.06001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.