Common quartets of several phylogenetic trees: h(3) = 14 and exponential bounds for h(k)

Let h(k) be the least n such that any k unrooted binary phylogenetic trees on the same n leaves display a common quartet. Snir and Yuster (Discrete Appl. Math. 387, 2026) asked for its value; h(2) = 6 and 11 ≤ h(3) ≤ 14 were known (the same numbers appear earlier as τk(4) in Humphries's 2008 thesis, whose conjecture τk(m) = κk(m) thus fails at (3, 4)). We show h(3) = 14, with three trees T, 3T, 9T on Z13 with no common quartet and an exhaustive search with checked LRAT proofs for the matching upper bound; up to symmetry there are exactly six such examples. We also prove 2k+2 ≤ h(k) ≤ 2·3k-1+1 for every k (an explicit caterpillar family and an iterated two-bipartition argument) and find four trees on 21 leaves with no common quartet. Later independent work (Yorke and Valyu DeepResearch, 27 October 2026) also determined h(3) = 14 and improved the general upper bound and the bounds on h(4); version 2 records this. The general bounds and the 13-leaf example are formally verified in Lean 4. The archive holds the LaTeX source, the Lean development with mutation tests, the SAT encodings, LRAT proofs and independent rechecks (code under the MIT licence). Version 2 of the preprint (version 1: 20 October 2026); identical to the folder common-quartets at tag common-quartets-v2 in github.com/jvvk/mathematics.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-20
DOI
https://doi.org/10.5281/zenodo.24406671
Primary Topic
Genomics and Phylogenetic Studies
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Common quartets of several phylogenetic trees: h(3) = 14 and exponential bounds for h(k)

Vamshi Jandhyala
Zenodo (CERN European Organization for Nuclear Research)
Genomics and Phylogenetic Studies
preprint

Common quartets of several phylogenetic trees: h(3) = 14 and exponential bounds for h(k)

Vamshi Jandhyala
preprint en

Abstract

Let h(k) be the least n such that any k unrooted binary phylogenetic trees on the same n leaves display a common quartet. Snir and Yuster (Discrete Appl. Math. 387, 2026) asked for its value; h(2) = 6 and 11 ≤ h(3) ≤ 14 were known (the same numbers appear earlier as τk(4) in Humphries's 2008 thesis, whose conjecture τk(m) = κk(m) thus fails at (3, 4)). We show h(3) = 14, with three trees T, 3T, 9T on Z13 with no common quartet and an exhaustive search with checked LRAT proofs for the matching upper bound; up to symmetry there are exactly six such examples. We also prove 2k+2 ≤ h(k) ≤ 2·3k-1+1 for every k (an explicit caterpillar family and an iterated two-bipartition argument) and find four trees on 21 leaves with no common quartet. Later independent work (Yorke and Valyu DeepResearch, 27 October 2026) also determined h(3) = 14 and improved the general upper bound and the bounds on h(4); version 2 records this. The general bounds and the 13-leaf example are formally verified in Lean 4. The archive holds the LaTeX source, the Lean development with mutation tests, the SAT encodings, LRAT proofs and independent rechecks (code under the MIT licence). Version 2 of the preprint (version 1: 20 October 2026); identical to the folder common-quartets at tag common-quartets-v2 in github.com/jvvk/mathematics.

Zenodo (CERN European Organization for Nuclear Research)
Genomics and Phylogenetic Studies
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon