23 citations · 54 across the 45 of their papers we have counts for
Showing 2013 · math.COShow all
3 papers · 2 filters
math.CO2013
Forcing -repetitions in degree sequences
Yair Caro, Asaf Shapira, Raphael Yuster
One of the most basic results in graph theory states that every graph with at least two vertices has two vertices with the same degree. Since there are graphs without vertices…
math.CO2013★ 4 cited
A Short Proof of Gowers' Lower Bound for the Regularity Lemma
Guy Moshkovitz, Asaf Shapira
A celebrated result of Gowers states that for every ε> 0 there is a graph G so that every ε-regular partition of G (in the sense of Szemeredi's regularity lemma) has order given by…
math.CO2013★ 4 cited
Deterministic vs Non-deterministic Graph Property Testing
Lior Gishboliner, Asaf Shapira
A graph property P is said to be testable if one can check if a graph is close or far from satisfying P using few random local inspections. Property P is said to be non-determinist…