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 Mathematics 32-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 Mathematics 32-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 q≥max{Cklogn,500k3Δ1/(k−1)}.The Glauber Dynamics will become close to uniform in O(nlogn) time, given a random (improper) q-coloring as a start.

            "How many randomly colored edges make a randomly colored dense graph rainbow hamiltonian or rainbow connected?(Submitted, arXiv)

• with Alan Frieze
  

            "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