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\}|\le |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.

13 pages, 4 figures, to appear, Electron. J. Comb.. This is the final version, incorporating the referee comments