Improved bounds for the Graham-Pollak problem for hypergraphs

MaRDI QIDQ1691097zbMATH OpenFDO

Authors Imre Leader, Ta Sheng Tan

Publication date 15 January 2018

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

Full work available at URL https://arxiv.org/abs/1708.01898, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p4

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

zbMATH Keywords

decompositionGraham-Pollak problemhypergraph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Extremal set theory (05D05)

Abstract: 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 $$, and we write $c_r$ for the least number such that $$. It was known that $c_r<1$ for each even $rgeq4$, 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}ightarrow0$, answering another open problem.

Review text

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.

Recommendations

• Bounds for the Graham-Pollak theorem for hypergraphs
• Decomposing the complete \(r\)-graph
• Multicovering hypergraphs
• Decomposition of the complete r-graph into complete r-partite r-graphs
• k-clique partition of complete k-uniform hypergraphs

Cites work

• A counting proof of the Graham-Pollak theorem
• A new proof of a theorem of Graham and Pollak
• A polynomial space proof of the Graham-Pollak theorem
• Decomposing the complete \(r\)-graph
• Decomposition of the complete r-graph into complete r-partite r-graphs
• scientific article; zbMATH DE number 3395950 (Why is no real title available?)
• On decompositions of complete hypergraphs
• On the Addressing Problem for Loop Switching
• On the decomposition ofkn into complete bipartite graphs
• Variations on a theme of Graham and Pollak

Cited in

(8)

• Improved bounds for covering complete uniform hypergraphs
• Multicovering hypergraphs
• Bounds for the Graham-Pollak theorem for hypergraphs
• Improved Bounds for Uniform Hypergraphs without Property B
• Finding biclique partitions of co-chordal graphs
• On the decomposition of random hypergraphs
• Odd covers of complete graphs and hypergraphs
• The de Bruijn-Erdős theorem for hypergraphs

This page was built for publication: Improved bounds for the Graham-Pollak problem for hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1691097)