40 citations · 141 across the 8 of their papers we have counts for
8 papers
A New Lower Bound on the Spectral Radius of Graphs with Prescribed Average Degree
Sonny Ben-Shimon, Idan Eisner, Shlomo Hoory
This work establishes an improved lower bound for the spectral radius of a graph given its average degree. The new bound follows from an exact solution of the fractional relaxation…
On the resilience of Hamiltonicity and optimal packing of Hamilton cycles in random graphs
Sonny Ben-Shimon, Michael Krivelevich, Benny Sudakov
Let $\bk=(k_1,...,k_n)$ be a sequence of integers. For an increasing monotone graph property $\mP$ we say that a base graph is \emph{$\bk$-resilient} with respect t…
Hitting time results for Maker-Breaker games
Sonny Ben-Shimon, Asaf Ferber, Dan Hefetz +1
We study Maker-Breaker games played on the edge set of a random graph. Specifically, we consider the random graph process and analyze the first time in a typical random graph proce…
Local resilience and Hamiltonicity Maker-Breaker games in random-regular graphs
Sonny Ben-Shimon, Michael Krivelevich, Benny Sudakov
For an increasing monotone graph property $\mP$ the \emph{local resilience} of a graph with respect to $\mP$ is the minimal for which there exists of a subgraph $H\subseteq…
A note on regular Ramsey graphs
Noga Alon, Sonny Ben-Shimon, Michael Krivelevich
We prove that there is an absolute constant so that for every natural there exists a triangle-free \emph{regular} graph with no independent set of size at least $C\sqrt{n…
Message passing for the coloring problem: Gallager meets Alon and Kahale
Sonny Ben-Shimon, Dan Vilenchik
Message passing algorithms are popular in many combinatorial optimization problems. For example, experimental results show that {\em survey propagation} (a certain message passing…