Michael Anastos

My research interests include Probabilistic and Extremal Combinatorics, Random Graphs, and  Random Discrete Structures and Algorithms.

Selected research papers

(a full list of papers is available here) 

Nearly spanning cycle in the percolated hypercube (with Sahar Diskin, Joshua Erde, Mihyun Kang, Michael Krivelevich and Lyuben Lichev), preprint, arxiv version. 

Let Q(d,p) be the random subgraph of the d-dimensional hypercube formed by retaining each edge independently with probability p. We show that, if dp tends to infinity then Q(d,p) contains a cycle that covers almost all of its vertices with high probability. This confirms a long-standing folklore conjecture, stated in particular by Condon, Espuny Díaz, Girão, Kühn, and Osthus [Hamiltonicity of random subgraphs of the hypercube, Mem. Amer. Math. Soc. 305 (2024), No. 1534] 

 The law of the circumference of sparse binomial random graphs (with Joshua Erde, Mihyun Kang, and Vincent Pfenninger), preprint, arxiv version.

There has been much interest in the distribution of the circumference, the length of the longest cycle, of a random graph G(n,p) in the sparse regime, when p=c/n, c constant. Alan Frieze and I, established a scaling limit for the circumference in this regime, along the way establishing an alternative 'structural' approximation for this parameter. In this paper, we give a central limit theorem for the circumference in this regime using a novel argument based on the Efron-Stein inequality, which relies on a combinatorial analysis of the effect of resampling edges on this approximation.

Smoothed analysis for graph isomorphism ( with Matthew Kwan, and Benjamin Moore), accepted at the 57th Annual ACM Symposium on Theory of Computing June 23-27, 2025 in Prague (STOC 2025), arxiv version.

There is no known polynomial-time algorithm for graph isomorphism testing, but elementary combinatorial "refinement" algorithms seem to be very efficient in practice. Some philosophical justification is provided by a classical theorem of Babai, Erdős and Selkow: an extremely simple polynomial-time combinatorial algorithm (variously known as "naïve refinement", "naïve vertex classification", "colour refinement" or the "1-dimensional Weisfeiler-Leman algorithm") yields a so-called canonical labelling scheme for "almost all graphs". More precisely, for a typical outcome of a random graph, this simple combinatorial algorithm assigns labels to vertices in a way that easily permits isomorphism-testing against any other graph. We improve the Babai-Erdős-Selkow theorem in two directions. First, we consider randomly perturbed graphs, in accordance with the smoothed analysis philosophy of Spielman and Teng: for any graph, naïve refinement becomes effective after a tiny random perturbation to  (specifically, the addition and removal of random edges). Actually, with a twist on naïve refinement, we show that random additions and removals suffice. These results significantly improve on previous work of Gaudio-Rácz-Sridhar, and are in certain senses best-possible. Second, we complete a long line of research on canonical labelling of random graphs: for any  (possibly depending on), we prove that a random graph  can typically be canonically labelled in polynomial time. This is most interesting in the extremely sparse regime where has order of magnitude ; denser regimes were previously handled by Bollobás, Czajka-Pandurangan, and Linial-Mosheiff. Our proof also provides a description of the automorphism group of a typical outcome of  (slightly correcting a prediction of Linial-Mosheiff).

Partitioning problems via random processes (with Oliver Cooley, Mihyun Kang, and Matthew Kwan), Journal of London Mathematical Society 110(2) (2024), arxiv version.

There are a number of well-known problems and conjectures about partitioning graphs to satisfy local constraints. For example, the majority colouring conjecture of Kreutzer, Oum, Seymour, van der Zypen and Wood states that every directed graph has a 3-colouring such that for every vertex v, at most half of the out-neighbours of have the same colour as v. As another example, the internal partition conjecture, due to DeVos and to Ban and Linial, states that for every, all but finitely many d-regular graphs have a partition into two nonempty parts such that for every vertex v, at least half of the neighbours of v lie in the same part as v. We prove several results in this spirit: in particular, two of our results are that the majority colouring conjecture holds for Erdős-Rényi random directed graphs (of any density), and that the internal partition conjecture holds if we permit a tiny number of "exceptional vertices". Our proofs involve a variety of techniques, including several different methods to analyse random recolouring processes. One highlight is a "personality-changing" scheme: we "forget" certain information based on the state of a Markov chain, giving us more independence to work with.

A fast algorithm on average for solving the Hamilton Cycle problem, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022, arxiv version.

We present CertifyHAM, an algorithm which takes as input a graph G and either finds a Hamilton cycle of G or it outputs that such a cycle does not exists. If G=G(n, p) and p >2000/n then the expected running time of CertifyHAM is O(n/p). This improves upon previous results due to Gurevich and Shelah, Thomason, and Alon and Krivelevich.

A scaling limit for the length of the longest cycle in a sparse random graph (with Alan Frieze), J. Comb. Theory, Ser. B 148: 184-208 (2021), arxiv version.

We discuss the length of the longest cycle in a sparse random graph G(n,p), with p=c/n, c constant, denoted by L(c,n). We show that for large c there is a function f(c) such that L(c,n)/n converges to f(c) a.s. We show that f(c) can be expessed as a sum of terms of the form p_k(c)e^{-kc} where p_k(c) is a polynomial of degree at most k.