Michael Krivelevich
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Michael Krivelevich has a total of 20 co-authors. Here are the top co-authors by number of shared publications:
- Noga Alon
Department of Mathematics, Princeton University, Princeton, USA
7 shared publications - Benny Sudakov
ETH Zurich, Switzerland
4 shared publications - Benny Sudakov
Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel
3 shared publications - Van H. Vu
Microsoft Research
3 shared publications Alan Frieze
Department of Mathematical Sciences Carnegie Mellon University PA15213 Pittsburgh U.S.A
1 shared publication- Alan Frieze
Department of Mathematical Sciences Carnegie Mellon University Pittsburgh Pennsylvania USA
1 shared publication
Latest Publications
- Open Access
- 20 January 2017
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 24 (1) , P1.28
Small Subgraphs in the Trace of a Random Walk
We consider the combinatorial properties of the trace of a random walk on the complete graph and on the random graph $G(n,p)$. In particular, we study the appearance of a fixed subgraph in the trace. We prove that for a subgraph containing a cycle, the threshold for its appearance in the trace of a random walk of length $m$ is essentially equal to the threshold for its appearance in the random graph drawn from $G(n,m)$. In the case where the base graph is the complete graph, we show that a fixed forest appears in the trace typically much earlier than it appears in $G(n,m)$.- 20 January 2017
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 24 (1) , P1.28
Open AccessSmall Subgraphs in the Trace of a Random Walk
We consider the combinatorial properties of the trace of a random walk on the complete graph and on the random graph $G(n,p)$. In particular, we study the appearance of a fixed subgraph in the trace. We prove that for a subgraph containing a cycle, the threshold for its appearance in the trace of a random walk of length $m$ is essentially equal to the threshold for its appearance in the random graph drawn from $G(n,m)$. In the case where the base graph is the complete graph, we show that a fixed forest appears in the trace typically much earlier than it appears in $G(n,m)$. - Open Access
The emergence of a giant component in random subgraphs of pseudo-random graphs
Let $G$ be a $d$-regular graph $G$ on $n$ vertices. Suppose that the adjacency matrix of $G$ is such that the eigenvalue $\lambda$ which is second largest in absolute value satisfies $\lambda=o(d)$. Let $G_p$ with $p=\frac{\alpha}{d}$ be obtained from $G$ by including each edge of $G$ independently with probability $p$. We show that if $\alpha1$ then $G_p$ contains a unique giant component of size $\Omega(n)$, with all other components of size $O(\log n)$.Open AccessThe emergence of a giant component in random subgraphs of pseudo-random graphs
Let $G$ be a $d$-regular graph $G$ on $n$ vertices. Suppose that the adjacency matrix of $G$ is such that the eigenvalue $\lambda$ which is second largest in absolute value satisfies $\lambda=o(d)$. Let $G_p$ with $p=\frac{\alpha}{d}$ be obtained from $G$ by including each edge of $G$ independently with probability $p$. We show that if $\alpha1$ then $G_p$ contains a unique giant component of size $\Omega(n)$, with all other components of size $O(\log n)$. - 1 July 2004
- Published by Springer Nature in Combinatorica
- Vol. 24 (3) , 403-426
Triangle Factors In Sparse Pseudo-Random Graphs
- 1 July 2004
- Published by Springer Nature in Combinatorica
- Vol. 24 (3) , 403-426
Triangle Factors In Sparse Pseudo-Random Graphs
- 31 October 2003
- Published by Wiley in Random Structures & Algorithms
- Vol. 24 (1) , 42-50
The emergence of a giant component in random subgraphs of pseudo‐random graphs
Let G be a d‐regular graph G on n vertices. Suppose that the adjacency matrix of G is such that the eigenvalue λ which is second largest in absolute value satisfies λ = o(d). Let Gp with p = α/d be obtained from G by including each edge of G independently with probability p. We show that if α < 1, then whp the maximum component size of Gp is O(log n) and if α > 1, then Gp contains a unique giant component of size Ω(n), with all other components of size O(log n). © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2004
- 31 October 2003
- Published by Wiley in Random Structures & Algorithms
- Vol. 24 (1) , 42-50
The emergence of a giant component in random subgraphs of pseudo‐random graphs
Let G be a d‐regular graph G on n vertices. Suppose that the adjacency matrix of G is such that the eigenvalue λ which is second largest in absolute value satisfies λ = o(d). Let Gp with p = α/d be obtained from G by including each edge of G independently with probability p. We show that if α < 1, then whp the maximum component size of Gp is O(log n) and if α > 1, then Gp contains a unique giant component of size Ω(n), with all other components of size O(log n). © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2004
- 28 January 2003
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 12 (1) , 61-72
The Largest Eigenvalue of Sparse Random Graphs
We prove that, for all values of the edge probability tends to infinity.
- 28 January 2003
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 12 (1) , 61-72
The Largest Eigenvalue of Sparse Random Graphs
We prove that, for all values of the edge probability tends to infinity.
- 1 December 2002
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 131 (1) , 259-267
On the concentration of eigenvalues of random symmetric matrices
- 1 December 2002
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 131 (1) , 259-267
On the concentration of eigenvalues of random symmetric matrices
- 1 January 2002
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 27 (4) , 585-602
Fractional Planks
- 1 January 2002
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 27 (4) , 585-602
Fractional Planks
- 20 June 2001
- Published by Wiley in Random Structures & Algorithms
- Vol. 18 (4) , 346-363
Random regular graphs of high degree
Random d‐regular graphs have been well studied when d is fixed and the number of vertices goes to infinity. We obtain results on many of the properties of a random d‐regular graph when d=d(n) grows more quickly than $\sqrt{n}$ . These properties include connectivity, hamiltonicity, independent set size, chromatic number, choice number, and the size of the second eigenvalue, among others. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 346–363, 2001.- 20 June 2001
- Published by Wiley in Random Structures & Algorithms
- Vol. 18 (4) , 346-363
Random regular graphs of high degree
Random d‐regular graphs have been well studied when d is fixed and the number of vertices goes to infinity. We obtain results on many of the properties of a random d‐regular graph when d=d(n) grows more quickly than $\sqrt{n}$ . These properties include connectivity, hamiltonicity, independent set size, chromatic number, choice number, and the size of the second eigenvalue, among others. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 346–363, 2001.- Open Access
THe largest eigenvalue of sparse random graphs
We prove that for all values of the edge probability p(n) the largest eigenvalue of a random graph G(n,p) satisfies almost surely: \lambda_1(G)=(1+o(1))max{\sqrt{\Delta},np}, where \Delta is a maximal degree of G, and the o(1) term tends to zero as max{\sqrt{\Delta},np} tends to infinity.
Open AccessTHe largest eigenvalue of sparse random graphs
We prove that for all values of the edge probability p(n) the largest eigenvalue of a random graph G(n,p) satisfies almost surely: \lambda_1(G)=(1+o(1))max{\sqrt{\Delta},np}, where \Delta is a maximal degree of G, and the o(1) term tends to zero as max{\sqrt{\Delta},np} tends to infinity.
- Open Access
On the concentration of eigenvalues of random symmetric matrices
We prove that few largest (and most important) eigenvalues of random symmetric matrices of various kinds are very strongly concentrated. This strong concentration enables us to compute the means of these eigenvalues with high precision. Our approach uses Talagrand's inequality and is very different from standard approaches.
Open AccessOn the concentration of eigenvalues of random symmetric matrices
We prove that few largest (and most important) eigenvalues of random symmetric matrices of various kinds are very strongly concentrated. This strong concentration enables us to compute the means of these eigenvalues with high precision. Our approach uses Talagrand's inequality and is very different from standard approaches.