Michael Krivelevich
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Michael Krivelevich has a total of 175 co-authors. Here are the top co-authors by number of shared publications:
- Benny Sudakov
ETH Zurich, Switzerland
47 shared publications - Alan Frieze
Department of Mathematical Sciences Carnegie Mellon University Pittsburgh Pennsylvania USA
19 shared publications - Dan Hefetz
Department of Computer Science, Ariel University, Ariel, Israel
17 shared publications - Sahar Diskin
Tel-Aviv University, Israel
14 shared publications - Peleg Michaeli
Mathematical Institute University of Oxford Oxford UK
11 shared publications - Joshua Erde
Institute of Discrete Mathematics Graz University of Technology Steyrergasse 30 8010 Graz Austria
9 shared publications
Latest Publications
- Open Access
- 25 June 2026
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 35 (5) , 1-11
A large hole in pseudo-random graphs
We show that there exist constants delta 1 comma delta 2 greater than 0 $\delta _1,\delta _2\gt 0$ such that if upper G $G$ is an left parenthesis n comma d comma lamda right parenthesis $(n,d,\lambda )$ -graph with lamda divided by d less than or equals delta 1 $\lambda /d\le \delta _1$ , then upper G $G$ contains an induced cycle of length at least delta 2 n divided by d $\delta _2n/d$ . We further demonstrate that, up to a constant factor, this is best possible. Utilising our techniques, we derive that the number of non-isomorphic induced subgraphs of such upper G $G$ is at least exponential in n log d divided by d $n\log d/d$ , and further demonstrate that this is tight up to a constant factor in the exponent.- 25 June 2026
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 35 (5) , 1-11
Open AccessA large hole in pseudo-random graphs
We show that there exist constants delta 1 comma delta 2 greater than 0 $\delta _1,\delta _2\gt 0$ such that if upper G $G$ is an left parenthesis n comma d comma lamda right parenthesis $(n,d,\lambda )$ -graph with lamda divided by d less than or equals delta 1 $\lambda /d\le \delta _1$ , then upper G $G$ contains an induced cycle of length at least delta 2 n divided by d $\delta _2n/d$ . We further demonstrate that, up to a constant factor, this is best possible. Utilising our techniques, we derive that the number of non-isomorphic induced subgraphs of such upper G $G$ is at least exponential in n log d divided by d $n\log d/d$ , and further demonstrate that this is tight up to a constant factor in the exponent. - Open Access
Subgraph discrepancies in the complete graph
Given a 2-edge-coloring $f : E(K_n) \rightarrow \{\pm 1\}$, the discrepancy of a subgraph $F \subseteq K_n$ is defined as $\left| \sum_{e \in E(F)} f(e) \right|$. Erdős, Füredi, Loebl and Sós showed that if $F$ is an $n$-vertex tree with maximum degree at most $(1-\varepsilon)n$, then every 2-coloring of $K_n$ has a copy of $F$ with discrepancy $Ω(\varepsilon)n$. We extend this result by showing that the same conclusion holds for every $n$-vertex graph with maximum degree at most $(1-\varepsilon)n$ and no isolated vertices. We also show that for every $d$-regular $n$-vertex graph $F$ with $d \leq (1-\varepsilon)n$, every 2-coloring of $K_n$ has a copy of $F$ with discrepancy $Ω(\sqrt{\varepsilon d}) \cdot n$. The dependence on $d$ and $n$ is best possible. Finally, we consider specific graphs $F$, namely $K_r$-factors and 2-factors. For each such graph $F$, we determine the optimal constant $λ$ such that every 2-coloring of $K_n$ has a copy of $F$ with discrepancy at least $(λ+ o(1))n$.Open AccessSubgraph discrepancies in the complete graph
Given a 2-edge-coloring $f : E(K_n) \rightarrow \{\pm 1\}$, the discrepancy of a subgraph $F \subseteq K_n$ is defined as $\left| \sum_{e \in E(F)} f(e) \right|$. Erdős, Füredi, Loebl and Sós showed that if $F$ is an $n$-vertex tree with maximum degree at most $(1-\varepsilon)n$, then every 2-coloring of $K_n$ has a copy of $F$ with discrepancy $Ω(\varepsilon)n$. We extend this result by showing that the same conclusion holds for every $n$-vertex graph with maximum degree at most $(1-\varepsilon)n$ and no isolated vertices. We also show that for every $d$-regular $n$-vertex graph $F$ with $d \leq (1-\varepsilon)n$, every 2-coloring of $K_n$ has a copy of $F$ with discrepancy $Ω(\sqrt{\varepsilon d}) \cdot n$. The dependence on $d$ and $n$ is best possible. Finally, we consider specific graphs $F$, namely $K_r$-factors and 2-factors. For each such graph $F$, we determine the optimal constant $λ$ such that every 2-coloring of $K_n$ has a copy of $F$ with discrepancy at least $(λ+ o(1))n$. - 26 January 2026
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 154 (4) , 1407-1420
Minors in small-set expanders
We study large minors in small-set expanders. More precisely, we consider graphs with n n vertices and the property that every set of size at most α n / t \alpha n / t expands by a factor of t t , for some (constant) α > 0 \alpha > 0 and large t = t ( n ) t = t(n) . We obtain the following: Improving results of Krivelevich and Sudakov, we show that a small-set expander contains a complete minor of order n t / log n \sqrt {n t / \log n} . We show that a small-set expander contains every graph H H with O ( n log t / log n ) O(n \log t / \log n) edges and vertices as a minor. We complement this with an upper bound showing that if an n n -vertex graph G G has average degree d d , then there exists a graph with O ( n log d / log n ) O(n \log d / \log n) edges and vertices which is not a minor of G G . This has two consequences: (i) It implies the optimality of our result in the case t = d c t = d^c for some constant c > 0 c > 0 , and (ii) it shows expanders are optimal minor-universal graphs of a given average degree.
- 26 January 2026
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 154 (4) , 1407-1420
Minors in small-set expanders
We study large minors in small-set expanders. More precisely, we consider graphs with n n vertices and the property that every set of size at most α n / t \alpha n / t expands by a factor of t t , for some (constant) α > 0 \alpha > 0 and large t = t ( n ) t = t(n) . We obtain the following: Improving results of Krivelevich and Sudakov, we show that a small-set expander contains a complete minor of order n t / log n \sqrt {n t / \log n} . We show that a small-set expander contains every graph H H with O ( n log t / log n ) O(n \log t / \log n) edges and vertices as a minor. We complement this with an upper bound showing that if an n n -vertex graph G G has average degree d d , then there exists a graph with O ( n log d / log n ) O(n \log d / \log n) edges and vertices which is not a minor of G G . This has two consequences: (i) It implies the optimality of our result in the case t = d c t = d^c for some constant c > 0 c > 0 , and (ii) it shows expanders are optimal minor-universal graphs of a given average degree.
- Open Access
On Independent Spanning Trees in Random and Pseudorandom Graphs
In 1989, Zehavi and Itai conjectured that every $k$-connected graph contains $k$ independent spanning trees rooted at any prescribed vertex $r$. That is, for each vertex $v$, the unique $r$-$v$ paths within these $k$ spanning trees are internally disjoint. This fundamental problem has received much attention, in part motivated by its applications to network reliability, but despite that has only been resolved for $k \le 4$ and certain restricted graph families. We establish the conjecture for almost all graphs of essentially any relevant density. Specifically, we prove that there exists a constant $C > 1$ such that, with high probability, the random graph $G(n,p)$ contains $δ(G)$ independent spanning trees rooted at any vertex whenever $C \log n/n \leq p < 0.99$. Since the lower bound on $p$ coincides (up to the constant $C$) with the connectivity threshold of $G(n,p)$, this result is essentially optimal. In addition, we show that $(n,d,λ)$-graphs with fairly mild bounds on the spectral ratio $d/λ$ contain $(1-o(1))d$ independent spanning trees rooted at each vertex, thereby settling the conjecture asymptotically for random $d$-regular graphs as well.Open AccessOn Independent Spanning Trees in Random and Pseudorandom Graphs
In 1989, Zehavi and Itai conjectured that every $k$-connected graph contains $k$ independent spanning trees rooted at any prescribed vertex $r$. That is, for each vertex $v$, the unique $r$-$v$ paths within these $k$ spanning trees are internally disjoint. This fundamental problem has received much attention, in part motivated by its applications to network reliability, but despite that has only been resolved for $k \le 4$ and certain restricted graph families. We establish the conjecture for almost all graphs of essentially any relevant density. Specifically, we prove that there exists a constant $C > 1$ such that, with high probability, the random graph $G(n,p)$ contains $δ(G)$ independent spanning trees rooted at any vertex whenever $C \log n/n \leq p < 0.99$. Since the lower bound on $p$ coincides (up to the constant $C$) with the connectivity threshold of $G(n,p)$, this result is essentially optimal. In addition, we show that $(n,d,λ)$-graphs with fairly mild bounds on the spectral ratio $d/λ$ contain $(1-o(1))d$ independent spanning trees rooted at each vertex, thereby settling the conjecture asymptotically for random $d$-regular graphs as well. - Open Access
On the edge expansion of random polytopes
A $0/1$-polytope in $\mathbb{R}^n$ is the convex hull of a subset of $\{0,1\}^n$. The graph of a polytope $P$ is the graph whose vertices are the zero-dimensional faces of $P$ and whose edges are the one-dimensional faces of $P$. A conjecture of Mihail and Vazirani states that the edge expansion of the graph of every $0/1$-polytope is at least one. We study a random version of the problem, where the polytope is generated by selecting vertices of $\{0,1\}^n$ independently at random with probability $p\in (0,1)$. Improving earlier results, we show that, for any $p\in (0,1)$, with high probability the edge expansion of the random $0/1$-polytope is bounded from below by an absolute constant.Open AccessOn the edge expansion of random polytopes
A $0/1$-polytope in $\mathbb{R}^n$ is the convex hull of a subset of $\{0,1\}^n$. The graph of a polytope $P$ is the graph whose vertices are the zero-dimensional faces of $P$ and whose edges are the one-dimensional faces of $P$. A conjecture of Mihail and Vazirani states that the edge expansion of the graph of every $0/1$-polytope is at least one. We study a random version of the problem, where the polytope is generated by selecting vertices of $\{0,1\}^n$ independently at random with probability $p\in (0,1)$. Improving earlier results, we show that, for any $p\in (0,1)$, with high probability the edge expansion of the random $0/1$-polytope is bounded from below by an absolute constant. - Open Access
The Hamilton cycle space of random regular graphs and randomly perturbed graphs
The cycle space of a graph $G$, denoted $C(G)$, is a vector space over ${\mathbb F}_2$, spanned by all incidence vectors of edge-sets of cycles of $G$. If $G$ has $n$ vertices, then $C_n(G)$ is the subspace of $C(G)$, spanned by the incidence vectors of Hamilton cycles of $G$. We prove that asymptotically almost surely $C_n(G_{n,d}) = C(G_{n,d})$ holds whenever $n$ is odd and $d$ is a sufficiently large (even) integer. This extends (though with a weaker bound on $d$) the well-known result asserting that $G_{n,d}$ is asymptotically almost surely Hamiltonian for every $d \geq 3$ (but not for $d < 3$). Since $n$ being odd mandates that $d$ be even, somewhat limiting the generality of our result, we also prove that if $n$ is even and $d$ is any sufficiently large integer, then asymptotically almost surely $C_{n-1}(G_{n,d}) = C(G_{n,d})$. An influential result of Bohman, Frieze, and Martin asserts that if $H$ is an $n$-vertex graph with minimum degree at least $δn$ for some constant $δ> 0$, and $G \sim \mathbb{G}(n, C/n)$, where $C := C(δ)$ is a sufficiently large constant, then $H \cup G$ is asymptotically almost surely Hamiltonian. We strengthen this result by proving that the same assumptions on $H$ and $G$ ensure that $C_n(H \cup G) = C(H \cup G)$ holds asymptotically almost surely.Open AccessThe Hamilton cycle space of random regular graphs and randomly perturbed graphs
The cycle space of a graph $G$, denoted $C(G)$, is a vector space over ${\mathbb F}_2$, spanned by all incidence vectors of edge-sets of cycles of $G$. If $G$ has $n$ vertices, then $C_n(G)$ is the subspace of $C(G)$, spanned by the incidence vectors of Hamilton cycles of $G$. We prove that asymptotically almost surely $C_n(G_{n,d}) = C(G_{n,d})$ holds whenever $n$ is odd and $d$ is a sufficiently large (even) integer. This extends (though with a weaker bound on $d$) the well-known result asserting that $G_{n,d}$ is asymptotically almost surely Hamiltonian for every $d \geq 3$ (but not for $d < 3$). Since $n$ being odd mandates that $d$ be even, somewhat limiting the generality of our result, we also prove that if $n$ is even and $d$ is any sufficiently large integer, then asymptotically almost surely $C_{n-1}(G_{n,d}) = C(G_{n,d})$. An influential result of Bohman, Frieze, and Martin asserts that if $H$ is an $n$-vertex graph with minimum degree at least $δn$ for some constant $δ> 0$, and $G \sim \mathbb{G}(n, C/n)$, where $C := C(δ)$ is a sufficiently large constant, then $H \cup G$ is asymptotically almost surely Hamiltonian. We strengthen this result by proving that the same assumptions on $H$ and $G$ ensure that $C_n(H \cup G) = C(H \cup G)$ holds asymptotically almost surely. - Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 329-335
Disjoint Connected Dominating Sets in Pseudorandom Graphs
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 329-335
Open AccessDisjoint Connected Dominating Sets in Pseudorandom Graphs
- Open Access
A large hole in pseudo-random graphs
We show that there exist constants $δ_1,δ_2>0$ such that if $G$ is an $(n,d,λ)$-graph with $λ/d\leδ_1$, then $G$ contains an induced cycle of length at least $δ_2n/d$. We further demonstrate that, up to a constant factor, this is best possible. Utilising our techniques, we derive that the number of non-isomorphic induced subgraphs of such $G$ is at least exponential in $n\log d/d$, and further demonstrate that this is tight up to a constant factor in the exponent.Open AccessA large hole in pseudo-random graphs
We show that there exist constants $δ_1,δ_2>0$ such that if $G$ is an $(n,d,λ)$-graph with $λ/d\leδ_1$, then $G$ contains an induced cycle of length at least $δ_2n/d$. We further demonstrate that, up to a constant factor, this is best possible. Utilising our techniques, we derive that the number of non-isomorphic induced subgraphs of such $G$ is at least exponential in $n\log d/d$, and further demonstrate that this is tight up to a constant factor in the exponent. - Open Access
Non-isomorphic subgraphs in random graphs
We establish the asymptotic behaviour of $μ(G(n,p))$, the number of unlabelled induced subgraphs in the binomial random graph $G(n,p)$, for almost the entire range of the probability parameter $p=p(n)\in[0,1]$. In particular, we show that typically the number of subgraphs becomes exponential when $p$ passes $1/n$, reaches maximum possible base of exponent (asymptotically) when $p\gg 1/n$, and reaches the asymptotic value $2^n$ when $p$ passes $2\ln n/n$. For $p\gg \ln n/n$, we get the first order term and asymptotics of the second order term of $μ(G(n,p))$. We also prove that random regular graphs $G_{n,d}$ typically have $μ(G_{n,d})\geq 2^{c_d n}$ for all $d\geq 3$ and some positive constant $c_d$ such that $c_d\to 1$ as $d\to\infty$.Open AccessNon-isomorphic subgraphs in random graphs
We establish the asymptotic behaviour of $μ(G(n,p))$, the number of unlabelled induced subgraphs in the binomial random graph $G(n,p)$, for almost the entire range of the probability parameter $p=p(n)\in[0,1]$. In particular, we show that typically the number of subgraphs becomes exponential when $p$ passes $1/n$, reaches maximum possible base of exponent (asymptotically) when $p\gg 1/n$, and reaches the asymptotic value $2^n$ when $p$ passes $2\ln n/n$. For $p\gg \ln n/n$, we get the first order term and asymptotics of the second order term of $μ(G(n,p))$. We also prove that random regular graphs $G_{n,d}$ typically have $μ(G_{n,d})\geq 2^{c_d n}$ for all $d\geq 3$ and some positive constant $c_d$ such that $c_d\to 1$ as $d\to\infty$. - Open Access
Nearly spanning cycle in the percolated hypercube
Let $Q^d$ be the $d$-dimensional binary hypercube. We form a random subgraph $Q^d_p\subseteq Q^d$ by retaining each edge of $Q^d$ independently with probability $p$. We show that, for every constant $\varepsilon>0$, there exists a constant $C=C(\varepsilon)>0$ such that, if $p\ge C/d$, then with high probability $Q^d_p$ contains a cycle of length at least $(1-\varepsilon)2^d$. This confirms a long-standing folklore conjecture, stated in particular by Condon, Espuny Díaz, Girão, Kühn, and Osthus [Hamiltonicity of random subgraphs of the hypercube, Mem. Amer. Math. Soc. 305 (2024), No. 1534].Open AccessNearly spanning cycle in the percolated hypercube
Let $Q^d$ be the $d$-dimensional binary hypercube. We form a random subgraph $Q^d_p\subseteq Q^d$ by retaining each edge of $Q^d$ independently with probability $p$. We show that, for every constant $\varepsilon>0$, there exists a constant $C=C(\varepsilon)>0$ such that, if $p\ge C/d$, then with high probability $Q^d_p$ contains a cycle of length at least $(1-\varepsilon)2^d$. This confirms a long-standing folklore conjecture, stated in particular by Condon, Espuny Díaz, Girão, Kühn, and Osthus [Hamiltonicity of random subgraphs of the hypercube, Mem. Amer. Math. Soc. 305 (2024), No. 1534].