A bound on partitioning clusters

zbMATH Open1432.05114arXiv1702.00912MaRDI QIDQ2628261FDOQ2628261

Authors: Daniel M. Kane, Terence Tao 

Publication date: 13 June 2017

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Let $X$ be a finite collection of sets (or "clusters"). We consider the problem of counting the number of ways a cluster $AinX$ can be partitioned into two disjoint clusters $A_1,A_{2}inX$, 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 ${\displaystyle }$ | { (A_1,A_2,A) in X imes X imes X: A = A_1 uplus A_2 } | leq |X|^{3/p} ${\displaystyle }$ where $|X|$ denotes the cardinality of $X$, and $p:=lo{g}_{3}frac274=1.73814dots$, so that $frac3p=1.72598dots$. 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{|}^{lo{g}_{2}6}$, and that this exponent is best possible.

Full work available at URL: https://arxiv.org/abs/1702.00912

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

Recommendations

• Partitioning into sets of bounded cardinality
• Convolution estimates and number of disjoint partitions
• Optimality of Nested Partitions and Its Application to Cluster Analysis
• scientific article; zbMATH DE number 1998302
• A low-energy decomposition theorem

zbMATH Keywords

Hamming cubeadditive energy

Mathematics Subject Classification ID

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

Cites Work

• Additive combinatorics
• Logarithmic Sobolev inequalities for finite Markov chains
• Constructing optimal trees from quartets
• Uniformly Bounded Representations and Harmonic Analysis of the 2 x 2 Real Unimodular Group
• Sums in the grid
• On the weighted quartet consensus problem
• Title not available (Why is that?)

Cited In (8)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Clustering and isolation in the consensus problem for partitions
• Some remarks on the distribution of additive energy
• Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
• A note on clutter partitions
• On binomial sums, additive energies, and lazy random walks
• Convolution estimates and number of disjoint partitions

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)