A bound on partitioning clusters (Q2628261)

Summary: 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.