Decomposition of the complete r-graph into complete r-partite r-graphs

Noga Alon

doi:10.1007/BF01788083

Decomposition of the complete r-graph into complete r-partite r-graphs

Noga Alon

Research output: Contribution to journal › Article › peer-review

17 Scopus citations

Abstract

For n ≥ r ≥ 1, let f_r(n) denote the minimum number q, such that it is possible to partition all edges of the complete r-graph on n vertices into q complete r-partite r-graphs. Graham and Pollak showed that f₂(n) =n - 1. Here we observe that f₃(n) =n - 2 and show that for every fixed r ≥ 2, there are positive constants c₁(r) and c₂(r) such that c₁(r) ≤f_r(n){dot operator}n^-[r/2] ≤n₂(r) for all n ≥ r. This solves a problem of Aharoni and Linial. The proof uses some simple ideas of linear algebra.

Original language	English (US)
Pages (from-to)	95-100
Number of pages	6
Journal	Graphs and Combinatorics
Volume	2
Issue number	1
DOIs	https://doi.org/10.1007/BF01788083
State	Published - Dec 1986
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/BF01788083

Cite this

@article{d6627664388248c0bc97fef2347ba69a,

title = "Decomposition of the complete r-graph into complete r-partite r-graphs",

abstract = "For n ≥ r ≥ 1, let fr(n) denote the minimum number q, such that it is possible to partition all edges of the complete r-graph on n vertices into q complete r-partite r-graphs. Graham and Pollak showed that f2(n) =n - 1. Here we observe that f3(n) =n - 2 and show that for every fixed r ≥ 2, there are positive constants c1(r) and c2(r) such that c1(r) ≤fr(n)\{dot operator\}n-[r/2] ≤n2(r) for all n ≥ r. This solves a problem of Aharoni and Linial. The proof uses some simple ideas of linear algebra.",

author = "Noga Alon",

year = "1986",

month = dec,

doi = "10.1007/BF01788083",

language = "English (US)",

volume = "2",

pages = "95--100",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "1",

}

TY - JOUR

T1 - Decomposition of the complete r-graph into complete r-partite r-graphs

AU - Alon, Noga

PY - 1986/12

Y1 - 1986/12

N2 - For n ≥ r ≥ 1, let fr(n) denote the minimum number q, such that it is possible to partition all edges of the complete r-graph on n vertices into q complete r-partite r-graphs. Graham and Pollak showed that f2(n) =n - 1. Here we observe that f3(n) =n - 2 and show that for every fixed r ≥ 2, there are positive constants c1(r) and c2(r) such that c1(r) ≤fr(n){dot operator}n-[r/2] ≤n2(r) for all n ≥ r. This solves a problem of Aharoni and Linial. The proof uses some simple ideas of linear algebra.

AB - For n ≥ r ≥ 1, let fr(n) denote the minimum number q, such that it is possible to partition all edges of the complete r-graph on n vertices into q complete r-partite r-graphs. Graham and Pollak showed that f2(n) =n - 1. Here we observe that f3(n) =n - 2 and show that for every fixed r ≥ 2, there are positive constants c1(r) and c2(r) such that c1(r) ≤fr(n){dot operator}n-[r/2] ≤n2(r) for all n ≥ r. This solves a problem of Aharoni and Linial. The proof uses some simple ideas of linear algebra.

UR - https://www.scopus.com/pages/publications/0002192710

UR - https://www.scopus.com/inward/citedby.url?scp=0002192710&partnerID=8YFLogxK

U2 - 10.1007/BF01788083

DO - 10.1007/BF01788083

M3 - Article

AN - SCOPUS:0002192710

SN - 0911-0119

VL - 2

SP - 95

EP - 100

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 1

ER -

Decomposition of the complete r-graph into complete r-partite r-graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this