A bound on partitioning clusters

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Extremal set theory (05D05) Arithmetic combinatorics; higher degree uniformity (11B30)

Abstract: Let

X

be a finite collection of sets (or "clusters"). We consider the problem of counting the number of ways a cluster

A i n X

can be partitioned into two disjoint clusters

A_{1}, A_{2} i n X

, thus

A = A_{1} u p l u s 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 imes X imes X: A = A_1 uplus A_2 } | leq |X|^{3/p}

where

| X |

denotes the cardinality of

X

, and

p := l o g_{3} f r a c 274 = 1.73814 d o t s

, so that

f r a c 3 p = 1.72598 d o t s

. 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 |^{l o g_{2} 6}

, and that this exponent is best possible.

Review text

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.

Recommendations

Cites work

Cited in

(9)

Describes a project that uses

Uses Software

ASTRAL-II

This page was built for publication: A bound on partitioning clusters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2628261)