3 papers
math.CO2019
A Tight Bound for Hyperaph Regularity
Guy Moshkovitz, Asaf Shapira
The hypergraph regularity lemma -- the extension of Szemerédi's graph regularity lemma to the setting of -uniform hypergraphs -- is one of the most celebrated combinatorial resu…
math.CO2015
Constructing Near Spanning Trees with Few Local Inspections
Reut Levi, Guy Moshkovitz, Dana Ron +2
Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following var…
math.CO2015
Decomposing a Graph Into Expanding Subgraphs
Guy Moshkovitz, Asaf Shapira
A paradigm that was successfully applied in the study of both pure and algorithmic problems in graph theory can be colloquially summarized as stating that "any graph is close to be…