Neighborly families of boxes and bipartite coverings

Research output: Chapter in Book/Report/Conference proceedingChapter

1 Scopus citations


A bipartite covering of order k of the complete graph Kn on n vertices is a collection of complete bipartite graphs so that every edge of Kn lies in at least 1 and at most k of them. It is shown that the minimum possible number of subgraphs in such a collection is Θ(kn1/k). This extends a result of Graham and Pollak, answers a question of Felzenbaum and Perles, and has some geometric consequences. The proofs combine combinatorial techniques with some simple linear algebraic tools.

Original languageEnglish (US)
Title of host publicationThe Mathematics of Paul Erdos II, Second Edition
PublisherSpringer New York
Number of pages6
ISBN (Electronic)9781461472544
ISBN (Print)9781461472537
StatePublished - Jan 1 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Mathematics


Dive into the research topics of 'Neighborly families of boxes and bipartite coverings'. Together they form a unique fingerprint.

Cite this