Consider a boolean function $f : V \rightarrow \{0,1\}$ with $m$ true points. Are there any non-trivial bounds in $m$ on the size of the smallest decision tree for $f$?
It seems to me that assuming $f$ has $n$ variables and $m$ true points then any minimal decision tree has at most $$ 2^{\lceil{\log_2 m}\rceil}−m+m⋅(n−\lceil{\log_2 m}\rceil) $$ 0-leaves (obviously, one can take the dual as well). I am wondering if whether this sort of thing has been covered before (I presume it has somewhere).
I think the number of true points isn't a good measure to say anything about the size of the smallest decision tree.
There is a chapter in Branching programs and binary decision diagrams: theory and applications by Ingo Wegener about the size of decision trees for boolean functions.
The size of the smallest DT is determined up to constant factors by the number of leaves of the tree. There is a lemma in the book that says: If you have a DT for a function $f$ with $s_0$ 0-leaves and $s_1$ 1-leaves then $f$ can be represented by a DNF with $s_1$ monomials and a CNF with $s_0$ clauses. So even if you have a function with only a small number of true points, the size of the smallest DT could be very large. So you need small size of CNF and DNF to have a small DT size.
There is a upper bound of the DT size with respect to the sum of the minimal number of monomials of $f$ and the minimal number of monomials of $\overline{f}$. Lets call this sum $DCNF(f)$. Then you have the following upper bound for the number of leaves $DT(f)$ of the smallest DT for the function $f: \lbrace 0,1 \rbrace^n \rightarrow \lbrace 0,1 \rbrace$ $$ DT(f) \leq n^{O(log^2 DCNF(f))}. $$
