Neighborly families of boxes and bipartite coverings

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

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
Pages15-20
Number of pages6
ISBN (Electronic)9781461472544
ISBN (Print)9781461472537
DOIs
StatePublished - Jan 1 2013
Externally publishedYes

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Cite this

Alon, N. (2013). Neighborly families of boxes and bipartite coverings. In The Mathematics of Paul Erdos II, Second Edition (pp. 15-20). Springer New York. https://doi.org/10.1007/978-1-4614-7254-4_2