Title: A bound on partitioning clusters,
Abstract: Let $X$ be a finite collection of sets (or "clusters"). We consider the
problem of counting the number of ways a cluster $A \in X$ can be partitioned
into two disjoint clusters $A_1, A_2 \in X$, thus $A = A_1 \uplus A_2$ is the
disjoint union of $A_1$ and $A_2$; this problem arises in the run time analysis
of the ASTRAL algorithm in phylogenetic reconstruction. We obtain the bound $$
| \{ (A_1,A_2,A) \in X \times X \times X: A = A_1 \uplus A_2 \} | \leq
|X|^{3/p} $$ where $|X|$ denotes the cardinality of $X$, and $p := \log_3
\frac{27}{4} = 1.73814\dots$, so that $\frac{3}{p} = 1.72598\dots$.
Furthermore, the exponent $p$ cannot be replaced by any larger quantity. This
improves upon the trivial bound of $|X|^2$. The argument relies on establishing
a one-dimensional convolution inequality that can be established by elementary
calculus combined with some numerical verification.
In a similar vein, we show that for any subset $A$ of a discrete cube
$\{0,1\}^n$, the additive energy of $A$ (the number of quadruples
$(a_1,a_2,a_3,a_4)$ in $A^4$ with $a_1+a_2=a_3+a_4$) is at most $|A|^{\log_2
6}$, and that this exponent is best possible.