Decomposing the complete r-graph

DOI10.1016/J.JCTA.2017.08.008MaRDI QIDQ1679321zbMATHOpenAlexFDO

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

Publication date 9 November 2017

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

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

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)

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$.

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

Cites work

• scientific article; zbMATH DE number 3395950 (Why is no real title available?)
• 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
• Decomposition of product graphs into complete bipartite subgraphs
• Decomposition of the complete r-graph into complete r-partite r-graphs
• Depth-3 Arithmetic Circuits for S^2_n(X) and Extensions of the Graham-Pollack Theorem
• On Extremal Set Partitions in Cartesian Product Spaces
• On Partitioning and Packing Products with Rectangles
• On decompositions of complete hypergraphs
• On partitions of discrete boxes
• 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

(15)

• Covering complete \(r\)-graphs with spanning complete \(r\)-partite \(r\)-graphs
• A note on \(k\)-wise oddtown problems
• Partition problems in high dimensional boxes
• Bounds for the Graham-Pollak theorem for hypergraphs
• scientific article; zbMATH DE number 890666 (Why is no real title available?)
• \(k\)-clique partition of complete \(k\)-uniform hypergraphs
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• \(H\)-decompositions of \(r\)-graphs when \(H\) is an \(r\)-graph with exactly 2 edges
• On the decomposition of random hypergraphs
• Decomposing complete graphs into \(K_{r} \times K_{c}\)'s.
• Factoring complete graphs and hypergraphs into factors with few maximal cliques
• Multicovering hypergraphs
• Improved bounds for the Graham-Pollak problem for hypergraphs
• Decomposition of the complete r-graph into complete r-partite r-graphs
• Odd covers of graphs

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)