Schur positivity and log-concavity related to longest increasing subsequences

Chen proposed a conjecture on the log-concavity of the generating function for the symmetric group with respect to the length of longest increasing subsequences of permutations. Motivated by Chen’s log-concavity conjecture, Bóna, Lackner and Sagan further studied similar problems by restricting the whole symmetric group to certain of its subsets. They obtained the log-concavity of the corresponding generating functions for these subsets by using the hook-length formula. In this paper, we generalize and prove their results by establishing the Schur positivity of certain symmetric functions. This also enables us to propose a new approach to Chen’s original conjecture.     

Law of large numbers for increasing subsequences of random permutations

Let the random variable Z_n,k denote the number of increasing subsequences of length k in a random permutation from S_n, the symmetric group of permutations of {1,…,n}. We show that Var(Z) = o((EZ)²) as n → ∞ if and only if . In particular then, the weak law of large numbers holds for Z if ; that is, We also show the following approximation result for the uniform measure U_n on S_n. Define the probability measure μ on S_n by where U denotes the uniform measure on the subset of permutations that contain the increasing subsequence {x₁,x₂,…,x}. Then the weak law of large numbers holds for Z if and only if where ∣∣˙∣∣ denotes the total variation norm. In particular then, (*) holds if . In order to evaluate the asymptotic behavior of the second moment, we need to analyze occupation times of certain conditioned two‐dimensional random walks. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Efficient algorithms for the longest common subsequence problem with sequential substring constraints

In this paper, we generalize the inclusion constrained longest common subsequence (CLCS) problem to the hybrid CLCS problem which is the combination of the sequence inclusion CLCS and the string inclusion CLCS, called the sequential substring constrained longest common subsequence   (SSCLCS) problem. In the SSCLCS problem, we are given two strings A$A$ and B$B$ of lengths m$m$ and n$n$, respectively, formed by alphabet Σ$\Sigma$ and a constraint sequence C$C$ formed by ordered strings (C¹,C²,C³,…,C^l)$(C^1,C^2,C^3,\dots ,C^l)$ with total length r$r$. The problem is that of finding the longest common subsequence D$D$ of A$A$ and B$B$ containing C¹,C²,C³,…,C^l$C^1,C^2,C^3,\dots ,C^l$ as substrings and with the order of the C$C$’s retained. This problem has two variants, depending on whether the strings in C$C$ cannot overlap or may overlap. We propose algorithms with O(mnl+(m+n)(|Σ|+r))$O(mnl+(m+n)(\left|\Sigma \right|+r))$ and O(mnr+(m+n)|Σ|)$O(mnr+(m+n)\left|\Sigma \right|)$ time for the two variants. For the special case with one or two constraints, our algorithm runs in O(mn+(m+n)(|Σ|+r))$O(mn+(m+n)(\left|\Sigma \right|+r))$ or O(mnr+(m+n)|Σ|)$O(mnr+(m+n)\left|\Sigma \right|)$ time, respectively—an order faster than the algorithm proposed by Chen and Chao.     

Fast algorithms for identifying maximal common connected sets of interval graphs

Given a family of interval graphs F={G₁=(V,E₁),…,G_k=(V,E_k)} on the same vertices V, a set S⊂V is a maximal common connected set of F if the subgraphs of G_i,1?i?k, induced by S are connected in all G_i and S is maximal for the inclusion order. The maximal general common connected set for interval graphs problem (gen-CCPI) consists in efficiently computing the partition of V in maximal common connected sets of F. This problem has many practical applications, notably in computational biology. Let n=|V| and . For k?2, an algorithm in O((kn+m)logn) time is presented in Habib et al. [Maximal common connected sets of interval graphs, in: Combinatorial Pattern Matching (CPM), Lecture Notes in Computer Science, vol. 3109, Springer, Berlin, 2004, pp. 359-372]. In this paper, we improve this bound to O(knlogn+m). Moreover, if the interval graphs are given as k sets of n intervals, which is often the case in bioinformatics, we present a simple time algorithm.     

Iterative algorithms for finding common solutions of variational inequalities and systems of equilibrium problems and fixed points of families and semigroups of nonexpansive mappings

We introduce iterative algorithms for finding a common element of the set of solutions of a system of equilibrium problems and of the set of fixed points of a finite family and a left amenable semigroup of nonexpansive mappings in a Hilbert space. We prove the strong convergence of the proposed iterative algorithm to the unique solution of a variational inequality, which is the optimality condition for a minimization problem. Our results extend, for example, the recent result of [V. Colao, G. Marino, H.K. Xu, An Iterative Method for finding common solutions of equilibrium and fixed point problems, J. Math. Anal. Appl. 344 (2008) 340–352] to systems of equilibrium problems.