2024/01/01 by Ebrahem, Ehab, Hoory, Shlomo, Kotlar, Dani
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2401.00807
This work is about a partition problem which is an instance of the distance magic graph labeling problem. Given positive integers n,k and p1≤ p2≤ ⋯≤ pk such that p1+⋯+pk=n and k divides ∑i=1ni, we study the problem of characterizing the cases where it is possible to find a partition of the set \1,2,…,n\ into k subsets of respective sizes p1,…,pk, such that the element sum in each subset is equal. Using a computerized search we found examples showing that the necessary condition, ∑i=1p1+⋯+pj (n-i+1)≥ j\binomn+12/k for all j=1,…,k, is not generally sufficient, refuting a past conjecture. Moreover, we show that there are infinitely many such counter-examples. The question whether there is a simple characterization is left open and for all we know the corresponding decision problem might be NP-complete.