7 papers · 1 filter
On Generalized Regularity
Noga Alon, Guy Moshkovitz
Szemeredi's regularity lemma is one instance in a family of regularity lemmas, replacing the definition of density of a graph by a more general coefficient. Recently, Fan Chung pro…
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…
A Tight Bound for Hypergraph Regularity II
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…
Traces of Hypergraphs
Noga Alon, Guy Moshkovitz, Noam Solomon
Let denote the largest number of distinct projections onto coordinates guaranteed in any family of binary vectors of length . The classical Sauer-Perl…
A Tight Bound for Hypergraph Regularity I
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…
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…