105 citations · 130 across the 18 of their papers we have counts for
4 papers · 1 filter
The Effect of Induced Subgraphs on Quasi-Randomness
Asaf Shapira, Raphael Yuster
One of the main questions that arise when studying random and quasi-random structures is which properties P are such that any object that satisfies P "behaves" like a truly random…
On the Density of a Graph and its Blowup
Asaf Shapira, Raphael Yuster
The theorem of Chung, Graham, and Wilson on quasi-random graphs asserts that of all graphs with edge density p, the random graph G(n,p) contains the smallest density of copies of K…
Hardness and Algorithms for Rainbow Connectivity
Sourav Chakraborty, Eldar Fischer, Arie Matsliah +1
An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connectivity of a connected graph G, denoted…
Multigraphs (only) satisfy a weak triangle removal lemma
Asaf Shapira, Raphael Yuster
The triangle removal lemma states that a simple graph with o(n^3) triangles can be made triangle-free by removing o(n^2) edges. It is natural to ask if this widely used result can…