Expected Length of the Longest Common Subsequence of Multiple Strings

We study the generalized Chvátal-Sankoff constant ${\gamma }_{k,d}$, which represents the normalized expected length of the longest common subsequence (LCS) of $d$ independent uniformly random strings over an alphabet of size $k$. We derive asymptotically tight bounds for ${\gamma }_{2,d}$, establishing that ${\gamma }_{2,d}=\frac{1}{2}+\mathrm{\Theta }\left(\frac{1}{\sqrt{d}}\right)$. We also derive asymptotically near-optimal bounds on ${\gamma }_{k,d}$ for $d\ge \mathrm{\Omega }(\log k)$.