### 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 language | English (US) |
---|---|

Title of host publication | STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing |

Pages | 1079-1089 |

Number of pages | 11 |

DOIs | |

State | Published - Jun 26 2012 |

Externally published | Yes |

Event | 44th Annual ACM Symposium on Theory of Computing, STOC '12 - New York, NY, United States Duration: May 19 2012 → May 22 2012 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | 44th Annual ACM Symposium on Theory of Computing, STOC '12 |
---|---|

Country | United States |

City | New York, NY |

Period | 5/19/12 → 5/22/12 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- additive combinatorics
- induced matchings

## Cite this

*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