On a Speculated Relation Between Chvátal–Sankoff Constants of Several Sequences
M. KIWI, J. SOTO · Combinatorics Probability Computing · 2009
It is well known that, when normalized byn, the expected length of a longest common subsequence ofdsequences of lengthnover an alphabet of size σ converges to a constant γσ,d. We disprove a speculation by Steele regarding a possible relation between γ2,dand γ2,2. In order to do that we also obtain some new lower bounds for γσ,d, when both σ anddare small integers.