Nearly complete graphs decomposable into large induced matchings and their applications

Noga Alon, Ankur Moitra, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

We describe two constructions of (very) dense graphs which are edge disjoint unions of large induced matchings. The first construction exhibits graphs on N vertices with (N2) - o(N2) edges, which can be decomposed into pairwise disjoint induced matchings, each of size N1-o(1). The second construction provides a covering of all edges of the complete graph KN by two graphs, each being the edge disjoint union of at most N2-δ induced matchings, where δ > 0.076. This disproves (in a strong form) a conjecture of Meshulam, substantially improves a result of Birk, Linial and Meshulam on communicating over a shared channel, and (slightly) extends the analysis of Håstad and Wigderson of the graph test of Samorodnitsky and Trevisan for linearity. Additionally, our constructions settle a combinatorial question of Vempala regarding a candidate rounding scheme for the directed Steiner tree problem.

Original languageEnglish (US)
Pages (from-to)1575-1596
Number of pages22
JournalJournal of the European Mathematical Society
Volume15
Issue number5
DOIs
StatePublished - 2013

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Nearly complete graphs decomposable into large induced matchings and their applications'. Together they form a unique fingerprint.

Cite this