JournalsjemsVol. 15, No. 5pp. 1575–1596

Nearly complete graphs decomposable into large induced matchings and their applications

  • Noga Alon

    Sackler Faculty of Exact Sciences, Tel Aviv, Israel
  • Ankur Moitra

    Institute for Advanced Study, Princeton, USA
  • Benjamin Sudakov

    ETH Zürich, Switzerland
Nearly complete graphs decomposable into large induced matchings and their applications cover
Download PDF

Abstract

We describe two constructions of (very) dense graphs which are edge disjoint unions of large {\em induced} matchings. The first construction exhibits graphs on NN vertices with (N2)o(N2){N \choose 2}-o(N^2) edges, which can be decomposed into pairwise disjoint induced matchings, each of size N1o(1)N^{1-o(1)}. The second construction provides a covering of all edges of the complete graph KNK_N by two graphs, each being the edge disjoint union of at most N2δN^{2-\delta} induced matchings, where δ>0.076\delta > 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{\aa}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.

Cite this article

Noga Alon, Ankur Moitra, Benjamin Sudakov, Nearly complete graphs decomposable into large induced matchings and their applications. J. Eur. Math. Soc. 15 (2013), no. 5, pp. 1575–1596

DOI 10.4171/JEMS/398