On Regularity Lemma and Barriers in Streaming and Dynamic Matching
Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan Li
Abstract
We present a new approach for finding matchings in dense graphs by building on Szemerédi’s celebrated Regularity Lemma. This allows us to obtain non-trivial albeit slight improvements over longstanding bounds for matchings in streaming and dynamic graphs. In particular, we establish the following results for n-vertex graphs:
Topics & Concepts
Lemma (botany)Vertex (graph theory)Matching (statistics)CombinatoricsBipartite graphComputer scienceMathematicsGraphDiscrete mathematicsStatisticsEcologyBiologyPoaceaeComplexity and Algorithms in GraphsCooperative Communication and Network CodingAdvanced Graph Theory Research