A bound on partitioning clusters

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 $$\mathrm{\mid }\{(A_1,A_2,A)\in X\times X\times X:A=A_1\uplus A_2\}\mathrm{\mid }\le \mathrm{\mid }X{\mathrm{\mid }}^{3\mathrm{/}p}$$ where $\mathrm{\mid }X\mathrm{\mid }$ denotes the cardinality of $X$, and $p := \log_3 \frac{27}{4} = 1.73814\dots$,sothat$\frac{3}{p} = 1.72598\dots$. Furthermore, the exponent $p$ cannot be replaced by any larger quantity. This improves upon the trivial bound of $\mathrm{\mid }X{\mathrm{\mid }}^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.