Some general results in combinatorial enumeration  pp. 3-40

Some general results in combinatorial enumeration

By Martin Klazar
[100] N. Robertson and P. Seymour . Graph minors i–xx. J. Combinatorial Theory Ser. B, 1983–2004.
[101] A. Salomaa . Formal languages. Academic Press [Harcourt Brace Jovanovich Publishers], New York, 1973. ACM Monograph Series.
[102] A. Salomaa and M. Soittola . Automata-theoretic aspects of formal power series. Springer-Verlag, New York, 1978. Texts and Monographs in Computer Science.
[103] E. R. Scheinerman and J. Zito . On the size of hereditary classes of graphs. J. Combin. Theory Ser. B, 61(1):16–39, 1994.
[104] S. Shelah . Spectra of monadic second order sentences. Sci. Math. Jpn., 59(2):351–355, 2004.
[105] S. Shelah and M. Doron . Bounded m-ary patch-width are equivalent for m > 2. arXiv:math/0607375v1 [math.LO].
[106] R. Simion . Noncrossing partitions. Discrete Math., 217(1-3):367–409, 2000. Formal power series and algebraic combinatorics (Vienna, 1997).
[107] E. Specker . Application of logic and combinatorics to enumeration problems. In Trends in theoretical computer science (Udine, 1984), volume 12 of Principles Comput. Sci. Ser., pages 143–169. Computer Sci. Press, Rockville, MD, 1988.
[108] E. Specker . Modular counting and substitution of structures. Combin. Probab. Comput., 14(1-2):203–210, 2005.
[109] J. Spencer . The strange logic of random graphs, volume 22 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 2001.
[10] M. D. Atkinson , M. M. Murphy , and N. Ruškuc . Partially well-ordered closed sets of permutations. Order, 19(2):101–113, 2002.
[110] R. P. Stanley . Solution to problem E2546. Amer. Math. Monthly, 83(10):813–814, 1976.
[111] R. P. Stanley . Enumerative combinatorics. Vol. 1, volume 49 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 1997.
[112] R. P. Stanley . Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999.
[113] V. I. Trofimov . Growth functions of some classes of languages. Cybernetics, 17:727–731, 1982. translated from Kibernetika (1981), 9–12.
[114] V. Vatter . Permutation classes of every growth rate above 2.48188. Mathematika, 56:182–192, 2010.
[115] V. Vatter . Small permutation classes. arXiv:0712.4006v2 [math.CO].
[116] V. Vatter . Enumeration schemes for restricted permutations. Combin. Probab. Comput., 17:137–159, 2008.
[117] H. S. Wilf . What is an answer? Amer. Math. Monthly, 89(5):289–292, 1982.
[11] J. Balogh and B. Bollobás . Hereditary properties of words. Theor. Inform. Appl., 39(1):49–65, 2005.
[12] J. Balogh , B. Bollobás , and R. Morris . Hereditary properties of ordered graphs. In M. Klazar , J. Kratochvíl , M. Loebl , J. Matoušek , R. Thomas , and P. Valtr , editors, Topics in discrete mathematics, volume 26 of Algorithms Combin., pages 179–213. Springer, Berlin, 2006.
[13] J. Balogh , B. Bollobás , and R. Morris . Hereditary properties of partitions, ordered graphs and ordered hypergraphs. European J. Combin., 27(8):1263–1281, 2006.
[14] J. Balogh , B. Bollobás , and R. Morris . Hereditary properties of combinatorial structures: posets and oriented graphs. J. Graph Theory, 56(4):311–332, 2007.
[15] J. Balogh , B. Bollobás , and R. Morris . Hereditary properties of tournaments. Electron. J. Combin., 14(1):Research Paper 60, 25 pp., 2007.
[16] J. Balogh , B. Bollobás , M. Saks , and V. T. Sós . The unlabeled speed of a hereditary graph property. Preprint.
[17] J. Balogh , B. Bollobás , and M. Simonovits . The number of graphs without forbidden subgraphs. J. Combin. Theory Ser. B, 91(1):1–24, 2004.
[18] J. Balogh , B. Bollobás , and D. Weinreich . The speed of hereditary properties of graphs. J. Combin. Theory Ser. B, 79(2):131–156, 2000.
[19] J. Balogh , B. Bollobás , and D. Weinreich . The penultimate rate of growth for graph properties. European J. Combin., 22(3):277–289, 2001.
[1] M. H. Albert and M. D. Atkinson . Simple permutations and pattern restricted permutations. Discrete Math., 300(1-3):1–15, 2005.
[20] J. Balogh , B. Bollobás , and D. Weinreich . Measures on monotone properties of graphs. Discrete Appl. Math., 116(1-2):17–36, 2002.
[21] J. Balogh , B. Bollobás , and D. Weinreich . A jump to the Bell number for hereditary graph properties. J. Combin. Theory Ser. B, 95(1):29–48, 2005.
[22] E. Barcucci , A. Del Lungo , A. Frosini , and S. Rinaldi . From rational functions to regular languages. In Formal power series and algebraic combinatorics (Moscow, 2000), pages 633–644. Springer, Berlin, 2000.
[23] A. Barvinok . The complexity of generating functions for integer points in polyhedra and beyond. In International Congress of Mathematicians. Vol. III, pages 763–787. Eur. Math. Soc., Zürich, 2006.
[24] A. Barvinok and K. Woods . Short rational generating functions for lattice point problems. J. Amer. Math. Soc., 16(4):957–979, 2003.
[25] M. Beck and S. Robins . Computing the continuous discretely. Undergraduate Texts in Mathematics. Springer, New York, 2007.
[26] O. Bernardi , M. Noy , and D. Welsh . On the growth rate of minor-closed classes of graphs. arXiv:06710.2995 [math.CO].
[27] C. Blatter and E. Specker . Le nombre de structures finies d'une théorie à caractère fini. Sci. Math. Fonds Nat. Rec. Sci. Bruxelles, pages 41–44, 1981.
[28] C. Blatter and E. Specker . Modular periodicity of combinatorial sequences. Abstract Amer. Math. Soc., 4:313, 1983.
[29] C. Blatter and E. Specker . Recurrence relations for the number of labeled structures on a finite set. In E. Börger , G. Hasenjaeger , and D. Rödding , editors, Logic and Machines, pages 43–61, 1983.
[2] M. H. Albert , M. D. Atkinson , and R. Brignall . Permutation classes of polynomial growth. Ann. Comb., 11(3–4):249–264, 2007.
[30] B. Bollobás . Hereditary and monotone properties of combinatorial structures. In A. Hilton and J. Talbot , editors, Surveys in Combinatorics 2007, number 346 in London Mathematical Society Lecture Note Series, pages 1–39. Cambridge University Press, 2007.
[31] B. Bollobás and A. Thomason . Projections of bodies and hereditary properties of hypergraphs. Bull. London Math. Soc., 27(5):417–424, 1995.
[32] B. Bollobás and A. Thomason . Hereditary and monotone properties of graphs. In The mathematics of Paul Erdős, II, volume 14 of Algorithms Combin., pages 70–78. Springer, Berlin, 1997.
[33] M. Bóna . Permutations avoiding certain patterns: the case of length 4 and some generalizations. Discrete Math., 175(1-3):55–67, 1997.
[34] M. Bóna . Combinatorics of permutations. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2004.
[35] Y. Boudabbous and M. Pouzet . The morphology of infinite tournaments. application to the growth of their profile. arXiv:0801.4069 [math.CO].
[36] M. Bousquet-Mélou . Algebraic generating functions in enumerative combinatorics and context-free languages. In STACS 2005, volume 3404 of Lecture Notes in Comput. Sci., pages 18–35. Springer, Berlin, 2005.
[37] M. Bousquet-Mélou . Rational and algebraic series in combinatorial enumeration. In International Congress of Mathematicians. Vol. III, pages 789–826. Eur. Math. Soc., Zürich, 2006.
[38] M. R. Bridson and R. H. Gilman . Context-free languages of sub-exponential growth. J. Comput. System Sci., 64(2):308–310, 2002.
[39] R. Brignall . A survey of simple permutations. In this volume, 41–65.
[3] M. H. Albert , M. Elder , A. Rechnitzer , P. Westcott , and M. Zabrocki . On the Wilf-Stanley limit of 4231-avoiding permutations and a conjecture of Arratia. Adv. in Appl. Math., 36(2):95–105, 2006.
[40] R. Brignall , S. Huczynska , and V. Vatter . Simple permutations and algebraic generating functions. J. Combin. Theory Ser. A, 115(3):423–441, 2008.
[41] R. Brignall , N. Ruškuc , and V. Vatter . Simple permutations: decidability and unavoidable substructures. Theoret. Comput. Sci., 391(1–2):150–163, 2008.
[42] S. N. Burris . Number theoretic density and logical limit laws, volume 86 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2001.
[43] P. J. Cameron . Oligomorphic permutation groups, volume 152 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 1990.
[44] P. J. Cameron . Some counting problems related to permutation groups. Discrete Math., 225(1-3):77–92, 2000.
[45] T. Ceccherini-Silberstein . Growth and ergodicity of context-free languages. II. The linear case. Trans. Amer. Math. Soc., 359(2):605–618, 2007.
[46] T. Ceccherini-Silberstein , A. Machi , and F. Scarabotti . On the entropy of regular languages. Theoret. Comput. Sci., 307(1):93–102, 2003.
[47] T. Ceccherini-Silberstein and W. Woess . Growth and ergodicity of context-free languages. Trans. Amer. Math. Soc., 354(11):4597–4625, 2002.
[48] T. Ceccherini-Silberstein and W. Woess . Growth-sensitivity of context-free languages. Theoret. Comput. Sci., 307(1):103–116, 2003.
[49] N. Chomsky and M. P. Schützenberger . The algebraic theory of context-free languages. In Computer programming and formal systems, pages 118–161. North-Holland, Amsterdam, 1963.
[4] M. H. Albert and S. Linton . Growing at a perfect speed. Combin. Probab. Comput., 18:301–308, 2009.
[50] L. Comtet . Advanced combinatorics. D. Reidel Publishing Co., Dordrecht, 1974.
[51] F. D'Alessandro , B. Intrigila , and S. Varricchio . On the structure of the counting function of sparse context-free languages. Theoret. Comput. Sci., 356(1-2):104–117, 2006.
[52] P. de la Harpe . Topics in geometric group theory. Chicago Lectures in Mathematics. University of Chicago Press, Chicago, IL, 2000.
[53] E. Deutsch and B. E. Sagan . Congruences for Catalan and Motzkin numbers and related sequences. J. Number Theory, 117(1):191–215, 2006.
[54] V. Domocoş . Minimal coverings of uniform hypergraphs and P-recursiveness. Discrete Math., 159(1-3):265–271, 1996.
[55] H.-D. Ebbinghaus and J. Flum . Finite model theory. Springer Monographs in Mathematics. Springer-Verlag, Berlin, enlarged edition, 2006.
[56] E. Ehrhart . Sur les polyèdres rationnels homothétiques à n dimensions. C. R. Acad. Sci. Paris, 254:616–618, 1962.
[57] M. Elder and V. Vatter . Problems and conjectures presented at the Third International Conference on Permutation Patterns, University of Florida, March 7–11, 2005. arXiv:0505504 [math.CO].
[58] S.-P. Eu , S.-C. Liu , and Y.-N. Yeh . Catalan and Motzkin numbers modulo 4 and 8. European J. Combin., 29(6):1449–1466, 2008.
[59] E. Fischer . The Specker-Blatter theorem does not hold for quaternary relations. J. Combin. Theory Ser. A, 103(1):121–136, 2003.
[5] M. H. Albert , S. Linton , and N. Ruškuc . The insertion encoding of permutations. Electron. J. Combin., 12(1):Research paper 47, 31 pp., 2005.
[60] E. Fischer and J. A. Makowsky . The Specker-Blatter theorem revisited. In Computing and combinatorics, volume 2697 of Lecture Notes in Comput. Sci., pages 90–101. Springer, Berlin, 2003.
[61] E. Fischer and J. A. Makowsky . On spectra of sentences of monadic second order logic with counting. J. Symbolic Logic, 69(3):617–640, 2004.
[62] P. Flajolet . Analytic models and ambiguity of context-free languages. Theoret. Comput. Sci., 49(2-3):283–309, 1987.
[63] P. Flajolet and R. Sedgewick . Analytic combinatorics. Cambridge University Press, Cambridge, 2009.
[64] R. Fraïssé . Sur quelques classifications des systèmes de relations. PhD thesis, Université de Paris, 1953.
[65] R. Fraïssé . Sur l'extension aux relations de quelques propriétés des ordres. Ann. Sci. Ecole Norm. Sup. (3), 71:363–388, 1954.
[66] R. Fraïssé . Theory of relations, volume 145 of Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Co., Amsterdam, revised edition, 2000.
[67] I. M. Gessel . Symmetric functions and P-recursiveness. J. Combin. Theory Ser. A, 53(2):257–285, 1990.
[68] I. P. Goulden and D. M. Jackson . Labelled graphs with small vertex degrees and P-recursiveness. SIAM J. Algebraic Discrete Methods, 7(1):60–66, 1986.
[69] R. Grigorchuk and I. Pak . Groups of intermediate growth: an introduction. Enseign. Math. (2), 54(3-4):251–272, 2008.
[6] V. E. Alekseev . Range of values of entropy of hereditary classes of graphs. Diskret. Mat., 4(2):148–157, 1992.
[70] R. I. Grigorchuk . On the Milnor problem of group growth. Dokl. Akad. Nauk SSSR, 271(1):30–33, 1983.
[71] G. Higman . Ordering by divisibility in abstract algebras. Proc. London Math. Soc. (3), 2:326–336, 1952.
[72] S. Huczynska and V. Vatter . Grid classes and the Fibonacci dichotomy for restricted permutations. Electron. J. Combin., 13:Research paper 54, 14 pp., 2006.
[73] R. Incitti . The growth function of context-free languages. Theoret. Comput. Sci., 255(1-2):601–605, 2001.
[74] Y. Ishigami . The number of hypergraphs and colored hypergraphs with hereditary properties. arXiv:0712.0425v1 [math.CO].
[75] V. Jelínek and M. Klazar . Generalizations of Khovanski's theorems on the growth of sumsets in abelian semigroups. Adv. in Appl. Math., 41(1):115–132, 2008.
[76] T. Kaiser and M. Klazar . On growth rates of closed permutation classes. Electron. J. Combin., 9(2):Research paper 10, 20 pp., 2003.
[77] M. Klazar . Counting pattern-free set partitions. I. A generalization of Stirling numbers of the second kind. European J. Combin., 21(3):367–378, 2000.
[78] M. Klazar . Counting pattern-free set partitions. II. Noncrossing and other hypergraphs. Electron. J. Combin., 7:Research Paper 34, 25 pp., 2000.
[79] M. Klazar . Extremal problems for ordered (hyper) graphs: applications of Davenport-Schinzel sequences. European J. Combin., 25(1):125–140, 2004.
[7] J.-P. Allouche and J. Shallit . Automatic sequences. Cambridge University Press, Cambridge, 2003.
[80] M. Klazar . On the least exponential growth admitting uncountably many closed permutation classes. Theoret. Comput. Sci., 321(2-3):271–281, 2004.
[81] M. Klazar . On growth rates of permutations, set partitions, ordered graphs and other objects. Electron. J. Combin., 15(1):Research paper 75, 22 pp., 2008.
[82] W. F. Lunnon , P. A. B. Pleasants , and N. M. Stephens . Arithmetic properties of Bell numbers to a composite modulus. I. Acta Arith., 35(1):1–16, 1979.
[83] I. G. Macdonald . The volume of a lattice polyhedron. Proc. Cambridge Philos. Soc., 59:719–726, 1963.
[84] I. G. Macdonald . Polynomials associated with finite cell-complexes. J. London Math. Soc. (2), 4:181–192, 1971.
[85] H. D. Macpherson . Growth rates in infinite graphs and permutation groups. Proc. London Math. Soc. (3), 51(2):285–294, 1985.
[86] H. D. Macpherson . Orbits of infinite permutation groups. Proc. London Math. Soc. (3), 51(2):246–284, 1985.
[87] A. Marcus and G. Tardos . Excluded permutation matrices and the Stanley-Wilf conjecture. J. Combin. Theory Ser. A, 107(1):153–160, 2004.
[88] D. Marinov and R. Radoičić . Counting 1324-avoiding permutations. Electron. J. Combin., 9(2):Research paper 13, 9 pp., 2003.
[89] C. McDiarmid , A. Steger , and D. J. A. Welsh . Random graphs from planar and other addable classes. In Topics in discrete mathematics, volume 26 of Algorithms Combin., pages 231–246. Springer, Berlin, 2006.
[8] G. E. Andrews . The theory of partitions. Addison-Wesley Publishing Co., Reading, Mass.Mass.-London-Amsterdam, 1976.
[90] M. Mishna . Automatic enumeration of regular objects. J. Integer Seq., 10(5):Article 07.5.5, 18 pp., 2007.
[91] M. J. Mishna . Une approche holonome à la combinatoire algébrique. PhD thesis, Univ. Québec à Montréal, 2003.
[92] M. Morse and G. A. Hedlund . Symbolic Dynamics. Amer. J. Math., 60(4):815–866, 1938.
[93] S. Norine , P. Seymour , R. Thomas , and P. Wollan . Proper minor-closed families are small. J. Combin. Theory Ser. B, 96(5):754–757, 2006.
[94] C. H. Papadimitriou . Computational complexity. Addison-Wesley Publishing Company, Reading, MA, 1994.
[95] M. Pouzet . Sur la théorie des relations. PhD thesis, Université Claude-Bernard, Lyon 1, 1978.
[96] M. Pouzet . Application de la notion de relation presque-enchaînable au dénombrement des restrictions finies d'une relation. Z. Math. Logik Grundlag. Math., 27(4):289–332, 1981.
[97] M. Pouzet . The profile of relations. Glob. J. Pure Appl. Math., 2(3):237–272, 2006.
[98] M. Pouzet and N. M. Thiéry . Some relational structures with polynomial growth and their associated algebras. arXiv:0601256v1 [math.CO].
[99] C. R. Read . Enumeration. In L. W. Beineke and R. J. Wilson , editors, Graph connections, pages 13–33, New York, 1997. The Clarendon Press Oxford University Press.
[9] R. Arratia . On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern. Electron. J. Combin., 6:Note, N1, 4 pp., 1999.