{"id":"arxiv/2607.15658","url":"https://arxiv.org/abs/2607.15658","tags":["math.CO","cs.DM"],"score":0,"title":"New bounds on the Graham-Pollak theorem for hypergraphs","domain":"math.CO","source":"arxiv","authors":["Anand Babu"],"reviews":0,"subject":"math.CO","summary":"For a fixed $r$, let $f_r(n)$ denote the minimum number of complete $r$-partite $r$-uniform hypergraphs whose edge sets partition the complete $r$-uniform hypergraph on $n$ vertices. The Graham-Pollak theorem asserts that $f_2(n)=n-1$. Let $c_r$ be the smallest constant such that $f_r(n)\\le c_r(1+o(1))\\binom{n}{\\lfloor r/2\\rfloor}$. We give two constructions that improve upper bounds for $f_r(n)$. The first partitions $E(K_4)\\times E(K_{17})$ into $44$ products of edge sets of complete bipartite graphs and yields $c_4\\le11/12$, improving the previous bound of $c_4\\le14/15$. The second gives…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-17","reactions":{}}