A bound on partitioning clusters

Original · EN

Let X be a finite collection of sets (or "clusters"). We consider the problem of counting the number of ways a cluster A ∈ X can be partitioned into two disjoint clusters A₁, A₂ ∈ X, thus A = A₁ A₂ is the disjoint union of A₁ and A₂; this problem arises in the run time analysis of the ASTRAL algorithm in phylogenetic reconstruction. We obtain the bound | { (A₁,A₂,A) ∈ X × X × X: A = A₁ A₂ } | ≤ |X|³/ᵖ where |X| denotes the cardinality of X, and p:= ₃ 27/4 = 1.73814, so that 3/p = 1.72598. Furthermore, the exponent p cannot be replaced by any larger quantity. This improves upon the trivial bound of |X|². 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}ⁿ, the additive energy of A (the number of quadruples (a₁,a₂,a₃,a₄) in A⁴ with a₁+a₂=a₃+a₄) is at most |A|₂ 6, and that this exponent is best possible.