Log-concavity and q-Log-convexity Conjectures on the Longest Increasing Subsequences of Permutations

William Y.C. Chen

  Abstract:  Let Pn,k be the number of permutations π on [n]={1, 2,..., n} such that the length of the longest increasing subsequences of π equals k, and let M2n, k be the number of matchings on [2n] with crossing number k. Define Pn(x)= k Pn,kxk and M2n(x)=k M2n,kxk. We propose some conjectures on the log-concavity and q-log-convexity of the polynomials Pn(x) and M2n(x). We also introduce the notions of ∞-q-log-convexity and ∞-q-log-concavity, and the notion of higher order log-concavity with respect to ∞-q-log-convex or ∞-q-log-concavity. A conjecture on the ∞-q-log-convexity of the Boros-Moll polynomials is presented. It seems that M2n(x) are log-concave of any order with respect to ∞-q-log-convexity.

  AMS Classification:  05A20, 05E99.

  Keywords:  crossing number, log-concavity, longest increasing subsequences, matching, nesting number, q-log-concavity, q-log-convexity, strong q-log-convexity, Boros-Moll polynomials

  Download:   PDF