Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: A linear bound on the number of states in optimal convex characters for
  maximum parsimony distance   Given two phylogenetic trees on the same set of taxa X, the maximum parsimony
distance d_MP is defined as the maximum, ranging over all characters c on X, of
the absolute difference in parsimony score induced by c on the two trees. In
this note we prove that for binary trees there exists a character achieving
this maximum that is convex on one of the trees (i.e. the parsimony score
induced on that tree is equal to the number of states in the character minus 1)
and such that the number of states in the character is at most 7d_MP - 5. This
is the first non-trivial bound on the number of states required by optimal
characters, convex or otherwise. The result potentially has algorithmic
significance because, unlike general characters, convex characters with a
bounded number of states can be enumerated in polynomial time.

5
The categories of this paper are: gr-qc
29
The categories of this paper are: funct-an
30
The categories of this paper are: q-alg
23
The categories of this paper are: solv-int
17
The categories of this paper are: q-fin
33
The categories of this paper are: plasm-ph
14
The categories of this paper are: math-ph
24
The categories of this paper are: dg-ga
21
The categories of this paper are: adap-org
0
The categories of this paper are: hep-ph
37
The categories of this paper are: supr-con
7
The categories of this paper are: hep-th
2
The categories of this paper are: math
9
The categories of this paper are: nlin
13
The categories of this paper are: quant-ph
12
The categories of this paper are: nucl-th