Decomposing the complete r-graph

DOI10.1016/J.JCTA.2017.08.008zbMATH Open1373.05149arXiv1701.08335OpenAlexW2584968584MaRDI QIDQ1679321FDOQ1679321

Luka Milićević, Imre Leader, Ta Sheng Tan

Publication date: 9 November 2017

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: Let $f_r(n)$ be the minimum number of complete $r$-partite $r$-graphs needed to partition the edge set of the complete $r$-uniform hypergraph on $n$ vertices. Graham and Pollak showed that $f_2(n)=n-1$. An easy construction shows that $$ and it has been unknown if this upper bound is asymptotically sharp. In this paper we show that $$ for each even $rge4$.

Full work available at URL: https://arxiv.org/abs/1701.08335

Recommendations

• Decomposition of the complete r-graph into complete r-partite r-graphs
• Decompositions of Complete Graphs
• On a decomposition of complete graphs
• Decomposing complete graphs into \(K_{r} \times K_{c}\)'s.
• Complete decomposable graphs
• On complementary decompositions of the complete graph
• Decompositions of complete graphs into circulants
• Decompositions and factorizations of complete graphs
• Decompositions of generalized complete graphs
• Decompositions of complete multipartite graphs

zbMATH Keywords

decompositionhypergraph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• On the Addressing Problem for Loop Switching
• Title not available (Why is that?)
• Variations on a theme of Graham and Pollak
• On the decomposition ofkn into complete bipartite graphs
• A polynomial space proof of the Graham-Pollak theorem
• A new proof of a theorem of Graham and Pollak
• On partitions of discrete boxes
• On decompositions of complete hypergraphs
• Decomposition of the complete r-graph into complete r-partite r-graphs
• A counting proof of the Graham-Pollak theorem
• Depth-3 Arithmetic Circuits for S^2_n(X) and Extensions of the Graham-Pollack Theorem
• Decomposition of product graphs into complete bipartite subgraphs
• On Extremal Set Partitions in Cartesian Product Spaces
• On Partitioning and Packing Products with Rectangles

Cited In (11)

• Odd covers of graphs
• On the decomposition of random hypergraphs
• Decomposing complete graphs into \(K_{r} \times K_{c}\)'s.
• Partition problems in high dimensional boxes
• Improved bounds for the Graham-Pollak problem for hypergraphs
• Decomposition of the complete r-graph into complete r-partite r-graphs
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• A note on \(k\)-wise oddtown problems
• Bounds for the Graham-Pollak theorem for hypergraphs
• Multicovering hypergraphs
• Title not available (Why is that?)

This page was built for publication: Decomposing the complete \(r\)-graph

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