Michael Krivelevich

activity

20002026

most citedAdding random edges to dense graphs

53 citations · 436 across the 144 of their papers we have counts for

collaborators

178 papers

math.CO2026

Long induced cycles in pseudorandom graphs

Sahar Diskin, Lyuben Lichev, Michael Krivelevich +1

We show that, for some absolute constants $c_{1}, c_{2} > 0$ , every $(n, d, λ)$ -graph with $λ \leq c_{1} d$ contains an induced cycle of length at least $c_{2} n lo g (d / λ) / d$ . This is best possible…

math.CO2026

Rigidity of expanders and pseudorandom graphs

Michael Krivelevich, Alan Lew, Peleg Michaeli

A graph $G = (V, E)$ is called $d$ -rigid if, for a generic embedding of its vertices in $R^{d}$ , the only continuous motions of the vertices preserving the distances between al…

math.CO2026

On graphs whose cycle space is spanned by their Hamilton cycles

Dan Hefetz, Michael Krivelevich

The cycle space of a graph $G$ , denoted $C (G)$ , is a vector space over $F_{2}$ , spanned by all incidence vectors of edge-sets of cycles of $G$ . If $G$ has $n$ ver…

math.CO2026

Efficient Hamilton covers and linear arboricity of random graphs

Nemanja Draganić, Michael Krivelevich

A Hamilton cover of a graph is a collection of Hamilton cycles whose union contains all edges. Since each Hamilton cycle covers two edges at every vertex, every Hamilton cover has…

math.CO2026

Supercritical Site Percolation on Regular Graphs

Sahar Diskin, Michael Krivelevich, Itay Markbreit

We consider site (vertex) percolation on $d$ -regular graphs, for both constant-degree and growing-degree cases. We give sufficient, and relatively tight, conditions for the emergen…

math.CO2026

Combinatorial sufficient conditions for graph rigidity and applications to random graphs

Michael Krivelevich, Alan Lew, Peleg Michaeli

A graph $G = (V, E)$ is called $d$ -rigid if, for a generic embedding of its vertices in $R^{d}$ , every edge-length preserving continuous motion of the vertices preserves the di…