Source-linked AI summary
Typical growth of the F\"uredi-Hajnal and Stanley-Wilf limits
Jesse Geneson
TL;DR
For a uniformly random permutation matrix, the growth of the Füredi–Hajnal and Stanley–Wilf limits is the paper’s focus. The authors use random translates of row and column intervals and an asymmetric local lemma; Theorem 1 determines the power of k in the logarithms of both limits.
Problem
Fox proved an exp(O(k)) upper bound for c(P) and lower bounds of exp(k^Ω(1)) for both limits for almost all permutations.
Source: §1 · p. 1Method
The proof places row and column intervals at random translates, applies an asymmetric local lemma, deletes rows and columns with many zeros, and then uses Cibulka and Kynčl’s theorem [4, Theorem 1.5].
Source: §1 · p. 2Results
Theorem 1 determines the power of k in the logarithms of both limits.
Source: §1 · p. 2Takeaways & Limitations
The paper’s theorem and earlier bounds give a conclusion about the growth exponent of both limits for typical permutations.
Source: §1 · p. 2For almost all permutations, the bounds on log c(Pk) still differ by a factor of order (log k)^3.
Source: §4 · p. 5
Abstract
from arXiv · showhide
We prove that the F\"uredi-Hajnal limit and the Stanley-Wilf limit of a uniformly random permutation matrix of order $k$ are at most $\exp\bigl(O(\sqrt{k}(\log k)^{5/2})\bigr)$ with probability tending to one as $k\to\infty$. This improves the bound $\exp\bigl(O(k^{2/3}(\log k)^{7/3}/(\log\log k)^{1/3})\bigr)$ of Cibulka and Kyn\v{c}l. Together with the lower bound due to Fox, these bounds show that the logarithms of both limits are $k^{1/2+o(1)}$ for almost all permutations.
1 Introduction
The introduction frames how the two limits grow for typical forbidden permutations and presents an improved upper bound holding with probability tending to one. Its proof route controls cell occupancies and uses that control to bound the limits.
- The Furedi–Hajnal limit is the limiting extremal density, while the Stanley–Wilf limit is the limiting exponential growth rate of avoiding permutations.Source: §1 · p. 1
- Fox showed both limits are at least exp(k^Ω(1)) for almost all permutations; the stronger lower bound holds with probability tending to one.Source: §1 · pp. 1–2
- With probability tending to one, the paper improves the previous upper bound for both limits of a uniformly random order-k permutation matrix.Source: §1 · p. 2
- At s = ⌈√k log k⌉, the largest cell occupancy is O(log k) with probability tending to one, providing the random-permutation input to the theorem.Source: §1 · p. 2
- The embedding argument independently translates row and column intervals, then applies the asymmetric local lemma to find P when each row and column has few zeros.Source: §1 · p. 2
2 A bound from cell occupancies
This section bounds pattern-avoiding matrices by showing that matrices with few zeros per row and column contain the pattern, then converting that embedding guarantee into an extremal bound.
2 A bound from cell occupancies
- For permutation matrix P of order k ≥ 2 and integer 1 ≤ s ≤ k, every 2s⌈k/s⌉ × 2s⌈k/s⌉ zero-one matrix with at most s/(32t) zeros in each row and column contains P, where t = ts(P).Here ts(P) is the maximum number of ones in any cell Ia × Ib.Source: §2 · pp. 2–3
- Independent shifts map the pattern’s rows and columns increasingly into the matrix, and the local lemma ensures no pattern one lands on a zero.An event’s probability is bounded by the number of zeros in its corresponding 2s × 2s cell divided by s²; each cell contains at most t pattern ones.Source: §2 · pp. 3–4
- Deleting the k rows and then k columns with the most zeros leaves a 3k × 3k matrix containing a submatrix to which the embedding lemma applies.The argument begins with a 4k × 4k matrix having at most B = ks/(32t) zeros.Source: §2 · p. 4
- Every P-avoiding matrix of order 4k has more than B zeros, giving ex(4k, P) < 16k² − B = q(4k)², where q = 1 − s/(512tk).The Cibulka–Kynčl theorem is then applied to convert this extremal-density bound into a bound on the relevant limit.Source: §2 · p. 4
3 Random permutations
The proof controls cell occupancies in a random permutation, then uses the cell-occupancy bound to obtain typical upper bounds for both limits.
3 Random permutations
- Each s × s cell has expected occupancy asymptotic to log k, and a union bound shows every cell has fewer than h = ⌈16 log k⌉ ones with probability tending to one.The proof bounds the probability that any fixed cell has at least h ones, then takes a union bound over at most k² cells.Source: §3 · p. 4
- With probability tending to one, ts(Pk) < h = O(log k), and therefore kts(Pk)/s = O(√k log k).Theorem 3 uses this occupancy estimate to obtain the upper bound for log c(Pk).Source: §3 · p. 5
- With probability tending to one, ts(Pk) < h = O(log k), and therefore k ts(Pk)/s = O(√k log k).Source: §3 · p. 5
4 Concluding remarks
The typical upper and lower bounds remain separated by a logarithmic factor, leaving their sharper asymptotic order unresolved.
4 Concluding remarks
- For almost all permutations, the bounds on log c(Pk) differ by a factor of order (log k)³, and the same gap holds for log L(Pk).The paper asks whether log c(Pk) = Θ(√k) with probability tending to one; by equation (1), the corresponding question for log L(Pk) is equivalent.Source: §4 · p. 5
Declaration of generative AI and AI-assisted technologies
The author reports AI assistance with proof work and manuscript revision, while retaining responsibility for the article’s content.
Declaration of generative AI and AI-assisted technologies
- GPT-6 Astra Ultra assisted with finding and checking proofs and revising the manuscript; the author read and edited the proofs and takes responsibility for the article’s content.Source: Declaration of generative AI and… · p. 5