1999/08/25 by Richard Arratia · 7 citations
Mathematics · Engineering · #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #graph theory and CDMA systems #Combinatorics #Conjecture #Mathematics #Sigma #Permutation (music) #Limit (mathematics) #Discrete mathematics #Physics
paper · pdf · doi:10.37236/1477
openalex publication_date 1999/08/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/09
Consider, for a permutation σ ∈ \cal Sk, the number F(n,σ) of permutations in \cal Sn which avoid σ as a subpattern. The conjecture of Stanley and Wilf is that for every σ there is a constant c(σ) < ∞ such that for all n, F(n,σ) ≤ c(σ)n. All the recent work on this problem also mentions the "stronger conjecture" that for every σ, the limit of F(n,σ)1/n exists and is finite. In this short note we prove that the two versions of the conjecture are equivalent, with a simple argument involving subadditivity We also discuss n-permutations, containing all σ ∈ \cal Sk as subpatterns. We prove that this can be achieved with n=k2, we conjecture that asymptotically n ∼ (k/e)2 is the best achievable, and we present Noga Alon's conjecture that n ∼ (k/2)2 is the threshold for random permutations.