Nearly complete graphs decomposable into large induced matchings and their applications

Noga Alon, Ankur Moitra, Benny Sudakov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

23 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 ( N 2)-o(N 2) edges, which can be decomposed into pairwise disjoint induced matchings, each of size N 1-o(1). The second construction provides a covering of all edges of the complete graph K N by two graphs, each being the edge disjoint union of at most N 2-δ 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 Hastad 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)
Title of host publicationSTOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing
Pages1079-1089
Number of pages11
DOIs
StatePublished - Jun 26 2012
Externally publishedYes
Event44th Annual ACM Symposium on Theory of Computing, STOC '12 - New York, NY, United States
Duration: May 19 2012May 22 2012

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other44th Annual ACM Symposium on Theory of Computing, STOC '12
CountryUnited States
CityNew York, NY
Period5/19/125/22/12

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • additive combinatorics
  • induced matchings

Cite this

Alon, N., Moitra, A., & Sudakov, B. (2012). Nearly complete graphs decomposable into large induced matchings and their applications. In STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing (pp. 1079-1089). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2213977.2214074