Michael Krivelevich

From MaRDI portal
Person:178700

Available identifiers

zbMath Open krivelevich.michaelDBLP09/3445WikidataQ16196545 ScholiaQ16196545MaRDI QIDQ178700

List of research outcomes





PublicationDate of PublicationType
Climbing up a random subgraph of the hypercube2024-12-20Paper
The power of many colours2024-12-12Paper
Percolation on irregular high-dimensional product graphs2024-11-05Paper
Expansion in supercritical random subgraphs of expanders and its consequences2024-10-24Paper
Isoperimetric inequalities and supercritical percolation on high-dimensional graphs2024-09-19Paper
The largest hole in sparse random graphs2024-09-13Paper
Greedy maximal independent sets via local limits2024-05-17Paper
Hamilton completion and the path cover number of sparse random graphs2024-03-26Paper
On vertex Ramsey graphs with forbidden subgraphs2024-01-17Paper
https://portal.mardi4nfdi.de/entity/Q61472552024-01-15Paper
Colouring random subgraphs2023-12-13Paper
Climbing up a random subgraph of the hypercube2023-11-28Paper
Rigid partitions: from high connectivity to random graphs2023-11-24Paper
Supercritical site percolation on the hypercube: small components are small2023-11-23Paper
Component sizes in the supercritical percolation on the binary cube2023-11-13Paper
Cycle lengths in randomly perturbed graphs2023-11-07Paper
Site percolation on pseudo‐random graphs2023-10-17Paper
Cycle lengths in sparse random graphs2023-10-17Paper
The largest hole in sparse random graphs2023-10-17Paper
Color‐biased Hamilton cycles in random graphs2023-10-12Paper
The size‐Ramsey number of short subdivisions2023-10-12Paper
Complete minors and average degree: A short proof2023-10-12Paper
On subgraphs with degrees of prescribed residues in the random graph2023-10-12Paper
Oriented discrepancy of Hamilton cycles2023-10-10Paper
Divisible subdivisions2023-10-04Paper
The power of many colours2023-08-29Paper
Turán‐type problems for long cycles in random and pseudo‐random graphs2023-08-23Paper
Sparse pancyclic subgraphs of random graphs2023-08-03Paper
Largest subgraph from a hereditary property in a random graph2023-06-12Paper
Crowns in pseudo-random graphs and Hamilton cycles in their squares2023-05-15Paper
Short proofs for long induced paths2023-03-31Paper
Large complete minors in random subgraphs2023-03-30Paper
https://portal.mardi4nfdi.de/entity/Q58744192023-02-07Paper
Minors, connectivity, and diameter in randomly perturbed sparse graphs2022-12-14Paper
Expansion in supercritical random subgraphs of the hypercube and its consequences2022-12-08Paper
Obituary: Robin Thomas (1962--2020)2022-11-23Paper
On the performance of the depth first search algorithm in supercritical random graphs2022-10-06Paper
Every graph contains a linearly sized induced subgraph with all degrees odd2022-08-04Paper
Spanning Trees at the Connectivity Threshold2022-07-28Paper
Fast construction on a restricted budget2022-07-14Paper
Rolling backwards can move you forward: On embedding problems in sparse expanders2022-06-16Paper
The choosability version of Brooks' theorem -- a short proof2022-05-15Paper
Expansion in Supercritical Random Subgraphs of Expanders and its Consequences2022-05-10Paper
Complete Minors in Graphs Without Sparse Cuts2022-04-05Paper
Hitting Time of Edge Disjoint Hamilton Cycles in Random Subgraph Processes on Dense Base Graphs2022-04-01Paper
Discrepancies of spanning trees and Hamilton cycles2022-03-03Paper
Cycle lengths in expanding graphs2021-06-29Paper
The genus of the Erd\H{o}s-R\'enyi random graph and the fragile genus property2021-06-15Paper
Edge-statistics on large graphs2021-06-15Paper
Expansion, long cycles, and complete minors in supercritical random subgraphs of the hypercube2021-06-08Paper
Expanders – how to find them, and what to find in them2021-02-06Paper
Very fast construction of bounded-degree spanning graphs via the semi-random graph process2021-02-02Paper
Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process2021-01-05Paper
The Kőnig graph process2021-01-05Paper
Component Games on Random Graphs2020-12-16Paper
Asymptotics in percolation on high‐girth expanders2020-10-26Paper
Ron Graham (1935--2020)2020-09-24Paper
Finding a Hamilton cycle fast on average using rotations and extensions2020-09-16Paper
The genus of the Erdős‐Rényi random graph and the fragile genus property2020-06-19Paper
Random graph's Hamiltonicity is strongly tied to its minimum degree2020-01-27Paper
Semirandom Models as Benchmarks for Coloring Algorithms2019-09-16Paper
Goldberg's conjecture is true for random multigraphs2019-07-17Paper
Greedy maximal independent sets via local limits2019-07-16Paper
Long cycles in locally expanding graphs, with applications2019-05-23Paper
https://portal.mardi4nfdi.de/entity/Q57434972019-05-10Paper
https://portal.mardi4nfdi.de/entity/Q46338542019-05-06Paper
The random k‐matching‐free process2019-02-20Paper
Complete minors in graphs without sparse cuts2018-12-05Paper
Approximation algorithms and hardness results for cycle packing problems2018-11-05Paper
On MAXCUT in strictly supercritical random graphs, and coloring of random graphs and random tournaments2018-09-05Paper
Clique coloring of dense random graphs2018-08-16Paper
Waiter-Client Maximum Degree Game2018-07-29Paper
Packing Hamilton Cycles Online2018-07-24Paper
Elegantly Colored Paths and Cycles in Edge Colored Random Graphs2018-07-18Paper
On the trace of random walks on random graphs2018-05-03Paper
Finding and Using Expanders in Locally Sparse Graphs2018-03-05Paper
Compatible Hamilton cycles in Dirac graphs2018-02-12Paper
Proper colouring painter-builder game2018-01-19Paper
Contagious sets in random graphs2018-01-04Paper
Positional Games2017-11-06Paper
Manipulative Waiters with Probabilistic Intuition2017-10-10Paper
Cycles and Matchings in Randomly Perturbed Digraphs and Hypergraphs2017-10-10Paper
Contagious Sets in Expanders2017-10-05Paper
Decomposing Random Graphs into Few Cycles and Edges2017-10-04Paper
https://portal.mardi4nfdi.de/entity/Q53650892017-09-29Paper
https://portal.mardi4nfdi.de/entity/Q53650902017-09-29Paper
Long paths and Hamiltonicity in random graphs2017-07-24Paper
Efficient Winning Strategies in Random‐Turn Maker–Breaker Games2017-07-05Paper
Waiter-client and client-waiter Hamiltonicity games on random graphs2017-06-19Paper
Smoothed Analysis on Connected Graphs2017-03-22Paper
Small subgraphs in the trace of a random walk2017-02-17Paper
Bounded-Degree Spanning Trees in Randomly Perturbed Graphs2017-01-27Paper
Rainbow Hamilton cycles in random graphs and hypergraphs2017-01-25Paper
Client-waiter games on complete and random graphs2017-01-18Paper
Counting and packing Hamilton cycles in dense graphs and oriented graphs2016-11-25Paper
Some remarks on rainbow connectivity2016-11-17Paper
Compatible Hamilton cycles in random graphs2016-11-09Paper
Some remarks on rainbow connectivity2016-10-14Paper
Cycles and matchings in randomly perturbed digraphs and hypergraphs2016-10-14Paper
Coloring random graphs2016-06-09Paper
Waiter-Client and Client-Waiter planarity, colorability and minor games2016-04-07Paper
Counting and packing Hamilton \(\ell\)-cycles in dense hypergraphs2016-02-19Paper
The phase transition in site percolation on pseudo-random graphs2016-01-25Paper
Generating random graphs in biased Maker-Breaker games2016-01-07Paper
Large Subgraphs without Short Cycles2015-11-27Paper
Random-player maker-breaker games2015-11-02Paper
Bounds on Distance Distributions in Codes of Given Size2015-10-27Paper
On saturation games2015-09-30Paper
Smoothed Analysis on Connected Graphs2015-09-23Paper
Walker-Breaker Games2015-09-02Paper
Biased games on random boards2015-07-23Paper
Long paths and cycles in random subgraphs of graphs with large minimum degree2015-04-09Paper
A Construction of Almost Steiner Systems2014-12-22Paper
Approximation algorithms for cycle packing problems2014-10-13Paper
On the random 2-stage minimum spanning tree2014-10-13Paper
Packing tree factors in random and pseudo-random graphs2014-09-04Paper
Long paths and cycles in random subgraphs of \(\mathcal{H}\)-free graphs2014-09-04Paper
Cores of random graphs are born Hamiltonian2014-08-08Paper
Robust Hamiltonicity of Dirac graphs2014-06-11Paper
On covering expander graphs by hamilton cycles2014-04-15Paper
Positional games2014-03-05Paper
On the Non-Planarity of a Random Subgraph2014-02-24Paper
Avoider-Enforcer games played on edge disjoint hypergraphs2014-01-27Paper
Fast embedding of spanning trees in biased maker-breaker games2013-11-01Paper
Avoider-Enforcer: the rules of the game2013-10-10Paper
Playing to retain the advantage2013-10-10Paper
The phase transition in random graphs: a simple proof2013-10-09Paper
Longest cycles in sparse random digraphs2013-08-27Paper
On the Number of Hamilton Cycles in Sparse Random Graphs2013-06-27Paper
The biased odd cycle game2013-06-07Paper
Comparing the strength of query types in property testing: the case of \(k\)-colorability2013-04-11Paper
Expanders Are Universal for the Class of All Spanning Trees2013-03-14Paper
Optimal Packings of Hamilton Cycles in Sparse Random Graphs2013-01-04Paper
Sharp threshold for the appearance of certain spanning trees in random graphs2012-12-14Paper
Fast Strategies In Maker–Breaker Games Played on Random Boards2012-10-31Paper
Creating small subgraphs in Achlioptas processes with growing parameter2012-09-12Paper
Hitting time results for maker-breaker games2012-08-30Paper
Packing Hamilton cycles in random and pseudo-random hypergraphs2012-08-30Paper
Long cycles in subgraphs of (pseudo)random directed graphs2012-07-10Paper
Long paths and cycles in random subgraphs of graphs with large minimum degree2012-07-02Paper
Hierarchy theorems for property testing2012-06-26Paper
Fast embedding of spanning trees in biased maker-breaker games2012-06-18Paper
Variations on cops and robbers2012-06-13Paper
On the number of Hamilton cycles in pseudo-random graphs2012-06-12Paper
Biased orientation games2012-05-30Paper
Packing tight Hamilton cycles in 3-uniform hypergraphs2012-05-14Paper
The size Ramsey number of a directed path2012-05-11Paper
On the Resilience of Hamiltonicity and Optimal Packing of Hamilton Cycles in Random Graphs2012-03-15Paper
Hamilton cycles in random geometric graphs2011-07-19Paper
Embedding Spanning Trees in Random Graphs2011-07-18Paper
The logic of random regular graphs2011-06-27Paper
Regular induced subgraphs of a random Graph2011-05-11Paper
Hamilton Cycles in Random Graphs with a Fixed Degree Sequence2011-04-15Paper
Resilient Pancyclicity of Random and Pseudorandom Graphs2011-03-15Paper
Local Resilience and Hamiltonicity Maker–Breaker Games in Random Regular Graphs2011-03-07Paper
The number of \(F\)-matchings in almost every tree is a zero residue2011-02-17Paper
The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛2011-02-09Paper
Hamilton cycles in highly connected and expanding graphs2011-02-08Paper
Ramsey games with giants2011-01-17Paper
Global maker-breaker games on sparse graphs2011-01-07Paper
Hamiltonicity thresholds in Achlioptas processes2010-11-24Paper
Offline thresholds for Ramsey-type games on random graphs2010-11-10Paper
A note on regular Ramsey graphs2010-11-10Paper
Equitable coloring of random graphs2010-11-09Paper
Playing to Retain the Advantage2010-10-14Paper
Hierarchy Theorems for Property Testing2010-10-12Paper
Comparing the Strength of Query Types in Property Testing: The Case of Testing k-Colorability2010-10-12Paper
Testing triangle-freeness in general graphs2010-08-16Paper
Solving random satisfiable 3CNF formulas in expected polynomial time2010-08-16Paper
https://portal.mardi4nfdi.de/entity/Q35794352010-08-06Paper
https://portal.mardi4nfdi.de/entity/Q35767562010-08-02Paper
Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques2010-05-26Paper
Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques2010-05-26Paper
Why almost all \(k\)-colorable graphs are easy to color2010-05-05Paper
Avoider-enforcer: the rules of the game2010-04-27Paper
On the Random Satisfiable Process2010-04-22Paper
Spanning Directed Trees with Many Leaves2010-03-17Paper
The rainbow connection of a graph is (at most) reciprocal to its minimum degree2010-03-15Paper
Fast winning strategies in avoider-enforcer games2010-01-18Paper
Random regular graphs of non-constant degree: concentration of the chromatic number2009-12-09Paper
Large Nearly Regular Induced Subgraphs2009-11-27Paper
Hierarchy Theorems for Property Testing2009-10-28Paper
Perfectly balanced partitions of smoothed graphs2009-07-08Paper
Minors in expanding graphs2009-07-06Paper
Hamiltonicity of the random geometric graph2009-05-30Paper
Testing Triangle-Freeness in General Graphs2009-05-27Paper
On rainbow trees and cycles2009-04-07Paper
Biased positional games and small hypergraphs with large covers2009-04-07Paper
Planarity, Colorability, and Minor Games2009-03-16Paper
Avoiding small subgraphs in Achlioptas processes2009-03-04Paper
A sharp threshold for the Hamilton cycle Maker–Breaker game2009-03-04Paper
Vertex percolation on expander graphs2009-03-04Paper
Winning Fast in Sparse Graph Construction Games2009-03-04Paper
Corrigendum: On fractional K-factors of random graphs2009-03-04Paper
Fast winning strategies in maker-breaker games2009-01-21Paper
Testing Reed–Muller Codes2008-12-21Paper
Bounds on Distance Distributions in Codes of Known Size2008-12-21Paper
Covering codes with improved density2008-12-21Paper
Small Sample Spaces Cannot Fool Low Degree Polynomials2008-11-27Paper
Embedding nearly-spanning bounded degree trees2008-10-22Paper
On two Hamilton cycle problems in random graphs2008-10-16Paper
Fast winning strategies in positional games2008-06-05Paper
Better Algorithms and Bounds for Directed Maximum Leaf Problems2008-04-24Paper
On the Chromatic Number of Random Graphs with a Fixed Degree Sequence2008-02-22Paper
The isoperimetric constant of the random graph process2008-01-18Paper
Parameterized Algorithms for Directed Maximum Leaf Problems2007-11-28Paper
Why Almost All k-Colorable Graphs Are Easy2007-09-03Paper
On fractional K‐factors of random graphs2007-07-18Paper
Addendum to ``Scalable secure storage when half the system is faulty [inform. comput. 174 (2)(2002) 203-213]2007-07-16Paper
Avoider-Enforcer games2007-07-04Paper
Bart--Moe games, JumbleG and discrepancy2007-04-10Paper
Coloring complete bipartite graphs from random lists2007-02-07Paper
On smoothed analysis in dense graphs and formulas2007-02-07Paper
Almost universal graphs2006-09-06Paper
https://portal.mardi4nfdi.de/entity/Q54778172006-06-29Paper
On the asymptotic value of the choice number of complete multi‐partite graphs2006-06-06Paper
Recognizing More Unsatisfiable Random k-SAT Instances Efficiently2006-06-01Paper
The Strong Chromatic Index of Random Graphs2006-06-01Paper
On the random 2-stage minimum spanning tree2006-03-24Paper
MaxCut in ${\bm H)$-Free Graphs2005-11-14Paper
The Game of JumbleG2005-11-14Paper
Discrepancy games2005-11-01Paper
Triangle factors in sparse pseudo-random graphs2005-07-05Paper
Upper bounds on the rate of LDPC codes2005-05-11Paper
On packing Hamilton cycles in \(\varepsilon\)-regular graphs2005-05-04Paper
https://portal.mardi4nfdi.de/entity/Q46589502005-03-21Paper
Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions2005-03-08Paper
Tight Bounds for Testing Bipartiteness in General Graphs2005-02-21Paper
Colouring powers of cycles from random lists2004-10-13Paper
Algorithms with large domination ratio2004-10-04Paper
Approximate coloring of uniform hypergraphs2004-10-01Paper
Adding random edges to dense graphs2004-03-29Paper
The emergence of a giant component in random subgraphs of pseudo-random graphs2004-02-03Paper
Generalized hashing and parent-identifying codes.2004-01-06Paper
https://portal.mardi4nfdi.de/entity/Q44289082003-09-22Paper
Induced subgraphs of prescribed size2003-08-20Paper
Maximum cuts and judicious partitions in graphs without short cycles2003-08-17Paper
On the concentration of eigenvalues of random symmetric matrices2003-06-30Paper
Deciding \(k\)-colorability in expected polynomial time2003-06-24Paper
The Largest Eigenvalue of Sparse Random Graphs2003-06-13Paper
A Sharp Threshold for Network Reliability2003-04-11Paper
Sparse pseudo‐random graphs are Hamiltonian2003-03-19Paper
On the probability of independent sets in random graphs2003-03-19Paper
Scalable secure storage when half the system is faulty2003-01-14Paper
Choosability in random hypergraphs2002-12-10Paper
Hamilton cycles in random subgraphs of pseudo-random graphs2002-12-02Paper
Fractional planks2002-11-18Paper
Random regular graphs of high degree2002-11-06Paper
Two‐coloring random hypergraphs2002-08-08Paper
Approximating coloring and maximum independent sets in 3-uniform hypergraphs2002-08-01Paper
Sparse graphs usually have exponentially many optimal colorings2002-07-01Paper
Approximating the independence number and the chromatic number in expected polynomial time2002-05-28Paper
Testing \(k\)-colorability2002-04-23Paper
Approximating coloring and maximum independent sets in 3-uniform hypergraphs2002-03-24Paper
https://portal.mardi4nfdi.de/entity/Q27627902002-01-09Paper
https://portal.mardi4nfdi.de/entity/Q27541782001-12-09Paper
https://portal.mardi4nfdi.de/entity/Q27541302001-11-11Paper
Efficient testing of large graphs2001-06-13Paper
Long cycles in critical graphs2001-05-10Paper
Regular languages are testable with a constant number of queries2001-03-19Paper
Sharp thresholds for certain Ramsey properties of random graphs2001-01-23Paper
On the concentration of eigenvalues of random symmetric matrices2000-09-21Paper
Coloring graphs with sparse neighborhoods2000-06-25Paper
List coloring of random and pseudo-random graphs2000-05-14Paper
The Choice Number of Dense Random Graphs2000-04-26Paper
https://portal.mardi4nfdi.de/entity/Q47053441999-12-19Paper
https://portal.mardi4nfdi.de/entity/Q47053181999-12-19Paper
https://portal.mardi4nfdi.de/entity/Q42520441999-10-06Paper
The choice number of random bipartite graphs1999-06-28Paper
https://portal.mardi4nfdi.de/entity/Q42502281999-06-17Paper
The concentration of the chromatic number of random graphs1999-03-14Paper
On the minimal number of edges in color-critical graphs1998-11-24Paper
A lower bound for irredundant Ramsey numbers1998-10-01Paper
Constructive bounds for a Ramsey-type problem1998-06-22Paper
Triangle Factors in Random Graphs1998-05-04Paper
Subgraphs with a large cochromatic number1998-03-02Paper
An improved bound on the minimal number of edges in color-critical graphs1998-02-18Paper
Approximate Set Covering in Uniform Hypergraphs1997-11-25Paper
https://portal.mardi4nfdi.de/entity/Q47163321997-10-15Paper
Almost perfect matchings in random uniform hypergraphs1997-08-10Paper
On a theorem of Lovász on covers in \(r\)-partite hypergraphs1997-03-11Paper
Onk-saturated graphs with restrictions on the degrees1997-02-26Paper
Bounding Ramsey numbers through large deviation inequalities1995-09-20Paper
On a conjecture of Tuza about packing and covering of triangles1995-08-27Paper
On the edge distribution in triangle-free graphs1995-07-02Paper
Ks-Free Graphs Without Large Kr-Free Subgraphs1995-04-09Paper
Percolation on High-dimensional Product GraphsN/APaper
Percolation on Irregular High-dimensional Product GraphsN/APaper
Isoperimetric Inequalities and Supercritical Percolation on High-dimensional GraphsN/APaper
Maximum chordal subgraphs of random graphsN/APaper
Percolation through IsoperimetryN/APaper
Colouring graphs from random listsN/APaper
Hitting time of connectedness in the random hypercube processN/APaper
Reconstructing random graphs from distance queriesN/APaper

Research outcomes over time

This page was built for person: Michael Krivelevich