Michael Krivelevich

Research interests

Publications

• The phase transition in random graphs: A simple proof

  Random Structures and Algorithms · 2012 · 10.1002/rsa.20470

• Variations on cops and robbers

  Journal of Graph Theory · 2011 · 10.1002/jgt.20591

• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛

  Journal of the American Mathematical Society · 2010 · 10.1090/s0894-0347-2010-00678-9

• The rainbow connection of a graph is (at most) reciprocal to its minimum degree

  Journal of Graph Theory · 2009 · 10.1002/jgt.20418

• On two Hamilton cycle problems in random graphs

  Israel Journal of Mathematics · 2008 · 10.1007/s11856-008-1028-8

• Pseudo-random Graphs

  Bolyai Society mathematical studies · 2006 · https://doi.org/10.1007/978-3-540-32439-3_10

• Testing Reed–Muller Codes

  IEEE Transactions on Information Theory · 2005 · 10.1109/tit.2005.856958

• Tight Bounds for Testing Bipartiteness in General Graphs

  SIAM Journal on Computing · 2004 · 10.1137/s0097539703436424

• Maximum cuts and judicious partitions in graphs without short cycles

  Journal of Combinatorial Theory Series B · 2003 · 10.1016/s0095-8956(03)00036-4

• Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions

  Combinatorics Probability Computing · 2003 · 10.1017/s0963548303005741

• Testing Low-Degree Polynomials over GF(2)

  Lecture notes in computer science · 2003 · 10.1007/978-3-540-45198-3_17

• The Largest Eigenvalue of Sparse Random Graphs

  Combinatorics Probability Computing · 2003 · https://doi.org/10.1017/s0963548302005424

• Upper bounds on the rate of LDPC codes

  IEEE Transactions on Information Theory · 2002 · 10.1109/tit.2002.801408

• Sparse pseudo‐random graphs are Hamiltonian

  Journal of Graph Theory · 2002 · 10.1002/jgt.10065

• On the concentration of eigenvalues of random symmetric matrices

  Israel Journal of Mathematics · 2002 · 10.1007/bf02785860

• Testing k -colorability

  SIAM Journal on Discrete Mathematics · 2002 · 10.1137/s0895480199358655

• Regular Languages are Testable with a Constant Number of Queries

  SIAM Journal on Computing · 2001 · 10.1137/s0097539700366528

• Random regular graphs of high degree

  Random Structures and Algorithms · 2001 · 10.1002/rsa.1013

• Efficient Testing of Large Graphs

  COMBINATORICA · 2000 · https://doi.org/10.1007/s004930070001

• Coloring Graphs with Sparse Neighborhoods

  Journal of Combinatorial Theory Series B · 1999 · 10.1006/jctb.1999.1910

• Finding a large hidden clique in a random graph

  Random Structures and Algorithms · 1998 · https://doi.org/10.1002/(sici)1098-2418(199810/12)13:3/4<457::aid-rsa14>3.0.co;2-w

• The concentration of the chromatic number of random graphs

  COMBINATORICA · 1997 · 10.1007/bf01215914

Current projects

No projects listed.