# Michael Anastos                                                                                          Home    Publications   Teaching

###### Publications:

## "Finding perfect matchings in random regular graphs in linear time" (Submitted, arXiv)

• we give an algorithm that finds a perfect matching in a random k-regular graph in linear time in expectation for k=O(1).

## "Finding perfect matchings in random cubic graphs in linear time" (Submitted, arXiv)

• with Alan Frieze
• we give an algorithm that finds a perfect matching in a random cubic graph in linear time in expectation.

## ''On the connectivity threshold for colorings of random graphs and hypergraphs"(Submitted, arXiv)

• with Alan Frieze
• The coloring space of q-colorings of a random k-uniform hypegraph with dn/k edges is connected when q>(1+c)((k-1)d/logd)^(1/k-1), where c tends to 0 as d tends to infinity (with high probability)

## "Constraining the clustering transition for colorings of sparse random graphs" (The Electronic Journal of Combinatorics 25-1 (2018), arXiv)

• with Alan Frieze and Wesley Pegden
• The coloring space of q-colorings of a random graph with dn/2 edges has a giant component when q>1.5d/log d. (with high probability, the logarithm is taken over base e).

## "Pattern Colored Hamilton Cycles in Random Graphs" (Submitted,  arXiv)

• with Alan Frieze
• The edges of the random graph process G_0,G_1,...G_n(n-1)/2 are randomly [q]-colored as they appear. Given a pattern Q (i.e. a finite sequence of colors in [q]) we give  a hitting time result for the first appearance of a Q-pattern Hamilton cycle (the colors will appear and circle around the cycle in the same order as they appear in Q).

## "Connectivity of the k-out Hypercube"(SIAM Journal on Discrete Mathematics32-3 (2018), 2194–2216, arXiv)

• Let G be a random graph generated by the k-out model with host graph being the n-hypercube. Let h=log n-2 log log n. If h<k then G is disconnected whereas  if  k >h +1 then G  is k-connected (with high probability, the logarithms are taken over base 2)

## "A Ramsey Property of Random Regular and k-out Graphs"(Submitted, arXiv)

• with Deepak Bal
• The edges of a random 2k-regular graph can be k colored such that there in no monochromatic component of linear size. At the same time for every k coloring of a (2k+1)- regular graphs there exists a monochromatic cycle of linear size. A similar result holds for random k-out graphs (with high probability).

## "Packing Directed Hamilton Cycles Online"(SIAM Journal on Discrete Mathematics32-2 (2018), 1505-1539,arXiv)

• with Joseph Briggs
• The edges in the random directed graph process  D_1,D_2,...,D_n(n-1) can be n-colored online so that the first graph with minimum degree 2 has a rainbow Hamilton cycle (with high probability).

## "Randomly Coloring Simple Hypergraphs with Fewer Colors" (Information Processing Letters 126 (2017): 39-42, arXiv)

• with Alan Frieze
• Let H be a simple k-uniform hypergraph with maximum degree Δ. Let qmax{Cklogn,500k3Δ1/(k1)}.The Glauber Dynamics will become close to uniform in O(nlogn) time, given a random (improper) q-coloring as a start.

## "Purchasing a C_4 Online" (Submitted, arXiv)

• We calculate the minimum expected cost, over all strategies, of purchasing a cycle of length 4 in two online settings