TY - GEN

T1 - Nearly complete graphs decomposable into large induced matchings and their applications

AU - Alon, Noga

AU - Moitra, Ankur

AU - Sudakov, Benny

PY - 2012/6/26

Y1 - 2012/6/26

N2 - 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.

AB - 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.

KW - additive combinatorics

KW - induced matchings

UR - http://www.scopus.com/inward/record.url?scp=84862606987&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84862606987&partnerID=8YFLogxK

U2 - 10.1145/2213977.2214074

DO - 10.1145/2213977.2214074

M3 - Conference contribution

AN - SCOPUS:84862606987

SN - 9781450312455

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1079

EP - 1089

BT - STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing

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

Y2 - 19 May 2012 through 22 May 2012

ER -