Improved bounds for the Graham-Pollak problem for hypergraphs (Q1691097)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Improved bounds for the Graham-Pollak problem for hypergraphs |
scientific article |
Statements
Improved bounds for the Graham-Pollak problem for hypergraphs (English)
0 references
15 January 2018
0 references
Summary: For a fixed \(r\), let \(f_r(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 \(f_2(n)=n-1\). An easy construction shows that \(f_r(n) \leqslant (1+o(1))\binom{n}{\lfloor r/2 \rfloor}\), and we write \(c_r\) for the least number such that \(f_r(n) \leq c_r (1+o(1))\binom{n}{\lfloor r/2 \rfloor}\). It was known that \(c_r < 1\) for each even \(r \geq 4\), but this was not known for any odd value of \(r\). In this short note, we prove that \(c_{295}<1\). Our method also shows that \(c_r \rightarrow 0\), answering another open problem.
0 references
hypergraph
0 references
decomposition
0 references
Graham-Pollak problem
0 references