School of Mathematics and Statistics - Research Publications

Permanent URI for this collection

Search Results

Now showing 1 - 10 of 11
  • Item
    Thumbnail Image
    Classical Length-5 Pattern-Avoiding Permutations
    Clisby, N ; Conway, AR ; Guttmann, AJ ; Inoue, Y (The Electronic Journal of Combinatorics, 2022-01-01)
    We have made a systematic numerical study of the 16 Wilf classes of length-5 classical pattern-avoiding permutations from their generating function coefficients. We have extended the number of known coefficients in fourteen of the sixteen classes. Careful analysis, including sequence extension, has allowed us to estimate the growth constant of all classes, and in some cases to estimate the sub-dominant power-law term associated with the exponential growth. In six of the sixteen classes we find the familiar power-law behaviour, so that the coefficients behave like $s_n \sim C \cdot \mu^n \cdot n^g,$ while in the remaining ten cases we find a stretched exponential as the most likely sub-dominant term, so that the coefficients behave like $s_n \sim C \cdot \mu^n \cdot \mu_1^{n^\sigma} \cdot n^g,$ where $0 < \sigma < 1.$ We have also classified the 120 possible permutations into the 16 distinct classes. We give compelling numerical evidence, and in one case a proof, that all 16 Wilf-class generating function coefficients can be represented as moments of a non-negative measure on $[0,\infty)$. Such sequences are known as Stieltjes moment sequences. They have a number of nice properties, such as log-convexity, which can be used to provide quite strong rigorous lower bounds. Stronger bounds still can be established under plausible monotonicity assumptions about the terms in the continued-fraction expansion of the generating functions implied by the Stieltjes property. In this way we provide strong (non-rigorous) lower bounds to the growth constants, which are sometimes within a few percent of the exact value.
  • Item
    Thumbnail Image
    Asymptotics of 3-Stack-Sortable Permutations
    Defant, C ; Price, AE ; Guttmann, AJ (ELECTRONIC JOURNAL OF COMBINATORICS, 2021-06-18)
    We derive a simple functional equation with two catalytic variables characterising the generating function of 3-stack-sortable permutations. Using this functional equation, we extend the 174-term series to 1000 terms. From this series, we conjecture that the generating function behaves as  $$W(t) \sim C_0(1-\mu_3 t)^\alpha \cdot \log^\beta(1-\mu_3 t), $$ so that $$[t^n]W(t)=w_n \sim \frac{c_0\mu_3^n}{  n^{(\alpha+1)}\cdot \log^\lambda{n}} ,$$ where $\mu_3 = 9.69963634535(30),$ $\alpha = 2.0 \pm 0.25.$ If $\alpha = 2$ exactly, then $\lambda = -\beta+1$, and we estimate $\beta \approx -2,$ but with a wide uncertainty of $\pm 1.$  If $\alpha$ is not an integer, then $\lambda=-\beta$, but we cannot give a useful estimate of $\beta$. The growth constant estimate (just) contradicts a conjecture of the first author that $$9.702 < \mu_3 \le 9.704.$$ We also prove a new rigorous lower bound of $\mu_3\geq 9.4854$, allowing us to disprove a conjecture of Bóna.  We then further extend the series using differential-approximants to obtain approximate coefficients $O(t^{2000}),$ expected to be accurate to $20$ significant digits, and use the approximate coefficients to provide additional evidence supporting the results obtained from the exact coefficients.
  • Item
    Thumbnail Image
    Self-avoiding walks in a rectangle
    Guttmann, AJ ; Kennedy, T (SPRINGER, 2014-02-01)
  • Item
    Thumbnail Image
    The Critical Fugacity for Surface Adsorption of Self-Avoiding Walks on the Honeycomb Lattice is
    Beaton, NR ; Bousquet-Melou, M ; de Gier, J ; Duminil-Copin, H ; Guttmann, AJ (SPRINGER, 2014-03-01)
  • Item
    Thumbnail Image
    Compressed self-avoiding walks, bridges and polygons
    Beaton, NR ; Guttmann, AJ ; Jensen, I ; Lawler, GF (IOP PUBLISHING LTD, 2015-11-13)
  • Item
  • Item
    Thumbnail Image
    Scaling function and universal amplitude combinations for self-avoiding polygons
    Richard, C ; Guttmann, AJ ; Jensen, I (IOP PUBLISHING LTD, 2001-09-14)
  • Item
    Thumbnail Image
    The perimeter generating function of punctured staircase polygons
    Guttmann, AJ ; Jensen, I (IOP PUBLISHING LTD, 2006-04-14)
  • Item
    Thumbnail Image
    Scaling prediction for self-avoiding polygons revisited
    Richard, C ; Jensen, I ; Guttmann, AJ (IOP PUBLISHING LTD, 2004-08-01)
  • Item
    Thumbnail Image
    Vicious walkers, friendly walkers, and young tableaux. III. Between two walls
    Krattenthaler, C ; Guttmann, AJ ; Viennot, XG (SPRINGER, 2003-03-01)