Log-concavity and q-Log-convexity Conjectures on the Longest Increasing Subsequences of Permutations
William Y.C. Chen
Abstract: Let P_{n,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 M_{2n, k} be the number of matchings on [2n] with crossing number k. Define P_{n}(x)= ∑_{k} P_{n,k}x^{k} and M_{2n}(x)=∑_{k} M_{2n,k}x^{k}. We propose some conjectures on the log-concavity and q-log-convexity of the polynomials P_{n}(x) and M_{2n}(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 M_{2n}(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 |