Nearly complete graphs decomposable into large induced matchings and their applications

Alon, Noga, Moitra, Ankur, and Sudakov, Benjamin. "Nearly complete graphs decomposable into large induced matchings and their applications." Journal of the European Mathematical Society 015.5 (2013): 1575-1596. <http://eudml.org/doc/277191>.

@article{Alon2013,
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 $(\frac\{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-\delta \}$ induced matchings, where $\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å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.},
author = {Alon, Noga, Moitra, Ankur, Sudakov, Benjamin},
journal = {Journal of the European Mathematical Society},
keywords = {Ruzsa-Szemerédi graphs; induced matchings; testing linearity; Ruzsa-Szemerédi graphs; induced matchings; testing linearity},
language = {eng},
number = {5},
pages = {1575-1596},
publisher = {European Mathematical Society Publishing House},
title = {Nearly complete graphs decomposable into large induced matchings and their applications},
url = {http://eudml.org/doc/277191},
volume = {015},
year = {2013},
}

TY - JOUR
AU - Alon, Noga
AU - Moitra, Ankur
AU - Sudakov, Benjamin
TI - Nearly complete graphs decomposable into large induced matchings and their applications
JO - Journal of the European Mathematical Society
PY - 2013
PB - European Mathematical Society Publishing House
VL - 015
IS - 5
SP - 1575
EP - 1596
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 $(\frac{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-\delta }$ induced matchings, where $\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å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.
LA - eng
KW - Ruzsa-Szemerédi graphs; induced matchings; testing linearity; Ruzsa-Szemerédi graphs; induced matchings; testing linearity
UR - http://eudml.org/doc/277191
ER -