Skip to content
Cairn Commons
X Sign in
Level B · Reproducible Probability P-constant-31a-chvatal-sankoff-constant-for-a-binary-alphabet

Chvátal–Sankoff constant for a binary alphabet

Let λ_n,2 be the random variable assigning two uniformly random binary strings of length n the length of their longest common subsequence. Then C_31a is the (well-defined) limit C_31a := lim_n → inftyE[λ_n,2]/n.

From the catalogue. Imported from Terence Tao and contributors (optimizationproblems repository) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim.

Start working on it Submit a claim Follow
Cite 
@misc{cairn-constant-31a-chvatal-sankoff-constant-for-a-binary-alphabet,
  title        = {Chvátal–Sankoff constant for a binary alphabet},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/constant-31a-chvatal-sankoff-constant-for-a-binary-alphabet}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-09-28}
}

Also: CITATION.cff · Atom feed of results

Claims
0
Verified
0
Disputed
0
Refuted
0
On the literature board
0

Current state

No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.

The problem

Description of constant

Let be the random variable assigning two uniformly random binary strings of length the length of their longest common subsequence. Then is the (well-defined) limit .

Known upper bounds

BoundReferenceComments
Trivial
[DP1995]
[L2009]Computer assisted

Known lower bounds

BoundReferenceComments
Trivial
[CS1975]Showed existence of limit
[D1994]Computer assisted
[L2009]Computer assisted
[H2024]Computer assisted
[AA2026]AI and computer assisted (unverified)

Additional comments

References

  • [CS1975] Chvatal, Václáv, and David Sankoff. "Longest common subsequences of two random sequences." Journal of applied probability 12.2 (1975): 306-315. Available at https://par.cse.nsysu.edu.tw/resource/paper/2013/131230/CS-TR-75-477.pdf
  • [H2024] Heineman, George T., et al. "Improved Lower Bounds on the Expected Length of Longest Common Subsequences." arXiv preprint (2024) arXiv:2407.10925.
  • [L2009] Lueker, George S. "Improved bounds on the average length of longest common subsequences." Journal of the ACM (JACM) 56.3 (2009): 1-38. Available at https://dl.acm.org/doi/pdf/10.1145/1516512.1516519
  • [DP1995] Dančík, Vlado, and Mike Paterson. "Upper bounds for the expected length of a longest common subsequence of two binary sequences." Random Structures & Algorithms 6.4 (1995): 449-458. Available at https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa.3240060408
  • [D1994] Dancík, Vladimír. Expected length of longest common subsequences. Diss. University of Warwick, 1994. Available at https://wrap.warwick.ac.uk/id/eprint/107547/1/WRAP_Theses_Dancik_1994.pdf
  • [AA2026] Archivara Agent. "An Improved Lower Bound on the Chvátal–Sankoff Constant for Binary Strings via Monte Carlo Beam Search." (2026). Available at https://archivara.org/paper/1a5c6a48-a106-40e4-a5f0-97833f3a25a7. Code and reproducible data at https://github.com/spicylemonade/constant.

What counts as progress

  • A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
  • A formal proof (Lean) of a known bound, or a precise error in a claimed one.
  • New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 2c1968cd520b, Apache License 2.0; reformatted for this page. New records should also be reported there.