2017/02/03 by Kane, Daniel, Tao, Terence · 4 citations
#11B30 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1702.00912
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 A1, A2 ∈ X, thus A = A1 \uplus A2 is the disjoint union of A1 and A2; this problem arises in the run time analysis of the ASTRAL algorithm in phylogenetic reconstruction. We obtain the bound | \ (A1,A2,A) ∈ X × X × X: A = A1 \uplus A2 \ | ≤ |X|3/p where |X| denotes the cardinality of X, and p := log3 (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|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 (a1,a2,a3,a4) in A4 with a1+a2=a3+a4) is at most |A|log2 6, and that this exponent is best possible.