Nearly complete graphs decomposable into large induced matchings and their applications

DOI10.4171/JEMS/398zbMath1278.05183MaRDI QIDQ363228

Ankur Moitra, Noga Alon, Benjamin Sudakov

Publication date: 2 September 2013

Published in: Journal of the European Mathematical Society (JEMS) (Search for Journal in Brave)

zbMATH Keywords

induced matchingsRuzsa-Szemerédi graphstesting linearity

Mathematics Subject Classification ID

Applications of graph theory (05C90) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Number on the forehead protocols yielding dense Ruzsa-Szemerédi graphs and hypergraphs, Colorings with only rainbow arithmetic progressions

Cites Work

• Unnamed Item
• On an extremal hypergraph problem of Brown, Erdős and Sós
• Self-testing/correcting with applications to numerical problems
• Representing Boolean functions as polynomials modulo composite numbers
• On the uniform-traffic capacity of single-hop interconnections employing shared directional multichannels
• Testing subgraphs in large graphs
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• Testing subgraphs in directed graphs