More Like this

1. Counting Hamilton cycles in sparse random directed graphs

   https://doi.org/10.1002/rsa.20815  

   Ferber, Asaf ; Kwan, Matthew ; Sudakov, Benny ( October 2018 , Random Structures & Algorithms)

   Letbe the random directed graph onnvertices where each of thepossible arcs is present independently with probabilityp. A celebrated result of Frieze shows that ifthentypically has a directed Hamilton cycle, and this is best possible. In this paper, we obtain a strengthening of this result, showing that under the same condition, the number of directed Hamilton cycles inis typically. We also prove a hitting‐time version of this statement, showing that in the random directed graph process, as soon as every vertex has in‐/out‐degrees at least 1, there are typicallydirected Hamilton cycles.

    

   more » « less
2. On the discrepancy of random low degree set systems

   https://doi.org/10.1002/rsa.20935  

   Bansal, Nikhil ; Meka, Raghu ( June 2020 , Random Structures & Algorithms)

   Motivated by the celebrated Beck‐Fiala conjecture, we consider the random setting where there arenelements andmsets and each element lies intrandomly chosen sets. In this setting, Ezra and Lovett showed andiscrepancy bound whenn ≤ mand anO(1) bound whenn ≫ m^t. In this paper, we give a tightbound for the entire range ofnandm, under a mild assumption that. The result is based on two steps. First, applying the partial coloring method to the case whenand using the properties of the random set system we show that the overall discrepancy incurred is at most. Second, we reduce the general case to that ofusing LP duality and a careful counting argument.

    

   more » « less
3. Spanning universality in random graphs

   https://doi.org/10.1002/rsa.20816  

   Ferber, Asaf ; Nenadov, Rajko ( October 2018 , Random Structures & Algorithms)

   A graph is said to be‐universal if it contains every graph withnvertices and maximum degree at most Δ as a subgraph. Dellamonica, Kohayakawa, Rödl and Ruciński used a “matching‐based” embedding technique introduced by Alon and Füredi to show that the random graphis asymptotically almost surely‐universal for, a threshold for the property that every subset of Δ vertices has a common neighbor. This bound has become a benchmark in the field and many subsequent results on embedding spanning graphs of maximum degree Δ in random graphs are proven only up to this threshold. We take a step towards overcoming limitations of former techniques by showing thatis almost surely‐universal for.

    

   more » « less
4. Square percolation and the threshold for quadratic divergence in random right‐angled Coxeter groups

   https://doi.org/10.1002/rsa.21049  

   Behrstock, Jason ; Falgas‐Ravry, Victor ; Susse, Tim ( September 2021 , Random Structures & Algorithms)

   Given a graph, its auxiliarysquare‐graphis the graph whose vertices are the non‐edges ofand whose edges are the pairs of non‐edges which induce a square (i.e., a 4‐cycle) in. We determine the threshold edge‐probabilityat which the Erdős–Rényi random graphbegins to asymptotically almost surely (a.a.s.) have a square‐graph with a connected component whose squares together cover all the vertices of. We show, a polylogarithmic improvement on earlier bounds ondue to Hagen and the authors. As a corollary, we determine the thresholdat which the random right‐angled Coxeter groupa.a.s. becomes strongly algebraically thick of order 1 and has quadratic divergence.

    

   more » « less
5. Fast uniform generation of random graphs with given degree sequences

   https://doi.org/10.1002/rsa.21004  

   Arman, Andrii ; Gao, Pu ; Wormald, Nicholas ( March 2021 , Random Structures & Algorithms)

   In this paper we provide an algorithm that generates a graph with given degree sequence uniformly at random. Provided that, whereis the maximal degree andmis the number of edges, the algorithm runs in expected timeO(m). Our algorithm significantly improves the previously most efficient uniform sampler, which runs in expected timefor the same family of degree sequences. Our method uses a novel ingredient which progressively relaxes restrictions on an object being generated uniformly at random, and we use this to give fast algorithms for uniform sampling of graphs with other degree sequences as well. Using the same method, we also obtain algorithms with expected run time which is (i) linear for power‐law degree sequences in cases where the previous best wasO(n^4.081), and (ii)O(nd + d⁴) ford‐regular graphs when, where the previous best wasO(nd³).

    

   more » « less