Michael Krivelevich's Papers

1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013
Preprints

TOP
1994

  • M. Krivelevich,
    • K^s-free graphs without large K^r-free subgraphs,
    Combinatorics, Probability and Computing 3 (1994), 349-354.  

    TOP
    1995

  • M. Krivelevich,
    • On a conjecture of Tuza about packing and covering of triangles,
    Discrete Mathematics 142 (1995), 281-286.  
  • M. Krivelevich,
    • On the edge distribution of triangle-free graphs,
    Combinatorics, Probability and Computing 3 (1994), 349-354.  
  • M. Krivelevich,
    • Bounding Ramsey numbers through large deviation inequalities,
    Random Structures and Algorithms 7 (1995), 145-155.  

    TOP
    1996

  • R. Aharoni, R. Holzman and M. Krivelevich,
    • On a Theorem of Lovasz on covers in r-partite hypergraphs,
    Combinatorica 16 (1996), 149-174.  
  • N. Alon, P. Erdos, R. Holzman and M. Krivelevich,
    • On k-saturated graphs with restrictions on the degrees,
    Journal of Graph Theory 23 (1996), 1-20.  
  • M. Krivelevich,
    • Perfect fractional matchings in random uniform hypergraphs,
    Random Structures and Algorithms 9 (1996), 317-334.  

    TOP
    1997

  • M. Krivelevich,
    • Almost perfect matchings in random uniform hypergraphs,
    Discrete Mathematics 170 (1997), 259-263.  
  • N. Alon, M. Krivelevich and B. Sudakov,
    • Subgraphs with a large cochromatic number,
    Journal of Graph Theory 26 (1997), 295-297.  
  • M. Krivelevich,
    • Triangle factors in random graphs,
    Combinatorics, Probability and Computing 6 (1997), 337-347.  
  • N. Alon and M. Krivelevich,
    • Constructive bounds for a Ramsey-type problem,
    Graphs and Combinatorics 13 (1997), 217-225.  
  • M. Krivelevich,
    • Approximate set covering in uniform hypergraphs,
    Journal of Algorithms 25 (1997), 118-143.  
  • N. Alon and M. Krivelevich,
    • The concentration of the chromatic number of random graphs,
    Combinatorica 17 (1997), 303-313.  
  • M. Krivelevich,
    • On the minimal number of edges in color-critical graphs,
    Combinatorica 17 (1997), 401-426.  

    TOP
    1998

  • M. Krivelevich,
    • An improved bound on the minimal number of edges in color-critical graphs,
    Electronic J. Combinatorics, Volume 5(1) (1998), paper R4.  
  • N. Alon, M. Krivelevich and B. Sudakov,
    • Finding a large hidden clique in a random graph,
    Proceedings of the $9^{th}$ Symposium on Discrete Algorithms (SODA'98), 594-598. Journal version: Random Structures and Algorithms, 13 (1998), 457-466.  
  • M. Krivelevich,
    • A lower bound for irredundant Ramsey numbers,
    Discrete Mathematics 183 (1998), 185-192.  
  • M. Krivelevich and B. Sudakov,
    • The chromatic numbers of random hypergraphs,
    Random Structures and Algorithms 12 (1998), 381-403.  
  • M. Krivelevich and B. Sudakov,
    • Coloring random graphs,
    Information Processing Letters 67 (1998), 71-74.  
  • M. Krivelevich and B. Sudakov,
    • Approximate coloring of uniform hypergraphs,
    Proceedings of the $6^{th}$ Annual European Symposium on Algorithms (ESA'98), Lecture Notes in Computer Science 1461, 477-489. Journal version: Journal of Algorithms 49 (2003), 2-12.  
  • N. Alon and M. Krivelevich,
    • The choice number of random bipartite graphs,
    Annals of Combinatorics 2 (1998), 291-297.  

    TOP
    1999

  • N. Alon, M. Krivelevich and B. Sudakov,
    • Coloring graphs with sparse neighborhoods,
    Journal of Combinatorial Theory Ser. B 77 (1999), 73-82.  
  • N. Alon, E. Fischer, M. Krivelevich and M. Szegedy,
    • Efficient testing of large graphs,
    Proceedings of the 40th Symposium on Foundations of Computer Science (FOCS'99), IEEE Press 1999, 656-666. Journal version: Combinatorica 20 (2000), 451-476.  
  • N. Alon, M. Krivelevich, I. Newman and M. Szegedy,
    • Regular languages are testable with a constant number of queries,
    Proceedings of the 40th Symposium on Foundations of Computer Science (FOCS'99), IEEE Press 1999, 645-655. Journal version: SIAM Journal on Computing 30 (2001), 1842-1862.  
  • N. Alon, M. Krivelevich and B. Sudakov,
    • List coloring of random and pseudo-random graphs,
    Combinatorica 19 (1999), 453-472.  

    TOP
    2000

  • M. Krivelevich,
    • The choice number of dense random graphs,
    Combinatorics, Probability and Computing 9 (2000), 19-26.  
  • M. Krivelevich and V. H. Vu,
    • Approximating the independence number and the chromatic number in expected polynomial time,
    27th International Colloquium on Automata, Languages and Programming (ICALP'2000), Lecture Notes in Computer Science 1853, 13-24. Also: Journal of Combinatorial Optimization 6 (2002), 143-155.  
  • N. Alon, H. Kaplan, M. Krivelevich, D. Malkhi and J. Stern,
    • Scalable secure storage when half the system is faulty,
    27th International Colloquium on Automata, Languages and Programming (ICALP'2000), Lecture Notes in Computer Science 1853, 576-587. Journal version: Information and Computation 174 (2002), 203-213.  
  • D. Achlioptas, J. H. Kim, M. Krivelevich and P. Tetali,
    • Two-coloring random hypergraphs,
    4th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM'2000), ICALP Workshops 2000, Proceedings in Informatics 8, Carleton Scientific, 85-96. Journal version: Random Structures and Algorithms 20 (2002), 249-259.  
  • E. Friedgut and M. Krivelevich,
    • Sharp thresholds for certain Ramsey properties of random graphs,
    Random Structures and Algorithms 17 (2000), 1-19.  
  • N. Alon, M. Krivelevich and P. Seymour,
    • Long cycles in critical graphs,
    Journal of Graph Theory 35 (2000), 193-196.  

    TOP
    2001

  • M. Krivelevich, R. Nathaniel and B. Sudakov,
    • Approximating coloring and maximum independent set in 3-uniform hypergraphs,
    Proceedings of the 12th Symposium on Discrete Algorithms (SODA'2001), 327-328. Journal version: Journal of Algorithms 41 (2001), 99-113.  
  • A. Goerdt and M. Krivelevich,
    • Efficient recognition of random unsatisfiable k-SAT instances by spectral methods,
    Proceedings of the 18th International Symposium on Theoretical Aspects of Computer Science (STACS'2001), Lecture Notes in Computer Science 2010, 294-304.  
  • M. Krivelevich, B. Sudakov, V. H. Vu and N. Wormald,
    • Random regular graphs of high degree,
    Random Structures and Algorithms 18 (2001), 346-363.  
  • M. Krivelevich and V. H. Vu,
    • Choosability in random hypergraphs,
    Journal of Combinatorial Theory Ser. B 83 (2001), 241-257.  

    TOP
    2002

  • M. Krivelevich,
    • Deciding k-colorability in expected polynomial time,
    Information Processing Letters 81 (2002), 1-6.  
  • N. Alon and M. Krivelevich,
    • Testing k-colorability,
    SIAM Journal on Discrete Mathematics 15 (2002), 211-227.  
  • R. Aharoni, R. Holzman, M. Krivelevich and R. Meshulam,
    • Fractional planks,
    Discrete and Computational Geometry 27 (2002), 585-602.  
  • M. Krivelevich,
    • Sparse graphs usually have exponentially many optimal colorings.
    Electronic Journal of Combinatorics 9 (2002), publ. R27, 8pp.  
  • N. Alon, G. Cohen, M. Krivelevich and S. Litsyn,
    • Generalized hashing and applications to digital fingerprinting.
    Proceedings of the IEEE International Symposium on Information Theory (ISIT) 2002, p. 436. Journal version: Journal of Combinatorial Theory Series A 104 (2003), 207-215.  
  • D. Burshtein, M. Krivelevich, S. Litsyn and G. Miller,
    • Upper bounds on the rate of LDPC codes.
    IEEE Transactions on Information Theory 48 (2002), 2437-2449.  
  • M. Krivelevich,
    • Coloring random graphs - an algorithmic perspective.
    Proceedings of the 2nd Colloquium on Mathematics and Computer Science (MathInfo'2002), B. Chauvin et al. Eds., Birkhauser, Basel, 2002, 175-195.  
  • A. Frieze and M. Krivelevich,
    • Hamilton cycles in random subgraphs of pseudo-random graphs,
    Discrete Mathematics 256 (2002), 137-150.  
  • M. Krivelevich, B. Sudakov and V. H. Vu,
    • A sharp threshold for network reliability,
    Combinatorics, Probability and Computing 11 (2002), 465-474..  
  • N. Alon, M. Krivelevich and V. H. Vu,
    • On the concentration of eigenvalues of random symmetric matrices,
    Israel Journal of Mathematics 131 (2002), 259-267.  

    TOP
    2003

  • M. Krivelevich, B. Sudakov, V. H. Vu and N. Wormald,
    • On the probability of independent sets in random graphs.
    Random Structures and Algorithms 22 (2003), 1-14.  
  • M. Krivelevich and B. Sudakov,
    • Sparse pseudo-random graphs are Hamiltonian.
    Journal of Graph Theory 42 (2003), 17-33.  
  • M. Krivelevich and B. Sudakov,
    • The largest eigenvalue of sparse random graphs.
    Combinatorics, Probability and Computing 12 (2003), 61-72.  
  • G. Cohen, M. Krivelevich and S. Litsyn,
    • Bounds on distance distributions in codes of given size.
    Chapter 4 of "Communication, Information and Network Security", V. Bhargava et al., pp. 33-41.  
  • N. Alon, M. Krivelevich and B. Sudakov,
    • Induced subgraphs of prescribed size.
    Journal of Graph Theory 43 (2003), 239-251.  
  • N. Alon, B. Bollobas, M. Krivelevich and B. Sudakov,
    • Maximum cuts and judicious partitions in graphs without short cycles.
    Journal of Combinatorial Theory Ser. B 88 (2003), 329-346.  
  • M. Krivelevich, B. Sudakov and V. H. Vu,
    • Covering codes with improved density.
    IEEE Transactions on Information Theory 49 (2003), 1812-1815.  
  • T. Kaufman, M. Krivelevich and D. Ron,
    • Tight bounds for testing bipartiteness in general graphs.
    Lecture Notes in Computer Science 2764, 341-353. Journal version: SIAM Journal on Computing 33 (2004), 1441-1483.  
  • N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn and D. Ron,
    • Testing low-degree polynomials over GF(2).
    Lecture Notes in Computer Science 2764, 188-199. Journal version. IEEE Transactions on Information Theory 51 (2005), 4032-4039.  
  • N. Alon, M. Krivelevich and B. Sudakov,
    • Turan numbers of bipartite graphs and related Ramsey-type questions.
    Combinatorics, Probability and Computing 12 (2003), 477-494.  

    TOP
    2004

  • A. Frieze, M. Krivelevich and R. Martin,
    • The emergence of a giant component in random subgraphs of pseudo-random graphs.
    Random Structures and Algorithms 24 (2004), 42-50.  
  • N. Alon, G. Gutin and M. Krivelevich,
    • Algorithms with large domination ratio.
    Journal of Algorithms 50 (2004), 118-131.  
  • T. Bohman, A. Frieze, M. Krivelevich and R. Martin,
    • Adding random edges to dense graphs.
    Random Structures and Algorithms 24 (2004), 105-117.  
  • M. Krivelevich, S. Litsyn and A. Vardy,
    • A lower bound on the density of sphere packings via graph theory.
    International Mathematical Research Notices 43 (2004), 2271-2279.  
  • M. Krivelevich, B. Sudakov and T. Szabo,
    • Triangle factors in pseudo-random graphs.
    Combinatorica 24 (2004), 403-426.  
  • M. Krivelevich and A. Nachmias,
    • Colouring powers of cycles from random lists.
    European Journal of Combinatorics 25 (2004), 961-968.  

    TOP
    2005

  • A. Ashikhmin, G. Cohen, M. Krivelevich and S. Litsyn,
    • Bounds on distance distributions in codes of known size.
    IEEE Transactions on Information Theory 51 (2005), 250-258.  
  • A. Flaxman, A. Frieze and M. Krivelevich,
    • On the random 2-stage minimum spanning tree.
    Proceedings of the 16th Symposium on Discrete Algorithms (SODA'2005), 919-926. Journal version. Random Structures and Algorithms 28 (2006), 24-36  
  • M. Krivelevich, Z. Nutov and R. Yuster,
    • Approximation algorithms for cycle packing problems.
    Proceedings of the 16th Symposium on Discrete Algorithms (SODA'2005), 556-561.  
  • A. Frieze and M. Krivelevich,
    • On packing Hamilton cycles in epsilon-regular graphs.
    Journal of Combinatorial Theory Series B 94 (2005), 159-172.  
  • N. Alon, M. Krivelevich, J. Spencer and T. Szabo,
    • Discrepancy games.
    Electronic Journal of Combinatorics Volume 12 (1) (2005), publ. R51.  
  • J. Friedman, A. Goerdt and M. Krivelevich,
    • Recognizing more unsatisfiable random k-SAT instances efficiently.
    SIAM Journal on Computing 35 (1005), 408-430.  
  • N. Alon, M. Krivelevich and B. Sudakov,
    • MaxCut in H-free graphs.
    Combinatorics, Probability and Computing 14 (2005), 629-647.  
  • A. Frieze, M. Krivelevich, O. Pikhurko and T. Szabo,
    • The game of JumbleG.
    Combinatorics, Probability and Computing 14 (2005), 783-793.  
  • A. Frieze, M. Krivelevich and B. Sudakov,
    • The strong chromatic index of random graphs.
    SIAM Journal on Discrete Mathematics 19 (2005), 719-727.  

    TOP
    2006

  • N. Alon, T. Kaufman, M. Krivelevich and D. Ron,
    • Testing triangle-freeness in general graphs.
    Proceedings of the 17th Symposium on Discrete Algorithms (SODA'06), 279-288. Journal version: SIAM Journal on Discrete Mathematics 22 (2008), 786-819.  
  • M. Krivelevich and D. Vilenchik,
    • Solving random satisfiable 3CNF formulas in expected polynomial time.
    Proceedings of the 17th Symposium on Discrete Algorithms (SODA'06), 454-463.  
  • M. Krivelevich and D. Vilenchik,
    • Semirandom models as benchmarks for coloring algorithms.
    Proceedings of 3rd Workshop on Analytic Algorithmics and Combinatorics (ANALCO'06), 211--221.  
  • N. Gazit and M. Krivelevich,
    • On the asymptotic value of the choice number of complete multi-partite graphs.
    Journal of Graph Theory 52 (2006), 123-134.  
  • M. Krivelevich and B. Sudakov,
    • Pseudo-random graphs.
    More sets, graphs and numbers, E. Gyori, G. O. H. Katona and L. Lovasz, Eds., Bolyai Society Mathematical Studies Vol. 15, 199--262.  
  • A. Frieze and M. Krivelevich,
    • Almost universal graphs.
    Random Structures and Algorithms 28 (2006), 499-510.  
  • M. Krivelevich, B. Sudakov and P. Tetali,
    • On smoothed analysis in dense graphs and formulas.
    Random Structures and Algorithms 29 (2006), 180-193.  
  • M. Krivelevich and A. Nachmias,
    • Colouring complete bipartite graphs from random lists.
    Random Structures and Algorithms 29 (2006), 436-449.  

    TOP
    2007

  • A. Coja-Oghlan, M. Krivelevich and D. Vilenchik,
    • Why almost all k-colorable graphs are easy.
    Proceedings of the 24th International Symposium on Theoretical Computer Science (STACS'2007), Lecture Notes in Computer Science 4393, 121-132. Journal version: Theory of Computing Systems 46 (2010), 523-565.  
  • D. Hefetz, M. Krivelevich and T. Szabo,
    • BartMoe games, JumbleG and discrepancy.
    European Journal of Combinatorics 28 (2007), 1131-1143.  
  • S. Haber and M. Krivelevich,
    • On fractional K-factors of random graphs.
    Random Structures and Algorithms 30 (2007), 441-463.  
  • D. Hefetz, M. Krivelevich and T. Szabo,
    • Avoider-Enforcer games.
    Journal of Combinatorial Theory Series A 114 (2007), 840-853.  
  • A. Frieze, M. Krivelevich and C. Smyth,
    • On the chromatic number of random graphs with a fixed degree sequence.
    Combinatorics, Probability and Computing 16 (2007), 733-746.  
  • N. Alon, F. Fomin, G. Gutin, M. Krivelevich and S. Saurabh, Parametrized algorithms for directed maximum leaf problems.
    Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP'2007), Lecture Notes in Computer Science 4596, 352-362.  
  • M. Krivelevich, Z. Nutov, M. Salavatipour, J. Verstraete and R. Yuster,
    • Approximation algorithms and hardness results for cycle packing problems.
    ACM Transactions on Algorithms, Volume 3 (2007), Article 48.  
  • N. Alon, F. Fomin, G. Gutin, M. Krivelevich and S. Saurabh, Better algorithms and bounds for directed maximum leaf problems.
    Proceedings of the Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'2007), Lecture Notes in Computer Science 4855, 316-327. Journal version: Spanning directed trees with many leaves. SIAM Journal on Discrete Mathematics 23 (2009), 466-476.  
  • A. Coja-Oghlan, M. Krivelevich and D. Vilenchik, Why almost all k-CNF formulas are easy.
    Conference on Analysis of Algorithms (AOFA'2007), Discrete Mathematics and Theoretical Computer Science (DMTCS), AH, 2007, 89-102.  
  • N. Alon, M. Krivelevich and B. Sudakov,
    • Embedding nearly spanning bounded degree trees.
    Combinatorica 27 (2007), 629-644.  

    TOP
    2008

  • I. Benjamini, S. Haber, M. Krivelevich and E. Lubetzky,
    • The isoperimetric constant of the random graph process.
    Random Structures and Algorithms 32 (2008), 101-114.  
  • I. Ben-Eliezer, T. Kaufman, M. Krivelevich and D. Ron, Comparing the strength of query types in property testing: the case of testing k-colorability.
    Proceedings of the 19th Symposium on Discrete Algorithms (SODA'08), 1213-1222. Journal version: Computational Complexity 22 (2013), 89-135.  
  • D. Hefetz, M. Krivelevich, M. Stojakovic and T. Szabo,
    • Planarity, colorability and minor games.
    SIAM Journal on Discrete Mathematics 22 (2008), 194-212.  
  • A. Frieze and M. Krivelevich, On rainbow trees and cycles.
    Electronic Journal of Combinatorics, Vol. 15 (1) (2008), publ. R59.  
  • M. Krivelevich and T. Szabo, Biased positional games and small hypergraphs with large covers.
    Electronic Journal of Combinatorics, Vol. 15 (1) (2008), publ. R70.  
  • A. Frieze and M. Krivelevich,
    • On two Hamilton cycle problems in random graphs.
    Israel Journal of Mathematics 166 (2008), 221-234.  
  • N. Alon, I. Ben-Eliezer and M. Krivelevich, Small sample spaces cannot fool low degree polynomials.
    Proceedings of the 12th International Workshop on Randomized Techniques in Computation (RANDOM'2008), Lecture Notes in Computer Science 5171 (2008), 266-275.  
  • N. Alon, M. Krivelevich and B. Sudakov, Large nearly regular induced subgraphs.
    SIAM Journal on Discrete Mathematics 22 (2008), 1325-1337.  
  • O. Feldheim and M. Krivelevich, Winning fast in sparse graph construction games.
    Combinatorics, Probability and Computing 17 (2008), 781-791.  
  • N. Alon and M. Krivelevich,
    • Extremal and Probabilistic Combinatorics.
    In: Princeton Compantion to Mathematics, W. T. Gowers, Ed., Princeton University Press 2008, pp. 562-575.  

    TOP
    2009

  • D. Hefetz, M. Krivelevich, M. Stojakovic and T. Szabo, A sharp threshold for the Hamilton cycle Maker-Breaker game.
    Random Structures and Algorithms 34 (2009), 112-122.  
  • M. Krivelevich, P.-S. Loh and B. Sudakov, Avoiding small subgraphs in Achlioptas processes.
    Random Structures and Algorithms 34 (2009), 165-195.  
  • D. Hefetz, M. Krivelevich, M. Stojakovic and T. Szabo,
    • Fast winning strategies in Maker-Breaker games.
    Journal of Combinatorial Theory Series B 99 (2009), 39-47.  
  • S. Ben-Shimon and M. Krivelevich,
    • Vertex percolation on expander graphs.
    European Journal of Combinatorics 30 (2009), 339-350.  
  • A. Coja-Oghlan, U. Feige, A. Frieze, M. Krivelevich and D. Vilenchik, On smoothed k-CNF formulas and the Walksat algorithm.
    Proceedings of the 20th Symposium on Discrete Algorithms (SODA'09), 451-460.  
  • I. Ben-Eliezer and M. Krivelevich, Perfectly balanced partitions of smoothed graphs.
    Electronic Journal of Combinatorics, Vol. 16 (1) (2009), note N14.  
  • S. Ben-Shimon and M. Krivelevich,
    • Random regular graphs of non-constant degree: concentration of the chromatic number.
    Discrete Mathematics 309 (2009), 4149-4161.  
  • M. Krivelevich and B. Sudakov,
    • Minors in expanding graphs.
    Geometric and Functional Analysis 19 (2009), 294-331.  
  • M. Krivelevich and B. Patkos, Equitable coloring of random graphs.
    Random Structures and Algorithms 35 (2009), 83-99.  
  • O. Goldreich, M. Krivelevich, I. Newman and E.Rozenberg, Hierarchy theorems for property testing.
    Proceedings of the 12th International Workshop on Randomization and Computation (RANDOM'2009), Lecture Notes in Computer Science 5867 (2009), 504-519. Journal version: Computational Complexity 21 (2012), 129-192.  
  • M. Krivelevich, B. Sudakov and D. Vilenchik, On the random satisfiable process.
    Combinatorics, Probability and Computing 18 (2009), 775-801.  
  • D. Hefetz, M. Krivelevich and T. Szabo,
    • Hamilton cycles in highly connected and expanding graphs.
    Combinatorica 29 (2009), 547-568.  
  • D. Hefetz, M. Krivelevich, M. Stojakovic and T. Szabo, Fast winning strategies in Avoider-Enforcer games.
    Graphs and Combinatorics 25 (2009), 533-544.  

    TOP
    2010

  • D. Hefetz, M. Krivelevich, M. Stojakovic and T. Szabo, Avoider - Enforcer: the rules of the game.
    Journal of Combinatorial Theory Series A 117 (2010), 152-163.  
  • M. Krivelevich, R. Spohel and A. Steger, Offline thresholds for Ramsey-type games on random graphs.
    Random Structures and Algorithms 36 (2010), 57--79.  
  • M. Krivelevich and R. Yuster, The rainbow connection of a graph is (at most) reciprocal to its minimum degree.
    Journal of Graph Theory 63 (2010), 185-191.  
  • M. Krivelevich, C. Lee and B. Sudakov, Resilient pancyclicity of random and pseudo-random graphs.
    SIAM Journal on Discrete Mathematics 24 (2010), 1-16.  
  • C. Cooper, A. Frieze and M. Krivelevich, Hamilton cycles in random graphs with a given degree sequence.
    SIAM Journal on Discrete Mathematics 24 (2010), 558-569.  
  • N. Alon, D. Hefetz and M. Krivelevich, Playing to retain the advantage.
    Combinatorics, Probability and Computing 19 (2010), 481-491.  
  • N. Alon, S. Ben-Shimon and M. Krivelevich, A note on regular Ramsey graphs.
    Journal of Graph Theory 64 (2010), 244-249.  
  • M. Krivelevich, E. Lubetzky and B. Sudakov, Hamiltonicity thresholds in Achlioptas processes.
    Random Structures and Algorithms 37 (2010), 1-24.  
  • M. Krivelevich, Embedding spanning trees in random graphs.
    SIAM Journal on Discrete Mathematics 24 (2010), 1495-1500.  
  • S. Haber and M. Krivelevich, The logic of random regular graphs.
    Journal of Combinatorics 1 (2010), 389-440.  

    TOP
    2011

  • M. Krivelevich, The critical bias for the Hamiltonicity game is (1+o(1))n/ln n.
    Journal of the American Mathematical Society 24 (2011), 125-131.  
  • D. Hefetz, M. Krivelevich, M. Stojakovic and T. Szabo, Global Maker-Breaker games on sparse graphs.
    European Journal of Combinatorics 32 (2011), 162-177.  
  • T. Bohman, A. Frieze, M. Krivelevich, P.-S. Loh and B. Sudakov, Ramsey games with giants.
    Random Structures and Algorithms 38 (2011), 1-32.  
  • S. Ben-Shimon, M. Krivelevich and B. Sudakov, Local resilience and Hamiltonicity Maker-Breaker games in random regular graphs.
    Combinatorics, Probability and Computing 20 (2011), 173-211.  
  • S. Ben-Shimon, A. Ferber, D. Hefetz and M. Krivelevich, Hitting time results for Maker-Breaker games.
    Proceedings of the 22nd Symposium on Discrete Algorithms (SODA'11), 900-912. Journal version. Random Structures and Algorithms 41 (2012), 23-46.  
  • A. Frieze, M. Krivelevich and P.-S. Loh, Packing tight Hamilton cycles in 3-uniform hypergraphs.
    Proceedings of the 22nd Symposium on Discrete Algorithms (SODA'11), 913-932. Journal version: Random Structures and Algorithms 40 (2012), 269-300.  
  • N. Alon, S. Haber and M. Krivelevich, The number of F-matchings in almost every tree is a zero residue.
    Electronic Journal of Combinatorics, Volume 18 (1) (2011), publication P30.  
  • M. Krivelevich, B. Sudakov and N. Wormald, Regular induced subgraphs of a random graph.
    Random Structures and Algorithms 28 (2011), 235-250.  
  • J. Balogh, B. Bollobas, M. Krivelevich, T. Muller and M. Walters, Hamilton cycles in random geometric graphs.
    Annals of Applied Probability 21 (2011), 1053-1072.  
  • S. Ben-Shimon, M. Krivelevich and B. Sudakov, On the resilience of Hamiltonicity and optimal packing of Hamilton cycles in random graphs.
    SIAM Journal on Discrete Mathematics 25 (2011), 1176-1193.  

    TOP
    2012

  • D. Johannsen, M. Krivelevich and W. Samotij, Expanders are universal for the class of all spanning trees.
    Proceedings of the 23nd Symposium on Discrete Algorithms (SODA'12), 1539-1551. Journal version: Combinatorics, Probability and Computing 22 (2013), 253-281.  
  • M. Krivelevich, On the number of Hamilton cycles in pseudo-random graphs.
    Electronic Journal of Combinatorics, Volume 19 (2012), publication P25.  
  • A. Ferber, D. Hefetz and M. Krivelevich, Fast embedding of spanning trees in biased Maker-Breaker games.
    European Journal of Combinatorics 33 (2012), 1086-1099.  
  • I. Ben-Eliezer, M. Krivelevich and B. Sudakov, The size Ramsey number of a directed path.
    Journal of Combinatorial Theory Series B 102 (2012), 743-755.  
  • I. Ben-Eliezer, M. Krivelevich and B. Sudakov, Biased orientation games.
    Discrete Mathematics 312 (2012), 1732-1742.  
  • A. Frieze, M. Krivelevich and P.-S. Loh, Variations on cops and robbers.
    Journal of Graph Theory 69 (2012), 383-402.  
  • M. Krivelevich and R. Spohel, Creating small subgraphs in Achlioptas processes with growing parameter.
    SIAM Journal on Discrete Mathematics 26 (2012), 670-686.  
  • A. Frieze and M. Krivelevich, Packing Hamilton cycles in random and pseudo-random hypergraphs.
    Random Structures and Algorithms 41 (2012), 1-22.  
  • I. Ben-Eliezer, M. Krivelevich and B. Sudakov, Long cycles in subgraphs of (pseudo)random directed graphs.
    Journal of Graph Theory 70 (2012), 284-296.  
  • M. Krivelevich and W. Samotij, Optimal packings of Hamilton cycles in sparse random graphs.
    SIAM Journal on Discrete Mathematics 26 (2012), 964-982.  
  • D. Clemens, A. Ferber, M. Krivelevich and A. Liebenau, Fast strategies in Maker-Breaker games played on random boards.
    Combinatorics, Probability and Computing 21 (2012), 897-915.  
  • D. Hefetz, M. Krivelevich and T. Szabo, Sharp threshold for the appearance of certain spanning trees in random graphs.
    Random Structures and Algorithms 41 (2012), 391-412.  

    TOP
    2013

  • R. Glebov and M. Krivelevich, On the number of Hamilton cycles in sparse random graphs.
    SIAM Journal on Discrete Mathematics 27 (2013), 27-42.  
  • A. Ferber, R. Glebov, M. Krivelevich, H. Liu, C. Palmer, T. Valla and M. Vizer, The biased odd cycle game.
    Electronic Journal of Combinatorics Vol. 20, Issue 2 (2013), publ. P9.  
  • M. Krivelevich, E. Lubetzky and B. Sudakov, Longest cycles in sparse random digraphs.
    Random Structures and Algorithms 43 (2013), 1-15.  
  • M. Krivelevich and B. Sudakov, The phase transition in random graphs - a simple proof.
    Random Structures and Algorithms 43 (2013), 131-138.  
  • A. Frieze and M. Krivelevich, On the non-planarity of a random subgraph.
    Combinatorics, Probability and Computing 22 (2013), 722-732.  

    TOP
    Preprints

  • D. Hefetz, M. Krivelevich, M. Stojakovic and T. Szabo, Continuous Box game.  
  • R. Glebov, M. Krivelevich and T. Szabo, On covering expander graphs by Hamilton cycles.  
  • M. Krivelevich, C. Lee and B. Sudakov, Robust Hamiltonicity of Dirac graphs.  
  • M. Krivelevich, C. Lee and B. Sudakov, Long paths and cycles in random subgraphs of graphs with large minimum degree.  
  • A. Ferber, M. Krivelevich and A. Naor, Avoider-Enforcer games played on edge disjoint hypergraphs.  
  • A. Ferber, R. Glebov, M. Krivelevich and A. Naor, Biased games on random graphs.  
  • A. Ferber, M. Krivelevich and B. Sudakov, Counting and packing Hamilton cycles in dense graphs and oriented graphs.  
  • M. Krivelevich and W. Samotij, Long paths and cycles in H-free graphs.  
  • M. Krivelevich, E. Lubetzky and B. Sudakov, Cores of random graphs are born Hamiltonian.  
  • A. Ferber, R. Hod, M. Krivelevich and B. Sudakov, A construction of almost Steiner systems.  
  • D. Bal, A. Frieze, M. Krivelevich and P.-S. Loh, Packing tree factors in random and pseudo-random graphs.  
  • A. Coja-Oghlan, U. Feige, M. Krivelevich and D. Reichman, Contagious sets in expanders.  
  • M. Krivelevich, D. Reichman and W. Samotij, Expansion in randomly perturbed connected graphs and its consequences.