Improved bounds for the graham-pollak problem for hypergraphs

Document Type

Article

Publication Date

1-1-2018

Abstract

For a fixed r, let fr(n) denote the minimum number of complete r-partite r- graphs needed to partition the complete r-graph on n vertices. The Graham-Pollak theorem asserts that f2(n) = n – 1. An easy construction shows that [formula presented], and we write cr for the least number such that [formula presented] It was known that cr < 1 for each even r ≥ 4, but this was not known for any odd value of r. In this short note, we prove that c295 < 1. Our method also shows that cr → 0, answering another open problem.

Keywords

Decomposition, Graham-Pollak, Hypergraph

Divisions

MathematicalSciences

Publication Title

Electronic Journal of Combinatorics

Volume

25

Issue

1

Publisher

Australian National University

This document is currently not available here.

Share

COinS