Nearly Complete Graphs Decomposable into Large Induced Matchings and\n their Applications

2011/11/01 by Noga Alon, Ankur Moitra, Alon, Noga +3 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1111.0253

openalex publication_date 2011/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We describe two constructions of (very) dense graphs which are edge disjoint\nunions of large em induced matchings. The first construction exhibits graphs\non N vertices with N choose 2-o(N²) edges, which can be decomposed into\npairwise disjoint induced matchings, each of size N^1-o(1). The second\nconstruction provides a covering of all edges of the complete graph K_N by\ntwo graphs, each being the edge disjoint union of at most N^2-\δ\ninduced matchings, where \δ > 0.058. This disproves (in a strong form) a\nconjecture of Meshulam, substantially improves a result of Birk, Linial and\nMeshulam on communicating over a shared channel, and (slightly) extends the\nanalysis of H aastad and Wigderson of the graph test of Samorodnitsky and\nTrevisan for linearity. Additionally, our constructions settle a combinatorial\nquestion of Vempala regarding a candidate rounding scheme for the directed\nSteiner tree problem.\n

Cited by

• Constructing Long Paths in Graph Streams
• A Two-Pass Lower Bound for Semi-Streaming Maximum Matching

Related

• On graphs decomposable into induced matchings of linear sizes
• Dense Matchings of Linear Size in Graphs with Independence Number 2
• Characterization of saturated graphs related to pairs of disjoint matchings
• Tree decompositions meet induced matchings: beyond Max Weight Independent Set
• Connected matching in graphs with independence number two