Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-09T03:30:07.863Z Has data issue: false hasContentIssue false
  • English
  • Français

Growing at a Perfect Speed

Published online by Cambridge University Press:  01 May 2009

M. H. ALBERT  and
S. A. LINTON
M. H. ALBERT
Affiliation:
Department of Computer Science, University of Otago, Dunedin, New Zealand (e-mail: malbert@cs.otago.ac.nz)
S. A. LINTON
Affiliation:
Centre for Interdisciplinary Research in Computational Algebra, University of St Andrews, Fife, Scotland (e-mail: sal@dcs.st-and.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A collection of permutation classes is exhibited whose growth rates form a perfect set, thereby refuting some conjectures of Balogh, Bollobás and Morris.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 18 , Issue 3 , May 2009 , pp. 301 - 308
Copyright
Copyright © Cambridge University Press 2009

References

[1]Albert, M. H. (2007) On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation. Random Struct. Alg. 31 227–238.CrossRefGoogle Scholar
[2]Albert, M. H., Atkinson, M. D. and Ruškuc, N. (2003) Regular closed sets of permutations. Theoret. Comput. Sci. 306 85–100.CrossRefGoogle Scholar
[3]Balogh, J., Bollobás, B. and Morris, R. (2006) Hereditary properties of ordered graphs. In Topics in Discrete Mathematics, Vol. 26 of Algorithms Combin., Springer, Berlin, pp. 179–213.CrossRefGoogle Scholar
[4]Delgado, M., Linton, S. and Morais, J. (2007) Automata: A GAP package (1.10). http://cmup.fc.up.pt/cmup/mdelgado/automata/Google Scholar
[5]GAP: Groups, Algorithms, and Programming, Version 4.4.10 (2007). http://www.gap-system.orgGoogle Scholar
[6]Huczynska, S. and Vatter, V.Grid classes and the Fibonacci dichotomy for restricted permutations. Electron. J. Combin. 13 #54 (electronic).Google Scholar
[7]Kaiser, T. and Klazar, M. (2002/03) On growth rates of closed permutation classes. Electron. J. Combin. 9 #10 (electronic).Google Scholar
[8]Marcus, A. and Tardos, G. (2004) Excluded permutation matrices and the Stanley–Wilf conjecture. J. Combin. Theory Ser. A 107 153–160.CrossRefGoogle Scholar
[9]Vatter, V. Small permutation classes (preprint) arXiv:0712.4006v2 [Math.CO].Google Scholar