ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let XX be a finite set of taxa. An rr-state character on XX is a partition of XX into at most rr states. A set CC of characters is compatible if there is a tree on XX that displays every character in CC; such a tree is a perfect phylogeny for CC.

Finite-character-subset conjecture. For each positive integer rr, there exists an integer f(r)f(r) such that, for any finite set XX and any set CC of rr-state characters on XX, CC is compatible if and only if every subset of at most f(r)f(r) characters in CC is compatible.

This conjecture formalizes the question of whether compatibility can always be determined by checking character subsets of bounded size, independently of the total number of characters. The paper states that the conjecture is false, so it is refuted.

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.