Geodesic
Nearly complete graphs decomposable into large induced matchings and their applications
Journal of the European Mathematical Society, Tome 15 (2013) no. 5, pp. 1575-1596

Voir la notice de l'article provenant de la source EMS Press

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 (2N​)−o(N2) edges, which can be decomposed into pairwise disjoint induced matchings, each of size N1−o(1). The second construction provides a covering of all edges of the complete graph KN​ by two graphs, each being the edge disjoint union of at most N2−δ 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 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.
DOI : 10.4171/jems/398
Classification : 05-XX, 68-XX, 00-XX
Keywords: Ruzsa-Szemerédi graphs, induced matchings, testing linearity 
@article{JEMS_2013_15_5_a0,
     author = {Noga Alon and Ankur Moitra and Benjamin Sudakov},
     title = {Nearly complete graphs decomposable into large induced matchings and their applications},
     journal = {Journal of the European Mathematical Society},
     pages = {1575--1596},
     publisher = {mathdoc},
     volume = {15},
     number = {5},
     year = {2013},
     doi = {10.4171/jems/398},
     url = {http://geodesic.mathdoc.fr/articles/10.4171/jems/398/}
}
TY  - JOUR
AU  - Noga Alon
AU  - Ankur Moitra
AU  - Benjamin Sudakov
TI  - Nearly complete graphs decomposable into large induced matchings and their applications
JO  - Journal of the European Mathematical Society
PY  - 2013
SP  - 1575
EP  - 1596
VL  - 15
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.4171/jems/398/
DO  - 10.4171/jems/398
ID  - JEMS_2013_15_5_a0
ER  - 
%0 Journal Article
%A Noga Alon
%A Ankur Moitra
%A Benjamin Sudakov
%T Nearly complete graphs decomposable into large induced matchings and their applications
%J Journal of the European Mathematical Society
%D 2013
%P 1575-1596
%V 15
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.4171/jems/398/
%R 10.4171/jems/398
%F JEMS_2013_15_5_a0
Noga Alon; Ankur Moitra; Benjamin Sudakov. Nearly complete graphs decomposable into large induced matchings and their applications. Journal of the European Mathematical Society, Tome 15 (2013) no. 5, pp. 1575-1596. doi: 10.4171/jems/398

Cité par Sources :