Search

We exhibit a procedure to asymptotically enumerate monotone grid classes of permutations. This is then applied to compute the asymptotic number of permutations in any connected one-corner class. Our strategy consists of enumerating the gridded permutations, finding the asymptotic distribution of points between the cells in a typical large gridded permutation, and analysing in detail the ways in which a typical permutation can be gridded. We also determine the limit shape of any connected monotone grid class., Comment: 40 pages

We present some results on the proportion of permutations of length $n$ containing certain mesh patterns as $n$ grows large, and give exact enumeration results in some cases. In particular, we focus on mesh patterns where entire rows and columns are shaded. We prove some general results which apply to mesh patterns of any length, and then consider mesh patterns of length four. An important consequence of these results is to show that the proportion of permutations containing a mesh pattern can take a wide range of values between $0$ and $1$.

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 -3.$ 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\'ona. 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.

We prove that permutations with few inversions exhibit a local-global dichotomy in the following sense. Suppose ${\boldsymbol\sigma}$ is a permutation chosen uniformly at random from the set of all permutations of $[n]$ with exactly $m=m(n)\ll n^2$ inversions. If $i

A permutation is centrosymmetric if it is fixed by a half-turn rotation of its diagram. Initially motivated by a question by Alexander Woo, we investigate the question of whether the growth rate of a permutation class equals the growth rate of its even-size centrosymmetric elements. We present various examples where the latter growth rate is strictly less, but we conjecture that the reverse inequality cannot occur. We conjecture that equality holds if the class is sum closed, and we prove this conjecture in the special case where the growth rate is at most $\xi \approx 2.30522$, using results from Pantone and Vatter on growth rates less than $\xi$. We prove one direction of inequality for sum closed classes and for some geometric grid classes. We end with preliminary findings on new kinds of growth-rate thresholds that are a little bit larger than $\xi$., Comment: 20 pages. Major changes from v1 to v2: Removed Prop. 4.2 for being very false (thank you to those at Permutation Patterns 2018 who alerted me to this), added some figures and tables, and added a new section on avoiding a monotone pattern. Major changes from v2 to v3 (current): switched Secs. 4.1 and 4.2, and added a summary of the algebraic-geometry motivations of my main question (in Sec. 1.3)

We prove that the set of growth rates of permutation classes includes an infinite sequence of intervals whose infimum is $\theta_B\approx2.35526$, and that it also contains every value at least $\lambda_B\approx2.35698$. These results improve on a theorem of Vatter, who determined that there are permutation classes of every growth rate at least $\lambda_A\approx2.48187$. Thus, we also refute his conjecture that the set of growth rates below $\lambda_A$ is nowhere dense. Our proof is based upon an analysis of expansions of real numbers in non-integer bases, the study of which was initiated by R\'enyi in the 1950s. In particular, we prove two generalisations of a result of Pedicini concerning expansions in which the digits are drawn from sets of allowed values., Comment: 20 pages, 10 figures, ancillary files containing computer-aided calculations included

The class Av(1324), of permutations avoiding the pattern 1324, is one of the simplest sets of combinatorial objects to define that has, thus far, failed to reveal its enumerative secrets. By considering certain large subsets of the class, which consist of permutations with a particularly regular structure, we prove that the growth rate of the class exceeds 9.81. This improves on a previous lower bound of 9.47. Central to our proof is an examination of the asymptotic distributions of certain substructures in the Hasse graphs of the permutations. In this context, we consider occurrences of patterns in {\L}ukasiewicz paths and prove that in the limit they exhibit a concentrated Gaussian distribution., Comment: 20 pages, 12 figures

We prove that the number of permutations avoiding an arbitrary consecutive pattern of length m is asymptotically largest when the avoided pattern is 12...m, and smallest when the avoided pattern is 12...(m-2)m(m-1). This settles a conjecture of the author and Noy from 2001, as well as another recent conjecture of Nakamura. We also show that among non-overlapping patterns of length m, the pattern 134...m2 is the one for which the number of permutations avoiding it is asymptotically largest.

We investigate the number of symmetric matrices of non-negative integers with zero diagonal such that each row sum is the same. Equivalently, these are zero diagonal symmetric contingency tables with uniform margins, or loop-free regular multigraphs. We determine the asymptotic value of this number as the size of the matrix tends to infinity, provided the row sum is large enough. We conjecture that our answer is valid for all row sums.