2025
Percolation on High-Dimensional Product Graphs.
Random Struct. Algorithms, January, 2025
2024
Isoperimetric Inequalities and Supercritical Percolation on High-Dimensional Graphs.
Comb., August, 2024
Greedy maximal independent sets via local limits.
Random Struct. Algorithms, July, 2024
On vertex Ramsey graphs with forbidden subgraphs.
Discret. Math., March, 2024
Hamilton completion and the path cover number of sparse random graphs.
Eur. J. Comb., 2024
Maximum chordal subgraphs of random graphs.
Comb. Probab. Comput., 2024
Percolation on irregular high-dimensional product graphs.
Comb. Probab. Comput., 2024
2023
Cycle lengths in randomly perturbed graphs.
Random Struct. Algorithms, December, 2023
Site percolation on pseudo-random graphs.
Random Struct. Algorithms, September, 2023
Largest subgraph from a hereditary property in a random graph.
Discret. Math., September, 2023
On subgraphs with degrees of prescribed residues in the random graph.
Random Struct. Algorithms, August, 2023
Oriented discrepancy of Hamilton cycles.
J. Graph Theory, August, 2023
Complete minors and average degree: A short proof.
J. Graph Theory, July, 2023
Supercritical site percolation on the hypercube: small components are small.
Comb. Probab. Comput., May, 2023
Robin Thomas (1962-2020).
J. Comb. Theory B, 2023
2022
Component Games on Random Graphs.
Comb., December, 2022
Spanning Trees at the Connectivity Threshold.
SIAM J. Discret. Math., 2022
Hitting Time of Edge Disjoint Hamilton Cycles in Random Subgraph Processes on Dense Base Graphs.
SIAM J. Discret. Math., 2022
Color-biased Hamilton cycles in random graphs.
Random Struct. Algorithms, 2022
The largest hole in sparse random graphs.
Random Struct. Algorithms, 2022
Cycle lengths in sparse random graphs.
Random Struct. Algorithms, 2022
Discrepancies of spanning trees and Hamilton cycles.
J. Comb. Theory B, 2022
Short proofs for long induced paths.
Comb. Probab. Comput., 2022
On the Performance of the Depth First Search Algorithm in Supercritical Random Graphs.
Electron. J. Comb., 2022
2021
The size-Ramsey number of short subdivisions.
Random Struct. Algorithms, 2021
Large complete minors in random subgraphs.
Comb. Probab. Comput., 2021
Cycle Lengths in Expanding Graphs.
Comb., 2021
Rolling backwards can move you forward: on embedding problems in sparse expanders.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021
2020
Asymptotics in percolation on high-girth expanders.
Random Struct. Algorithms, July, 2020
Random Struct. Algorithms, 2020
The genus of the Erdős-Rényi random graph and the fragile genus property.
Random Struct. Algorithms, 2020
Very fast construction of bounded-degree spanning graphs via the semi-random graph process.
Random Struct. Algorithms, 2020
Finding a Hamilton cycle fast on average using rotations and extensions.
Random Struct. Algorithms, 2020
Edge-statistics on large graphs.
Comb. Probab. Comput., 2020
Random Graph's Hamiltonicity is Strongly Tied to its Minimum Degree.
Electron. J. Comb., 2020
2019
Goldberg's conjecture is true for random multigraphs.
J. Comb. Theory B, 2019
Long Cycles in Locally Expanding Graphs, with Applications.
Comb., 2019
Optimal shattering of complex networks.
Appl. Netw. Sci., 2019
Expanders - how to find them, and what to find in them.
Proceedings of the Surveys in Combinatorics, 2019: Invited lectures from the 27th British Combinatorial Conference, Birmingham, UK, July 29, 2019
2018
Finding and Using Expanders in Locally Sparse Graphs.
SIAM J. Discret. Math., 2018
Elegantly Colored Paths and Cycles in Edge Colored Random Graphs.
SIAM J. Discret. Math., 2018
The random k-matching-free process.
Random Struct. Algorithms, 2018
On MAXCUT in strictly supercritical random graphs, and coloring of random graphs and random tournaments.
Random Struct. Algorithms, 2018
Clique coloring of dense random graphs.
J. Graph Theory, 2018
Proper colouring Painter-Builder game.
Discret. Math., 2018
Packing Hamilton Cycles Online.
Comb. Probab. Comput., 2018
2017
Bounded-Degree Spanning Trees in Randomly Perturbed Graphs.
SIAM J. Discret. Math., 2017
Finding paths in sparse random graphs requires many queries.
Random Struct. Algorithms, 2017
Efficient Winning Strategies in Random-Turn Maker-Breaker Games.
J. Graph Theory, 2017
Counting and packing Hamilton cycles in dense graphs and oriented graphs.
J. Comb. Theory B, 2017
Waiter-Client and Client-Waiter Hamiltonicity games on random graphs.
Eur. J. Comb., 2017
Small Subgraphs in the Trace of a Random Walk.
Electron. J. Comb., 2017
Compatible Hamilton cycles in Dirac graphs.
Comb., 2017
2016
Compatible Hamilton cycles in random graphs.
Random Struct. Algorithms, 2016
Finding Hamilton cycles in random graphs with few queries.
Random Struct. Algorithms, 2016
Some Remarks on Rainbow Connectivity.
J. Graph Theory, 2016
Waiter-Client and Client-Waiter planarity, colorability and minor games.
Discret. Math., 2016
Manipulative Waiters with Probabilistic Intuition.
Comb. Probab. Comput., 2016
The Phase Transition in Site Percolation on Pseudo-Random Graphs.
Electron. J. Comb., 2016
Client-Waiter Games on Complete and Random Graphs.
Electron. J. Comb., 2016
Random Graphs, Geometry and Asymptotic Structure.
London Mathematical Society student texts 84, Cambridge University Press, ISBN: 978-1-316-50191-7, 2016
2015
Smoothed Analysis on Connected Graphs.
SIAM J. Discret. Math., 2015
Large Subgraphs without Short Cycles.
SIAM J. Discret. Math., 2015
SIAM J. Discret. Math., 2015
Long paths and cycles in random subgraphs of graphs with large minimum degree.
Random Struct. Algorithms, 2015
Generating random graphs in biased Maker-Breaker games.
Random Struct. Algorithms, 2015
Biased games on random boards.
Random Struct. Algorithms, 2015
Cycles and matchings in randomly perturbed digraphs and hypergraphs.
Electron. Notes Discret. Math., 2015
Decomposing Random Graphs into Few Cycles and Edges.
Comb. Probab. Comput., 2015
Random-Player Maker-Breaker games.
Electron. J. Comb., 2015
Contagious Sets in Expanders.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015
2014
On covering expander graphs by hamilton cycles.
Random Struct. Algorithms, 2014
Long Paths and Cycles in Random Subgraphs of $\mathcal{H}$-free Graphs.
Electron. J. Comb., 2014
Packing Tree Factors in Random and Pseudo-random Graphs.
Electron. J. Comb., 2014
2013
On the Number of Hamilton Cycles in Sparse Random Graphs.
SIAM J. Discret. Math., 2013
The phase transition in random graphs: A simple proof.
Random Struct. Algorithms, 2013
Longest cycles in sparse random digraphs.
Random Struct. Algorithms, 2013
Avoider-Enforcer games played on edge disjoint hypergraphs.
Discret. Math., 2013
Expanders Are Universal for the Class of All Spanning Trees.
Comb. Probab. Comput., 2013
On the Non-Planarity of a Random Subgraph.
Comb. Probab. Comput., 2013
The Biased Odd Cycle Game.
Electron. J. Comb., 2013
Comparing the strength of query types in property testing: The case of k-colorability.
Comput. Complex., 2013
2012
Optimal Packings of Hamilton Cycles in Sparse Random Graphs.
SIAM J. Discret. Math., 2012
Creating Small Subgraphs in Achlioptas Processes With Growing Parameter.
SIAM J. Discret. Math., 2012
Sharp threshold for the appearance of certain spanning trees in random graphs.
Random Struct. Algorithms, 2012
Packing tight Hamilton cycles in 3-uniform hypergraphs.
Random Struct. Algorithms, 2012
Packing hamilton cycles in random and pseudo-random hypergraphs.
Random Struct. Algorithms, 2012
Hitting time results for Maker-Breaker games.
Random Struct. Algorithms, 2012
Variations on cops and robbers.
J. Graph Theory, 2012
Long cycles in subgraphs of (pseudo)random directed graphs.
J. Graph Theory, 2012
The size Ramsey number of a directed path.
J. Comb. Theory B, 2012
Biased orientation games.
Discret. Math., 2012
Fast Strategies In Maker-Breaker Games Played on Random Boards.
Comb. Probab. Comput., 2012
On the Number of Hamilton Cycles in Pseudo-Random Graphs.
Electron. J. Comb., 2012
Hierarchy Theorems for Property Testing.
Comput. Complex., 2012
2011
On the Resilience of Hamiltonicity and Optimal Packing of Hamilton Cycles in Random Graphs.
SIAM J. Discret. Math., 2011
Regular induced subgraphs of a random Graph.
Random Struct. Algorithms, 2011
Ramsey games with giants.
Random Struct. Algorithms, 2011
Fast embedding of spanning trees in biased Maker-Breaker games.
Electron. Notes Discret. Math., 2011
Global Maker-Breaker games on sparse graphs.
Eur. J. Comb., 2011
Local Resilience and Hamiltonicity Maker-Breaker Games in Random Regular Graphs.
Comb. Probab. Comput., 2011
The Number of <i>f</i>-Matchings in Almost Every Tree is a Zero Residue.
Electron. J. Comb., 2011
2010
Resilient Pancyclicity of Random and Pseudorandom Graphs.
SIAM J. Discret. Math., 2010
Embedding Spanning Trees in Random Graphs.
SIAM J. Discret. Math., 2010
Hamilton Cycles in Random Graphs with a Fixed Degree Sequence.
SIAM J. Discret. Math., 2010
Offline thresholds for Ramsey-type games on random graphs.
Random Struct. Algorithms, 2010
Hamiltonicity thresholds in Achlioptas processes.
Random Struct. Algorithms, 2010
Why Almost All <i>k</i>-Colorable Graphs Are Easy to Color.
Theory Comput. Syst., 2010
The rainbow connection of a graph is (at most) reciprocal to its minimum degree.
J. Graph Theory, 2010
A note on regular Ramsey graphs.
J. Graph Theory, 2010
Avoider-Enforcer: The rules of the game.
J. Comb. Theory A, 2010
Hierarchy Theorems for Property Testing.
Proceedings of the Property Testing - Current Research and Surveys, 2010
Comparing the Strength of Query Types in Property Testing: The Case of Testing <i>k</i>-Colorability.
Proceedings of the Property Testing - Current Research and Surveys, 2010
2009
Spanning Directed Trees with Many Leaves.
SIAM J. Discret. Math., 2009
Equitable coloring of random graphs.
Random Struct. Algorithms, 2009
Avoiding small subgraphs in Achlioptas processes.
Random Struct. Algorithms, 2009
A sharp threshold for the Hamilton cycle Maker-Breaker game.
Random Struct. Algorithms, 2009
Fast winning strategies in Maker-Breaker games.
J. Comb. Theory B, 2009
Fast Winning Strategies in Avoider-Enforcer Games.
Graphs Comb., 2009
Playing to retain the advantage.
Electron. Notes Discret. Math., 2009
Vertex percolation on expander graphs.
Eur. J. Comb., 2009
Random regular graphs of non-constant degree: Concentration of the chromatic number.
Discret. Math., 2009
On the Random Satisfiable Process.
Comb. Probab. Comput., 2009
Perfectly Balanced Partitions of Smoothed Graphs.
Electron. J. Comb., 2009
Hamilton cycles in highly connected and expanding graphs.
Comb., 2009
On smoothed <i>k</i>-CNF formulas and the Walksat algorithm.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009
2008
Planarity, Colorability, and Minor Games.
SIAM J. Discret. Math., 2008
Large Nearly Regular Induced Subgraphs.
SIAM J. Discret. Math., 2008
Testing Triangle-Freeness in General Graphs.
SIAM J. Discret. Math., 2008
Corrigendum: On fractional K-factors of random graphs.
Random Struct. Algorithms, 2008
The isoperimetric constant of the random graph process.
Random Struct. Algorithms, 2008
Winning Fast in Sparse Graph Construction Games.
Comb. Probab. Comput., 2008
Biased Positional Games and Small Hypergraphs with Large Covers.
Electron. J. Comb., 2008
On Rainbow Trees and Cycles.
Electron. J. Comb., 2008
Comparing the strength of query types in property testing: the case of testing <i>k</i>-colorability.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008
Small Sample Spaces Cannot Fool Low Degree Polynomials.
Proceedings of the Approximation, 2008
2007
Approximation algorithms and hardness results for cycle packing problems.
ACM Trans. Algorithms, 2007
On fractional <i>K</i>-factors of random graphs.
Random Struct. Algorithms, 2007
Addendum to "Scalable secure storage when half the system is faulty" [Inform. Comput 174 (2)(2002) 203-213].
Inf. Comput., 2007
Fast winning strategies in positional games.
Electron. Notes Discret. Math., 2007
Bart-Moe games, JumbleG and discrepancy.
Eur. J. Comb., 2007
On the Chromatic Number of Random Graphs with a Fixed Degree Sequence.
Comb. Probab. Comput., 2007
Embedding nearly-spanning bounded degree trees.
Comb., 2007
Why Almost All <i>k</i> -Colorable Graphs Are Easy.
Proceedings of the STACS 2007, 2007
Parameterized Algorithms for Directed Maximum Leaf Problems.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007
Better Algorithms and Bounds for Directed Maximum Leaf Problems.
Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007
2006
On smoothed analysis in dense graphs and formulas.
Random Struct. Algorithms, 2006
Coloring complete bipartite graphs from random lists.
Random Struct. Algorithms, 2006
Random Struct. Algorithms, 2006
On the random 2-stage minimum spanning tree.
Random Struct. Algorithms, 2006
On the asymptotic value of the choice number of complete multi-partite graphs.
J. Graph Theory, 2006
Solving random satisfiable 3CNF formulas in expected polynomial time.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006
Semirandom Models as Benchmarks for Coloring Algorithms.
Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics, 2006
2005
Bounds on distance distributions in codes of known size.
IEEE Trans. Inf. Theory, 2005
Testing Reed-Muller codes.
IEEE Trans. Inf. Theory, 2005
The Strong Chromatic Index of Random Graphs.
SIAM J. Discret. Math., 2005
Recognizing More Unsatisfiable Random k-SAT Instances Efficiently.
SIAM J. Comput., 2005
On packing Hamilton cycles in ?-regular graphs.
J. Comb. Theory B, 2005
Approximation algorithms for cycle packing problems.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005
2004
Tight Bounds for Testing Bipartiteness in General Graphs.
SIAM J. Comput., 2004
The emergence of a giant component in random subgraphs of pseudo-random graphs.
Random Struct. Algorithms, 2004
Adding random edges to dense graphs.
Random Struct. Algorithms, 2004
Algorithms with large domination ratio.
J. Algorithms, 2004
Colouring powers of cycles from random lists.
Eur. J. Comb., 2004
Triangle Factors In Sparse Pseudo-Random Graphs.
Comb., 2004
2003
Covering codes with improved density.
IEEE Trans. Inf. Theory, 2003
On the probability of independent sets in random graphs.
Random Struct. Algorithms, 2003
Sparse pseudo-random graphs are Hamiltonian.
J. Graph Theory, 2003
Induced subgraphs of prescribed size.
J. Graph Theory, 2003
Generalized hashing and parent-identifying codes.
J. Comb. Theory A, 2003
Maximum cuts and judicious partitions in graphs without short cycles.
J. Comb. Theory B, 2003
Approximate coloring of uniform hypergraphs.
J. Algorithms, 2003
The Largest Eigenvalue Of Sparse Random Graphs.
Comb. Probab. Comput., 2003
Tura'n Numbers of Bipartite Graphs and Related Ramsey-Type Questions.
Comb. Probab. Comput., 2003
Testing Low-Degree Polynomials over GF(2(.
Proceedings of the Approximation, 2003
2002
Upper bounds on the rate of LDPC Codes.
IEEE Trans. Inf. Theory, 2002
SIAM J. Discret. Math., 2002
Two-coloring random hypergraphs.
Random Struct. Algorithms, 2002
Approximating the Independence Number and the Chromatic Number in Expected Polynomial Time.
J. Comb. Optim., 2002
Deciding k-colorability in expected polynomial time.
Inf. Process. Lett., 2002
Scalable Secure Storage When Half the System Is Faulty.
Inf. Comput., 2002
Hamilton cycles in random subgraphs of pseudo-random graphs.
Discret. Math., 2002
Discret. Comput. Geom., 2002
A Sharp Threshold For Network Reliability.
Comb. Probab. Comput., 2002
Sparse Graphs Usually Have Exponentially Many Optimal Colorings.
Electron. J. Comb., 2002
2001
Random regular graphs of high degree.
Random Struct. Algorithms, 2001
Choosability in Random Hypergraphs.
J. Comb. Theory B, 2001
Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs.
J. Algorithms, 2001
Efficient Recognition of Random Unsatisfiable k-SAT Instances by Spectral Methods.
Proceedings of the STACS 2001, 2001
2000
Regular Languages are Testable with a Constant Number of Queries.
SIAM J. Comput., 2000
Sharp thresholds for certain Ramsey properties of random graphs.
Random Struct. Algorithms, 2000
Long cycles in critical graphs.
J. Graph Theory, 2000
The Choice Number Of Dense Random Graphs.
Comb. Probab. Comput., 2000
Efficient Testing of Large Graphs.
Comb., 2000
Approximating the Independence Number and the Chromatic Number in Expected Polynominal Time.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000
1999
Coloring Graphs with Sparse Neighborhoods.
J. Comb. Theory B, 1999
List Coloring of Random and Pseudo-Random Graphs.
Comb., 1999
1998
The chromatic numbers of random hypergraphs.
Random Struct. Algorithms, 1998
Finding a large hidden clique in a random graph.
Random Struct. Algorithms, 1998
Inf. Process. Lett., 1998
A lower bound for irredundant Ramsey numbers.
Discret. Math., 1998
An Improved Bound on the Minimal Number of Edges in Color-Critical Graphs.
Electron. J. Comb., 1998
Approximate Coloring of Uniform Hypergraphs (Extended Abstract).
Proceedings of the Algorithms, 1998
1997
Approximate Set Covering in Uniform Hypergraphs.
J. Algorithms, 1997
Constructive Bounds for a Ramsey-Type Problem.
Graphs Comb., 1997
Almost perfect matchings in random uniform hypergraphs.
Discret. Math., 1997
Triangle Factors in Random Graphs.
Comb. Probab. Comput., 1997
On the Minimal Number of Edges in Color-Critical Graphs.
Comb., 1997
The Concentration of the Chromatic Number of Random Graphs.
Comb., 1997
1996
Perfect fractional matchings in random hypergraphs.
Random Struct. Algorithms, 1996
On <i>k</i>-saturated graphs with restrictions on the degrees.
J. Graph Theory, 1996
On a Theorem of Lovász on Covers in tau-Partite Hypergraphs.
Comb., 1996
1995
Bounding Ramsey Numbers through Large Deviation Inequalities.
Random Struct. Algorithms, 1995
On the Edge Distribution in Triangle-free Graphs.
J. Comb. Theory B, 1995
On a conjecture of Tuza about packing and covering of triangles.
Discret. Math., 1995
1994
K<sub>s</sub>-Free Graphs Without Large K<sub>r</sub>-Free Subgraphs.
Comb. Probab. Comput., 1994
