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

Abstract: Let

P_{n, k}

be the number of permutations

p i

on [n]={1, 2,..., n} such that the length of the longest increasing subsequences of

p i

equals k, and let

M_{2 n, k}

be the number of matchings on [2n] with crossing number k. Define

P_{n} (x) = s u m_{k} P_{n, k} x^{k}

and

M_{2 n} (x) = s u m_{k} M_{2 n, k} x^{k}

. We propose some conjectures on the log-concavity and q-log-convexity of the polynomials

P_{n} (x)

and

M_{2 n} (x)

. We also introduce the notions of

i n f t y

-q-log-convexity and

i n f t y

-q-log-concavity, and the notion of higher order log-concavity with respect to

i n f t y

-q-log-convex or

i n f t y

-q-log-concavity. A conjecture on the

i n f t y

-q-log-convexity of the Boros-Moll polynomials is presented. It seems that

M_{2 n} (x)

are log-concave of any order with respect to

i n f t y

-q-log-convexity.

This page was built for publication: Log-concavity and q-Log-convexity Conjectures on the Longest Increasing Subsequences of Permutations