ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let dr(n)d_r(n) be the maximum, over all binary phylogenetic trees with nn leaves, of the minimum number of rr-state characters required to define the tree. Let nrn_r be the least integer NN such that the Semple–Steel lower bound is attained for every n≥Nn\geq N, namely dr(n)=⌈n−3r−1⌉d_r(n)=\left\lceil\frac{n-3}{r-1}\right\rceil. Exact threshold conjecture. For every r≥4r\geq4,

nr=3r+1.n_r=3r+1.

Moreover, whenever n≥3r+1n\geq3r+1, there is an explicit construction of

⌈n−3r−1⌉\left\lceil \frac{n-3}{r-1} \right\rceil

rr-state characters defining any prescribed binary phylogenetic tree with nn leaves. The paper proves the lower bound nr≥3r+1n_r\geq3r+1 and an upper bound of order O(rlog⁡r)O(r\log r); the conjecture asserts that the lower bound is exact and that the bound can be attained constructively from this threshold onward.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.