# Nearly complete graphs decomposable into large induced matchings and their applications

Noga Alon; Ankur Moitra; Benjamin Sudakov

Journal of the European Mathematical Society (2013)

- Volume: 015, Issue: 5, page 1575-1596
- ISSN: 1435-9855

## Access Full Article

top## Abstract

top## How to cite

topAlon, 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 -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.