×

Some relational structures with polynomial growth and their associated algebras. I: Quasi-polynomiality of the profile. (English) Zbl 1267.05304

Summary: The profile of a relational structure \(R\) is the function \(\phi_R\) which counts for every integer \(n\) the number \(\phi_R(n)\), possibly infinite, of substructures of \(R\) induced on the \(n\)-element subsets, isomorphic substructures being identified. If \(\phi_R\) takes only finite values, this is the Hilbert function of a graded algebra associated with \(R\), the age algebra \(KA(R)\), introduced by P. J. Cameron. In this paper we give a closer look at this association, particularly when the relational structure \(R\) admits a finite monomorphic decomposition. This setting still encompass well-studied graded commutative algebras like invariant rings of finite permutation groups, or the rings of quasi-symmetric polynomials. We prove that \(\phi_R\) is eventually a quasi-polynomial, this supporting the conjecture that, under mild assumptions on \(R, \phi_R\) is eventually a quasi-polynomial when it is bounded by some polynomial.

MSC:

05E99 Algebraic combinatorics

Software:

OEIS
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] M. H. Albert and M. D. Atkinson. Simple permutations and pattern restricted permutations. Discrete Math., 300(1-3):1-15, 2005. · Zbl 1073.05002
[2] M. H. Albert, M. D. Atkinson, and Robert Brignall. Permutation classes of polynomial growth. Ann. Comb., 11(3-4):249-264, 2007. the electronic journal of combinatorics 20(2) (2013), #P131 · Zbl 1141.05009
[3] J´ozsef Balogh, B´ela Bollob´as, and Robert Morris. Hereditary properties of combinatorial structures: posets and oriented graphs. J. Graph Theory, 56(4):311– 332, 2007. · Zbl 1135.05024
[4] J´ozsef Balogh, B´ela Bollob´as, Michael Saks, and Vera T. S´os. The unlabelled speed of a hereditary graph property. J. Combin. Theory Ser. B, 99(1):9-19, 2009. · Zbl 1168.05042
[5] Robert Brignall, Sophie Huczynska, and Vincent Vatter. Decomposing simple permutations, with enumerative consequences. Combinatorica, 28(4):385-400, 2008. · Zbl 1164.05001
[6] B´ela Bollob´as. Hereditary properties of graphs: asymptotic enumeration, global structure, and colouring. In Proceedings of the International Congress of Mathematicians, Vol. III (Berlin, 1998), number Extra Vol. III, pages 333-342 (electronic), 1998. · Zbl 0902.05028
[7] Youssef Boudabbous and Maurice Pouzet. The morphology of infinite tournaments; application to the growth of their profile.European J. Combin., 31(2):461-481, 2010. · Zbl 1230.05138
[8] Peter J. Cameron. Oligomorphic permutation groups, volume 152 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 1990. · Zbl 0813.20002
[9] Peter J. Cameron. The algebra of an age. In Model theory of groups and automorphism groups (Blaubeuren, 1995), volume 244 of London Math. Soc. Lecture Note Ser., pages 126-133. Cambridge Univ. Press, Cambridge, 1997. · Zbl 0888.20002
[10] Peter Cameron. Oligomorphic permutation groups. In Mohan Delampady N. S. Narasimha Sastry, T. S. S. R. K. Rao and B. Rajeev, editors, Perspectives in Mathematical Sciences II: Pure Mathematics, pages 37-61. World Scientific, Singapore, 2009. · Zbl 1205.20002
[11] David Cox, John Little, and Donal O’Shea. Ideals, varieties, and algorithms. Springer-Verlag, New York, second edition, 1997. An introduction to computational algebraic geometry and commutative algebra. · Zbl 0756.13017
[12] Vesselin Drensky and Lothar Gerritzen. Nonassociative exponential and logarithm. J. Algebra, 272(1):311-320, 2004. · Zbl 1077.17003
[13] P. Erd˝os and A. Tarski. On families of mutually exclusive sets. Ann. of Math. (2), 44:315-329, 1943. · Zbl 0060.12602
[14] OEIS Foundation Inc. The on-line encyclopedia of integer sequences, 2012.
[15] Roland Fra¨ıss´e and Maurice Pouzet. Interpr´etabilit´e d’une relation pour une chaˆıne. C. R. Acad. Sci. Paris S´er. A-B, 272:A1624-A1627, 1971. · Zbl 0223.04001
[16] Roland Fra¨ıss´e. Sur quelques classifications des syst‘emes de relations. Publ. Sci. Univ. Alger. S´er. A., 1:35-182 (1955), 1954. the electronic journal of combinatorics 20(2) (2013), #P132 · Zbl 0068.24302
[17] Claude Frasnay. Quelques probl‘emes combinatoires concernant les ordres totaux et les relations monomorphes. Ann. Inst. Fourier (Grenoble), 15(fasc. 2):415-524, 1965. · Zbl 0201.33901
[18] Roland Fra¨ıss´e. Cours de logique math´ematique. Tome 1: Relation et formule logique. Gauthier-Villars ´Editeur, Paris, 1971. Deuxi“eme ´edition revue et modifi´ee, Collection de “Logique Math´ematique”, S´erie A, No. 23. · Zbl 0247.02002
[19] Roland Fra¨ıss´e. Theory of relations, volume 145 of Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Co., Amsterdam, revised edition, 2000. With an appendix by Norbert Sauer. · Zbl 0965.03059
[20] L. Gerritzen. Planar shuffle product, co-addition and the non-associative exponential. 2005. arXiv:math/0502378v1 [math.RA].
[21] Ira M. Gessel. Multipartite P -partitions and inner products of skew Schur functions. In Combinatorics and algebra (Boulder, Colo., 1983), volume 34 of Contemp. Math., pages 289-317. Amer. Math. Soc., Providence, RI, 1984. · Zbl 0562.05007
[22] A. M. Garsia and N. Wallach. Qsym over Sym is free. J. Combin. Theory Ser. A, 104(2):217-263, 2003. · Zbl 1032.05139
[23] Graham Higman. Ordering by divisibility in abstract algebras. Proc. London Math. Soc. (3), 2:326-336, 1952. · Zbl 0047.03402
[24] Florent Hivert. Local actions of the symmetric group and generalisations of quasi-symmetric functions, 2005.
[25] Tom´aˇs Kaiser and Martin Klazar.On growth rates of closed permutation classes.Electron. J. Combin., 9(2):Research paper 10, 20 pp. (electronic), 2002/03. Permutation patterns (Otago, 2003). · Zbl 1015.05002
[26] M. Klazar. Overview of some general results in combinatorial enumeration. Arxiv preprint arXiv:0803.4292, 2008.
[27] Martin Klazar. On growth rates of permutations, set partitions, ordered graphs and other objects. Electron. J. Combin., 15(1):Research Paper 75, 22, 2008. · Zbl 1163.05308
[28] M. Lothaire. Combinatorics on words. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1997. With a foreword by Roger Lyndon and a preface by Dominique Perrin, Corrected reprint of the 1983 original, with a new preface by Perrin. · Zbl 0874.20040
[29] Adam Marcus and G´abor Tardos. Excluded permutation matrices and the Stanley-Wilf conjecture. J. Combin. Theory Ser. A, 107(1):153-160, 2004. · Zbl 1051.05004
[30] Jean-Christophe Novelli, Jean-Yves Thibon, and Nicolas M. Thi´ery. Alg‘ebres de Hopf de graphes.C. R. Math. Acad. Sci. Paris, 339(9):607-610, 2004. doi:10.1016/j.crma.2004.09.012, arXiv:0812.3407v1 [math.CO]. · Zbl 1062.16046
[31] C. St. J. A. Nash-Williams. On well-quasi-ordering finite trees. Proc. Cambridge Philos. Soc., 59:833-835, 1963. · Zbl 0122.25001
[32] Djamila Oudrar and Maurice Pouzet. Profile and hereditary classes of relational structures. In H.Ait Haddadene, I.Bouchemakh, M.Boudar, and S.Bouroubi the electronic journal of combinatorics 20(2) (2013), #P133 (LAID3), editors, Proceedings ISOR’11, International Symposium on Operational Research, Algiers, Algeria, May 30-June 2, 2011. · Zbl 1393.05036
[33] Maurice Pouzet. Un bel ordre d’abritement et ses rapports avec les bornes d’une multirelation. C. R. Acad. Sci. Paris S´er. A-B, 274:A1677-A1680, 1972. · Zbl 0254.08001
[34] Maurice Pouzet. Application d’une propri´et´e combinatoire des parties d’un ensemble aux groupes et aux relations. Math. Z., 150(2):117-134, 1976. · Zbl 0327.20002
[35] Maurice Pouzet. Sur la th´eorie des relations. Th‘ese d’´etat, Universit´e ClaudeBernard, Lyon 1, 1978.
[36] Maurice Pouzet. Relation minimale pour son ˆage. Z. Math. Logik Grundlag. Math., 25(4):315-344, 1979. · Zbl 0481.04002
[37] Maurice Pouzet. The asymptotic behavior of a class of counting functions. In M. Deza and I. G. Rosenberg, editors, Combinatorics 79. Part II, Proceedings of the Colloquium held at the University of Montr´eal, Montreal, Que., June 11-16, 1979, volume 9, pages 223-224. Elsevier, 1980.
[38] M. Pouzet.Relations impartibles.Dissertationes Math. (Rozprawy Mat.), 193:43, 1981. · Zbl 0521.04001
[39] Maurice Pouzet. Application de la notion de relation presque-enchaˆınable au d´enombrement des restrictions finies d’une relation. Z. Math. Logik Grundlag. Math., 27(4):289-332, 1981. · Zbl 0499.03019
[40] Maurice Pouzet. The profile of relations. Glob. J. Pure Appl. Math., 2(3):237– 272, 2006. · Zbl 1120.03022
[41] Maurice Pouzet. When is the orbit algebra of a group an integral domain? Proof of a conjecture of P. J. Cameron. Theor. Inform. Appl., 42(1):83-103, 2008. · Zbl 1146.03015
[42] Maurice Pouzet and Mohamed Sobrani. Sandwiches of ages. In Proceedings of the XIth Latin American Symposium on Mathematical Logic (M´erida, 1998), volume 108, pages 295-326, 2001. · Zbl 0987.03043
[43] Maurice Pouzet and Nicolas M. Thi´ery. Some relational structures with polynomial growth and their associated algebras.In Proceedings of FPSAC’05 Taormina, 2005. arXiv:0601256 [math.CO]. · Zbl 1267.05304
[44] Maurice Pouzet and Nicolas M. Thi´ery. Some relational structures with polynomial growth and their associated algebras. In Youssef Boudabbous and Nejib Zaguia, editors, ROGICS’08: International Conference on Relations, Orders and Graphs: Interaction with Computer Science, 12-17 may, 2008 Mahdia, Tunisia. Nouha, 2008. arXiv:0801.4404v1 [math.CO].
[45] Maurice Pouzet and Nicolas M. Thi´ery. Some relational structures with polynomial growth and their associated algebras II: Finite generation. 2012. In preparation, 20 pages.
[46] C. Ryll-Nardzewski. On the categoricity in power 6 ℵ0. Bull. Acad. Polon. Sci. S´er. Sci. Math. Astr. Phys., 7:545-548., 1959. the electronic journal of combinatorics 20(2) (2013), #P134 · Zbl 0117.01101
[47] James H. Schmerl. Coinductive ℵ0-categorical theories. J. Symbolic Logic, 55(3):1130-1137, 1990. · Zbl 0724.03022
[48] R. Sedgewick and P. Flajolet. Analysis of algorithms. Addison Wesley, 42:192, 1996. · Zbl 0841.68059
[49] Richard P. Stanley. Enumerative combinatorics. Vol. 1, volume 49 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1997. With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986 original. · Zbl 0889.05001
[50] Nicolas M. Thi´ery and St´ephan Thomass´e. Convex cones and SAGBI bases of permutation invariants. In Invariant theory in all characteristics, volume 35 of CRM Proc. Lecture Notes, pages 259-263. Amer. Math. Soc., Providence, RI, 2004. arXiv:0607380 [math.AC]. · Zbl 1086.13502
[51] V. Vatter. Small permutation classes. Proceedings of the London Mathematical Society, 103(5):879-921, 2011. arXiv:0712.4006. · Zbl 1258.05004
[52] J. H. van Lint and R. M. Wilson. A course in combinatorics. Cambridge University Press, Cambridge, 1992. · Zbl 0769.05001
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.